Line data Source code
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 class itself should be a plug in replacement for list. This list
15 : // replacement does not provide a constant time size() method, so be careful to
16 : // use empty() when you really want to know if it's empty.
17 : //
18 : // The ilist class is implemented as a circular list. The list itself contains
19 : // a sentinel node, whose Next points at begin() and whose Prev points at
20 : // rbegin(). The sentinel node itself serves as end() and rend().
21 : //
22 : //===----------------------------------------------------------------------===//
23 :
24 : #ifndef LLVM_ADT_ILIST_H
25 : #define LLVM_ADT_ILIST_H
26 :
27 : #include "llvm/ADT/simple_ilist.h"
28 : #include <cassert>
29 : #include <cstddef>
30 : #include <iterator>
31 :
32 : namespace llvm {
33 :
34 : /// Use delete by default for iplist and ilist.
35 : ///
36 : /// Specialize this to get different behaviour for ownership-related API. (If
37 : /// you really want ownership semantics, consider using std::list or building
38 : /// something like \a BumpPtrList.)
39 : ///
40 : /// \see ilist_noalloc_traits
41 : template <typename NodeTy> struct ilist_alloc_traits {
42 5014863 : static void deleteNode(NodeTy *V) { delete V; }
43 : };
44 :
45 : /// Custom traits to do nothing on deletion.
46 : ///
47 : /// Specialize ilist_alloc_traits to inherit from this to disable the
48 : /// non-intrusive deletion in iplist (which implies ownership).
49 : ///
50 : /// If you want purely intrusive semantics with no callbacks, consider using \a
51 : /// simple_ilist instead.
52 : ///
53 : /// \code
54 : /// template <>
55 : /// struct ilist_alloc_traits<MyType> : ilist_noalloc_traits<MyType> {};
56 : /// \endcode
57 : template <typename NodeTy> struct ilist_noalloc_traits {
58 0 : static void deleteNode(NodeTy *V) {}
59 : };
60 :
61 : /// Callbacks do nothing by default in iplist and ilist.
62 : ///
63 : /// Specialize this for to use callbacks for when nodes change their list
64 : /// membership.
65 : template <typename NodeTy> struct ilist_callback_traits {
66 0 : void addNodeToList(NodeTy *) {}
67 0 : void removeNodeFromList(NodeTy *) {}
68 :
69 : /// Callback before transferring nodes to this list.
70 : ///
71 : /// \pre \c this!=&OldList
72 : template <class Iterator>
73 0 : void transferNodesFromList(ilist_callback_traits &OldList, Iterator /*first*/,
74 : Iterator /*last*/) {
75 : (void)OldList;
76 0 : }
77 0 : };
78 :
79 : /// A fragment for template traits for intrusive list that provides default
80 0 : /// node related operations.
81 0 : ///
82 : /// TODO: Remove this layer of indirection. It's not necessary.
83 : template <typename NodeTy>
84 0 : struct ilist_node_traits : ilist_alloc_traits<NodeTy>,
85 : ilist_callback_traits<NodeTy> {};
86 :
87 : /// Template traits for intrusive list.
88 : ///
89 : /// Customize callbacks and allocation semantics.
90 : template <typename NodeTy>
91 : struct ilist_traits : public ilist_node_traits<NodeTy> {};
92 :
93 : /// Const traits should never be instantiated.
94 : template <typename Ty> struct ilist_traits<const Ty> {};
95 :
96 : namespace ilist_detail {
97 :
98 : template <class T> T &make();
99 :
100 : /// Type trait to check for a traits class that has a getNext member (as a
101 : /// canary for any of the ilist_nextprev_traits API).
102 : template <class TraitsT, class NodeT> struct HasGetNext {
103 : typedef char Yes[1];
104 : typedef char No[2];
105 : template <size_t N> struct SFINAE {};
106 :
107 : template <class U>
108 : static Yes &test(U *I, decltype(I->getNext(&make<NodeT>())) * = 0);
109 : template <class> static No &test(...);
110 :
111 : public:
112 : static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
113 : };
114 :
115 : /// Type trait to check for a traits class that has a createSentinel member (as
116 : /// a canary for any of the ilist_sentinel_traits API).
117 : template <class TraitsT> struct HasCreateSentinel {
118 : typedef char Yes[1];
119 : typedef char No[2];
120 :
121 : template <class U>
122 : static Yes &test(U *I, decltype(I->createSentinel()) * = 0);
123 : template <class> static No &test(...);
124 :
125 : public:
126 : static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
127 : };
128 :
129 : /// Type trait to check for a traits class that has a createNode member.
130 : /// Allocation should be managed in a wrapper class, instead of in
131 : /// ilist_traits.
132 : template <class TraitsT, class NodeT> struct HasCreateNode {
133 : typedef char Yes[1];
134 : typedef char No[2];
135 : template <size_t N> struct SFINAE {};
136 :
137 : template <class U>
138 : static Yes &test(U *I, decltype(I->createNode(make<NodeT>())) * = 0);
139 : template <class> static No &test(...);
140 :
141 : public:
142 : static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
143 : };
144 :
145 : template <class TraitsT, class NodeT> struct HasObsoleteCustomization {
146 : static const bool value = HasGetNext<TraitsT, NodeT>::value ||
147 : HasCreateSentinel<TraitsT>::value ||
148 : HasCreateNode<TraitsT, NodeT>::value;
149 : };
150 :
151 : } // end namespace ilist_detail
152 :
153 : //===----------------------------------------------------------------------===//
154 : //
155 : /// A wrapper around an intrusive list with callbacks and non-intrusive
156 : /// ownership.
157 : ///
158 : /// This wraps a purely intrusive list (like simple_ilist) with a configurable
159 : /// traits class. The traits can implement callbacks and customize the
160 : /// ownership semantics.
161 : ///
162 : /// This is a subset of ilist functionality that can safely be used on nodes of
163 : /// polymorphic types, i.e. a heterogeneous list with a common base class that
164 : /// holds the next/prev pointers. The only state of the list itself is an
165 : /// ilist_sentinel, which holds pointers to the first and last nodes in the
166 : /// list.
167 : template <class IntrusiveListT, class TraitsT>
168 : class iplist_impl : public TraitsT, IntrusiveListT {
169 : typedef IntrusiveListT base_list_type;
170 :
171 : public:
172 : typedef typename base_list_type::pointer pointer;
173 : typedef typename base_list_type::const_pointer const_pointer;
174 : typedef typename base_list_type::reference reference;
175 : typedef typename base_list_type::const_reference const_reference;
176 : typedef typename base_list_type::value_type value_type;
177 : typedef typename base_list_type::size_type size_type;
178 : typedef typename base_list_type::difference_type difference_type;
179 : typedef typename base_list_type::iterator iterator;
180 : typedef typename base_list_type::const_iterator const_iterator;
181 : typedef typename base_list_type::reverse_iterator reverse_iterator;
182 : typedef
183 : typename base_list_type::const_reverse_iterator const_reverse_iterator;
184 :
185 : private:
186 : // TODO: Drop this assertion and the transitive type traits anytime after
187 : // v4.0 is branched (i.e,. keep them for one release to help out-of-tree code
188 : // update).
189 : static_assert(
190 : !ilist_detail::HasObsoleteCustomization<TraitsT, value_type>::value,
191 : "ilist customization points have changed!");
192 :
193 : static bool op_less(const_reference L, const_reference R) { return L < R; }
194 : static bool op_equal(const_reference L, const_reference R) { return L == R; }
195 :
196 : public:
197 : iplist_impl() = default;
198 :
199 : iplist_impl(const iplist_impl &) = delete;
200 : iplist_impl &operator=(const iplist_impl &) = delete;
201 :
202 : iplist_impl(iplist_impl &&X)
203 : : TraitsT(std::move(X)), IntrusiveListT(std::move(X)) {}
204 : iplist_impl &operator=(iplist_impl &&X) {
205 : *static_cast<TraitsT *>(this) = std::move(X);
206 : *static_cast<IntrusiveListT *>(this) = std::move(X);
207 : return *this;
208 : }
209 :
210 : ~iplist_impl() { clear(); }
211 :
212 : // Miscellaneous inspection routines.
213 : size_type max_size() const { return size_type(-1); }
214 :
215 : using base_list_type::begin;
216 : using base_list_type::end;
217 : using base_list_type::rbegin;
218 : using base_list_type::rend;
219 : using base_list_type::empty;
220 : using base_list_type::front;
221 : using base_list_type::back;
222 :
223 : void swap(iplist_impl &RHS) {
224 : assert(0 && "Swap does not use list traits callback correctly yet!");
225 : base_list_type::swap(RHS);
226 : }
227 :
228 54115094 : iterator insert(iterator where, pointer New) {
229 115210572 : this->addNodeToList(New); // Notify traits that we added a node...
230 54115093 : return base_list_type::insert(where, *New);
231 : }
232 0 :
233 : iterator insert(iterator where, const_reference New) {
234 0 : return this->insert(where, new value_type(New));
235 : }
236 11741987 :
237 13286782 : iterator insertAfter(iterator where, pointer New) {
238 13286782 : if (empty())
239 0 : return insert(begin(), New);
240 0 : else
241 1544795 : return insert(++where, New);
242 0 : }
243 :
244 0 : /// Clone another list.
245 : template <class Cloner> void cloneFrom(const iplist_impl &L2, Cloner clone) {
246 0 : clear();
247 : for (const_reference V : L2)
248 0 : push_back(clone(V));
249 : }
250 0 :
251 56329651 : pointer remove(iterator &IT) {
252 : pointer Node = &*IT++;
253 59634782 : this->removeNodeFromList(Node); // Notify traits that we removed a node...
254 : base_list_type::remove(*Node);
255 56329652 : return Node;
256 : }
257 22432238 :
258 0 : pointer remove(const iterator &IT) {
259 26667365 : iterator MutIt = IT;
260 3384427 : return remove(MutIt);
261 23285600 : }
262 :
263 5612317 : pointer remove(pointer IT) { return remove(iterator(IT)); }
264 : pointer remove(reference IT) { return remove(iterator(IT)); }
265 4761618 :
266 0 : // erase - remove a node from the controlled sequence... and delete it.
267 25504988 : iterator erase(iterator where) {
268 28595693 : this->deleteNode(remove(where));
269 28788405 : return where;
270 0 : }
271 665188 :
272 289090 : iterator erase(pointer IT) { return erase(iterator(IT)); }
273 530221 : iterator erase(reference IT) { return erase(iterator(IT)); }
274 0 :
275 798458 : /// Remove all nodes from the list like clear(), but do not call
276 670136 : /// removeNodeFromList() or deleteNode().
277 798624 : ///
278 166 : /// This should only be used immediately before freeing nodes in bulk to
279 5107719 : /// avoid traversing the list and bringing all the nodes into cache.
280 27699736 : void clearAndLeakNodesUnsafely() { base_list_type::clear(); }
281 27388204 :
282 0 : private:
283 2662 : // transfer - The heart of the splice function. Move linked list nodes from
284 701238 : // [first, last) into position.
285 2662 : //
286 1771007 : void transfer(iterator position, iplist_impl &L2, iterator first, iterator last) {
287 1884577 : if (position == last)
288 116232 : return;
289 113570 :
290 1901850 : if (this != &L2) // Notify traits we moved the nodes...
291 493738 : this->transferNodesFromList(L2, first, last);
292 :
293 0 : base_list_type::splice(position, L2, first, last);
294 16198 : }
295 40726 :
296 24528 : public:
297 526546 : //===----------------------------------------------------------------------===
298 4604235 : // Functionality derived from other functions defined above...
299 4623399 : //
300 0 :
301 526546 : using base_list_type::size;
302 4453973 :
303 4099144 : iterator erase(iterator first, iterator last) {
304 47542062 : while (first != last)
305 17440075 : first = erase(first);
306 43770 : return last;
307 871173 : }
308 1019165 :
309 3099649 : void clear() { erase(begin(), end()); }
310 0 :
311 871173 : // Front and back inserters...
312 575197 : void push_front(pointer val) { insert(begin(), val); }
313 24681 : void push_back(pointer val) { insert(end(), val); }
314 411 : void pop_front() {
315 0 : assert(!empty() && "pop_front() on empty list!");
316 3041126 : erase(begin());
317 3041536 : }
318 138585 : void pop_back() {
319 0 : assert(!empty() && "pop_back() on empty list!");
320 6488185 : iterator t = end(); erase(--t);
321 3177249 : }
322 :
323 0 : // Special forms of insert...
324 1167264 : template<class InIt> void insert(iterator where, InIt first, InIt last) {
325 20015 : for (; first != last; ++first) insert(where, *first);
326 125201 : }
327 0 :
328 125201 : // Splice members - defined in terms of transfer...
329 125201 : void splice(iterator where, iplist_impl &L2) {
330 421501 : if (!L2.empty())
331 262225 : transfer(where, L2, L2.begin(), L2.end());
332 159272 : }
333 10500607 : void splice(iterator where, iplist_impl &L2, iterator first) {
334 32401017 : iterator last = first; ++last;
335 22283343 : if (where == first || where == last) return; // No change
336 10205823 : transfer(where, L2, first, last);
337 0 : }
338 0 : void splice(iterator where, iplist_impl &L2, iterator first, iterator last) {
339 6375397 : if (first != last) transfer(where, L2, first, last);
340 0 : }
341 288306 : void splice(iterator where, iplist_impl &L2, reference N) {
342 1187262 : splice(where, L2, iterator(N));
343 700519 : }
344 300983 : void splice(iterator where, iplist_impl &L2, pointer N) {
345 179251 : splice(where, L2, iterator(N));
346 12822 : }
347 25247 :
348 92353 : template <class Compare>
349 136589 : void merge(iplist_impl &Right, Compare comp) {
350 1094506 : if (this == &Right)
351 140290 : return;
352 96182 : this->transferNodesFromList(Right, Right.begin(), Right.end());
353 187 : base_list_type::merge(Right, comp);
354 96114 : }
355 1 : void merge(iplist_impl &Right) { return merge(Right, op_less); }
356 96054 :
357 98711 : using base_list_type::sort;
358 2512 :
359 96054 : /// Get the previous node, or \c nullptr for the list head.
360 688446 : pointer getPrevNode(reference N) const {
361 14239575 : auto I = N.getIterator();
362 14072986 : if (I == begin())
363 208693 : return nullptr;
364 96112 : return &*std::prev(I);
365 9341 : }
366 5792 : /// Get the previous node, or \c nullptr for the list head.
367 192108 : const_pointer getPrevNode(const_reference N) const {
368 : return getPrevNode(const_cast<reference >(N));
369 3233541 : }
370 17374 :
371 393404 : /// Get the next node, or \c nullptr for the list tail.
372 1 : pointer getNextNode(reference N) const {
373 393405 : auto Next = std::next(N.getIterator());
374 6309222 : if (Next == end())
375 : return nullptr;
376 42710 : return &*Next;
377 350221 : }
378 : /// Get the next node, or \c nullptr for the list tail.
379 350221 : const_pointer getNextNode(const_reference N) const {
380 474 : return getNextNode(const_cast<reference >(N));
381 0 : }
382 474 : };
383 0 :
384 : /// An intrusive list with ownership and callbacks specified/controlled by
385 : /// ilist_traits, only with API safe for polymorphic types.
386 8111348 : ///
387 : /// The \p Options parameters are the same as those for \a simple_ilist. See
388 : /// there for a description of what's available.
389 : template <class T, class... Options>
390 5915896 : class iplist
391 887592 : : public iplist_impl<simple_ilist<T, Options...>, ilist_traits<T>> {
392 887592 : using iplist_impl_type = typename iplist::iplist_impl;
393 :
394 : public:
395 : iplist() = default;
396 :
397 : iplist(const iplist &X) = delete;
398 0 : iplist &operator=(const iplist &X) = delete;
399 18 :
400 : iplist(iplist &&X) : iplist_impl_type(std::move(X)) {}
401 0 : iplist &operator=(iplist &&X) {
402 : *static_cast<iplist_impl_type *>(this) = std::move(X);
403 0 : return *this;
404 522135 : }
405 : };
406 3307793 :
407 : template <class T, class... Options> using ilist = iplist<T, Options...>;
408 0 :
409 0 : } // end namespace llvm
410 :
411 0 : namespace std {
412 :
413 0 : // Ensure that swap uses the fast list swap...
414 0 : template<class Ty>
415 : void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) {
416 0 : Left.swap(Right);
417 : }
418 :
419 2 : } // end namespace std
420 :
421 : #endif // LLVM_ADT_ILIST_H
|
