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