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