1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
|
/////////////////////////////////////////////////////////////////////////////
// Copyright (c) Electronic Arts Inc. All rights reserved.
/////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
// *** Note ***
// This implementation is incomplete.
///////////////////////////////////////////////////////////////////////////////
#ifndef EASTL_INTRUSIVE_SLIST_H
#define EASTL_INTRUSIVE_SLIST_H
#include <EASTL/internal/config.h>
#include <EASTL/iterator.h>
#include <EASTL/algorithm.h>
#if defined(EA_PRAGMA_ONCE_SUPPORTED)
#pragma once // Some compilers (e.g. VC++) benefit significantly from using this. We've measured 3-4% build speed improvements in apps as a result.
#endif
namespace eastl
{
/// intrusive_slist_node
///
struct intrusive_slist_node
{
intrusive_slist_node* mpNext;
};
/// IntrusiveSListIterator
///
template <typename T, typename Pointer, typename Reference>
struct IntrusiveSListIterator
{
typedef IntrusiveSListIterator<T, Pointer, Reference> this_type;
typedef IntrusiveSListIterator<T, T*, T&> iterator;
typedef IntrusiveSListIterator<T, const T*, const T&> const_iterator;
typedef eastl_size_t size_type; // See config.h for the definition of eastl_size_t, which defaults to size_t.
typedef ptrdiff_t difference_type;
typedef T value_type;
typedef T node_type;
typedef Pointer pointer;
typedef Reference reference;
typedef EASTL_ITC_NS::forward_iterator_tag iterator_category;
public:
node_type* mpNode;
public:
IntrusiveSListIterator();
explicit IntrusiveSListIterator(pointer pNode); // Note that you can also construct an iterator from T via this, since value_type == node_type.
IntrusiveSListIterator(const iterator& x);
reference operator*() const;
pointer operator->() const;
this_type& operator++();
this_type operator++(int);
}; // struct IntrusiveSListIterator
/// intrusive_slist_base
///
/// Provides a template-less base class for intrusive_slist.
///
class intrusive_slist_base
{
public:
typedef eastl_size_t size_type; // See config.h for the definition of eastl_size_t, which defaults to size_t.
typedef ptrdiff_t difference_type;
protected:
intrusive_slist_node* mpNext;
public:
intrusive_slist_base();
bool empty() const; ///< Returns true if the container is empty.
size_type size() const; ///< Returns the number of elements in the list; O(n).
void clear(); ///< Clears the list; O(1). No deallocation occurs.
void pop_front(); ///< Removes an element from the front of the list; O(1). The element must be present, but is not deallocated.
void reverse(); ///< Reverses a list so that front and back are swapped; O(n).
//bool validate() const; ///< Scans a list for linkage inconsistencies; O(n) time, O(1) space. Returns false if errors are detected, such as loops or branching.
}; // class intrusive_slist_base
/// intrusive_slist
///
template <typename T = intrusive_slist_node>
class intrusive_slist : public intrusive_slist_base
{
public:
typedef intrusive_slist<T> this_type;
typedef intrusive_slist_base base_type;
typedef T node_type;
typedef T value_type;
typedef typename base_type::size_type size_type;
typedef typename base_type::difference_type difference_type;
typedef T& reference;
typedef const T& const_reference;
typedef T* pointer;
typedef const T* const_pointer;
typedef IntrusiveSListIterator<T, T*, T&> iterator;
typedef IntrusiveSListIterator<T, const T*, const T&> const_iterator;
public:
intrusive_slist(); ///< Creates an empty list.
//intrusive_slist(const this_type& x); ///< Creates an empty list; ignores the argument. To consider: Is this a useful function?
//this_type& operator=(const this_type& x); ///< Clears the list; ignores the argument. To consider: Is this a useful function?
iterator begin(); ///< Returns an iterator pointing to the first element in the list. O(1).
const_iterator begin() const; ///< Returns a const_iterator pointing to the first element in the list. O(1).
const_iterator cbegin() const; ///< Returns a const_iterator pointing to the first element in the list. O(1).
iterator end(); ///< Returns an iterator pointing one-after the last element in the list. O(1).
const_iterator end() const; ///< Returns a const_iterator pointing one-after the last element in the list. O(1).
const_iterator cend() const; ///< Returns a const_iterator pointing one-after the last element in the list. O(1).
iterator before_begin(); ///< Returns iterator to position before begin. O(1).
const_iterator before_begin() const; ///< Returns iterator to previous position. O(1).
const_iterator cbefore_begin() const; ///< Returns iterator to previous position. O(1).
iterator previous(const_iterator position); ///< Returns iterator to previous position. O(n).
const_iterator previous(const_iterator position) const; ///< Returns iterator to previous position. O(n).
reference front(); ///< Returns a reference to the first element. The list must be empty.
const_reference front() const; ///< Returns a const reference to the first element. The list must be empty.
void push_front(value_type& value); ///< Adds an element to the front of the list; O(1). The element is not copied. The element must not be in any other list.
void pop_front(); ///< Removes an element from the back of the list; O(n). The element must be present, but is not deallocated.
bool contains(const value_type& value) const; ///< Returns true if the given element is in the list; O(n). Equivalent to (locate(x) != end()).
iterator locate(value_type& value); ///< Converts a reference to an object in the list back to an iterator, or returns end() if it is not part of the list. O(n)
const_iterator locate(const value_type& value) const; ///< Converts a const reference to an object in the list back to a const iterator, or returns end() if it is not part of the list. O(n)
iterator insert(iterator position, value_type& value); ///< Inserts an element before the element pointed to by the iterator. O(n)
iterator insert_after(iterator position, value_type& value); ///< Inserts an element after the element pointed to by the iterator. O(1)
iterator erase(iterator position); ///< Erases the element pointed to by the iterator. O(n)
iterator erase_after(iterator position); ///< Erases the element after the element pointed to by the iterator. O(1)
iterator erase(iterator first, iterator last); ///< Erases elements within the iterator range [first, last). O(n).
iterator erase_after(iterator before_first, iterator last); ///< Erases elements within the iterator range [before_first, last). O(1).
void swap(this_type& x); ///< Swaps the contents of two intrusive lists; O(1).
void splice(iterator position, value_type& value); ///< Moves the given element into this list before the element pointed to by position; O(n).
///< Required: x must be in some list or have first/next pointers that point it itself.
void splice(iterator position, this_type& x); ///< Moves the contents of a list into this list before the element pointed to by position; O(n).
///< Required: &x != this (same as std::list).
void splice(iterator position, this_type& x, iterator xPosition); ///< Moves the given element pointed to i within the list x into the current list before
///< the element pointed to by position; O(n).
void splice(iterator position, this_type& x, iterator first, iterator last); ///< Moves the range of elements [first, last) from list x into the current list before
///< the element pointed to by position; O(n).
///< Required: position must not be in [first, last). (same as std::list).
void splice_after(iterator position, value_type& value); ///< Moves the given element into this list after the element pointed to by position; O(1).
///< Required: x must be in some list or have first/next pointers that point it itself.
void splice_after(iterator position, this_type& x); ///< Moves the contents of a list into this list after the element pointed to by position; O(n).
///< Required: &x != this (same as std::list).
void splice_after(iterator position, this_type& x, iterator xPrevious); ///< Moves the element after xPrevious to be after position. O(1).
///< Required: &x != this (same as std::list).
void splice_after(iterator position, this_type& x, iterator before_first, iterator before_last); ///< Moves the elements in the range of [before_first+1, before_last+1) to be after position. O(1).
bool validate() const;
int validate_iterator(const_iterator i) const;
}; // intrusive_slist
///////////////////////////////////////////////////////////////////////
// IntrusiveSListIterator
///////////////////////////////////////////////////////////////////////
template <typename T, typename Pointer, typename Reference>
inline IntrusiveSListIterator<T, Pointer, Reference>::IntrusiveSListIterator()
{
#if EASTL_DEBUG
mpNode = NULL;
#endif
}
template <typename T, typename Pointer, typename Reference>
inline IntrusiveSListIterator<T, Pointer, Reference>::IntrusiveSListIterator(pointer pNode)
: mpNode(pNode)
{
}
template <typename T, typename Pointer, typename Reference>
inline IntrusiveSListIterator<T, Pointer, Reference>::IntrusiveSListIterator(const iterator& x)
: mpNode(x.mpNode)
{
}
///////////////////////////////////////////////////////////////////////
// intrusive_slist_base
///////////////////////////////////////////////////////////////////////
// To do.
///////////////////////////////////////////////////////////////////////
// intrusive_slist
///////////////////////////////////////////////////////////////////////
// To do.
///////////////////////////////////////////////////////////////////////
// global operators
///////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////
// global operators
///////////////////////////////////////////////////////////////////////
template <typename T>
bool operator==(const intrusive_slist<T>& a, const intrusive_slist<T>& b)
{
// If we store an mSize member for intrusive_slist, we want to take advantage of it here.
typename intrusive_slist<T>::const_iterator ia = a.begin();
typename intrusive_slist<T>::const_iterator ib = b.begin();
typename intrusive_slist<T>::const_iterator enda = a.end();
typename intrusive_slist<T>::const_iterator endb = b.end();
while((ia != enda) && (ib != endb) && (*ia == *ib))
{
++ia;
++ib;
}
return (ia == enda) && (ib == endb);
}
template <typename T>
bool operator<(const intrusive_slist<T>& a, const intrusive_slist<T>& b)
{
return eastl::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
}
template <typename T>
bool operator!=(const intrusive_slist<T>& a, const intrusive_slist<T>& b)
{
return !(a == b);
}
template <typename T>
bool operator>(const intrusive_slist<T>& a, const intrusive_slist<T>& b)
{
return b < a;
}
template <typename T>
bool operator<=(const intrusive_slist<T>& a, const intrusive_slist<T>& b)
{
return !(b < a);
}
template <typename T>
bool operator>=(const intrusive_slist<T>& a, const intrusive_slist<T>& b)
{
return !(a < b);
}
template <typename T>
void swap(intrusive_slist<T>& a, intrusive_slist<T>& b)
{
a.swap(b);
}
} // namespace eastl
#endif // Header include guard
|