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