1 /*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef ART_LIBARTBASE_BASE_ARENA_CONTAINERS_H_
18 #define ART_LIBARTBASE_BASE_ARENA_CONTAINERS_H_
19
20 #include <deque>
21 #include <forward_list>
22 #include <queue>
23 #include <set>
24 #include <stack>
25 #include <unordered_map>
26 #include <utility>
27
28 #include "arena_allocator.h"
29 #include "dchecked_vector.h"
30 #include "hash_map.h"
31 #include "hash_set.h"
32 #include "safe_map.h"
33
34 namespace art {
35
36 // Adapter for use of ArenaAllocator in STL containers.
37 // Use ArenaAllocator::Adapter() to create an adapter to pass to container constructors.
38 // For example,
39 // struct Foo {
40 // explicit Foo(ArenaAllocator* allocator)
41 // : foo_vector(allocator->Adapter(kArenaAllocMisc)),
42 // foo_map(std::less<int>(), allocator->Adapter()) {
43 // }
44 // ArenaVector<int> foo_vector;
45 // ArenaSafeMap<int, int> foo_map;
46 // };
47 template <typename T>
48 class ArenaAllocatorAdapter;
49
50 template <typename T>
51 using ArenaDeque = std::deque<T, ArenaAllocatorAdapter<T>>;
52
53 template <typename T>
54 using ArenaForwardList = std::forward_list<T, ArenaAllocatorAdapter<T>>;
55
56 template <typename T>
57 using ArenaQueue = std::queue<T, ArenaDeque<T>>;
58
59 template <typename T>
60 using ArenaVector = dchecked_vector<T, ArenaAllocatorAdapter<T>>;
61
62 template <typename T, typename Comparator = std::less<T>>
63 using ArenaPriorityQueue = std::priority_queue<T, ArenaVector<T>, Comparator>;
64
65 template <typename T>
66 using ArenaStdStack = std::stack<T, ArenaDeque<T>>;
67
68 template <typename T, typename Comparator = std::less<T>>
69 using ArenaSet = std::set<T, Comparator, ArenaAllocatorAdapter<T>>;
70
71 template <typename K, typename V, typename Comparator = std::less<K>>
72 using ArenaSafeMap =
73 SafeMap<K, V, Comparator, ArenaAllocatorAdapter<std::pair<const K, V>>>;
74
75 template <typename T,
76 typename EmptyFn = DefaultEmptyFn<T>,
77 typename HashFn = DefaultHashFn<T>,
78 typename Pred = DefaultPred<T>>
79 using ArenaHashSet = HashSet<T, EmptyFn, HashFn, Pred, ArenaAllocatorAdapter<T>>;
80
81 template <typename Key,
82 typename Value,
83 typename EmptyFn = DefaultEmptyFn<std::pair<Key, Value>>,
84 typename HashFn = DefaultHashFn<Key>,
85 typename Pred = DefaultPred<Key>>
86 using ArenaHashMap = HashMap<Key,
87 Value,
88 EmptyFn,
89 HashFn,
90 Pred,
91 ArenaAllocatorAdapter<std::pair<Key, Value>>>;
92
93 template <typename Key,
94 typename Value,
95 typename Hash = std::hash<Key>,
96 typename Pred = std::equal_to<Value>>
97 using ArenaUnorderedMap = std::unordered_map<Key,
98 Value,
99 Hash,
100 Pred,
101 ArenaAllocatorAdapter<std::pair<const Key, Value>>>;
102
103 // Implementation details below.
104
105 template <bool kCount>
106 class ArenaAllocatorAdapterKindImpl;
107
108 template <>
109 class ArenaAllocatorAdapterKindImpl<false> {
110 public:
111 // Not tracking allocations, ignore the supplied kind and arbitrarily provide kArenaAllocSTL.
ArenaAllocatorAdapterKindImpl(ArenaAllocKind kind ATTRIBUTE_UNUSED)112 explicit ArenaAllocatorAdapterKindImpl(ArenaAllocKind kind ATTRIBUTE_UNUSED) {}
113 ArenaAllocatorAdapterKindImpl(const ArenaAllocatorAdapterKindImpl&) = default;
114 ArenaAllocatorAdapterKindImpl& operator=(const ArenaAllocatorAdapterKindImpl&) = default;
Kind()115 ArenaAllocKind Kind() { return kArenaAllocSTL; }
116 };
117
118 template <bool kCount>
119 class ArenaAllocatorAdapterKindImpl {
120 public:
ArenaAllocatorAdapterKindImpl(ArenaAllocKind kind)121 explicit ArenaAllocatorAdapterKindImpl(ArenaAllocKind kind) : kind_(kind) { }
122 ArenaAllocatorAdapterKindImpl(const ArenaAllocatorAdapterKindImpl&) = default;
123 ArenaAllocatorAdapterKindImpl& operator=(const ArenaAllocatorAdapterKindImpl&) = default;
Kind()124 ArenaAllocKind Kind() { return kind_; }
125
126 private:
127 ArenaAllocKind kind_;
128 };
129
130 using ArenaAllocatorAdapterKind = ArenaAllocatorAdapterKindImpl<kArenaAllocatorCountAllocations>;
131
132 template <>
133 class ArenaAllocatorAdapter<void> : private ArenaAllocatorAdapterKind {
134 public:
135 using value_type = void;
136 using pointer = void*;
137 using const_pointer = const void*;
138
139 template <typename U>
140 struct rebind {
141 using other = ArenaAllocatorAdapter<U>;
142 };
143
144 explicit ArenaAllocatorAdapter(ArenaAllocator* allocator,
145 ArenaAllocKind kind = kArenaAllocSTL)
ArenaAllocatorAdapterKind(kind)146 : ArenaAllocatorAdapterKind(kind),
147 allocator_(allocator) {
148 }
149 template <typename U>
ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U> & other)150 ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U>& other)
151 : ArenaAllocatorAdapterKind(other),
152 allocator_(other.allocator_) {
153 }
154 ArenaAllocatorAdapter(const ArenaAllocatorAdapter&) = default;
155 ArenaAllocatorAdapter& operator=(const ArenaAllocatorAdapter&) = default;
156 ~ArenaAllocatorAdapter() = default;
157
158 private:
159 ArenaAllocator* allocator_;
160
161 template <typename U>
162 friend class ArenaAllocatorAdapter;
163 };
164
165 template <typename T>
166 class ArenaAllocatorAdapter : private ArenaAllocatorAdapterKind {
167 public:
168 using value_type = T;
169 using pointer = T*;
170 using reference = T&;
171 using const_pointer = const T*;
172 using const_reference = const T&;
173 using size_type = size_t;
174 using difference_type = ptrdiff_t;
175
176 template <typename U>
177 struct rebind {
178 using other = ArenaAllocatorAdapter<U>;
179 };
180
ArenaAllocatorAdapter(ArenaAllocator * allocator,ArenaAllocKind kind)181 ArenaAllocatorAdapter(ArenaAllocator* allocator, ArenaAllocKind kind)
182 : ArenaAllocatorAdapterKind(kind),
183 allocator_(allocator) {
184 }
185 template <typename U>
ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U> & other)186 ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U>& other)
187 : ArenaAllocatorAdapterKind(other),
188 allocator_(other.allocator_) {
189 }
190 ArenaAllocatorAdapter(const ArenaAllocatorAdapter&) = default;
191 ArenaAllocatorAdapter& operator=(const ArenaAllocatorAdapter&) = default;
192 ~ArenaAllocatorAdapter() = default;
193
max_size()194 size_type max_size() const {
195 return static_cast<size_type>(-1) / sizeof(T);
196 }
197
address(reference x)198 pointer address(reference x) const { return &x; }
address(const_reference x)199 const_pointer address(const_reference x) const { return &x; }
200
201 pointer allocate(size_type n,
202 ArenaAllocatorAdapter<void>::pointer hint ATTRIBUTE_UNUSED = nullptr) {
203 DCHECK_LE(n, max_size());
204 return allocator_->AllocArray<T>(n, ArenaAllocatorAdapterKind::Kind());
205 }
deallocate(pointer p,size_type n)206 void deallocate(pointer p, size_type n) {
207 allocator_->MakeInaccessible(p, sizeof(T) * n);
208 }
209
210 template <typename U, typename... Args>
construct(U * p,Args &&...args)211 void construct(U* p, Args&&... args) {
212 ::new (static_cast<void*>(p)) U(std::forward<Args>(args)...);
213 }
214 template <typename U>
destroy(U * p)215 void destroy(U* p) {
216 p->~U();
217 }
218
219 private:
220 ArenaAllocator* allocator_;
221
222 template <typename U>
223 friend class ArenaAllocatorAdapter;
224
225 template <typename U>
226 friend bool operator==(const ArenaAllocatorAdapter<U>& lhs,
227 const ArenaAllocatorAdapter<U>& rhs);
228 };
229
230 template <typename T>
231 inline bool operator==(const ArenaAllocatorAdapter<T>& lhs,
232 const ArenaAllocatorAdapter<T>& rhs) {
233 return lhs.allocator_ == rhs.allocator_;
234 }
235
236 template <typename T>
237 inline bool operator!=(const ArenaAllocatorAdapter<T>& lhs,
238 const ArenaAllocatorAdapter<T>& rhs) {
239 return !(lhs == rhs);
240 }
241
Adapter(ArenaAllocKind kind)242 inline ArenaAllocatorAdapter<void> ArenaAllocator::Adapter(ArenaAllocKind kind) {
243 return ArenaAllocatorAdapter<void>(this, kind);
244 }
245
246 } // namespace art
247
248 #endif // ART_LIBARTBASE_BASE_ARENA_CONTAINERS_H_
249