Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2016 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 LIBMEMUNREACHABLE_ALLOCATOR_H_ |
| 18 | #define LIBMEMUNREACHABLE_ALLOCATOR_H_ |
| 19 | |
| 20 | #include <atomic> |
| 21 | #include <cstddef> |
| 22 | #include <functional> |
| 23 | #include <list> |
| 24 | #include <map> |
| 25 | #include <memory> |
| 26 | #include <set> |
Colin Cross | c1228c7 | 2016-03-04 16:36:12 -0800 | [diff] [blame] | 27 | #include <unordered_map> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 28 | #include <unordered_set> |
| 29 | #include <vector> |
| 30 | extern std::atomic<int> heap_count; |
| 31 | |
| 32 | class HeapImpl; |
| 33 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 34 | template <typename T> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 35 | class Allocator; |
| 36 | |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 37 | // Non-templated class that implements wraps HeapImpl to keep |
| 38 | // implementation out of the header file |
| 39 | class Heap { |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 40 | public: |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 41 | Heap(); |
| 42 | ~Heap(); |
| 43 | |
| 44 | // Copy constructor that does not take ownership of impl_ |
| 45 | Heap(const Heap& other) : impl_(other.impl_), owns_impl_(false) {} |
| 46 | |
| 47 | // Assignment disabled |
| 48 | Heap& operator=(const Heap&) = delete; |
| 49 | |
| 50 | // Allocate size bytes |
| 51 | void* allocate(size_t size); |
| 52 | |
| 53 | // Deallocate allocation returned by allocate |
| 54 | void deallocate(void*); |
| 55 | |
| 56 | bool empty(); |
| 57 | |
| 58 | static void deallocate(HeapImpl* impl, void* ptr); |
| 59 | |
| 60 | // Allocate a class of type T |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 61 | template <class T> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 62 | T* allocate() { |
| 63 | return reinterpret_cast<T*>(allocate(sizeof(T))); |
| 64 | } |
| 65 | |
| 66 | // Comparators, copied objects will be equal |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 67 | bool operator==(const Heap& other) const { return impl_ == other.impl_; } |
| 68 | bool operator!=(const Heap& other) const { return !(*this == other); } |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 69 | |
| 70 | // std::unique_ptr wrapper that allocates using allocate and deletes using |
| 71 | // deallocate |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 72 | template <class T> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 73 | using unique_ptr = std::unique_ptr<T, std::function<void(void*)>>; |
| 74 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 75 | template <class T, class... Args> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 76 | unique_ptr<T> make_unique(Args&&... args) { |
| 77 | HeapImpl* impl = impl_; |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 78 | return unique_ptr<T>(new (allocate<T>()) T(std::forward<Args>(args)...), [impl](void* ptr) { |
| 79 | reinterpret_cast<T*>(ptr)->~T(); |
| 80 | deallocate(impl, ptr); |
| 81 | }); |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 82 | } |
| 83 | |
| 84 | // std::unique_ptr wrapper that allocates using allocate and deletes using |
| 85 | // deallocate |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 86 | template <class T> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 87 | using shared_ptr = std::shared_ptr<T>; |
| 88 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 89 | template <class T, class... Args> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 90 | shared_ptr<T> make_shared(Args&&... args); |
| 91 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 92 | protected: |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 93 | HeapImpl* impl_; |
| 94 | bool owns_impl_; |
| 95 | }; |
| 96 | |
| 97 | // STLAllocator implements the std allocator interface on top of a Heap |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 98 | template <typename T> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 99 | class STLAllocator { |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 100 | public: |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 101 | using value_type = T; |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 102 | ~STLAllocator() {} |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 103 | |
| 104 | // Construct an STLAllocator on top of a Heap |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 105 | STLAllocator(const Heap& heap) |
| 106 | : // NOLINT, implicit |
| 107 | heap_(heap) {} |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 108 | |
| 109 | // Rebind an STLAllocator from an another STLAllocator |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 110 | template <typename U> |
| 111 | STLAllocator(const STLAllocator<U>& other) |
| 112 | : // NOLINT, implicit |
| 113 | heap_(other.heap_) {} |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 114 | |
| 115 | STLAllocator(const STLAllocator&) = default; |
| 116 | STLAllocator<T>& operator=(const STLAllocator<T>&) = default; |
| 117 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 118 | T* allocate(std::size_t n) { return reinterpret_cast<T*>(heap_.allocate(n * sizeof(T))); } |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 119 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 120 | void deallocate(T* ptr, std::size_t) { heap_.deallocate(ptr); } |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 121 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 122 | template <typename U> |
| 123 | bool operator==(const STLAllocator<U>& other) const { |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 124 | return heap_ == other.heap_; |
| 125 | } |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 126 | template <typename U> |
| 127 | inline bool operator!=(const STLAllocator<U>& other) const { |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 128 | return !(this == other); |
| 129 | } |
| 130 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 131 | template <typename U> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 132 | friend class STLAllocator; |
| 133 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 134 | protected: |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 135 | Heap heap_; |
| 136 | }; |
| 137 | |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 138 | // Allocator extends STLAllocator with some convenience methods for allocating |
| 139 | // a single object and for constructing unique_ptr and shared_ptr objects with |
| 140 | // appropriate deleters. |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 141 | template <class T> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 142 | class Allocator : public STLAllocator<T> { |
| 143 | public: |
| 144 | ~Allocator() {} |
| 145 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 146 | Allocator(const Heap& other) |
| 147 | : // NOLINT, implicit |
| 148 | STLAllocator<T>(other) {} |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 149 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 150 | template <typename U> |
| 151 | Allocator(const STLAllocator<U>& other) |
| 152 | : // NOLINT, implicit |
| 153 | STLAllocator<T>(other) {} |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 154 | |
| 155 | Allocator(const Allocator&) = default; |
| 156 | Allocator<T>& operator=(const Allocator<T>&) = default; |
| 157 | |
| 158 | using STLAllocator<T>::allocate; |
| 159 | using STLAllocator<T>::deallocate; |
| 160 | using STLAllocator<T>::heap_; |
| 161 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 162 | T* allocate() { return STLAllocator<T>::allocate(1); } |
| 163 | void deallocate(void* ptr) { heap_.deallocate(ptr); } |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 164 | |
| 165 | using shared_ptr = Heap::shared_ptr<T>; |
| 166 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 167 | template <class... Args> |
| 168 | shared_ptr make_shared(Args&&... args) { |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 169 | return heap_.template make_shared<T>(std::forward<Args>(args)...); |
| 170 | } |
| 171 | |
| 172 | using unique_ptr = Heap::unique_ptr<T>; |
| 173 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 174 | template <class... Args> |
| 175 | unique_ptr make_unique(Args&&... args) { |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 176 | return heap_.template make_unique<T>(std::forward<Args>(args)...); |
| 177 | } |
| 178 | }; |
| 179 | |
| 180 | // std::unique_ptr wrapper that allocates using allocate and deletes using |
| 181 | // deallocate. Implemented outside class definition in order to pass |
| 182 | // Allocator<T> to shared_ptr. |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 183 | template <class T, class... Args> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 184 | inline Heap::shared_ptr<T> Heap::make_shared(Args&&... args) { |
| 185 | return std::allocate_shared<T, Allocator<T>, Args...>(Allocator<T>(*this), |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 186 | std::forward<Args>(args)...); |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 187 | } |
| 188 | |
| 189 | namespace allocator { |
| 190 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 191 | template <class T> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 192 | using vector = std::vector<T, Allocator<T>>; |
| 193 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 194 | template <class T> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 195 | using list = std::list<T, Allocator<T>>; |
| 196 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 197 | template <class Key, class T, class Compare = std::less<Key>> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 198 | using map = std::map<Key, T, Compare, Allocator<std::pair<const Key, T>>>; |
| 199 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 200 | template <class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>> |
| 201 | using unordered_map = |
| 202 | std::unordered_map<Key, T, Hash, KeyEqual, Allocator<std::pair<const Key, T>>>; |
Colin Cross | c1228c7 | 2016-03-04 16:36:12 -0800 | [diff] [blame] | 203 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 204 | template <class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 205 | using unordered_set = std::unordered_set<Key, Hash, KeyEqual, Allocator<Key>>; |
| 206 | |
Colin Cross | a83881e | 2017-06-22 10:50:05 -0700 | [diff] [blame^] | 207 | template <class Key, class Compare = std::less<Key>> |
Colin Cross | bcb4ed3 | 2016-01-14 15:35:40 -0800 | [diff] [blame] | 208 | using set = std::set<Key, Compare, Allocator<Key>>; |
| 209 | |
| 210 | using string = std::basic_string<char, std::char_traits<char>, Allocator<char>>; |
| 211 | } |
| 212 | |
| 213 | #endif |