contrib/llvm/include/llvm/ADT/ilist.h

   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   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   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   void addNodeToList(NodeTy *) {}
  67   void removeNodeFromList(NodeTy *) {}
  68
  69   /// Callback before transferring nodes to this list.
  70   ///
  71   /// \pre \c this!=&OldList
  72   template <class Iterator>
  73   void transferNodesFromList(ilist_callback_traits &OldList, Iterator /*first*/,
  74                              Iterator /*last*/) {
  75     (void)OldList;
  76   }
  77 };
  78
  79 /// A fragment for template traits for intrusive list that provides default
  80 /// node related operations.
  81 ///
  82 /// TODO: Remove this layer of indirection.  It's not necessary.
  83 template <typename NodeTy>
  84 struct ilist_node_traits : ilist_alloc_traits<NodeTy>,
  85                            ilist_callback_traits<NodeTy> {};
  86
  87 /// Default template traits for intrusive list.
  88 ///
  89 /// By inheriting from this, you can easily use default implementations for all
  90 /// common operations.
  91 ///
  92 /// TODO: Remove this customization point.  Specializing ilist_traits is
  93 /// already fully general.
  94 template <typename NodeTy>
  95 struct ilist_default_traits : public ilist_node_traits<NodeTy> {};
  96
  97 /// Template traits for intrusive list.
  98 ///
  99 /// Customize callbacks and allocation semantics.
 100 template <typename NodeTy>
 101 struct ilist_traits : public ilist_default_traits<NodeTy> {};
 102
 103 /// Const traits should never be instantiated.
 104 template <typename Ty> struct ilist_traits<const Ty> {};
 105
 106 namespace ilist_detail {
 107
 108 template <class T> T &make();
 109
 110 /// Type trait to check for a traits class that has a getNext member (as a
 111 /// canary for any of the ilist_nextprev_traits API).
 112 template <class TraitsT, class NodeT> struct HasGetNext {
 113   typedef char Yes[1];
 114   typedef char No[2];
 115   template <size_t N> struct SFINAE {};
 116
 117   template <class U>
 118   static Yes &test(U *I, decltype(I->getNext(&make<NodeT>())) * = 0);
 119   template <class> static No &test(...);
 120
 121 public:
 122   static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
 123 };
 124
 125 /// Type trait to check for a traits class that has a createSentinel member (as
 126 /// a canary for any of the ilist_sentinel_traits API).
 127 template <class TraitsT> struct HasCreateSentinel {
 128   typedef char Yes[1];
 129   typedef char No[2];
 130
 131   template <class U>
 132   static Yes &test(U *I, decltype(I->createSentinel()) * = 0);
 133   template <class> static No &test(...);
 134
 135 public:
 136   static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
 137 };
 138
 139 /// Type trait to check for a traits class that has a createNode member.
 140 /// Allocation should be managed in a wrapper class, instead of in
 141 /// ilist_traits.
 142 template <class TraitsT, class NodeT> struct HasCreateNode {
 143   typedef char Yes[1];
 144   typedef char No[2];
 145   template <size_t N> struct SFINAE {};
 146
 147   template <class U>
 148   static Yes &test(U *I, decltype(I->createNode(make<NodeT>())) * = 0);
 149   template <class> static No &test(...);
 150
 151 public:
 152   static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
 153 };
 154
 155 template <class TraitsT, class NodeT> struct HasObsoleteCustomization {
 156   static const bool value = HasGetNext<TraitsT, NodeT>::value ||
 157                             HasCreateSentinel<TraitsT>::value ||
 158                             HasCreateNode<TraitsT, NodeT>::value;
 159 };
 160
 161 } // end namespace ilist_detail
 162
 163 //===----------------------------------------------------------------------===//
 164 //
 165 /// A wrapper around an intrusive list with callbacks and non-intrusive
 166 /// ownership.
 167 ///
 168 /// This wraps a purely intrusive list (like simple_ilist) with a configurable
 169 /// traits class.  The traits can implement callbacks and customize the
 170 /// ownership semantics.
 171 ///
 172 /// This is a subset of ilist functionality that can safely be used on nodes of
 173 /// polymorphic types, i.e. a heterogeneous list with a common base class that
 174 /// holds the next/prev pointers.  The only state of the list itself is an
 175 /// ilist_sentinel, which holds pointers to the first and last nodes in the
 176 /// list.
 177 template <class IntrusiveListT, class TraitsT>
 178 class iplist_impl : public TraitsT, IntrusiveListT {
 179   typedef IntrusiveListT base_list_type;
 180
 181 protected:
 182   typedef iplist_impl iplist_impl_type;
 183
 184 public:
 185   typedef typename base_list_type::pointer pointer;
 186   typedef typename base_list_type::const_pointer const_pointer;
 187   typedef typename base_list_type::reference reference;
 188   typedef typename base_list_type::const_reference const_reference;
 189   typedef typename base_list_type::value_type value_type;
 190   typedef typename base_list_type::size_type size_type;
 191   typedef typename base_list_type::difference_type difference_type;
 192   typedef typename base_list_type::iterator iterator;
 193   typedef typename base_list_type::const_iterator const_iterator;
 194   typedef typename base_list_type::reverse_iterator reverse_iterator;
 195   typedef
 196       typename base_list_type::const_reverse_iterator const_reverse_iterator;
 197
 198 private:
 199   // TODO: Drop this assertion and the transitive type traits anytime after
 200   // v4.0 is branched (i.e,. keep them for one release to help out-of-tree code
 201   // update).
 202   static_assert(
 203       !ilist_detail::HasObsoleteCustomization<TraitsT, value_type>::value,
 204       "ilist customization points have changed!");
 205
 206   static bool op_less(const_reference L, const_reference R) { return L < R; }
 207   static bool op_equal(const_reference L, const_reference R) { return L == R; }
 208
 209 public:
 210   iplist_impl() = default;
 211
 212   iplist_impl(const iplist_impl &) = delete;
 213   iplist_impl &operator=(const iplist_impl &) = delete;
 214
 215   iplist_impl(iplist_impl &&X)
 216       : TraitsT(std::move(X)), IntrusiveListT(std::move(X)) {}
 217   iplist_impl &operator=(iplist_impl &&X) {
 218     *static_cast<TraitsT *>(this) = std::move(X);
 219     *static_cast<IntrusiveListT *>(this) = std::move(X);
 220     return *this;
 221   }
 222
 223   ~iplist_impl() { clear(); }
 224
 225   // Miscellaneous inspection routines.
 226   size_type max_size() const { return size_type(-1); }
 227
 228   using base_list_type::begin;
 229   using base_list_type::end;
 230   using base_list_type::rbegin;
 231   using base_list_type::rend;
 232   using base_list_type::empty;
 233   using base_list_type::front;
 234   using base_list_type::back;
 235
 236   void swap(iplist_impl &RHS) {
 237     assert(0 && "Swap does not use list traits callback correctly yet!");
 238     base_list_type::swap(RHS);
 239   }
 240
 241   iterator insert(iterator where, pointer New) {
 242     this->addNodeToList(New); // Notify traits that we added a node...
 243     return base_list_type::insert(where, *New);
 244   }
 245
 246   iterator insert(iterator where, const_reference New) {
 247     return this->insert(where, new value_type(New));
 248   }
 249
 250   iterator insertAfter(iterator where, pointer New) {
 251     if (empty())
 252       return insert(begin(), New);
 253     else
 254       return insert(++where, New);
 255   }
 256
 257   /// Clone another list.
 258   template <class Cloner> void cloneFrom(const iplist_impl &L2, Cloner clone) {
 259     clear();
 260     for (const_reference V : L2)
 261       push_back(clone(V));
 262   }
 263
 264   pointer remove(iterator &IT) {
 265     pointer Node = &*IT++;
 266     this->removeNodeFromList(Node); // Notify traits that we removed a node...
 267     base_list_type::remove(*Node);
 268     return Node;
 269   }
 270
 271   pointer remove(const iterator &IT) {
 272     iterator MutIt = IT;
 273     return remove(MutIt);
 274   }
 275
 276   pointer remove(pointer IT) { return remove(iterator(IT)); }
 277   pointer remove(reference IT) { return remove(iterator(IT)); }
 278
 279   // erase - remove a node from the controlled sequence... and delete it.
 280   iterator erase(iterator where) {
 281     this->deleteNode(remove(where));
 282     return where;
 283   }
 284
 285   iterator erase(pointer IT) { return erase(iterator(IT)); }
 286   iterator erase(reference IT) { return erase(iterator(IT)); }
 287
 288   /// Remove all nodes from the list like clear(), but do not call
 289   /// removeNodeFromList() or deleteNode().
 290   ///
 291   /// This should only be used immediately before freeing nodes in bulk to
 292   /// avoid traversing the list and bringing all the nodes into cache.
 293   void clearAndLeakNodesUnsafely() { base_list_type::clear(); }
 294
 295 private:
 296   // transfer - The heart of the splice function.  Move linked list nodes from
 297   // [first, last) into position.
 298   //
 299   void transfer(iterator position, iplist_impl &L2, iterator first, iterator last) {
 300     if (position == last)
 301       return;
 302
 303     if (this != &L2) // Notify traits we moved the nodes...
 304       this->transferNodesFromList(L2, first, last);
 305
 306     base_list_type::splice(position, L2, first, last);
 307   }
 308
 309 public:
 310   //===----------------------------------------------------------------------===
 311   // Functionality derived from other functions defined above...
 312   //
 313
 314   using base_list_type::size;
 315
 316   iterator erase(iterator first, iterator last) {
 317     while (first != last)
 318       first = erase(first);
 319     return last;
 320   }
 321
 322   void clear() { erase(begin(), end()); }
 323
 324   // Front and back inserters...
 325   void push_front(pointer val) { insert(begin(), val); }
 326   void push_back(pointer val) { insert(end(), val); }
 327   void pop_front() {
 328     assert(!empty() && "pop_front() on empty list!");
 329     erase(begin());
 330   }
 331   void pop_back() {
 332     assert(!empty() && "pop_back() on empty list!");
 333     iterator t = end(); erase(--t);
 334   }
 335
 336   // Special forms of insert...
 337   template<class InIt> void insert(iterator where, InIt first, InIt last) {
 338     for (; first != last; ++first) insert(where, *first);
 339   }
 340
 341   // Splice members - defined in terms of transfer...
 342   void splice(iterator where, iplist_impl &L2) {
 343     if (!L2.empty())
 344       transfer(where, L2, L2.begin(), L2.end());
 345   }
 346   void splice(iterator where, iplist_impl &L2, iterator first) {
 347     iterator last = first; ++last;
 348     if (where == first || where == last) return; // No change
 349     transfer(where, L2, first, last);
 350   }
 351   void splice(iterator where, iplist_impl &L2, iterator first, iterator last) {
 352     if (first != last) transfer(where, L2, first, last);
 353   }
 354   void splice(iterator where, iplist_impl &L2, reference N) {
 355     splice(where, L2, iterator(N));
 356   }
 357   void splice(iterator where, iplist_impl &L2, pointer N) {
 358     splice(where, L2, iterator(N));
 359   }
 360
 361   template <class Compare>
 362   void merge(iplist_impl &Right, Compare comp) {
 363     if (this == &Right)
 364       return;
 365     this->transferNodesFromList(Right, Right.begin(), Right.end());
 366     base_list_type::merge(Right, comp);
 367   }
 368   void merge(iplist_impl &Right) { return merge(Right, op_less); }
 369
 370   using base_list_type::sort;
 371
 372   /// \brief Get the previous node, or \c nullptr for the list head.
 373   pointer getPrevNode(reference N) const {
 374     auto I = N.getIterator();
 375     if (I == begin())
 376       return nullptr;
 377     return &*std::prev(I);
 378   }
 379   /// \brief Get the previous node, or \c nullptr for the list head.
 380   const_pointer getPrevNode(const_reference N) const {
 381     return getPrevNode(const_cast<reference >(N));
 382   }
 383
 384   /// \brief Get the next node, or \c nullptr for the list tail.
 385   pointer getNextNode(reference N) const {
 386     auto Next = std::next(N.getIterator());
 387     if (Next == end())
 388       return nullptr;
 389     return &*Next;
 390   }
 391   /// \brief Get the next node, or \c nullptr for the list tail.
 392   const_pointer getNextNode(const_reference N) const {
 393     return getNextNode(const_cast<reference >(N));
 394   }
 395 };
 396
 397 /// An intrusive list with ownership and callbacks specified/controlled by
 398 /// ilist_traits, only with API safe for polymorphic types.
 399 ///
 400 /// The \p Options parameters are the same as those for \a simple_ilist.  See
 401 /// there for a description of what's available.
 402 template <class T, class... Options>
 403 class iplist
 404     : public iplist_impl<simple_ilist<T, Options...>, ilist_traits<T>> {
 405   typedef typename iplist::iplist_impl_type iplist_impl_type;
 406
 407 public:
 408   iplist() = default;
 409
 410   iplist(const iplist &X) = delete;
 411   iplist &operator=(const iplist &X) = delete;
 412
 413   iplist(iplist &&X) : iplist_impl_type(std::move(X)) {}
 414   iplist &operator=(iplist &&X) {
 415     *static_cast<iplist_impl_type *>(this) = std::move(X);
 416     return *this;
 417   }
 418 };
 419
 420 template <class T, class... Options> using ilist = iplist<T, Options...>;
 421
 422 } // end namespace llvm
 423
 424 namespace std {
 425
 426   // Ensure that swap uses the fast list swap...
 427   template<class Ty>
 428   void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) {
 429     Left.swap(Right);
 430   }
 431
 432 } // end namespace std
 433
 434 #endif // LLVM_ADT_ILIST_H