| //===- llvm/ADT/simple_ilist.h - Simple Intrusive List ----------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_ADT_SIMPLE_ILIST_H |
| #define LLVM_ADT_SIMPLE_ILIST_H |
| |
| #include "llvm/ADT/ilist_base.h" |
| #include "llvm/ADT/ilist_iterator.h" |
| #include "llvm/ADT/ilist_node.h" |
| #include "llvm/ADT/ilist_node_options.h" |
| #include "llvm/Support/Compiler.h" |
| #include <algorithm> |
| #include <cassert> |
| #include <cstddef> |
| #include <functional> |
| #include <iterator> |
| #include <utility> |
| |
| namespace llvm { |
| |
| /// A simple intrusive list implementation. |
| /// |
| /// This is a simple intrusive list for a \c T that inherits from \c |
| /// ilist_node<T>. The list never takes ownership of anything inserted in it. |
| /// |
| /// Unlike \a iplist<T> and \a ilist<T>, \a simple_ilist<T> never deletes |
| /// values, and has no callback traits. |
| /// |
| /// The API for adding nodes include \a push_front(), \a push_back(), and \a |
| /// insert(). These all take values by reference (not by pointer), except for |
| /// the range version of \a insert(). |
| /// |
| /// There are three sets of API for discarding nodes from the list: \a |
| /// remove(), which takes a reference to the node to remove, \a erase(), which |
| /// takes an iterator or iterator range and returns the next one, and \a |
| /// clear(), which empties out the container. All three are constant time |
| /// operations. None of these deletes any nodes; in particular, if there is a |
| /// single node in the list, then these have identical semantics: |
| /// \li \c L.remove(L.front()); |
| /// \li \c L.erase(L.begin()); |
| /// \li \c L.clear(); |
| /// |
| /// As a convenience for callers, there are parallel APIs that take a \c |
| /// Disposer (such as \c std::default_delete<T>): \a removeAndDispose(), \a |
| /// eraseAndDispose(), and \a clearAndDispose(). These have different names |
| /// because the extra semantic is otherwise non-obvious. They are equivalent |
| /// to calling \a std::for_each() on the range to be discarded. |
| /// |
| /// The currently available \p Options customize the nodes in the list. The |
| /// same options must be specified in the \a ilist_node instantiation for |
| /// compatibility (although the order is irrelevant). |
| /// \li Use \a ilist_tag to designate which ilist_node for a given \p T this |
| /// list should use. This is useful if a type \p T is part of multiple, |
| /// independent lists simultaneously. |
| /// \li Use \a ilist_sentinel_tracking to always (or never) track whether a |
| /// node is a sentinel. Specifying \c true enables the \a |
| /// ilist_node::isSentinel() API. Unlike \a ilist_node::isKnownSentinel(), |
| /// which is only appropriate for assertions, \a ilist_node::isSentinel() is |
| /// appropriate for real logic. |
| /// |
| /// Here are examples of \p Options usage: |
| /// \li \c simple_ilist<T> gives the defaults. \li \c |
| /// simple_ilist<T,ilist_sentinel_tracking<true>> enables the \a |
| /// ilist_node::isSentinel() API. |
| /// \li \c simple_ilist<T,ilist_tag<A>,ilist_sentinel_tracking<false>> |
| /// specifies a tag of A and that tracking should be off (even when |
| /// LLVM_ENABLE_ABI_BREAKING_CHECKS are enabled). |
| /// \li \c simple_ilist<T,ilist_sentinel_tracking<false>,ilist_tag<A>> is |
| /// equivalent to the last. |
| /// |
| /// See \a is_valid_option for steps on adding a new option. |
| template <typename T, class... Options> |
| class simple_ilist |
| : ilist_detail::compute_node_options<T, Options...>::type::list_base_type, |
| ilist_detail::SpecificNodeAccess< |
| typename ilist_detail::compute_node_options<T, Options...>::type> { |
| static_assert(ilist_detail::check_options<Options...>::value, |
| "Unrecognized node option!"); |
| using OptionsT = |
| typename ilist_detail::compute_node_options<T, Options...>::type; |
| using list_base_type = typename OptionsT::list_base_type; |
| ilist_sentinel<OptionsT> Sentinel; |
| |
| public: |
| using value_type = typename OptionsT::value_type; |
| using pointer = typename OptionsT::pointer; |
| using reference = typename OptionsT::reference; |
| using const_pointer = typename OptionsT::const_pointer; |
| using const_reference = typename OptionsT::const_reference; |
| using iterator = ilist_iterator<OptionsT, false, false>; |
| using const_iterator = ilist_iterator<OptionsT, false, true>; |
| using reverse_iterator = ilist_iterator<OptionsT, true, false>; |
| using const_reverse_iterator = ilist_iterator<OptionsT, true, true>; |
| using size_type = size_t; |
| using difference_type = ptrdiff_t; |
| |
| simple_ilist() = default; |
| ~simple_ilist() = default; |
| |
| // No copy constructors. |
| simple_ilist(const simple_ilist &) = delete; |
| simple_ilist &operator=(const simple_ilist &) = delete; |
| |
| // Move constructors. |
| simple_ilist(simple_ilist &&X) { splice(end(), X); } |
| simple_ilist &operator=(simple_ilist &&X) { |
| clear(); |
| splice(end(), X); |
| return *this; |
| } |
| |
| iterator begin() { return ++iterator(Sentinel); } |
| const_iterator begin() const { return ++const_iterator(Sentinel); } |
| iterator end() { return iterator(Sentinel); } |
| const_iterator end() const { return const_iterator(Sentinel); } |
| reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); } |
| const_reverse_iterator rbegin() const { |
| return ++const_reverse_iterator(Sentinel); |
| } |
| reverse_iterator rend() { return reverse_iterator(Sentinel); } |
| const_reverse_iterator rend() const { |
| return const_reverse_iterator(Sentinel); |
| } |
| |
| /// Check if the list is empty in constant time. |
| [[nodiscard]] bool empty() const { return Sentinel.empty(); } |
| |
| /// Calculate the size of the list in linear time. |
| [[nodiscard]] size_type size() const { return std::distance(begin(), end()); } |
| |
| reference front() { return *begin(); } |
| const_reference front() const { return *begin(); } |
| reference back() { return *rbegin(); } |
| const_reference back() const { return *rbegin(); } |
| |
| /// Insert a node at the front; never copies. |
| void push_front(reference Node) { insert(begin(), Node); } |
| |
| /// Insert a node at the back; never copies. |
| void push_back(reference Node) { insert(end(), Node); } |
| |
| /// Remove the node at the front; never deletes. |
| void pop_front() { erase(begin()); } |
| |
| /// Remove the node at the back; never deletes. |
| void pop_back() { erase(--end()); } |
| |
| /// Swap with another list in place using std::swap. |
| void swap(simple_ilist &X) { std::swap(*this, X); } |
| |
| /// Insert a node by reference; never copies. |
| iterator insert(iterator I, reference Node) { |
| list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node)); |
| return iterator(&Node); |
| } |
| |
| /// Insert a range of nodes; never copies. |
| template <class Iterator> |
| void insert(iterator I, Iterator First, Iterator Last) { |
| for (; First != Last; ++First) |
| insert(I, *First); |
| } |
| |
| /// Clone another list. |
| template <class Cloner, class Disposer> |
| void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) { |
| clearAndDispose(dispose); |
| for (const_reference V : L2) |
| push_back(*clone(V)); |
| } |
| |
| /// Remove a node by reference; never deletes. |
| /// |
| /// \see \a erase() for removing by iterator. |
| /// \see \a removeAndDispose() if the node should be deleted. |
| void remove(reference N) { list_base_type::remove(*this->getNodePtr(&N)); } |
| |
| /// Remove a node by reference and dispose of it. |
| template <class Disposer> |
| void removeAndDispose(reference N, Disposer dispose) { |
| remove(N); |
| dispose(&N); |
| } |
| |
| /// Remove a node by iterator; never deletes. |
| /// |
| /// \see \a remove() for removing by reference. |
| /// \see \a eraseAndDispose() it the node should be deleted. |
| iterator erase(iterator I) { |
| assert(I != end() && "Cannot remove end of list!"); |
| remove(*I++); |
| return I; |
| } |
| |
| /// Remove a range of nodes; never deletes. |
| /// |
| /// \see \a eraseAndDispose() if the nodes should be deleted. |
| iterator erase(iterator First, iterator Last) { |
| list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr()); |
| return Last; |
| } |
| |
| /// Remove a node by iterator and dispose of it. |
| template <class Disposer> |
| iterator eraseAndDispose(iterator I, Disposer dispose) { |
| auto Next = std::next(I); |
| erase(I); |
| dispose(&*I); |
| return Next; |
| } |
| |
| /// Remove a range of nodes and dispose of them. |
| template <class Disposer> |
| iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) { |
| while (First != Last) |
| First = eraseAndDispose(First, dispose); |
| return Last; |
| } |
| |
| /// Clear the list; never deletes. |
| /// |
| /// \see \a clearAndDispose() if the nodes should be deleted. |
| void clear() { Sentinel.reset(); } |
| |
| /// Clear the list and dispose of the nodes. |
| template <class Disposer> void clearAndDispose(Disposer dispose) { |
| eraseAndDispose(begin(), end(), dispose); |
| } |
| |
| /// Splice in another list. |
| void splice(iterator I, simple_ilist &L2) { |
| splice(I, L2, L2.begin(), L2.end()); |
| } |
| |
| /// Splice in a node from another list. |
| void splice(iterator I, simple_ilist &L2, iterator Node) { |
| splice(I, L2, Node, std::next(Node)); |
| } |
| |
| /// Splice in a range of nodes from another list. |
| void splice(iterator I, simple_ilist &, iterator First, iterator Last) { |
| list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(), |
| *Last.getNodePtr()); |
| } |
| |
| /// Merge in another list. |
| /// |
| /// \pre \c this and \p RHS are sorted. |
| ///@{ |
| void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); } |
| template <class Compare> void merge(simple_ilist &RHS, Compare comp); |
| ///@} |
| |
| /// Sort the list. |
| ///@{ |
| void sort() { sort(std::less<T>()); } |
| template <class Compare> void sort(Compare comp); |
| ///@} |
| }; |
| |
| template <class T, class... Options> |
| template <class Compare> |
| void simple_ilist<T, Options...>::merge(simple_ilist &RHS, Compare comp) { |
| if (this == &RHS || RHS.empty()) |
| return; |
| iterator LI = begin(), LE = end(); |
| iterator RI = RHS.begin(), RE = RHS.end(); |
| while (LI != LE) { |
| if (comp(*RI, *LI)) { |
| // Transfer a run of at least size 1 from RHS to LHS. |
| iterator RunStart = RI++; |
| RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); }); |
| splice(LI, RHS, RunStart, RI); |
| if (RI == RE) |
| return; |
| } |
| ++LI; |
| } |
| // Transfer the remaining RHS nodes once LHS is finished. |
| splice(LE, RHS, RI, RE); |
| } |
| |
| template <class T, class... Options> |
| template <class Compare> |
| void simple_ilist<T, Options...>::sort(Compare comp) { |
| // Vacuously sorted. |
| if (empty() || std::next(begin()) == end()) |
| return; |
| |
| // Split the list in the middle. |
| iterator Center = begin(), End = begin(); |
| while (End != end() && ++End != end()) { |
| ++Center; |
| ++End; |
| } |
| simple_ilist RHS; |
| RHS.splice(RHS.end(), *this, Center, end()); |
| |
| // Sort the sublists and merge back together. |
| sort(comp); |
| RHS.sort(comp); |
| merge(RHS, comp); |
| } |
| |
| } // end namespace llvm |
| |
| #endif // LLVM_ADT_SIMPLE_ILIST_H |