Stephen Hines | c6ca60f | 2023-05-09 02:19:22 -0700 | [diff] [blame^] | 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 deletes |
| 32 | /// 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 instantiation 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 | [[nodiscard]] bool empty() const { return Sentinel.empty(); } |
| 132 | |
| 133 | /// Calculate the size of the list in linear time. |
| 134 | [[nodiscard]] size_type size() const { return std::distance(begin(), end()); } |
| 135 | |
| 136 | reference front() { return *begin(); } |
| 137 | const_reference front() const { return *begin(); } |
| 138 | reference back() { return *rbegin(); } |
| 139 | const_reference back() const { return *rbegin(); } |
| 140 | |
| 141 | /// Insert a node at the front; never copies. |
| 142 | void push_front(reference Node) { insert(begin(), Node); } |
| 143 | |
| 144 | /// Insert a node at the back; never copies. |
| 145 | void push_back(reference Node) { insert(end(), Node); } |
| 146 | |
| 147 | /// Remove the node at the front; never deletes. |
| 148 | void pop_front() { erase(begin()); } |
| 149 | |
| 150 | /// Remove the node at the back; never deletes. |
| 151 | void pop_back() { erase(--end()); } |
| 152 | |
| 153 | /// Swap with another list in place using std::swap. |
| 154 | void swap(simple_ilist &X) { std::swap(*this, X); } |
| 155 | |
| 156 | /// Insert a node by reference; never copies. |
| 157 | iterator insert(iterator I, reference Node) { |
| 158 | list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node)); |
| 159 | return iterator(&Node); |
| 160 | } |
| 161 | |
| 162 | /// Insert a range of nodes; never copies. |
| 163 | template <class Iterator> |
| 164 | void insert(iterator I, Iterator First, Iterator Last) { |
| 165 | for (; First != Last; ++First) |
| 166 | insert(I, *First); |
| 167 | } |
| 168 | |
| 169 | /// Clone another list. |
| 170 | template <class Cloner, class Disposer> |
| 171 | void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) { |
| 172 | clearAndDispose(dispose); |
| 173 | for (const_reference V : L2) |
| 174 | push_back(*clone(V)); |
| 175 | } |
| 176 | |
| 177 | /// Remove a node by reference; never deletes. |
| 178 | /// |
| 179 | /// \see \a erase() for removing by iterator. |
| 180 | /// \see \a removeAndDispose() if the node should be deleted. |
| 181 | void remove(reference N) { list_base_type::remove(*this->getNodePtr(&N)); } |
| 182 | |
| 183 | /// Remove a node by reference and dispose of it. |
| 184 | template <class Disposer> |
| 185 | void removeAndDispose(reference N, Disposer dispose) { |
| 186 | remove(N); |
| 187 | dispose(&N); |
| 188 | } |
| 189 | |
| 190 | /// Remove a node by iterator; never deletes. |
| 191 | /// |
| 192 | /// \see \a remove() for removing by reference. |
| 193 | /// \see \a eraseAndDispose() it the node should be deleted. |
| 194 | iterator erase(iterator I) { |
| 195 | assert(I != end() && "Cannot remove end of list!"); |
| 196 | remove(*I++); |
| 197 | return I; |
| 198 | } |
| 199 | |
| 200 | /// Remove a range of nodes; never deletes. |
| 201 | /// |
| 202 | /// \see \a eraseAndDispose() if the nodes should be deleted. |
| 203 | iterator erase(iterator First, iterator Last) { |
| 204 | list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr()); |
| 205 | return Last; |
| 206 | } |
| 207 | |
| 208 | /// Remove a node by iterator and dispose of it. |
| 209 | template <class Disposer> |
| 210 | iterator eraseAndDispose(iterator I, Disposer dispose) { |
| 211 | auto Next = std::next(I); |
| 212 | erase(I); |
| 213 | dispose(&*I); |
| 214 | return Next; |
| 215 | } |
| 216 | |
| 217 | /// Remove a range of nodes and dispose of them. |
| 218 | template <class Disposer> |
| 219 | iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) { |
| 220 | while (First != Last) |
| 221 | First = eraseAndDispose(First, dispose); |
| 222 | return Last; |
| 223 | } |
| 224 | |
| 225 | /// Clear the list; never deletes. |
| 226 | /// |
| 227 | /// \see \a clearAndDispose() if the nodes should be deleted. |
| 228 | void clear() { Sentinel.reset(); } |
| 229 | |
| 230 | /// Clear the list and dispose of the nodes. |
| 231 | template <class Disposer> void clearAndDispose(Disposer dispose) { |
| 232 | eraseAndDispose(begin(), end(), dispose); |
| 233 | } |
| 234 | |
| 235 | /// Splice in another list. |
| 236 | void splice(iterator I, simple_ilist &L2) { |
| 237 | splice(I, L2, L2.begin(), L2.end()); |
| 238 | } |
| 239 | |
| 240 | /// Splice in a node from another list. |
| 241 | void splice(iterator I, simple_ilist &L2, iterator Node) { |
| 242 | splice(I, L2, Node, std::next(Node)); |
| 243 | } |
| 244 | |
| 245 | /// Splice in a range of nodes from another list. |
| 246 | void splice(iterator I, simple_ilist &, iterator First, iterator Last) { |
| 247 | list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(), |
| 248 | *Last.getNodePtr()); |
| 249 | } |
| 250 | |
| 251 | /// Merge in another list. |
| 252 | /// |
| 253 | /// \pre \c this and \p RHS are sorted. |
| 254 | ///@{ |
| 255 | void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); } |
| 256 | template <class Compare> void merge(simple_ilist &RHS, Compare comp); |
| 257 | ///@} |
| 258 | |
| 259 | /// Sort the list. |
| 260 | ///@{ |
| 261 | void sort() { sort(std::less<T>()); } |
| 262 | template <class Compare> void sort(Compare comp); |
| 263 | ///@} |
| 264 | }; |
| 265 | |
| 266 | template <class T, class... Options> |
| 267 | template <class Compare> |
| 268 | void simple_ilist<T, Options...>::merge(simple_ilist &RHS, Compare comp) { |
| 269 | if (this == &RHS || RHS.empty()) |
| 270 | return; |
| 271 | iterator LI = begin(), LE = end(); |
| 272 | iterator RI = RHS.begin(), RE = RHS.end(); |
| 273 | while (LI != LE) { |
| 274 | if (comp(*RI, *LI)) { |
| 275 | // Transfer a run of at least size 1 from RHS to LHS. |
| 276 | iterator RunStart = RI++; |
| 277 | RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); }); |
| 278 | splice(LI, RHS, RunStart, RI); |
| 279 | if (RI == RE) |
| 280 | return; |
| 281 | } |
| 282 | ++LI; |
| 283 | } |
| 284 | // Transfer the remaining RHS nodes once LHS is finished. |
| 285 | splice(LE, RHS, RI, RE); |
| 286 | } |
| 287 | |
| 288 | template <class T, class... Options> |
| 289 | template <class Compare> |
| 290 | void simple_ilist<T, Options...>::sort(Compare comp) { |
| 291 | // Vacuously sorted. |
| 292 | if (empty() || std::next(begin()) == end()) |
| 293 | return; |
| 294 | |
| 295 | // Split the list in the middle. |
| 296 | iterator Center = begin(), End = begin(); |
| 297 | while (End != end() && ++End != end()) { |
| 298 | ++Center; |
| 299 | ++End; |
| 300 | } |
| 301 | simple_ilist RHS; |
| 302 | RHS.splice(RHS.end(), *this, Center, end()); |
| 303 | |
| 304 | // Sort the sublists and merge back together. |
| 305 | sort(comp); |
| 306 | RHS.sort(comp); |
| 307 | merge(RHS, comp); |
| 308 | } |
| 309 | |
| 310 | } // end namespace llvm |
| 311 | |
| 312 | #endif // LLVM_ADT_SIMPLE_ILIST_H |