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