arena_containers.h revision 8081d2b8d7a743729557051d0294e040e61c747a
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_COMPILER_UTILS_ARENA_CONTAINERS_H_ 18#define ART_COMPILER_UTILS_ARENA_CONTAINERS_H_ 19 20#include <deque> 21#include <queue> 22#include <set> 23#include <vector> 24 25#include "utils/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) { } 70 ArenaAllocatorAdapterKindImpl& operator=(const ArenaAllocatorAdapterKindImpl& other) = default; 71 ArenaAllocKind Kind() { return kArenaAllocSTL; } 72}; 73 74template <bool kCount> 75class ArenaAllocatorAdapterKindImpl { 76 public: 77 explicit ArenaAllocatorAdapterKindImpl(ArenaAllocKind kind) : kind_(kind) { } 78 ArenaAllocatorAdapterKindImpl& operator=(const ArenaAllocatorAdapterKindImpl& other) = default; 79 ArenaAllocKind Kind() { return kind_; } 80 81 private: 82 ArenaAllocKind kind_; 83}; 84 85typedef ArenaAllocatorAdapterKindImpl<kArenaAllocatorCountAllocations> ArenaAllocatorAdapterKind; 86 87template <> 88class ArenaAllocatorAdapter<void> 89 : private DebugStackReference, 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 : DebugStackReference(arena_allocator), 103 ArenaAllocatorAdapterKind(kind), 104 arena_allocator_(arena_allocator) { 105 } 106 template <typename U> 107 ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U>& other) 108 : DebugStackReference(other), 109 ArenaAllocatorAdapterKind(other), 110 arena_allocator_(other.arena_allocator_) { 111 } 112 ArenaAllocatorAdapter(const ArenaAllocatorAdapter& other) = default; 113 ArenaAllocatorAdapter& operator=(const ArenaAllocatorAdapter& other) = default; 114 ~ArenaAllocatorAdapter() = default; 115 116 private: 117 ArenaAllocator* arena_allocator_; 118 119 template <typename U> 120 friend class ArenaAllocatorAdapter; 121}; 122 123template <typename T> 124class ArenaAllocatorAdapter : private DebugStackReference, private ArenaAllocatorAdapterKind { 125 public: 126 typedef T value_type; 127 typedef T* pointer; 128 typedef T& reference; 129 typedef const T* const_pointer; 130 typedef const T& const_reference; 131 typedef size_t size_type; 132 typedef ptrdiff_t difference_type; 133 134 template <typename U> 135 struct rebind { 136 typedef ArenaAllocatorAdapter<U> other; 137 }; 138 139 explicit ArenaAllocatorAdapter(ArenaAllocator* arena_allocator, ArenaAllocKind kind) 140 : DebugStackReference(arena_allocator), 141 ArenaAllocatorAdapterKind(kind), 142 arena_allocator_(arena_allocator) { 143 } 144 template <typename U> 145 ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U>& other) 146 : DebugStackReference(other), 147 ArenaAllocatorAdapterKind(other), 148 arena_allocator_(other.arena_allocator_) { 149 } 150 ArenaAllocatorAdapter(const ArenaAllocatorAdapter& other) = default; 151 ArenaAllocatorAdapter& operator=(const ArenaAllocatorAdapter& other) = default; 152 ~ArenaAllocatorAdapter() = default; 153 154 size_type max_size() const { 155 return static_cast<size_type>(-1) / sizeof(T); 156 } 157 158 pointer address(reference x) const { return &x; } 159 const_pointer address(const_reference x) const { return &x; } 160 161 pointer allocate(size_type n, ArenaAllocatorAdapter<void>::pointer hint = nullptr) { 162 DCHECK_LE(n, max_size()); 163 return reinterpret_cast<T*>(arena_allocator_->Alloc(n * sizeof(T), 164 ArenaAllocatorAdapterKind::Kind())); 165 } 166 void deallocate(pointer p, size_type n) { 167 } 168 169 void construct(pointer p, const_reference val) { 170 new (static_cast<void*>(p)) value_type(val); 171 } 172 void destroy(pointer p) { 173 p->~value_type(); 174 } 175 176 private: 177 ArenaAllocator* arena_allocator_; 178 179 template <typename U> 180 friend class ArenaAllocatorAdapter; 181 182 template <typename U> 183 friend bool operator==(const ArenaAllocatorAdapter<U>& lhs, 184 const ArenaAllocatorAdapter<U>& rhs); 185}; 186 187template <typename T> 188inline bool operator==(const ArenaAllocatorAdapter<T>& lhs, 189 const ArenaAllocatorAdapter<T>& rhs) { 190 return lhs.arena_allocator_ == rhs.arena_allocator_; 191} 192 193template <typename T> 194inline bool operator!=(const ArenaAllocatorAdapter<T>& lhs, 195 const ArenaAllocatorAdapter<T>& rhs) { 196 return !(lhs == rhs); 197} 198 199inline ArenaAllocatorAdapter<void> ArenaAllocator::Adapter(ArenaAllocKind kind) { 200 return ArenaAllocatorAdapter<void>(this, kind); 201} 202 203} // namespace art 204 205#endif // ART_COMPILER_UTILS_ARENA_CONTAINERS_H_ 206