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 <stack>
24#include <unordered_map>
25#include <utility>
26
27#include "arena_allocator.h"
28#include "base/dchecked_vector.h"
29#include "hash_map.h"
30#include "hash_set.h"
31#include "safe_map.h"
32
33namespace 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//   };
46template <typename T>
47class ArenaAllocatorAdapter;
48
49template <typename T>
50using ArenaDeque = std::deque<T, ArenaAllocatorAdapter<T>>;
51
52template <typename T>
53using ArenaQueue = std::queue<T, ArenaDeque<T>>;
54
55template <typename T>
56using ArenaVector = dchecked_vector<T, ArenaAllocatorAdapter<T>>;
57
58template <typename T, typename Comparator = std::less<T>>
59using ArenaPriorityQueue = std::priority_queue<T, ArenaVector<T>, Comparator>;
60
61template <typename T>
62using ArenaStdStack = std::stack<T, ArenaDeque<T>>;
63
64template <typename T, typename Comparator = std::less<T>>
65using ArenaSet = std::set<T, Comparator, ArenaAllocatorAdapter<T>>;
66
67template <typename K, typename V, typename Comparator = std::less<K>>
68using ArenaSafeMap =
69    SafeMap<K, V, Comparator, ArenaAllocatorAdapter<std::pair<const K, V>>>;
70
71template <typename T,
72          typename EmptyFn = DefaultEmptyFn<T>,
73          typename HashFn = std::hash<T>,
74          typename Pred = std::equal_to<T>>
75using ArenaHashSet = HashSet<T, EmptyFn, HashFn, Pred, ArenaAllocatorAdapter<T>>;
76
77template <typename Key,
78          typename Value,
79          typename EmptyFn = DefaultEmptyFn<std::pair<Key, Value>>,
80          typename HashFn = std::hash<Key>,
81          typename Pred = std::equal_to<Key>>
82using ArenaHashMap = HashMap<Key,
83                             Value,
84                             EmptyFn,
85                             HashFn,
86                             Pred,
87                             ArenaAllocatorAdapter<std::pair<Key, Value>>>;
88
89template <typename Key,
90          typename Value,
91          typename Hash = std::hash<Key>,
92          typename Pred = std::equal_to<Value>>
93using ArenaUnorderedMap = std::unordered_map<Key,
94                                             Value,
95                                             Hash,
96                                             Pred,
97                                             ArenaAllocatorAdapter<std::pair<const Key, Value>>>;
98
99// Implementation details below.
100
101template <bool kCount>
102class ArenaAllocatorAdapterKindImpl;
103
104template <>
105class 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
114template <bool kCount>
115class 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
126typedef ArenaAllocatorAdapterKindImpl<kArenaAllocatorCountAllocations> ArenaAllocatorAdapterKind;
127
128template <>
129class 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* arena_allocator,
141                                 ArenaAllocKind kind = kArenaAllocSTL)
142      : ArenaAllocatorAdapterKind(kind),
143        arena_allocator_(arena_allocator) {
144  }
145  template <typename U>
146  ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U>& other)  // NOLINT, implicit
147      : ArenaAllocatorAdapterKind(other),
148        arena_allocator_(other.arena_allocator_) {
149  }
150  ArenaAllocatorAdapter(const ArenaAllocatorAdapter&) = default;
151  ArenaAllocatorAdapter& operator=(const ArenaAllocatorAdapter&) = default;
152  ~ArenaAllocatorAdapter() = default;
153
154 private:
155  ArenaAllocator* arena_allocator_;
156
157  template <typename U>
158  friend class ArenaAllocatorAdapter;
159};
160
161template <typename T>
162class 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* arena_allocator, ArenaAllocKind kind)
178      : ArenaAllocatorAdapterKind(kind),
179        arena_allocator_(arena_allocator) {
180  }
181  template <typename U>
182  ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U>& other)  // NOLINT, implicit
183      : ArenaAllocatorAdapterKind(other),
184        arena_allocator_(other.arena_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 arena_allocator_->AllocArray<T>(n, ArenaAllocatorAdapterKind::Kind());
201  }
202  void deallocate(pointer p, size_type n) {
203    arena_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* arena_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
226template <typename T>
227inline bool operator==(const ArenaAllocatorAdapter<T>& lhs,
228                       const ArenaAllocatorAdapter<T>& rhs) {
229  return lhs.arena_allocator_ == rhs.arena_allocator_;
230}
231
232template <typename T>
233inline bool operator!=(const ArenaAllocatorAdapter<T>& lhs,
234                       const ArenaAllocatorAdapter<T>& rhs) {
235  return !(lhs == rhs);
236}
237
238inline ArenaAllocatorAdapter<void> ArenaAllocator::Adapter(ArenaAllocKind kind) {
239  return ArenaAllocatorAdapter<void>(this, kind);
240}
241
242}  // namespace art
243
244#endif  // ART_RUNTIME_BASE_ARENA_CONTAINERS_H_
245