contrib/llvm/include/llvm/ADT/simple_ilist.h

   1 //===- llvm/ADT/simple_ilist.h - Simple Intrusive List ----------*- 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 #ifndef LLVM_ADT_SIMPLE_ILIST_H
  11 #define LLVM_ADT_SIMPLE_ILIST_H
  12
  13 #include "llvm/ADT/ilist_base.h"
  14 #include "llvm/ADT/ilist_iterator.h"
  15 #include "llvm/ADT/ilist_node.h"
  16 #include <algorithm>
  17 #include <cassert>
  18 #include <cstddef>
  19
  20 namespace llvm {
  21
  22 /// A simple intrusive list implementation.
  23 ///
  24 /// This is a simple intrusive list for a \c T that inherits from \c
  25 /// ilist_node<T>.  The list never takes ownership of anything inserted in it.
  26 ///
  27 /// Unlike \a iplist<T> and \a ilist<T>, \a simple_ilist<T> never allocates or
  28 /// deletes values, and has no callback traits.
  29 ///
  30 /// The API for adding nodes include \a push_front(), \a push_back(), and \a
  31 /// insert().  These all take values by reference (not by pointer), except for
  32 /// the range version of \a insert().
  33 ///
  34 /// There are three sets of API for discarding nodes from the list: \a
  35 /// remove(), which takes a reference to the node to remove, \a erase(), which
  36 /// takes an iterator or iterator range and returns the next one, and \a
  37 /// clear(), which empties out the container.  All three are constant time
  38 /// operations.  None of these deletes any nodes; in particular, if there is a
  39 /// single node in the list, then these have identical semantics:
  40 /// \li \c L.remove(L.front());
  41 /// \li \c L.erase(L.begin());
  42 /// \li \c L.clear();
  43 ///
  44 /// As a convenience for callers, there are parallel APIs that take a \c
  45 /// Disposer (such as \c std::default_delete<T>): \a removeAndDispose(), \a
  46 /// eraseAndDispose(), and \a clearAndDispose().  These have different names
  47 /// because the extra semantic is otherwise non-obvious.  They are equivalent
  48 /// to calling \a std::for_each() on the range to be discarded.
  49 ///
  50 /// The currently available \p Options customize the nodes in the list.  The
  51 /// same options must be specified in the \a ilist_node instantation for
  52 /// compatibility (although the order is irrelevant).
  53 /// \li Use \a ilist_tag to designate which ilist_node for a given \p T this
  54 /// list should use.  This is useful if a type \p T is part of multiple,
  55 /// independent lists simultaneously.
  56 /// \li Use \a ilist_sentinel_tracking to always (or never) track whether a
  57 /// node is a sentinel.  Specifying \c true enables the \a
  58 /// ilist_node::isSentinel() API.  Unlike \a ilist_node::isKnownSentinel(),
  59 /// which is only appropriate for assertions, \a ilist_node::isSentinel() is
  60 /// appropriate for real logic.
  61 ///
  62 /// Here are examples of \p Options usage:
  63 /// \li \c simple_ilist<T> gives the defaults.  \li \c
  64 /// simple_ilist<T,ilist_sentinel_tracking<true>> enables the \a
  65 /// ilist_node::isSentinel() API.
  66 /// \li \c simple_ilist<T,ilist_tag<A>,ilist_sentinel_tracking<false>>
  67 /// specifies a tag of A and that tracking should be off (even when
  68 /// LLVM_ENABLE_ABI_BREAKING_CHECKS are enabled).
  69 /// \li \c simple_ilist<T,ilist_sentinel_tracking<false>,ilist_tag<A>> is
  70 /// equivalent to the last.
  71 ///
  72 /// See \a is_valid_option for steps on adding a new option.
  73 template <typename T, class... Options>
  74 class simple_ilist
  75     : ilist_detail::compute_node_options<T, Options...>::type::list_base_type,
  76       ilist_detail::SpecificNodeAccess<
  77           typename ilist_detail::compute_node_options<T, Options...>::type> {
  78   static_assert(ilist_detail::check_options<Options...>::value,
  79                 "Unrecognized node option!");
  80   typedef
  81       typename ilist_detail::compute_node_options<T, Options...>::type OptionsT;
  82   typedef typename OptionsT::list_base_type list_base_type;
  83   ilist_sentinel<OptionsT> Sentinel;
  84
  85 public:
  86   typedef typename OptionsT::value_type value_type;
  87   typedef typename OptionsT::pointer pointer;
  88   typedef typename OptionsT::reference reference;
  89   typedef typename OptionsT::const_pointer const_pointer;
  90   typedef typename OptionsT::const_reference const_reference;
  91   typedef ilist_iterator<OptionsT, false, false> iterator;
  92   typedef ilist_iterator<OptionsT, false, true> const_iterator;
  93   typedef ilist_iterator<OptionsT, true, false> reverse_iterator;
  94   typedef ilist_iterator<OptionsT, true, true> const_reverse_iterator;
  95   typedef size_t size_type;
  96   typedef ptrdiff_t difference_type;
  97
  98   simple_ilist() = default;
  99   ~simple_ilist() = default;
 100
 101   // No copy constructors.
 102   simple_ilist(const simple_ilist &) = delete;
 103   simple_ilist &operator=(const simple_ilist &) = delete;
 104
 105   // Move constructors.
 106   simple_ilist(simple_ilist &&X) { splice(end(), X); }
 107   simple_ilist &operator=(simple_ilist &&X) {
 108     clear();
 109     splice(end(), X);
 110     return *this;
 111   }
 112
 113   iterator begin() { return ++iterator(Sentinel); }
 114   const_iterator begin() const { return ++const_iterator(Sentinel); }
 115   iterator end() { return iterator(Sentinel); }
 116   const_iterator end() const { return const_iterator(Sentinel); }
 117   reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); }
 118   const_reverse_iterator rbegin() const {
 119     return ++const_reverse_iterator(Sentinel);
 120   }
 121   reverse_iterator rend() { return reverse_iterator(Sentinel); }
 122   const_reverse_iterator rend() const {
 123     return const_reverse_iterator(Sentinel);
 124   }
 125
 126   /// Check if the list is empty in constant time.
 127   LLVM_NODISCARD bool empty() const { return Sentinel.empty(); }
 128
 129   /// Calculate the size of the list in linear time.
 130   LLVM_NODISCARD size_type size() const {
 131     return std::distance(begin(), end());
 132   }
 133
 134   reference front() { return *begin(); }
 135   const_reference front() const { return *begin(); }
 136   reference back() { return *rbegin(); }
 137   const_reference back() const { return *rbegin(); }
 138
 139   /// Insert a node at the front; never copies.
 140   void push_front(reference Node) { insert(begin(), Node); }
 141
 142   /// Insert a node at the back; never copies.
 143   void push_back(reference Node) { insert(end(), Node); }
 144
 145   /// Remove the node at the front; never deletes.
 146   void pop_front() { erase(begin()); }
 147
 148   /// Remove the node at the back; never deletes.
 149   void pop_back() { erase(--end()); }
 150
 151   /// Swap with another list in place using std::swap.
 152   void swap(simple_ilist &X) { std::swap(*this, X); }
 153
 154   /// Insert a node by reference; never copies.
 155   iterator insert(iterator I, reference Node) {
 156     list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node));
 157     return iterator(&Node);
 158   }
 159
 160   /// Insert a range of nodes; never copies.
 161   template <class Iterator>
 162   void insert(iterator I, Iterator First, Iterator Last) {
 163     for (; First != Last; ++First)
 164       insert(I, *First);
 165   }
 166
 167   /// Clone another list.
 168   template <class Cloner, class Disposer>
 169   void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) {
 170     clearAndDispose(dispose);
 171     for (const_reference V : L2)
 172       push_back(*clone(V));
 173   }
 174
 175   /// Remove a node by reference; never deletes.
 176   ///
 177   /// \see \a erase() for removing by iterator.
 178   /// \see \a removeAndDispose() if the node should be deleted.
 179   void remove(reference N) { list_base_type::remove(*this->getNodePtr(&N)); }
 180
 181   /// Remove a node by reference and dispose of it.
 182   template <class Disposer>
 183   void removeAndDispose(reference N, Disposer dispose) {
 184     remove(N);
 185     dispose(&N);
 186   }
 187
 188   /// Remove a node by iterator; never deletes.
 189   ///
 190   /// \see \a remove() for removing by reference.
 191   /// \see \a eraseAndDispose() it the node should be deleted.
 192   iterator erase(iterator I) {
 193     assert(I != end() && "Cannot remove end of list!");
 194     remove(*I++);
 195     return I;
 196   }
 197
 198   /// Remove a range of nodes; never deletes.
 199   ///
 200   /// \see \a eraseAndDispose() if the nodes should be deleted.
 201   iterator erase(iterator First, iterator Last) {
 202     list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr());
 203     return Last;
 204   }
 205
 206   /// Remove a node by iterator and dispose of it.
 207   template <class Disposer>
 208   iterator eraseAndDispose(iterator I, Disposer dispose) {
 209     auto Next = std::next(I);
 210     erase(I);
 211     dispose(&*I);
 212     return Next;
 213   }
 214
 215   /// Remove a range of nodes and dispose of them.
 216   template <class Disposer>
 217   iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) {
 218     while (First != Last)
 219       First = eraseAndDispose(First, dispose);
 220     return Last;
 221   }
 222
 223   /// Clear the list; never deletes.
 224   ///
 225   /// \see \a clearAndDispose() if the nodes should be deleted.
 226   void clear() { Sentinel.reset(); }
 227
 228   /// Clear the list and dispose of the nodes.
 229   template <class Disposer> void clearAndDispose(Disposer dispose) {
 230     eraseAndDispose(begin(), end(), dispose);
 231   }
 232
 233   /// Splice in another list.
 234   void splice(iterator I, simple_ilist &L2) {
 235     splice(I, L2, L2.begin(), L2.end());
 236   }
 237
 238   /// Splice in a node from another list.
 239   void splice(iterator I, simple_ilist &L2, iterator Node) {
 240     splice(I, L2, Node, std::next(Node));
 241   }
 242
 243   /// Splice in a range of nodes from another list.
 244   void splice(iterator I, simple_ilist &, iterator First, iterator Last) {
 245     list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(),
 246                                    *Last.getNodePtr());
 247   }
 248
 249   /// Merge in another list.
 250   ///
 251   /// \pre \c this and \p RHS are sorted.
 252   ///@{
 253   void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); }
 254   template <class Compare> void merge(simple_ilist &RHS, Compare comp);
 255   ///@}
 256
 257   /// Sort the list.
 258   ///@{
 259   void sort() { sort(std::less<T>()); }
 260   template <class Compare> void sort(Compare comp);
 261   ///@}
 262 };
 263
 264 template <class T, class... Options>
 265 template <class Compare>
 266 void simple_ilist<T, Options...>::merge(simple_ilist &RHS, Compare comp) {
 267   if (this == &RHS || RHS.empty())
 268     return;
 269   iterator LI = begin(), LE = end();
 270   iterator RI = RHS.begin(), RE = RHS.end();
 271   while (LI != LE) {
 272     if (comp(*RI, *LI)) {
 273       // Transfer a run of at least size 1 from RHS to LHS.
 274       iterator RunStart = RI++;
 275       RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); });
 276       splice(LI, RHS, RunStart, RI);
 277       if (RI == RE)
 278         return;
 279     }
 280     ++LI;
 281   }
 282   // Transfer the remaining RHS nodes once LHS is finished.
 283   splice(LE, RHS, RI, RE);
 284 }
 285
 286 template <class T, class... Options>
 287 template <class Compare>
 288 void simple_ilist<T, Options...>::sort(Compare comp) {
 289   // Vacuously sorted.
 290   if (empty() || std::next(begin()) == end())
 291     return;
 292
 293   // Split the list in the middle.
 294   iterator Center = begin(), End = begin();
 295   while (End != end() && ++End != end()) {
 296     ++Center;
 297     ++End;
 298   }
 299   simple_ilist RHS;
 300   RHS.splice(RHS.end(), *this, Center, end());
 301
 302   // Sort the sublists and merge back together.
 303   sort(comp);
 304   RHS.sort(comp);
 305   merge(RHS, comp);
 306 }
 307
 308 } // end namespace llvm
 309
 310 #endif // LLVM_ADT_SIMPLE_ILIST_H