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