1 //===- llvm/ADT/AllocatorList.h - Custom allocator 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_ALLOCATORLIST_H 10 #define LLVM_ADT_ALLOCATORLIST_H 11 12 #include "llvm/ADT/ilist_node.h" 13 #include "llvm/ADT/iterator.h" 14 #include "llvm/ADT/simple_ilist.h" 15 #include "llvm/Support/Allocator.h" 16 #include <algorithm> 17 #include <cassert> 18 #include <cstddef> 19 #include <iterator> 20 #include <type_traits> 21 #include <utility> 22 23 namespace llvm { 24 25 /// A linked-list with a custom, local allocator. 26 /// 27 /// Expose a std::list-like interface that owns and uses a custom LLVM-style 28 /// allocator (e.g., BumpPtrAllocator), leveraging \a simple_ilist for the 29 /// implementation details. 30 /// 31 /// Because this list owns the allocator, calling \a splice() with a different 32 /// list isn't generally safe. As such, \a splice has been left out of the 33 /// interface entirely. 34 template <class T, class AllocatorT> class AllocatorList : AllocatorT { 35 struct Node : ilist_node<Node> { 36 Node(Node &&) = delete; 37 Node(const Node &) = delete; 38 Node &operator=(Node &&) = delete; 39 Node &operator=(const Node &) = delete; 40 41 Node(T &&V) : V(std::move(V)) {} 42 Node(const T &V) : V(V) {} 43 template <class... Ts> Node(Ts &&... Vs) : V(std::forward<Ts>(Vs)...) {} 44 T V; 45 }; 46 47 using list_type = simple_ilist<Node>; 48 49 list_type List; 50 51 AllocatorT &getAlloc() { return *this; } 52 const AllocatorT &getAlloc() const { return *this; } 53 54 template <class... ArgTs> Node *create(ArgTs &&... Args) { 55 return new (getAlloc()) Node(std::forward<ArgTs>(Args)...); 56 } 57 58 struct Cloner { 59 AllocatorList &AL; 60 61 Cloner(AllocatorList &AL) : AL(AL) {} 62 63 Node *operator()(const Node &N) const { return AL.create(N.V); } 64 }; 65 66 struct Disposer { 67 AllocatorList &AL; 68 69 Disposer(AllocatorList &AL) : AL(AL) {} 70 71 void operator()(Node *N) const { 72 N->~Node(); 73 AL.getAlloc().Deallocate(N); 74 } 75 }; 76 77 public: 78 using value_type = T; 79 using pointer = T *; 80 using reference = T &; 81 using const_pointer = const T *; 82 using const_reference = const T &; 83 using size_type = typename list_type::size_type; 84 using difference_type = typename list_type::difference_type; 85 86 private: 87 template <class ValueT, class IteratorBase> 88 class IteratorImpl 89 : public iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>, 90 IteratorBase, 91 std::bidirectional_iterator_tag, ValueT> { 92 template <class OtherValueT, class OtherIteratorBase> 93 friend class IteratorImpl; 94 friend AllocatorList; 95 96 using base_type = 97 iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>, IteratorBase, 98 std::bidirectional_iterator_tag, ValueT>; 99 100 public: 101 using value_type = ValueT; 102 using pointer = ValueT *; 103 using reference = ValueT &; 104 105 IteratorImpl() = default; 106 IteratorImpl(const IteratorImpl &) = default; 107 IteratorImpl &operator=(const IteratorImpl &) = default; 108 109 explicit IteratorImpl(const IteratorBase &I) : base_type(I) {} 110 111 template <class OtherValueT, class OtherIteratorBase> 112 IteratorImpl(const IteratorImpl<OtherValueT, OtherIteratorBase> &X, 113 typename std::enable_if<std::is_convertible< 114 OtherIteratorBase, IteratorBase>::value>::type * = nullptr) 115 : base_type(X.wrapped()) {} 116 117 ~IteratorImpl() = default; 118 119 reference operator*() const { return base_type::wrapped()->V; } 120 pointer operator->() const { return &operator*(); } 121 122 friend bool operator==(const IteratorImpl &L, const IteratorImpl &R) { 123 return L.wrapped() == R.wrapped(); 124 } 125 friend bool operator!=(const IteratorImpl &L, const IteratorImpl &R) { 126 return !(L == R); 127 } 128 }; 129 130 public: 131 using iterator = IteratorImpl<T, typename list_type::iterator>; 132 using reverse_iterator = 133 IteratorImpl<T, typename list_type::reverse_iterator>; 134 using const_iterator = 135 IteratorImpl<const T, typename list_type::const_iterator>; 136 using const_reverse_iterator = 137 IteratorImpl<const T, typename list_type::const_reverse_iterator>; 138 139 AllocatorList() = default; 140 AllocatorList(AllocatorList &&X) 141 : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {} 142 143 AllocatorList(const AllocatorList &X) { 144 List.cloneFrom(X.List, Cloner(*this), Disposer(*this)); 145 } 146 147 AllocatorList &operator=(AllocatorList &&X) { 148 clear(); // Dispose of current nodes explicitly. 149 List = std::move(X.List); 150 getAlloc() = std::move(X.getAlloc()); 151 return *this; 152 } 153 154 AllocatorList &operator=(const AllocatorList &X) { 155 List.cloneFrom(X.List, Cloner(*this), Disposer(*this)); 156 return *this; 157 } 158 159 ~AllocatorList() { clear(); } 160 161 void swap(AllocatorList &RHS) { 162 List.swap(RHS.List); 163 std::swap(getAlloc(), RHS.getAlloc()); 164 } 165 166 bool empty() { return List.empty(); } 167 size_t size() { return List.size(); } 168 169 iterator begin() { return iterator(List.begin()); } 170 iterator end() { return iterator(List.end()); } 171 const_iterator begin() const { return const_iterator(List.begin()); } 172 const_iterator end() const { return const_iterator(List.end()); } 173 reverse_iterator rbegin() { return reverse_iterator(List.rbegin()); } 174 reverse_iterator rend() { return reverse_iterator(List.rend()); } 175 const_reverse_iterator rbegin() const { 176 return const_reverse_iterator(List.rbegin()); 177 } 178 const_reverse_iterator rend() const { 179 return const_reverse_iterator(List.rend()); 180 } 181 182 T &back() { return List.back().V; } 183 T &front() { return List.front().V; } 184 const T &back() const { return List.back().V; } 185 const T &front() const { return List.front().V; } 186 187 template <class... Ts> iterator emplace(iterator I, Ts &&... Vs) { 188 return iterator(List.insert(I.wrapped(), *create(std::forward<Ts>(Vs)...))); 189 } 190 191 iterator insert(iterator I, T &&V) { 192 return iterator(List.insert(I.wrapped(), *create(std::move(V)))); 193 } 194 iterator insert(iterator I, const T &V) { 195 return iterator(List.insert(I.wrapped(), *create(V))); 196 } 197 198 template <class Iterator> 199 void insert(iterator I, Iterator First, Iterator Last) { 200 for (; First != Last; ++First) 201 List.insert(I.wrapped(), *create(*First)); 202 } 203 204 iterator erase(iterator I) { 205 return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this))); 206 } 207 208 iterator erase(iterator First, iterator Last) { 209 return iterator( 210 List.eraseAndDispose(First.wrapped(), Last.wrapped(), Disposer(*this))); 211 } 212 213 void clear() { List.clearAndDispose(Disposer(*this)); } 214 void pop_back() { List.eraseAndDispose(--List.end(), Disposer(*this)); } 215 void pop_front() { List.eraseAndDispose(List.begin(), Disposer(*this)); } 216 void push_back(T &&V) { insert(end(), std::move(V)); } 217 void push_front(T &&V) { insert(begin(), std::move(V)); } 218 void push_back(const T &V) { insert(end(), V); } 219 void push_front(const T &V) { insert(begin(), V); } 220 template <class... Ts> void emplace_back(Ts &&... Vs) { 221 emplace(end(), std::forward<Ts>(Vs)...); 222 } 223 template <class... Ts> void emplace_front(Ts &&... Vs) { 224 emplace(begin(), std::forward<Ts>(Vs)...); 225 } 226 227 /// Reset the underlying allocator. 228 /// 229 /// \pre \c empty() 230 void resetAlloc() { 231 assert(empty() && "Cannot reset allocator if not empty"); 232 getAlloc().Reset(); 233 } 234 }; 235 236 template <class T> using BumpPtrList = AllocatorList<T, BumpPtrAllocator>; 237 238 } // end namespace llvm 239 240 #endif // LLVM_ADT_ALLOCATORLIST_H 241