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