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