llvm/ADT/AllocatorList.h

0001 //===- llvm/ADT/AllocatorList.h - Custom allocator 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_ALLOCATORLIST_H
0010 #define LLVM_ADT_ALLOCATORLIST_H
0011
0012 #include "llvm/ADT/ilist_node.h"
0013 #include "llvm/ADT/iterator.h"
0014 #include "llvm/ADT/simple_ilist.h"
0015 #include "llvm/Support/Allocator.h"
0016 #include <cassert>
0017 #include <cstddef>
0018 #include <iterator>
0019 #include <type_traits>
0020 #include <utility>
0021
0022 namespace llvm {
0023
0024 /// A linked-list with a custom, local allocator.
0025 ///
0026 /// Expose a std::list-like interface that owns and uses a custom LLVM-style
0027 /// allocator (e.g., BumpPtrAllocator), leveraging \a simple_ilist for the
0028 /// implementation details.
0029 ///
0030 /// Because this list owns the allocator, calling \a splice() with a different
0031 /// list isn't generally safe.  As such, \a splice has been left out of the
0032 /// interface entirely.
0033 template <class T, class AllocatorT> class AllocatorList : AllocatorT {
0034   struct Node : ilist_node<Node> {
0035     Node(Node &&) = delete;
0036     Node(const Node &) = delete;
0037     Node &operator=(Node &&) = delete;
0038     Node &operator=(const Node &) = delete;
0039
0040     Node(T &&V) : V(std::move(V)) {}
0041     Node(const T &V) : V(V) {}
0042     template <class... Ts> Node(Ts &&... Vs) : V(std::forward<Ts>(Vs)...) {}
0043     T V;
0044   };
0045
0046   using list_type = simple_ilist<Node>;
0047
0048   list_type List;
0049
0050   AllocatorT &getAlloc() { return *this; }
0051   const AllocatorT &getAlloc() const { return *this; }
0052
0053   template <class... ArgTs> Node *create(ArgTs &&... Args) {
0054     return new (getAlloc()) Node(std::forward<ArgTs>(Args)...);
0055   }
0056
0057   struct Cloner {
0058     AllocatorList &AL;
0059
0060     Cloner(AllocatorList &AL) : AL(AL) {}
0061
0062     Node *operator()(const Node &N) const { return AL.create(N.V); }
0063   };
0064
0065   struct Disposer {
0066     AllocatorList &AL;
0067
0068     Disposer(AllocatorList &AL) : AL(AL) {}
0069
0070     void operator()(Node *N) const {
0071       N->~Node();
0072       AL.getAlloc().Deallocate(N);
0073     }
0074   };
0075
0076 public:
0077   using value_type = T;
0078   using pointer = T *;
0079   using reference = T &;
0080   using const_pointer = const T *;
0081   using const_reference = const T &;
0082   using size_type = typename list_type::size_type;
0083   using difference_type = typename list_type::difference_type;
0084
0085 private:
0086   template <class ValueT, class IteratorBase>
0087   class IteratorImpl
0088       : public iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>,
0089                                      IteratorBase,
0090                                      std::bidirectional_iterator_tag, ValueT> {
0091     template <class OtherValueT, class OtherIteratorBase>
0092     friend class IteratorImpl;
0093     friend AllocatorList;
0094
0095     using base_type =
0096         iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>, IteratorBase,
0097                               std::bidirectional_iterator_tag, ValueT>;
0098
0099   public:
0100     using value_type = ValueT;
0101     using pointer = ValueT *;
0102     using reference = ValueT &;
0103
0104     IteratorImpl() = default;
0105     IteratorImpl(const IteratorImpl &) = default;
0106     IteratorImpl &operator=(const IteratorImpl &) = default;
0107
0108     explicit IteratorImpl(const IteratorBase &I) : base_type(I) {}
0109
0110     template <class OtherValueT, class OtherIteratorBase>
0111     IteratorImpl(const IteratorImpl<OtherValueT, OtherIteratorBase> &X,
0112                  std::enable_if_t<std::is_convertible<
0113                      OtherIteratorBase, IteratorBase>::value> * = nullptr)
0114         : base_type(X.wrapped()) {}
0115
0116     ~IteratorImpl() = default;
0117
0118     reference operator*() const { return base_type::wrapped()->V; }
0119     pointer operator->() const { return &operator*(); }
0120   };
0121
0122 public:
0123   using iterator = IteratorImpl<T, typename list_type::iterator>;
0124   using reverse_iterator =
0125       IteratorImpl<T, typename list_type::reverse_iterator>;
0126   using const_iterator =
0127       IteratorImpl<const T, typename list_type::const_iterator>;
0128   using const_reverse_iterator =
0129       IteratorImpl<const T, typename list_type::const_reverse_iterator>;
0130
0131   AllocatorList() = default;
0132   AllocatorList(AllocatorList &&X)
0133       : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {}
0134
0135   AllocatorList(const AllocatorList &X) {
0136     List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
0137   }
0138
0139   AllocatorList &operator=(AllocatorList &&X) {
0140     clear(); // Dispose of current nodes explicitly.
0141     List = std::move(X.List);
0142     getAlloc() = std::move(X.getAlloc());
0143     return *this;
0144   }
0145
0146   AllocatorList &operator=(const AllocatorList &X) {
0147     List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
0148     return *this;
0149   }
0150
0151   ~AllocatorList() { clear(); }
0152
0153   void swap(AllocatorList &RHS) {
0154     List.swap(RHS.List);
0155     std::swap(getAlloc(), RHS.getAlloc());
0156   }
0157
0158   bool empty() { return List.empty(); }
0159   size_t size() { return List.size(); }
0160
0161   iterator begin() { return iterator(List.begin()); }
0162   iterator end() { return iterator(List.end()); }
0163   const_iterator begin() const { return const_iterator(List.begin()); }
0164   const_iterator end() const { return const_iterator(List.end()); }
0165   reverse_iterator rbegin() { return reverse_iterator(List.rbegin()); }
0166   reverse_iterator rend() { return reverse_iterator(List.rend()); }
0167   const_reverse_iterator rbegin() const {
0168     return const_reverse_iterator(List.rbegin());
0169   }
0170   const_reverse_iterator rend() const {
0171     return const_reverse_iterator(List.rend());
0172   }
0173
0174   T &back() { return List.back().V; }
0175   T &front() { return List.front().V; }
0176   const T &back() const { return List.back().V; }
0177   const T &front() const { return List.front().V; }
0178
0179   template <class... Ts> iterator emplace(iterator I, Ts &&... Vs) {
0180     return iterator(List.insert(I.wrapped(), *create(std::forward<Ts>(Vs)...)));
0181   }
0182
0183   iterator insert(iterator I, T &&V) {
0184     return iterator(List.insert(I.wrapped(), *create(std::move(V))));
0185   }
0186   iterator insert(iterator I, const T &V) {
0187     return iterator(List.insert(I.wrapped(), *create(V)));
0188   }
0189
0190   template <class Iterator>
0191   void insert(iterator I, Iterator First, Iterator Last) {
0192     for (; First != Last; ++First)
0193       List.insert(I.wrapped(), *create(*First));
0194   }
0195
0196   iterator erase(iterator I) {
0197     return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this)));
0198   }
0199
0200   iterator erase(iterator First, iterator Last) {
0201     return iterator(
0202         List.eraseAndDispose(First.wrapped(), Last.wrapped(), Disposer(*this)));
0203   }
0204
0205   void clear() { List.clearAndDispose(Disposer(*this)); }
0206   void pop_back() { List.eraseAndDispose(--List.end(), Disposer(*this)); }
0207   void pop_front() { List.eraseAndDispose(List.begin(), Disposer(*this)); }
0208   void push_back(T &&V) { insert(end(), std::move(V)); }
0209   void push_front(T &&V) { insert(begin(), std::move(V)); }
0210   void push_back(const T &V) { insert(end(), V); }
0211   void push_front(const T &V) { insert(begin(), V); }
0212   template <class... Ts> void emplace_back(Ts &&... Vs) {
0213     emplace(end(), std::forward<Ts>(Vs)...);
0214   }
0215   template <class... Ts> void emplace_front(Ts &&... Vs) {
0216     emplace(begin(), std::forward<Ts>(Vs)...);
0217   }
0218
0219   /// Reset the underlying allocator.
0220   ///
0221   /// \pre \c empty()
0222   void resetAlloc() {
0223     assert(empty() && "Cannot reset allocator if not empty");
0224     getAlloc().Reset();
0225   }
0226 };
0227
0228 template <class T> using BumpPtrList = AllocatorList<T, BumpPtrAllocator>;
0229
0230 } // end namespace llvm
0231
0232 #endif // LLVM_ADT_ALLOCATORLIST_H