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
24namespace 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.
77template <typename T, class... Options>
78class 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
89public:
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 =
96      typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
97                                          false, false>::type;
98  using const_iterator =
99      typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
100                                          false, true>::type;
101  using reverse_iterator =
102      typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
103                                          true, false>::type;
104  using const_reverse_iterator =
105      typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
106                                          true, true>::type;
107  using size_type = size_t;
108  using difference_type = ptrdiff_t;
109
110  simple_ilist() = default;
111  ~simple_ilist() = default;
112
113  // No copy constructors.
114  simple_ilist(const simple_ilist &) = delete;
115  simple_ilist &operator=(const simple_ilist &) = delete;
116
117  // Move constructors.
118  simple_ilist(simple_ilist &&X) { splice(end(), X); }
119  simple_ilist &operator=(simple_ilist &&X) {
120    clear();
121    splice(end(), X);
122    return *this;
123  }
124
125  iterator begin() { return ++iterator(Sentinel); }
126  const_iterator begin() const { return ++const_iterator(Sentinel); }
127  iterator end() { return iterator(Sentinel); }
128  const_iterator end() const { return const_iterator(Sentinel); }
129  reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); }
130  const_reverse_iterator rbegin() const {
131    return ++const_reverse_iterator(Sentinel);
132  }
133  reverse_iterator rend() { return reverse_iterator(Sentinel); }
134  const_reverse_iterator rend() const {
135    return const_reverse_iterator(Sentinel);
136  }
137
138  /// Check if the list is empty in constant time.
139  [[nodiscard]] bool empty() const { return Sentinel.empty(); }
140
141  /// Calculate the size of the list in linear time.
142  [[nodiscard]] size_type size() const { return std::distance(begin(), end()); }
143
144  reference front() { return *begin(); }
145  const_reference front() const { return *begin(); }
146  reference back() { return *rbegin(); }
147  const_reference back() const { return *rbegin(); }
148
149  /// Insert a node at the front; never copies.
150  void push_front(reference Node) { insert(begin(), Node); }
151
152  /// Insert a node at the back; never copies.
153  void push_back(reference Node) { insert(end(), Node); }
154
155  /// Remove the node at the front; never deletes.
156  void pop_front() { erase(begin()); }
157
158  /// Remove the node at the back; never deletes.
159  void pop_back() { erase(--end()); }
160
161  /// Swap with another list in place using std::swap.
162  void swap(simple_ilist &X) { std::swap(*this, X); }
163
164  /// Insert a node by reference; never copies.
165  iterator insert(iterator I, reference Node) {
166    list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node));
167    return iterator(&Node);
168  }
169
170  /// Insert a range of nodes; never copies.
171  template <class Iterator>
172  void insert(iterator I, Iterator First, Iterator Last) {
173    for (; First != Last; ++First)
174      insert(I, *First);
175  }
176
177  /// Clone another list.
178  template <class Cloner, class Disposer>
179  void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) {
180    clearAndDispose(dispose);
181    for (const_reference V : L2)
182      push_back(*clone(V));
183  }
184
185  /// Remove a node by reference; never deletes.
186  ///
187  /// \see \a erase() for removing by iterator.
188  /// \see \a removeAndDispose() if the node should be deleted.
189  void remove(reference N) { list_base_type::remove(*this->getNodePtr(&N)); }
190
191  /// Remove a node by reference and dispose of it.
192  template <class Disposer>
193  void removeAndDispose(reference N, Disposer dispose) {
194    remove(N);
195    dispose(&N);
196  }
197
198  /// Remove a node by iterator; never deletes.
199  ///
200  /// \see \a remove() for removing by reference.
201  /// \see \a eraseAndDispose() it the node should be deleted.
202  iterator erase(iterator I) {
203    assert(I != end() && "Cannot remove end of list!");
204    remove(*I++);
205    return I;
206  }
207
208  /// Remove a range of nodes; never deletes.
209  ///
210  /// \see \a eraseAndDispose() if the nodes should be deleted.
211  iterator erase(iterator First, iterator Last) {
212    list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr());
213    return Last;
214  }
215
216  /// Remove a node by iterator and dispose of it.
217  template <class Disposer>
218  iterator eraseAndDispose(iterator I, Disposer dispose) {
219    auto Next = std::next(I);
220    erase(I);
221    dispose(&*I);
222    return Next;
223  }
224
225  /// Remove a range of nodes and dispose of them.
226  template <class Disposer>
227  iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) {
228    while (First != Last)
229      First = eraseAndDispose(First, dispose);
230    return Last;
231  }
232
233  /// Clear the list; never deletes.
234  ///
235  /// \see \a clearAndDispose() if the nodes should be deleted.
236  void clear() { Sentinel.reset(); }
237
238  /// Clear the list and dispose of the nodes.
239  template <class Disposer> void clearAndDispose(Disposer dispose) {
240    eraseAndDispose(begin(), end(), dispose);
241  }
242
243  /// Splice in another list.
244  void splice(iterator I, simple_ilist &L2) {
245    splice(I, L2, L2.begin(), L2.end());
246  }
247
248  /// Splice in a node from another list.
249  void splice(iterator I, simple_ilist &L2, iterator Node) {
250    splice(I, L2, Node, std::next(Node));
251  }
252
253  /// Splice in a range of nodes from another list.
254  void splice(iterator I, simple_ilist &, iterator First, iterator Last) {
255    list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(),
256                                   *Last.getNodePtr());
257  }
258
259  /// Merge in another list.
260  ///
261  /// \pre \c this and \p RHS are sorted.
262  ///@{
263  void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); }
264  template <class Compare> void merge(simple_ilist &RHS, Compare comp);
265  ///@}
266
267  /// Sort the list.
268  ///@{
269  void sort() { sort(std::less<T>()); }
270  template <class Compare> void sort(Compare comp);
271  ///@}
272};
273
274template <class T, class... Options>
275template <class Compare>
276void simple_ilist<T, Options...>::merge(simple_ilist &RHS, Compare comp) {
277  if (this == &RHS || RHS.empty())
278    return;
279  iterator LI = begin(), LE = end();
280  iterator RI = RHS.begin(), RE = RHS.end();
281  while (LI != LE) {
282    if (comp(*RI, *LI)) {
283      // Transfer a run of at least size 1 from RHS to LHS.
284      iterator RunStart = RI++;
285      RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); });
286      splice(LI, RHS, RunStart, RI);
287      if (RI == RE)
288        return;
289    }
290    ++LI;
291  }
292  // Transfer the remaining RHS nodes once LHS is finished.
293  splice(LE, RHS, RI, RE);
294}
295
296template <class T, class... Options>
297template <class Compare>
298void simple_ilist<T, Options...>::sort(Compare comp) {
299  // Vacuously sorted.
300  if (empty() || std::next(begin()) == end())
301    return;
302
303  // Split the list in the middle.
304  iterator Center = begin(), End = begin();
305  while (End != end() && ++End != end()) {
306    ++Center;
307    ++End;
308  }
309  simple_ilist RHS;
310  RHS.splice(RHS.end(), *this, Center, end());
311
312  // Sort the sublists and merge back together.
313  sort(comp);
314  RHS.sort(comp);
315  merge(RHS, comp);
316}
317
318} // end namespace llvm
319
320#endif // LLVM_ADT_SIMPLE_ILIST_H
321