1 //===- llvm/ADT/AllocatorList.h - Custom allocator list ---------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_ADT_ALLOCATORLIST_H
11 #define LLVM_ADT_ALLOCATORLIST_H
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"
21 #include <type_traits>
26 /// A linked-list with a custom, local allocator.
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.
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;
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)...) {}
48 using list_type = simple_ilist<Node>;
52 AllocatorT &getAlloc() { return *this; }
53 const AllocatorT &getAlloc() const { return *this; }
55 template <class... ArgTs> Node *create(ArgTs &&... Args) {
56 return new (getAlloc()) Node(std::forward<ArgTs>(Args)...);
62 Cloner(AllocatorList &AL) : AL(AL) {}
64 Node *operator()(const Node &N) const { return AL.create(N.V); }
70 Disposer(AllocatorList &AL) : AL(AL) {}
72 void operator()(Node *N) const {
74 AL.getAlloc().Deallocate(N);
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;
88 template <class ValueT, class IteratorBase>
90 : public iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>,
92 std::bidirectional_iterator_tag, ValueT> {
93 template <class OtherValueT, class OtherIteratorBase>
94 friend class IteratorImpl;
98 iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>, IteratorBase,
99 std::bidirectional_iterator_tag, ValueT>;
102 using value_type = ValueT;
103 using pointer = ValueT *;
104 using reference = ValueT &;
106 IteratorImpl() = default;
107 IteratorImpl(const IteratorImpl &) = default;
108 IteratorImpl &operator=(const IteratorImpl &) = default;
110 explicit IteratorImpl(const IteratorBase &I) : base_type(I) {}
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()) {}
118 ~IteratorImpl() = default;
120 reference operator*() const { return base_type::wrapped()->V; }
121 pointer operator->() const { return &operator*(); }
123 friend bool operator==(const IteratorImpl &L, const IteratorImpl &R) {
124 return L.wrapped() == R.wrapped();
126 friend bool operator!=(const IteratorImpl &L, const IteratorImpl &R) {
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>;
140 AllocatorList() = default;
141 AllocatorList(AllocatorList &&X)
142 : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {}
144 AllocatorList(const AllocatorList &X) {
145 List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
148 AllocatorList &operator=(AllocatorList &&X) {
149 clear(); // Dispose of current nodes explicitly.
150 List = std::move(X.List);
151 getAlloc() = std::move(X.getAlloc());
155 AllocatorList &operator=(const AllocatorList &X) {
156 List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
160 ~AllocatorList() { clear(); }
162 void swap(AllocatorList &RHS) {
164 std::swap(getAlloc(), RHS.getAlloc());
167 bool empty() { return List.empty(); }
168 size_t size() { return List.size(); }
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());
179 const_reverse_iterator rend() const {
180 return const_reverse_iterator(List.rend());
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; }
188 template <class... Ts> iterator emplace(iterator I, Ts &&... Vs) {
189 return iterator(List.insert(I.wrapped(), *create(std::forward<Ts>(Vs)...)));
192 iterator insert(iterator I, T &&V) {
193 return iterator(List.insert(I.wrapped(), *create(std::move(V))));
195 iterator insert(iterator I, const T &V) {
196 return iterator(List.insert(I.wrapped(), *create(V)));
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));
205 iterator erase(iterator I) {
206 return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this)));
209 iterator erase(iterator First, iterator Last) {
211 List.eraseAndDispose(First.wrapped(), Last.wrapped(), Disposer(*this)));
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)...);
224 template <class... Ts> void emplace_front(Ts &&... Vs) {
225 emplace(begin(), std::forward<Ts>(Vs)...);
228 /// Reset the underlying allocator.
232 assert(empty() && "Cannot reset allocator if not empty");
237 template <class T> using BumpPtrList = AllocatorList<T, BumpPtrAllocator>;
239 } // end namespace llvm
241 #endif // LLVM_ADT_ALLOCATORLIST_H