include/llvm/ADT/simple_ilist.h

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