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