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
30namespace 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//   }
40template <typename T>
41class ScopedArenaAllocatorAdapter;
42
43template <typename T>
44using ScopedArenaDeque = std::deque<T, ScopedArenaAllocatorAdapter<T>>;
45
46template <typename T>
47using ScopedArenaQueue = std::queue<T, ScopedArenaDeque<T>>;
48
49template <typename T>
50using ScopedArenaVector = std::vector<T, ScopedArenaAllocatorAdapter<T>>;
51
52template <typename T, typename Comparator = std::less<T>>
53using ScopedArenaSet = std::set<T, Comparator, ScopedArenaAllocatorAdapter<T>>;
54
55template <typename K, typename V, typename Comparator = std::less<K>>
56using ScopedArenaSafeMap =
57    SafeMap<K, V, Comparator, ScopedArenaAllocatorAdapter<std::pair<const K, V>>>;
58
59template <typename K, typename V, class Hash = std::hash<K>, class KeyEqual = std::equal_to<K>>
60using ScopedArenaUnorderedMap =
61    std::unordered_map<K, V, Hash, KeyEqual, ScopedArenaAllocatorAdapter<std::pair<const K, V>>>;
62
63
64// Implementation details below.
65
66template <>
67class 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)
82      : DebugStackReference(arena_allocator),
83        DebugStackIndirectTopRef(arena_allocator),
84        ArenaAllocatorAdapterKind(kind),
85        arena_stack_(arena_allocator->arena_stack_) {
86  }
87  template <typename U>
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
105template <typename T>
106class 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)
125      : DebugStackReference(arena_allocator),
126        DebugStackIndirectTopRef(arena_allocator),
127        ArenaAllocatorAdapterKind(kind),
128        arena_stack_(arena_allocator->arena_stack_) {
129  }
130  template <typename U>
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
141  size_type max_size() const {
142    return static_cast<size_type>(-1) / sizeof(T);
143  }
144
145  pointer address(reference x) const { return &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  }
155  void deallocate(pointer p, size_type n) {
156    UNUSED(p);
157    UNUSED(n);
158    DebugStackIndirectTopRef::CheckTop();
159  }
160
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  }
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
181template <typename T>
182inline bool operator==(const ScopedArenaAllocatorAdapter<T>& lhs,
183                       const ScopedArenaAllocatorAdapter<T>& rhs) {
184  return lhs.arena_stack_ == rhs.arena_stack_;
185}
186
187template <typename T>
188inline bool operator!=(const ScopedArenaAllocatorAdapter<T>& lhs,
189                       const ScopedArenaAllocatorAdapter<T>& rhs) {
190  return !(lhs == rhs);
191}
192
193inline 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