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