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_SCOPED_ARENA_CONTAINERS_H_
18 #define ART_RUNTIME_BASE_SCOPED_ARENA_CONTAINERS_H_
19
20 #include <deque>
21 #include <queue>
22 #include <set>
23 #include <unordered_map>
24 #include <vector>
25
26 #include "arena_containers.h" // For ArenaAllocatorAdapterKind.
27 #include "scoped_arena_allocator.h"
28 #include "safe_map.h"
29
30 namespace art {
31
32 // Adapter for use of ScopedArenaAllocator in STL containers.
33 // Use ScopedArenaAllocator::Adapter() to create an adapter to pass to container constructors.
34 // For example,
35 // void foo(ScopedArenaAllocator* allocator) {
36 // ScopedArenaVector<int> foo_vector(allocator->Adapter(kArenaAllocMisc));
37 // ScopedArenaSafeMap<int, int> foo_map(std::less<int>(), allocator->Adapter());
38 // // Use foo_vector and foo_map...
39 // }
40 template <typename T>
41 class ScopedArenaAllocatorAdapter;
42
43 template <typename T>
44 using ScopedArenaDeque = std::deque<T, ScopedArenaAllocatorAdapter<T>>;
45
46 template <typename T>
47 using ScopedArenaQueue = std::queue<T, ScopedArenaDeque<T>>;
48
49 template <typename T>
50 using ScopedArenaVector = std::vector<T, ScopedArenaAllocatorAdapter<T>>;
51
52 template <typename T, typename Comparator = std::less<T>>
53 using ScopedArenaSet = std::set<T, Comparator, ScopedArenaAllocatorAdapter<T>>;
54
55 template <typename K, typename V, typename Comparator = std::less<K>>
56 using ScopedArenaSafeMap =
57 SafeMap<K, V, Comparator, ScopedArenaAllocatorAdapter<std::pair<const K, V>>>;
58
59 template <typename K, typename V, class Hash = std::hash<K>, class KeyEqual = std::equal_to<K>>
60 using ScopedArenaUnorderedMap =
61 std::unordered_map<K, V, Hash, KeyEqual, ScopedArenaAllocatorAdapter<std::pair<const K, V>>>;
62
63
64 // Implementation details below.
65
66 template <>
67 class ScopedArenaAllocatorAdapter<void>
68 : private DebugStackReference, private DebugStackIndirectTopRef,
69 private ArenaAllocatorAdapterKind {
70 public:
71 typedef void value_type;
72 typedef void* pointer;
73 typedef const void* const_pointer;
74
75 template <typename U>
76 struct rebind {
77 typedef ScopedArenaAllocatorAdapter<U> other;
78 };
79
80 explicit ScopedArenaAllocatorAdapter(ScopedArenaAllocator* arena_allocator,
81 ArenaAllocKind kind = kArenaAllocSTL)
DebugStackReference(arena_allocator)82 : DebugStackReference(arena_allocator),
83 DebugStackIndirectTopRef(arena_allocator),
84 ArenaAllocatorAdapterKind(kind),
85 arena_stack_(arena_allocator->arena_stack_) {
86 }
87 template <typename U>
ScopedArenaAllocatorAdapter(const ScopedArenaAllocatorAdapter<U> & other)88 ScopedArenaAllocatorAdapter(const ScopedArenaAllocatorAdapter<U>& other)
89 : DebugStackReference(other),
90 DebugStackIndirectTopRef(other),
91 ArenaAllocatorAdapterKind(other),
92 arena_stack_(other.arena_stack_) {
93 }
94 ScopedArenaAllocatorAdapter(const ScopedArenaAllocatorAdapter&) = default;
95 ScopedArenaAllocatorAdapter& operator=(const ScopedArenaAllocatorAdapter&) = default;
96 ~ScopedArenaAllocatorAdapter() = default;
97
98 private:
99 ArenaStack* arena_stack_;
100
101 template <typename U>
102 friend class ScopedArenaAllocatorAdapter;
103 };
104
105 template <typename T>
106 class ScopedArenaAllocatorAdapter
107 : private DebugStackReference, private DebugStackIndirectTopRef,
108 private ArenaAllocatorAdapterKind {
109 public:
110 typedef T value_type;
111 typedef T* pointer;
112 typedef T& reference;
113 typedef const T* const_pointer;
114 typedef const T& const_reference;
115 typedef size_t size_type;
116 typedef ptrdiff_t difference_type;
117
118 template <typename U>
119 struct rebind {
120 typedef ScopedArenaAllocatorAdapter<U> other;
121 };
122
123 explicit ScopedArenaAllocatorAdapter(ScopedArenaAllocator* arena_allocator,
124 ArenaAllocKind kind = kArenaAllocSTL)
DebugStackReference(arena_allocator)125 : DebugStackReference(arena_allocator),
126 DebugStackIndirectTopRef(arena_allocator),
127 ArenaAllocatorAdapterKind(kind),
128 arena_stack_(arena_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
max_size()141 size_type max_size() const {
142 return static_cast<size_type>(-1) / sizeof(T);
143 }
144
address(reference x)145 pointer address(reference x) const { return &x; }
address(const_reference x)146 const_pointer address(const_reference x) const { return &x; }
147
148 pointer allocate(size_type n, ScopedArenaAllocatorAdapter<void>::pointer hint = nullptr) {
149 UNUSED(hint);
150 DCHECK_LE(n, max_size());
151 DebugStackIndirectTopRef::CheckTop();
152 return reinterpret_cast<T*>(arena_stack_->Alloc(n * sizeof(T),
153 ArenaAllocatorAdapterKind::Kind()));
154 }
deallocate(pointer p,size_type n)155 void deallocate(pointer p, size_type n) {
156 UNUSED(p);
157 UNUSED(n);
158 DebugStackIndirectTopRef::CheckTop();
159 }
160
construct(pointer p,const_reference val)161 void construct(pointer p, const_reference val) {
162 // Don't CheckTop(), allow reusing existing capacity of a vector/deque below the top.
163 new (static_cast<void*>(p)) value_type(val);
164 }
destroy(pointer p)165 void destroy(pointer p) {
166 // Don't CheckTop(), allow reusing existing capacity of a vector/deque below the top.
167 p->~value_type();
168 }
169
170 private:
171 ArenaStack* arena_stack_;
172
173 template <typename U>
174 friend class ScopedArenaAllocatorAdapter;
175
176 template <typename U>
177 friend bool operator==(const ScopedArenaAllocatorAdapter<U>& lhs,
178 const ScopedArenaAllocatorAdapter<U>& rhs);
179 };
180
181 template <typename T>
182 inline bool operator==(const ScopedArenaAllocatorAdapter<T>& lhs,
183 const ScopedArenaAllocatorAdapter<T>& rhs) {
184 return lhs.arena_stack_ == rhs.arena_stack_;
185 }
186
187 template <typename T>
188 inline bool operator!=(const ScopedArenaAllocatorAdapter<T>& lhs,
189 const ScopedArenaAllocatorAdapter<T>& rhs) {
190 return !(lhs == rhs);
191 }
192
Adapter(ArenaAllocKind kind)193 inline ScopedArenaAllocatorAdapter<void> ScopedArenaAllocator::Adapter(ArenaAllocKind kind) {
194 return ScopedArenaAllocatorAdapter<void>(this, kind);
195 }
196
197 } // namespace art
198
199 #endif // ART_RUNTIME_BASE_SCOPED_ARENA_CONTAINERS_H_
200