llvm/ADT/simple_ilist.h

0001 //===- llvm/ADT/simple_ilist.h - Simple Intrusive List ----------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_ADT_SIMPLE_ILIST_H
0010 #define LLVM_ADT_SIMPLE_ILIST_H
0011
0012 #include "llvm/ADT/ilist_base.h"
0013 #include "llvm/ADT/ilist_iterator.h"
0014 #include "llvm/ADT/ilist_node.h"
0015 #include "llvm/ADT/ilist_node_options.h"
0016 #include "llvm/Support/Compiler.h"
0017 #include <algorithm>
0018 #include <cassert>
0019 #include <cstddef>
0020 #include <functional>
0021 #include <iterator>
0022 #include <utility>
0023
0024 namespace llvm {
0025
0026 /// A simple intrusive list implementation.
0027 ///
0028 /// This is a simple intrusive list for a \c T that inherits from \c
0029 /// ilist_node<T>.  The list never takes ownership of anything inserted in it.
0030 ///
0031 /// Unlike \a iplist<T> and \a ilist<T>, \a simple_ilist<T> never deletes
0032 /// values, and has no callback traits.
0033 ///
0034 /// The API for adding nodes include \a push_front(), \a push_back(), and \a
0035 /// insert().  These all take values by reference (not by pointer), except for
0036 /// the range version of \a insert().
0037 ///
0038 /// There are three sets of API for discarding nodes from the list: \a
0039 /// remove(), which takes a reference to the node to remove, \a erase(), which
0040 /// takes an iterator or iterator range and returns the next one, and \a
0041 /// clear(), which empties out the container.  All three are constant time
0042 /// operations.  None of these deletes any nodes; in particular, if there is a
0043 /// single node in the list, then these have identical semantics:
0044 /// \li \c L.remove(L.front());
0045 /// \li \c L.erase(L.begin());
0046 /// \li \c L.clear();
0047 ///
0048 /// As a convenience for callers, there are parallel APIs that take a \c
0049 /// Disposer (such as \c std::default_delete<T>): \a removeAndDispose(), \a
0050 /// eraseAndDispose(), and \a clearAndDispose().  These have different names
0051 /// because the extra semantic is otherwise non-obvious.  They are equivalent
0052 /// to calling \a std::for_each() on the range to be discarded.
0053 ///
0054 /// The currently available \p Options customize the nodes in the list.  The
0055 /// same options must be specified in the \a ilist_node instantiation for
0056 /// compatibility (although the order is irrelevant).
0057 /// \li Use \a ilist_tag to designate which ilist_node for a given \p T this
0058 /// list should use.  This is useful if a type \p T is part of multiple,
0059 /// independent lists simultaneously.
0060 /// \li Use \a ilist_sentinel_tracking to always (or never) track whether a
0061 /// node is a sentinel.  Specifying \c true enables the \a
0062 /// ilist_node::isSentinel() API.  Unlike \a ilist_node::isKnownSentinel(),
0063 /// which is only appropriate for assertions, \a ilist_node::isSentinel() is
0064 /// appropriate for real logic.
0065 ///
0066 /// Here are examples of \p Options usage:
0067 /// \li \c simple_ilist<T> gives the defaults.  \li \c
0068 /// simple_ilist<T,ilist_sentinel_tracking<true>> enables the \a
0069 /// ilist_node::isSentinel() API.
0070 /// \li \c simple_ilist<T,ilist_tag<A>,ilist_sentinel_tracking<false>>
0071 /// specifies a tag of A and that tracking should be off (even when
0072 /// LLVM_ENABLE_ABI_BREAKING_CHECKS are enabled).
0073 /// \li \c simple_ilist<T,ilist_sentinel_tracking<false>,ilist_tag<A>> is
0074 /// equivalent to the last.
0075 ///
0076 /// See \a is_valid_option for steps on adding a new option.
0077 template <typename T, class... Options>
0078 class simple_ilist
0079     : ilist_detail::compute_node_options<T, Options...>::type::list_base_type,
0080       ilist_detail::SpecificNodeAccess<
0081           typename ilist_detail::compute_node_options<T, Options...>::type> {
0082   static_assert(ilist_detail::check_options<Options...>::value,
0083                 "Unrecognized node option!");
0084   using OptionsT =
0085       typename ilist_detail::compute_node_options<T, Options...>::type;
0086   using list_base_type = typename OptionsT::list_base_type;
0087   ilist_sentinel<OptionsT> Sentinel;
0088
0089 public:
0090   using value_type = typename OptionsT::value_type;
0091   using pointer = typename OptionsT::pointer;
0092   using reference = typename OptionsT::reference;
0093   using const_pointer = typename OptionsT::const_pointer;
0094   using const_reference = typename OptionsT::const_reference;
0095   using iterator =
0096       typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
0097                                           false, false>::type;
0098   using const_iterator =
0099       typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
0100                                           false, true>::type;
0101   using reverse_iterator =
0102       typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
0103                                           true, false>::type;
0104   using const_reverse_iterator =
0105       typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
0106                                           true, true>::type;
0107   using size_type = size_t;
0108   using difference_type = ptrdiff_t;
0109
0110   simple_ilist() = default;
0111   ~simple_ilist() = default;
0112
0113   // No copy constructors.
0114   simple_ilist(const simple_ilist &) = delete;
0115   simple_ilist &operator=(const simple_ilist &) = delete;
0116
0117   // Move constructors.
0118   simple_ilist(simple_ilist &&X) { splice(end(), X); }
0119   simple_ilist &operator=(simple_ilist &&X) {
0120     clear();
0121     splice(end(), X);
0122     return *this;
0123   }
0124
0125   iterator begin() { return ++iterator(Sentinel); }
0126   const_iterator begin() const { return ++const_iterator(Sentinel); }
0127   iterator end() { return iterator(Sentinel); }
0128   const_iterator end() const { return const_iterator(Sentinel); }
0129   reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); }
0130   const_reverse_iterator rbegin() const {
0131     return ++const_reverse_iterator(Sentinel);
0132   }
0133   reverse_iterator rend() { return reverse_iterator(Sentinel); }
0134   const_reverse_iterator rend() const {
0135     return const_reverse_iterator(Sentinel);
0136   }
0137
0138   /// Check if the list is empty in constant time.
0139   [[nodiscard]] bool empty() const { return Sentinel.empty(); }
0140
0141   /// Calculate the size of the list in linear time.
0142   [[nodiscard]] size_type size() const { return std::distance(begin(), end()); }
0143
0144   reference front() { return *begin(); }
0145   const_reference front() const { return *begin(); }
0146   reference back() { return *rbegin(); }
0147   const_reference back() const { return *rbegin(); }
0148
0149   /// Insert a node at the front; never copies.
0150   void push_front(reference Node) { insert(begin(), Node); }
0151
0152   /// Insert a node at the back; never copies.
0153   void push_back(reference Node) { insert(end(), Node); }
0154
0155   /// Remove the node at the front; never deletes.
0156   void pop_front() { erase(begin()); }
0157
0158   /// Remove the node at the back; never deletes.
0159   void pop_back() { erase(--end()); }
0160
0161   /// Swap with another list in place using std::swap.
0162   void swap(simple_ilist &X) { std::swap(*this, X); }
0163
0164   /// Insert a node by reference; never copies.
0165   iterator insert(iterator I, reference Node) {
0166     list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node));
0167     return iterator(&Node);
0168   }
0169
0170   /// Insert a range of nodes; never copies.
0171   template <class Iterator>
0172   void insert(iterator I, Iterator First, Iterator Last) {
0173     for (; First != Last; ++First)
0174       insert(I, *First);
0175   }
0176
0177   /// Clone another list.
0178   template <class Cloner, class Disposer>
0179   void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) {
0180     clearAndDispose(dispose);
0181     for (const_reference V : L2)
0182       push_back(*clone(V));
0183   }
0184
0185   /// Remove a node by reference; never deletes.
0186   ///
0187   /// \see \a erase() for removing by iterator.
0188   /// \see \a removeAndDispose() if the node should be deleted.
0189   void remove(reference N) { list_base_type::remove(*this->getNodePtr(&N)); }
0190
0191   /// Remove a node by reference and dispose of it.
0192   template <class Disposer>
0193   void removeAndDispose(reference N, Disposer dispose) {
0194     remove(N);
0195     dispose(&N);
0196   }
0197
0198   /// Remove a node by iterator; never deletes.
0199   ///
0200   /// \see \a remove() for removing by reference.
0201   /// \see \a eraseAndDispose() it the node should be deleted.
0202   iterator erase(iterator I) {
0203     assert(I != end() && "Cannot remove end of list!");
0204     remove(*I++);
0205     return I;
0206   }
0207
0208   /// Remove a range of nodes; never deletes.
0209   ///
0210   /// \see \a eraseAndDispose() if the nodes should be deleted.
0211   iterator erase(iterator First, iterator Last) {
0212     list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr());
0213     return Last;
0214   }
0215
0216   /// Remove a node by iterator and dispose of it.
0217   template <class Disposer>
0218   iterator eraseAndDispose(iterator I, Disposer dispose) {
0219     auto Next = std::next(I);
0220     erase(I);
0221     dispose(&*I);
0222     return Next;
0223   }
0224
0225   /// Remove a range of nodes and dispose of them.
0226   template <class Disposer>
0227   iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) {
0228     while (First != Last)
0229       First = eraseAndDispose(First, dispose);
0230     return Last;
0231   }
0232
0233   /// Clear the list; never deletes.
0234   ///
0235   /// \see \a clearAndDispose() if the nodes should be deleted.
0236   void clear() { Sentinel.reset(); }
0237
0238   /// Clear the list and dispose of the nodes.
0239   template <class Disposer> void clearAndDispose(Disposer dispose) {
0240     eraseAndDispose(begin(), end(), dispose);
0241   }
0242
0243   /// Splice in another list.
0244   void splice(iterator I, simple_ilist &L2) {
0245     splice(I, L2, L2.begin(), L2.end());
0246   }
0247
0248   /// Splice in a node from another list.
0249   void splice(iterator I, simple_ilist &L2, iterator Node) {
0250     splice(I, L2, Node, std::next(Node));
0251   }
0252
0253   /// Splice in a range of nodes from another list.
0254   void splice(iterator I, simple_ilist &, iterator First, iterator Last) {
0255     list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(),
0256                                    *Last.getNodePtr());
0257   }
0258
0259   /// Merge in another list.
0260   ///
0261   /// \pre \c this and \p RHS are sorted.
0262   ///@{
0263   void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); }
0264   template <class Compare> void merge(simple_ilist &RHS, Compare comp);
0265   ///@}
0266
0267   /// Sort the list.
0268   ///@{
0269   void sort() { sort(std::less<T>()); }
0270   template <class Compare> void sort(Compare comp);
0271   ///@}
0272 };
0273
0274 template <class T, class... Options>
0275 template <class Compare>
0276 void simple_ilist<T, Options...>::merge(simple_ilist &RHS, Compare comp) {
0277   if (this == &RHS || RHS.empty())
0278     return;
0279   iterator LI = begin(), LE = end();
0280   iterator RI = RHS.begin(), RE = RHS.end();
0281   while (LI != LE) {
0282     if (comp(*RI, *LI)) {
0283       // Transfer a run of at least size 1 from RHS to LHS.
0284       iterator RunStart = RI++;
0285       RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); });
0286       splice(LI, RHS, RunStart, RI);
0287       if (RI == RE)
0288         return;
0289     }
0290     ++LI;
0291   }
0292   // Transfer the remaining RHS nodes once LHS is finished.
0293   splice(LE, RHS, RI, RE);
0294 }
0295
0296 template <class T, class... Options>
0297 template <class Compare>
0298 void simple_ilist<T, Options...>::sort(Compare comp) {
0299   // Vacuously sorted.
0300   if (empty() || std::next(begin()) == end())
0301     return;
0302
0303   // Split the list in the middle.
0304   iterator Center = begin(), End = begin();
0305   while (End != end() && ++End != end()) {
0306     ++Center;
0307     ++End;
0308   }
0309   simple_ilist RHS;
0310   RHS.splice(RHS.end(), *this, Center, end());
0311
0312   // Sort the sublists and merge back together.
0313   sort(comp);
0314   RHS.sort(comp);
0315   merge(RHS, comp);
0316 }
0317
0318 } // end namespace llvm
0319
0320 #endif // LLVM_ADT_SIMPLE_ILIST_H