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