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 28 namespace 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 // }; 41 template <typename T> 42 class ArenaAllocatorAdapter; 43 44 template <typename T> 45 using ArenaDeque = std::deque<T, ArenaAllocatorAdapter<T>>; 46 47 template <typename T> 48 using ArenaQueue = std::queue<T, ArenaDeque<T>>; 49 50 template <typename T> 51 using ArenaVector = std::vector<T, ArenaAllocatorAdapter<T>>; 52 53 template <typename T, typename Comparator = std::less<T>> 54 using ArenaSet = std::set<T, Comparator, ArenaAllocatorAdapter<T>>; 55 56 template <typename K, typename V, typename Comparator = std::less<K>> 57 using ArenaSafeMap = 58 SafeMap<K, V, Comparator, ArenaAllocatorAdapter<std::pair<const K, V>>>; 59 60 // Implementation details below. 61 62 template <bool kCount> 63 class ArenaAllocatorAdapterKindImpl; 64 65 template <> 66 class 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 74 template <bool kCount> 75 class 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 85 typedef ArenaAllocatorAdapterKindImpl<kArenaAllocatorCountAllocations> ArenaAllocatorAdapterKind; 86 87 template <> 88 class 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 123 template <typename T> 124 class 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 187 template <typename T> 188 inline bool operator==(const ArenaAllocatorAdapter<T>& lhs, 189 const ArenaAllocatorAdapter<T>& rhs) { 190 return lhs.arena_allocator_ == rhs.arena_allocator_; 191 } 192 193 template <typename T> 194 inline bool operator!=(const ArenaAllocatorAdapter<T>& lhs, 195 const ArenaAllocatorAdapter<T>& rhs) { 196 return !(lhs == rhs); 197 } 198 199 inline 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
