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