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