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