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 NodeNode41 Node(T &&V) : V(std::move(V)) {} NodeNode42 Node(const T &V) : V(V) {} NodeNode43 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 getAlloc()51 AllocatorT &getAlloc() { return *this; } getAlloc()52 const AllocatorT &getAlloc() const { return *this; } 53 create(ArgTs &&...Args)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 ClonerCloner61 Cloner(AllocatorList &AL) : AL(AL) {} 62 operatorCloner63 Node *operator()(const Node &N) const { return AL.create(N.V); } 64 }; 65 66 struct Disposer { 67 AllocatorList &AL; 68 DisposerDisposer69 Disposer(AllocatorList &AL) : AL(AL) {} 70 operatorDisposer71 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 IteratorImpl(const IteratorBase & I)109 explicit IteratorImpl(const IteratorBase &I) : base_type(I) {} 110 111 template <class OtherValueT, class OtherIteratorBase> 112 IteratorImpl(const IteratorImpl<OtherValueT, OtherIteratorBase> &X, 113 std::enable_if_t<std::is_convertible< 114 OtherIteratorBase, IteratorBase>::value> * = 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 123 public: 124 using iterator = IteratorImpl<T, typename list_type::iterator>; 125 using reverse_iterator = 126 IteratorImpl<T, typename list_type::reverse_iterator>; 127 using const_iterator = 128 IteratorImpl<const T, typename list_type::const_iterator>; 129 using const_reverse_iterator = 130 IteratorImpl<const T, typename list_type::const_reverse_iterator>; 131 132 AllocatorList() = default; AllocatorList(AllocatorList && X)133 AllocatorList(AllocatorList &&X) 134 : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {} 135 AllocatorList(const AllocatorList & X)136 AllocatorList(const AllocatorList &X) { 137 List.cloneFrom(X.List, Cloner(*this), Disposer(*this)); 138 } 139 140 AllocatorList &operator=(AllocatorList &&X) { 141 clear(); // Dispose of current nodes explicitly. 142 List = std::move(X.List); 143 getAlloc() = std::move(X.getAlloc()); 144 return *this; 145 } 146 147 AllocatorList &operator=(const AllocatorList &X) { 148 List.cloneFrom(X.List, Cloner(*this), Disposer(*this)); 149 return *this; 150 } 151 ~AllocatorList()152 ~AllocatorList() { clear(); } 153 swap(AllocatorList & RHS)154 void swap(AllocatorList &RHS) { 155 List.swap(RHS.List); 156 std::swap(getAlloc(), RHS.getAlloc()); 157 } 158 empty()159 bool empty() { return List.empty(); } size()160 size_t size() { return List.size(); } 161 begin()162 iterator begin() { return iterator(List.begin()); } end()163 iterator end() { return iterator(List.end()); } begin()164 const_iterator begin() const { return const_iterator(List.begin()); } end()165 const_iterator end() const { return const_iterator(List.end()); } rbegin()166 reverse_iterator rbegin() { return reverse_iterator(List.rbegin()); } rend()167 reverse_iterator rend() { return reverse_iterator(List.rend()); } rbegin()168 const_reverse_iterator rbegin() const { 169 return const_reverse_iterator(List.rbegin()); 170 } rend()171 const_reverse_iterator rend() const { 172 return const_reverse_iterator(List.rend()); 173 } 174 back()175 T &back() { return List.back().V; } front()176 T &front() { return List.front().V; } back()177 const T &back() const { return List.back().V; } front()178 const T &front() const { return List.front().V; } 179 emplace(iterator I,Ts &&...Vs)180 template <class... Ts> iterator emplace(iterator I, Ts &&... Vs) { 181 return iterator(List.insert(I.wrapped(), *create(std::forward<Ts>(Vs)...))); 182 } 183 insert(iterator I,T && V)184 iterator insert(iterator I, T &&V) { 185 return iterator(List.insert(I.wrapped(), *create(std::move(V)))); 186 } insert(iterator I,const T & V)187 iterator insert(iterator I, const T &V) { 188 return iterator(List.insert(I.wrapped(), *create(V))); 189 } 190 191 template <class Iterator> insert(iterator I,Iterator First,Iterator Last)192 void insert(iterator I, Iterator First, Iterator Last) { 193 for (; First != Last; ++First) 194 List.insert(I.wrapped(), *create(*First)); 195 } 196 erase(iterator I)197 iterator erase(iterator I) { 198 return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this))); 199 } 200 erase(iterator First,iterator Last)201 iterator erase(iterator First, iterator Last) { 202 return iterator( 203 List.eraseAndDispose(First.wrapped(), Last.wrapped(), Disposer(*this))); 204 } 205 clear()206 void clear() { List.clearAndDispose(Disposer(*this)); } pop_back()207 void pop_back() { List.eraseAndDispose(--List.end(), Disposer(*this)); } pop_front()208 void pop_front() { List.eraseAndDispose(List.begin(), Disposer(*this)); } push_back(T && V)209 void push_back(T &&V) { insert(end(), std::move(V)); } push_front(T && V)210 void push_front(T &&V) { insert(begin(), std::move(V)); } push_back(const T & V)211 void push_back(const T &V) { insert(end(), V); } push_front(const T & V)212 void push_front(const T &V) { insert(begin(), V); } emplace_back(Ts &&...Vs)213 template <class... Ts> void emplace_back(Ts &&... Vs) { 214 emplace(end(), std::forward<Ts>(Vs)...); 215 } emplace_front(Ts &&...Vs)216 template <class... Ts> void emplace_front(Ts &&... Vs) { 217 emplace(begin(), std::forward<Ts>(Vs)...); 218 } 219 220 /// Reset the underlying allocator. 221 /// 222 /// \pre \c empty() resetAlloc()223 void resetAlloc() { 224 assert(empty() && "Cannot reset allocator if not empty"); 225 getAlloc().Reset(); 226 } 227 }; 228 229 template <class T> using BumpPtrList = AllocatorList<T, BumpPtrAllocator>; 230 231 } // end namespace llvm 232 233 #endif // LLVM_ADT_ALLOCATORLIST_H 234