1 |
//==-- llvm/ADT/ilist.h - Intrusive Linked List Template ---------*- C++ -*-==// |
2 |
// |
3 |
// The LLVM Compiler Infrastructure |
4 |
// |
5 |
// This file is distributed under the University of Illinois Open Source |
6 |
// License. See LICENSE.TXT for details. |
7 |
// |
8 |
//===----------------------------------------------------------------------===// |
9 |
// |
10 |
// This file defines classes to implement an intrusive doubly linked list class |
11 |
// (i.e. each node of the list must contain a next and previous field for the |
12 |
// list. |
13 |
// |
14 |
// The ilist_traits trait class is used to gain access to the next and previous |
15 |
// fields of the node type that the list is instantiated with. If it is not |
16 |
// specialized, the list defaults to using the getPrev(), getNext() method calls |
17 |
// to get the next and previous pointers. |
18 |
// |
19 |
// The ilist class itself, should be a plug in replacement for list, assuming |
20 |
// that the nodes contain next/prev pointers. This list replacement does not |
21 |
// provide a constant time size() method, so be careful to use empty() when you |
22 |
// really want to know if it's empty. |
23 |
// |
24 |
// The ilist class is implemented by allocating a 'tail' node when the list is |
25 |
// created (using ilist_traits<>::createSentinel()). This tail node is |
26 |
// absolutely required because the user must be able to compute end()-1. Because |
27 |
// of this, users of the direct next/prev links will see an extra link on the |
28 |
// end of the list, which should be ignored. |
29 |
// |
30 |
// Requirements for a user of this list: |
31 |
// |
32 |
// 1. The user must provide {g|s}et{Next|Prev} methods, or specialize |
33 |
// ilist_traits to provide an alternate way of getting and setting next and |
34 |
// prev links. |
35 |
// |
36 |
//===----------------------------------------------------------------------===// |
37 |
|
38 |
#ifndef LLVM_ADT_ILIST_H |
39 |
#define LLVM_ADT_ILIST_H |
40 |
|
41 |
#include "llvm/Support/Compiler.h" |
42 |
#include <algorithm> |
43 |
#include <cassert> |
44 |
#include <cstddef> |
45 |
#include <iterator> |
46 |
|
47 |
namespace llvm { |
48 |
|
49 |
template<typename NodeTy, typename Traits> class iplist; |
50 |
template<typename NodeTy> class ilist_iterator; |
51 |
|
52 |
/// ilist_nextprev_traits - A fragment for template traits for intrusive list |
53 |
/// that provides default next/prev implementations for common operations. |
54 |
/// |
55 |
template<typename NodeTy> |
56 |
struct ilist_nextprev_traits { |
57 |
static NodeTy *getPrev(NodeTy *N) { return N->getPrev(); } |
58 |
static NodeTy *getNext(NodeTy *N) { return N->getNext(); } |
59 |
static const NodeTy *getPrev(const NodeTy *N) { return N->getPrev(); } |
60 |
static const NodeTy *getNext(const NodeTy *N) { return N->getNext(); } |
61 |
|
62 |
static void setPrev(NodeTy *N, NodeTy *Prev) { N->setPrev(Prev); } |
63 |
static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); } |
64 |
}; |
65 |
|
66 |
template<typename NodeTy> |
67 |
struct ilist_traits; |
68 |
|
69 |
/// ilist_sentinel_traits - A fragment for template traits for intrusive list |
70 |
/// that provides default sentinel implementations for common operations. |
71 |
/// |
72 |
/// ilist_sentinel_traits implements a lazy dynamic sentinel allocation |
73 |
/// strategy. The sentinel is stored in the prev field of ilist's Head. |
74 |
/// |
75 |
template<typename NodeTy> |
76 |
struct ilist_sentinel_traits { |
77 |
/// createSentinel - create the dynamic sentinel |
78 |
static NodeTy *createSentinel() { return new NodeTy(); } |
79 |
|
80 |
/// destroySentinel - deallocate the dynamic sentinel |
81 |
static void destroySentinel(NodeTy *N) { delete N; } |
82 |
|
83 |
/// provideInitialHead - when constructing an ilist, provide a starting |
84 |
/// value for its Head |
85 |
/// @return null node to indicate that it needs to be allocated later |
86 |
static NodeTy *provideInitialHead() { return 0; } |
87 |
|
88 |
/// ensureHead - make sure that Head is either already |
89 |
/// initialized or assigned a fresh sentinel |
90 |
/// @return the sentinel |
91 |
static NodeTy *ensureHead(NodeTy *&Head) { |
92 |
if (!Head) { |
93 |
Head = ilist_traits<NodeTy>::createSentinel(); |
94 |
ilist_traits<NodeTy>::noteHead(Head, Head); |
95 |
ilist_traits<NodeTy>::setNext(Head, 0); |
96 |
return Head; |
97 |
} |
98 |
return ilist_traits<NodeTy>::getPrev(Head); |
99 |
} |
100 |
|
101 |
/// noteHead - stash the sentinel into its default location |
102 |
static void noteHead(NodeTy *NewHead, NodeTy *Sentinel) { |
103 |
ilist_traits<NodeTy>::setPrev(NewHead, Sentinel); |
104 |
} |
105 |
}; |
106 |
|
107 |
/// ilist_node_traits - A fragment for template traits for intrusive list |
108 |
/// that provides default node related operations. |
109 |
/// |
110 |
template<typename NodeTy> |
111 |
struct ilist_node_traits { |
112 |
static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); } |
113 |
static void deleteNode(NodeTy *V) { delete V; } |
114 |
|
115 |
void addNodeToList(NodeTy *) {} |
116 |
void removeNodeFromList(NodeTy *) {} |
117 |
void transferNodesFromList(ilist_node_traits & /*SrcTraits*/, |
118 |
ilist_iterator<NodeTy> /*first*/, |
119 |
ilist_iterator<NodeTy> /*last*/) {} |
120 |
}; |
121 |
|
122 |
/// ilist_default_traits - Default template traits for intrusive list. |
123 |
/// By inheriting from this, you can easily use default implementations |
124 |
/// for all common operations. |
125 |
/// |
126 |
template<typename NodeTy> |
127 |
struct ilist_default_traits : public ilist_nextprev_traits<NodeTy>, |
128 |
public ilist_sentinel_traits<NodeTy>, |
129 |
public ilist_node_traits<NodeTy> { |
130 |
}; |
131 |
|
132 |
// Template traits for intrusive list. By specializing this template class, you |
133 |
// can change what next/prev fields are used to store the links... |
134 |
template<typename NodeTy> |
135 |
struct ilist_traits : public ilist_default_traits<NodeTy> {}; |
136 |
|
137 |
// Const traits are the same as nonconst traits... |
138 |
template<typename Ty> |
139 |
struct ilist_traits<const Ty> : public ilist_traits<Ty> {}; |
140 |
|
141 |
//===----------------------------------------------------------------------===// |
142 |
// ilist_iterator<Node> - Iterator for intrusive list. |
143 |
// |
144 |
template<typename NodeTy> |
145 |
class ilist_iterator |
146 |
: public std::iterator<std::bidirectional_iterator_tag, NodeTy, ptrdiff_t> { |
147 |
|
148 |
public: |
149 |
typedef ilist_traits<NodeTy> Traits; |
150 |
typedef std::iterator<std::bidirectional_iterator_tag, |
151 |
NodeTy, ptrdiff_t> super; |
152 |
|
153 |
typedef typename super::value_type value_type; |
154 |
typedef typename super::difference_type difference_type; |
155 |
typedef typename super::pointer pointer; |
156 |
typedef typename super::reference reference; |
157 |
private: |
158 |
pointer NodePtr; |
159 |
|
160 |
// ilist_iterator is not a random-access iterator, but it has an |
161 |
// implicit conversion to pointer-type, which is. Declare (but |
162 |
// don't define) these functions as private to help catch |
163 |
// accidental misuse. |
164 |
void operator[](difference_type) const; |
165 |
void operator+(difference_type) const; |
166 |
void operator-(difference_type) const; |
167 |
void operator+=(difference_type) const; |
168 |
void operator-=(difference_type) const; |
169 |
template<class T> void operator<(T) const; |
170 |
template<class T> void operator<=(T) const; |
171 |
template<class T> void operator>(T) const; |
172 |
template<class T> void operator>=(T) const; |
173 |
template<class T> void operator-(T) const; |
174 |
public: |
175 |
|
176 |
ilist_iterator(pointer NP) : NodePtr(NP) {} |
177 |
ilist_iterator(reference NR) : NodePtr(&NR) {} |
178 |
ilist_iterator() : NodePtr(0) {} |
179 |
|
180 |
// This is templated so that we can allow constructing a const iterator from |
181 |
// a nonconst iterator... |
182 |
template<class node_ty> |
183 |
ilist_iterator(const ilist_iterator<node_ty> &RHS) |
184 |
: NodePtr(RHS.getNodePtrUnchecked()) {} |
185 |
|
186 |
// This is templated so that we can allow assigning to a const iterator from |
187 |
// a nonconst iterator... |
188 |
template<class node_ty> |
189 |
const ilist_iterator &operator=(const ilist_iterator<node_ty> &RHS) { |
190 |
NodePtr = RHS.getNodePtrUnchecked(); |
191 |
return *this; |
192 |
} |
193 |
|
194 |
// Accessors... |
195 |
operator pointer() const { |
196 |
return NodePtr; |
197 |
} |
198 |
|
199 |
reference operator*() const { |
200 |
return *NodePtr; |
201 |
} |
202 |
pointer operator->() const { return &operator*(); } |
203 |
|
204 |
// Comparison operators |
205 |
bool operator==(const ilist_iterator &RHS) const { |
206 |
return NodePtr == RHS.NodePtr; |
207 |
} |
208 |
bool operator!=(const ilist_iterator &RHS) const { |
209 |
return NodePtr != RHS.NodePtr; |
210 |
} |
211 |
|
212 |
// Increment and decrement operators... |
213 |
ilist_iterator &operator--() { // predecrement - Back up |
214 |
NodePtr = Traits::getPrev(NodePtr); |
215 |
assert(NodePtr && "--'d off the beginning of an ilist!"); |
216 |
return *this; |
217 |
} |
218 |
ilist_iterator &operator++() { // preincrement - Advance |
219 |
NodePtr = Traits::getNext(NodePtr); |
220 |
return *this; |
221 |
} |
222 |
ilist_iterator operator--(int) { // postdecrement operators... |
223 |
ilist_iterator tmp = *this; |
224 |
--*this; |
225 |
return tmp; |
226 |
} |
227 |
ilist_iterator operator++(int) { // postincrement operators... |
228 |
ilist_iterator tmp = *this; |
229 |
++*this; |
230 |
return tmp; |
231 |
} |
232 |
|
233 |
// Internal interface, do not use... |
234 |
pointer getNodePtrUnchecked() const { return NodePtr; } |
235 |
}; |
236 |
|
237 |
// These are to catch errors when people try to use them as random access |
238 |
// iterators. |
239 |
template<typename T> |
240 |
void operator-(int, ilist_iterator<T>) LLVM_DELETED_FUNCTION; |
241 |
template<typename T> |
242 |
void operator-(ilist_iterator<T>,int) LLVM_DELETED_FUNCTION; |
243 |
|
244 |
template<typename T> |
245 |
void operator+(int, ilist_iterator<T>) LLVM_DELETED_FUNCTION; |
246 |
template<typename T> |
247 |
void operator+(ilist_iterator<T>,int) LLVM_DELETED_FUNCTION; |
248 |
|
249 |
// operator!=/operator== - Allow mixed comparisons without dereferencing |
250 |
// the iterator, which could very likely be pointing to end(). |
251 |
template<typename T> |
252 |
bool operator!=(const T* LHS, const ilist_iterator<const T> &RHS) { |
253 |
return LHS != RHS.getNodePtrUnchecked(); |
254 |
} |
255 |
template<typename T> |
256 |
bool operator==(const T* LHS, const ilist_iterator<const T> &RHS) { |
257 |
return LHS == RHS.getNodePtrUnchecked(); |
258 |
} |
259 |
template<typename T> |
260 |
bool operator!=(T* LHS, const ilist_iterator<T> &RHS) { |
261 |
return LHS != RHS.getNodePtrUnchecked(); |
262 |
} |
263 |
template<typename T> |
264 |
bool operator==(T* LHS, const ilist_iterator<T> &RHS) { |
265 |
return LHS == RHS.getNodePtrUnchecked(); |
266 |
} |
267 |
|
268 |
|
269 |
// Allow ilist_iterators to convert into pointers to a node automatically when |
270 |
// used by the dyn_cast, cast, isa mechanisms... |
271 |
|
272 |
template<typename From> struct simplify_type; |
273 |
|
274 |
template<typename NodeTy> struct simplify_type<ilist_iterator<NodeTy> > { |
275 |
typedef NodeTy* SimpleType; |
276 |
|
277 |
static SimpleType getSimplifiedValue(ilist_iterator<NodeTy> &Node) { |
278 |
return &*Node; |
279 |
} |
280 |
}; |
281 |
template<typename NodeTy> struct simplify_type<const ilist_iterator<NodeTy> > { |
282 |
typedef /*const*/ NodeTy* SimpleType; |
283 |
|
284 |
static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) { |
285 |
return &*Node; |
286 |
} |
287 |
}; |
288 |
|
289 |
|
290 |
//===----------------------------------------------------------------------===// |
291 |
// |
292 |
/// iplist - The subset of list functionality that can safely be used on nodes |
293 |
/// of polymorphic types, i.e. a heterogeneous list with a common base class that |
294 |
/// holds the next/prev pointers. The only state of the list itself is a single |
295 |
/// pointer to the head of the list. |
296 |
/// |
297 |
/// This list can be in one of three interesting states: |
298 |
/// 1. The list may be completely unconstructed. In this case, the head |
299 |
/// pointer is null. When in this form, any query for an iterator (e.g. |
300 |
/// begin() or end()) causes the list to transparently change to state #2. |
301 |
/// 2. The list may be empty, but contain a sentinel for the end iterator. This |
302 |
/// sentinel is created by the Traits::createSentinel method and is a link |
303 |
/// in the list. When the list is empty, the pointer in the iplist points |
304 |
/// to the sentinel. Once the sentinel is constructed, it |
305 |
/// is not destroyed until the list is. |
306 |
/// 3. The list may contain actual objects in it, which are stored as a doubly |
307 |
/// linked list of nodes. One invariant of the list is that the predecessor |
308 |
/// of the first node in the list always points to the last node in the list, |
309 |
/// and the successor pointer for the sentinel (which always stays at the |
310 |
/// end of the list) is always null. |
311 |
/// |
312 |
template<typename NodeTy, typename Traits=ilist_traits<NodeTy> > |
313 |
class iplist : public Traits { |
314 |
mutable NodeTy *Head; |
315 |
|
316 |
// Use the prev node pointer of 'head' as the tail pointer. This is really a |
317 |
// circularly linked list where we snip the 'next' link from the sentinel node |
318 |
// back to the first node in the list (to preserve assertions about going off |
319 |
// the end of the list). |
320 |
NodeTy *getTail() { return this->ensureHead(Head); } |
321 |
const NodeTy *getTail() const { return this->ensureHead(Head); } |
322 |
void setTail(NodeTy *N) const { this->noteHead(Head, N); } |
323 |
|
324 |
/// CreateLazySentinel - This method verifies whether the sentinel for the |
325 |
/// list has been created and lazily makes it if not. |
326 |
void CreateLazySentinel() const { |
327 |
this->ensureHead(Head); |
328 |
} |
329 |
|
330 |
static bool op_less(NodeTy &L, NodeTy &R) { return L < R; } |
331 |
static bool op_equal(NodeTy &L, NodeTy &R) { return L == R; } |
332 |
|
333 |
// No fundamental reason why iplist can't be copyable, but the default |
334 |
// copy/copy-assign won't do. |
335 |
iplist(const iplist &) LLVM_DELETED_FUNCTION; |
336 |
void operator=(const iplist &) LLVM_DELETED_FUNCTION; |
337 |
|
338 |
public: |
339 |
typedef NodeTy *pointer; |
340 |
typedef const NodeTy *const_pointer; |
341 |
typedef NodeTy &reference; |
342 |
typedef const NodeTy &const_reference; |
343 |
typedef NodeTy value_type; |
344 |
typedef ilist_iterator<NodeTy> iterator; |
345 |
typedef ilist_iterator<const NodeTy> const_iterator; |
346 |
typedef size_t size_type; |
347 |
typedef ptrdiff_t difference_type; |
348 |
typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
349 |
typedef std::reverse_iterator<iterator> reverse_iterator; |
350 |
|
351 |
iplist() : Head(this->provideInitialHead()) {} |
352 |
~iplist() { |
353 |
if (!Head) return; |
354 |
clear(); |
355 |
Traits::destroySentinel(getTail()); |
356 |
} |
357 |
|
358 |
// Iterator creation methods. |
359 |
iterator begin() { |
360 |
CreateLazySentinel(); |
361 |
return iterator(Head); |
362 |
} |
363 |
const_iterator begin() const { |
364 |
CreateLazySentinel(); |
365 |
return const_iterator(Head); |
366 |
} |
367 |
iterator end() { |
368 |
CreateLazySentinel(); |
369 |
return iterator(getTail()); |
370 |
} |
371 |
const_iterator end() const { |
372 |
CreateLazySentinel(); |
373 |
return const_iterator(getTail()); |
374 |
} |
375 |
|
376 |
// reverse iterator creation methods. |
377 |
reverse_iterator rbegin() { return reverse_iterator(end()); } |
378 |
const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } |
379 |
reverse_iterator rend() { return reverse_iterator(begin()); } |
380 |
const_reverse_iterator rend() const { return const_reverse_iterator(begin());} |
381 |
|
382 |
|
383 |
// Miscellaneous inspection routines. |
384 |
size_type max_size() const { return size_type(-1); } |
385 |
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { |
386 |
return Head == 0 || Head == getTail(); |
387 |
} |
388 |
|
389 |
// Front and back accessor functions... |
390 |
reference front() { |
391 |
assert(!empty() && "Called front() on empty list!"); |
392 |
return *Head; |
393 |
} |
394 |
const_reference front() const { |
395 |
assert(!empty() && "Called front() on empty list!"); |
396 |
return *Head; |
397 |
} |
398 |
reference back() { |
399 |
assert(!empty() && "Called back() on empty list!"); |
400 |
return *this->getPrev(getTail()); |
401 |
} |
402 |
const_reference back() const { |
403 |
assert(!empty() && "Called back() on empty list!"); |
404 |
return *this->getPrev(getTail()); |
405 |
} |
406 |
|
407 |
void swap(iplist &RHS) { |
408 |
assert(0 && "Swap does not use list traits callback correctly yet!"); |
409 |
std::swap(Head, RHS.Head); |
410 |
} |
411 |
|
412 |
iterator insert(iterator where, NodeTy *New) { |
413 |
NodeTy *CurNode = where.getNodePtrUnchecked(); |
414 |
NodeTy *PrevNode = this->getPrev(CurNode); |
415 |
this->setNext(New, CurNode); |
416 |
this->setPrev(New, PrevNode); |
417 |
|
418 |
if (CurNode != Head) // Is PrevNode off the beginning of the list? |
419 |
this->setNext(PrevNode, New); |
420 |
else |
421 |
Head = New; |
422 |
this->setPrev(CurNode, New); |
423 |
|
424 |
this->addNodeToList(New); // Notify traits that we added a node... |
425 |
return New; |
426 |
} |
427 |
|
428 |
iterator insertAfter(iterator where, NodeTy *New) { |
429 |
if (empty()) |
430 |
return insert(begin(), New); |
431 |
else |
432 |
return insert(++where, New); |
433 |
} |
434 |
|
435 |
NodeTy *remove(iterator &IT) { |
436 |
assert(IT != end() && "Cannot remove end of list!"); |
437 |
NodeTy *Node = &*IT; |
438 |
NodeTy *NextNode = this->getNext(Node); |
439 |
NodeTy *PrevNode = this->getPrev(Node); |
440 |
|
441 |
if (Node != Head) // Is PrevNode off the beginning of the list? |
442 |
this->setNext(PrevNode, NextNode); |
443 |
else |
444 |
Head = NextNode; |
445 |
this->setPrev(NextNode, PrevNode); |
446 |
IT = NextNode; |
447 |
this->removeNodeFromList(Node); // Notify traits that we removed a node... |
448 |
|
449 |
// Set the next/prev pointers of the current node to null. This isn't |
450 |
// strictly required, but this catches errors where a node is removed from |
451 |
// an ilist (and potentially deleted) with iterators still pointing at it. |
452 |
// When those iterators are incremented or decremented, they will assert on |
453 |
// the null next/prev pointer instead of "usually working". |
454 |
this->setNext(Node, 0); |
455 |
this->setPrev(Node, 0); |
456 |
return Node; |
457 |
} |
458 |
|
459 |
NodeTy *remove(const iterator &IT) { |
460 |
iterator MutIt = IT; |
461 |
return remove(MutIt); |
462 |
} |
463 |
|
464 |
// erase - remove a node from the controlled sequence... and delete it. |
465 |
iterator erase(iterator where) { |
466 |
this->deleteNode(remove(where)); |
467 |
return where; |
468 |
} |
469 |
|
470 |
/// Remove all nodes from the list like clear(), but do not call |
471 |
/// removeNodeFromList() or deleteNode(). |
472 |
/// |
473 |
/// This should only be used immediately before freeing nodes in bulk to |
474 |
/// avoid traversing the list and bringing all the nodes into cache. |
475 |
void clearAndLeakNodesUnsafely() { |
476 |
if (Head) { |
477 |
Head = getTail(); |
478 |
this->setPrev(Head, Head); |
479 |
} |
480 |
} |
481 |
|
482 |
private: |
483 |
// transfer - The heart of the splice function. Move linked list nodes from |
484 |
// [first, last) into position. |
485 |
// |
486 |
void transfer(iterator position, iplist &L2, iterator first, iterator last) { |
487 |
assert(first != last && "Should be checked by callers"); |
488 |
// Position cannot be contained in the range to be transferred. |
489 |
// Check for the most common mistake. |
490 |
assert(position != first && |
491 |
"Insertion point can't be one of the transferred nodes"); |
492 |
|
493 |
if (position != last) { |
494 |
// Note: we have to be careful about the case when we move the first node |
495 |
// in the list. This node is the list sentinel node and we can't move it. |
496 |
NodeTy *ThisSentinel = getTail(); |
497 |
setTail(0); |
498 |
NodeTy *L2Sentinel = L2.getTail(); |
499 |
L2.setTail(0); |
500 |
|
501 |
// Remove [first, last) from its old position. |
502 |
NodeTy *First = &*first, *Prev = this->getPrev(First); |
503 |
NodeTy *Next = last.getNodePtrUnchecked(), *Last = this->getPrev(Next); |
504 |
if (Prev) |
505 |
this->setNext(Prev, Next); |
506 |
else |
507 |
L2.Head = Next; |
508 |
this->setPrev(Next, Prev); |
509 |
|
510 |
// Splice [first, last) into its new position. |
511 |
NodeTy *PosNext = position.getNodePtrUnchecked(); |
512 |
NodeTy *PosPrev = this->getPrev(PosNext); |
513 |
|
514 |
// Fix head of list... |
515 |
if (PosPrev) |
516 |
this->setNext(PosPrev, First); |
517 |
else |
518 |
Head = First; |
519 |
this->setPrev(First, PosPrev); |
520 |
|
521 |
// Fix end of list... |
522 |
this->setNext(Last, PosNext); |
523 |
this->setPrev(PosNext, Last); |
524 |
|
525 |
this->transferNodesFromList(L2, First, PosNext); |
526 |
|
527 |
// Now that everything is set, restore the pointers to the list sentinels. |
528 |
L2.setTail(L2Sentinel); |
529 |
setTail(ThisSentinel); |
530 |
} |
531 |
} |
532 |
|
533 |
public: |
534 |
|
535 |
//===----------------------------------------------------------------------=== |
536 |
// Functionality derived from other functions defined above... |
537 |
// |
538 |
|
539 |
size_type LLVM_ATTRIBUTE_UNUSED_RESULT size() const { |
540 |
if (Head == 0) return 0; // Don't require construction of sentinel if empty. |
541 |
return std::distance(begin(), end()); |
542 |
} |
543 |
|
544 |
iterator erase(iterator first, iterator last) { |
545 |
while (first != last) |
546 |
first = erase(first); |
547 |
return last; |
548 |
} |
549 |
|
550 |
void clear() { if (Head) erase(begin(), end()); } |
551 |
|
552 |
// Front and back inserters... |
553 |
void push_front(NodeTy *val) { insert(begin(), val); } |
554 |
void push_back(NodeTy *val) { insert(end(), val); } |
555 |
void pop_front() { |
556 |
assert(!empty() && "pop_front() on empty list!"); |
557 |
erase(begin()); |
558 |
} |
559 |
void pop_back() { |
560 |
assert(!empty() && "pop_back() on empty list!"); |
561 |
iterator t = end(); erase(--t); |
562 |
} |
563 |
|
564 |
// Special forms of insert... |
565 |
template<class InIt> void insert(iterator where, InIt first, InIt last) { |
566 |
for (; first != last; ++first) insert(where, *first); |
567 |
} |
568 |
|
569 |
// Splice members - defined in terms of transfer... |
570 |
void splice(iterator where, iplist &L2) { |
571 |
if (!L2.empty()) |
572 |
transfer(where, L2, L2.begin(), L2.end()); |
573 |
} |
574 |
void splice(iterator where, iplist &L2, iterator first) { |
575 |
iterator last = first; ++last; |
576 |
if (where == first || where == last) return; // No change |
577 |
transfer(where, L2, first, last); |
578 |
} |
579 |
void splice(iterator where, iplist &L2, iterator first, iterator last) { |
580 |
if (first != last) transfer(where, L2, first, last); |
581 |
} |
582 |
|
583 |
|
584 |
|
585 |
//===----------------------------------------------------------------------=== |
586 |
// High-Level Functionality that shouldn't really be here, but is part of list |
587 |
// |
588 |
|
589 |
// These two functions are actually called remove/remove_if in list<>, but |
590 |
// they actually do the job of erase, rename them accordingly. |
591 |
// |
592 |
void erase(const NodeTy &val) { |
593 |
for (iterator I = begin(), E = end(); I != E; ) { |
594 |
iterator next = I; ++next; |
595 |
if (*I == val) erase(I); |
596 |
I = next; |
597 |
} |
598 |
} |
599 |
template<class Pr1> void erase_if(Pr1 pred) { |
600 |
for (iterator I = begin(), E = end(); I != E; ) { |
601 |
iterator next = I; ++next; |
602 |
if (pred(*I)) erase(I); |
603 |
I = next; |
604 |
} |
605 |
} |
606 |
|
607 |
template<class Pr2> void unique(Pr2 pred) { |
608 |
if (empty()) return; |
609 |
for (iterator I = begin(), E = end(), Next = begin(); ++Next != E;) { |
610 |
if (pred(*I)) |
611 |
erase(Next); |
612 |
else |
613 |
I = Next; |
614 |
Next = I; |
615 |
} |
616 |
} |
617 |
void unique() { unique(op_equal); } |
618 |
|
619 |
template<class Pr3> void merge(iplist &right, Pr3 pred) { |
620 |
iterator first1 = begin(), last1 = end(); |
621 |
iterator first2 = right.begin(), last2 = right.end(); |
622 |
while (first1 != last1 && first2 != last2) |
623 |
if (pred(*first2, *first1)) { |
624 |
iterator next = first2; |
625 |
transfer(first1, right, first2, ++next); |
626 |
first2 = next; |
627 |
} else { |
628 |
++first1; |
629 |
} |
630 |
if (first2 != last2) transfer(last1, right, first2, last2); |
631 |
} |
632 |
void merge(iplist &right) { return merge(right, op_less); } |
633 |
|
634 |
template<class Pr3> void sort(Pr3 pred); |
635 |
void sort() { sort(op_less); } |
636 |
}; |
637 |
|
638 |
|
639 |
template<typename NodeTy> |
640 |
struct ilist : public iplist<NodeTy> { |
641 |
typedef typename iplist<NodeTy>::size_type size_type; |
642 |
typedef typename iplist<NodeTy>::iterator iterator; |
643 |
|
644 |
ilist() {} |
645 |
ilist(const ilist &right) { |
646 |
insert(this->begin(), right.begin(), right.end()); |
647 |
} |
648 |
explicit ilist(size_type count) { |
649 |
insert(this->begin(), count, NodeTy()); |
650 |
} |
651 |
ilist(size_type count, const NodeTy &val) { |
652 |
insert(this->begin(), count, val); |
653 |
} |
654 |
template<class InIt> ilist(InIt first, InIt last) { |
655 |
insert(this->begin(), first, last); |
656 |
} |
657 |
|
658 |
// bring hidden functions into scope |
659 |
using iplist<NodeTy>::insert; |
660 |
using iplist<NodeTy>::push_front; |
661 |
using iplist<NodeTy>::push_back; |
662 |
|
663 |
// Main implementation here - Insert for a node passed by value... |
664 |
iterator insert(iterator where, const NodeTy &val) { |
665 |
return insert(where, this->createNode(val)); |
666 |
} |
667 |
|
668 |
|
669 |
// Front and back inserters... |
670 |
void push_front(const NodeTy &val) { insert(this->begin(), val); } |
671 |
void push_back(const NodeTy &val) { insert(this->end(), val); } |
672 |
|
673 |
void insert(iterator where, size_type count, const NodeTy &val) { |
674 |
for (; count != 0; --count) insert(where, val); |
675 |
} |
676 |
|
677 |
// Assign special forms... |
678 |
void assign(size_type count, const NodeTy &val) { |
679 |
iterator I = this->begin(); |
680 |
for (; I != this->end() && count != 0; ++I, --count) |
681 |
*I = val; |
682 |
if (count != 0) |
683 |
insert(this->end(), val, val); |
684 |
else |
685 |
erase(I, this->end()); |
686 |
} |
687 |
template<class InIt> void assign(InIt first1, InIt last1) { |
688 |
iterator first2 = this->begin(), last2 = this->end(); |
689 |
for ( ; first1 != last1 && first2 != last2; ++first1, ++first2) |
690 |
*first1 = *first2; |
691 |
if (first2 == last2) |
692 |
erase(first1, last1); |
693 |
else |
694 |
insert(last1, first2, last2); |
695 |
} |
696 |
|
697 |
|
698 |
// Resize members... |
699 |
void resize(size_type newsize, NodeTy val) { |
700 |
iterator i = this->begin(); |
701 |
size_type len = 0; |
702 |
for ( ; i != this->end() && len < newsize; ++i, ++len) /* empty*/ ; |
703 |
|
704 |
if (len == newsize) |
705 |
erase(i, this->end()); |
706 |
else // i == end() |
707 |
insert(this->end(), newsize - len, val); |
708 |
} |
709 |
void resize(size_type newsize) { resize(newsize, NodeTy()); } |
710 |
}; |
711 |
|
712 |
} // End llvm namespace |
713 |
|
714 |
namespace std { |
715 |
// Ensure that swap uses the fast list swap... |
716 |
template<class Ty> |
717 |
void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) { |
718 |
Left.swap(Right); |
719 |
} |
720 |
} // End 'std' extensions... |
721 |
|
722 |
#endif // LLVM_ADT_ILIST_H |