1*6777b538SAndroid Build Coastguard Worker // Copyright 2024 The Chromium Authors 2*6777b538SAndroid Build Coastguard Worker // Use of this source code is governed by a BSD-style license that can be 3*6777b538SAndroid Build Coastguard Worker // found in the LICENSE file. 4*6777b538SAndroid Build Coastguard Worker 5*6777b538SAndroid Build Coastguard Worker #ifndef BASE_CONTAINERS_HEAP_ARRAY_H_ 6*6777b538SAndroid Build Coastguard Worker #define BASE_CONTAINERS_HEAP_ARRAY_H_ 7*6777b538SAndroid Build Coastguard Worker 8*6777b538SAndroid Build Coastguard Worker #include <stddef.h> 9*6777b538SAndroid Build Coastguard Worker 10*6777b538SAndroid Build Coastguard Worker #include <memory> 11*6777b538SAndroid Build Coastguard Worker #include <type_traits> 12*6777b538SAndroid Build Coastguard Worker #include <utility> 13*6777b538SAndroid Build Coastguard Worker 14*6777b538SAndroid Build Coastguard Worker #include "base/compiler_specific.h" 15*6777b538SAndroid Build Coastguard Worker #include "base/containers/span.h" 16*6777b538SAndroid Build Coastguard Worker #include "third_party/abseil-cpp/absl/base/attributes.h" 17*6777b538SAndroid Build Coastguard Worker 18*6777b538SAndroid Build Coastguard Worker namespace base { 19*6777b538SAndroid Build Coastguard Worker 20*6777b538SAndroid Build Coastguard Worker // HeapArray<T> is a replacement for std::unique_ptr<T[]> that keeps track 21*6777b538SAndroid Build Coastguard Worker // of its size. It is intended to provide easy conversion to span<T> for most 22*6777b538SAndroid Build Coastguard Worker // usage, but it also provides bounds-checked indexing. 23*6777b538SAndroid Build Coastguard Worker // 24*6777b538SAndroid Build Coastguard Worker // By default, elements in the array are either value-initialized (i.e. zeroed 25*6777b538SAndroid Build Coastguard Worker // for primitive types) when the array is created using the WithSize() 26*6777b538SAndroid Build Coastguard Worker // static method, or uninitialized when the array is created via the Uninit() 27*6777b538SAndroid Build Coastguard Worker // static method. 28*6777b538SAndroid Build Coastguard Worker template <typename T, typename Deleter = void> 29*6777b538SAndroid Build Coastguard Worker class TRIVIAL_ABI GSL_OWNER HeapArray { 30*6777b538SAndroid Build Coastguard Worker public: 31*6777b538SAndroid Build Coastguard Worker static_assert(!std::is_const_v<T>, "HeapArray cannot hold const types"); 32*6777b538SAndroid Build Coastguard Worker static_assert(!std::is_reference_v<T>, 33*6777b538SAndroid Build Coastguard Worker "HeapArray cannot hold reference types"); 34*6777b538SAndroid Build Coastguard Worker 35*6777b538SAndroid Build Coastguard Worker using iterator = base::span<T>::iterator; 36*6777b538SAndroid Build Coastguard Worker using const_iterator = base::span<const T>::iterator; 37*6777b538SAndroid Build Coastguard Worker // We don't put this default value in the template parameter list to allow the 38*6777b538SAndroid Build Coastguard Worker // static_assert on is_reference_v to give a nicer error message. 39*6777b538SAndroid Build Coastguard Worker using deleter_type = std:: 40*6777b538SAndroid Build Coastguard Worker conditional_t<std::is_void_v<Deleter>, std::default_delete<T[]>, Deleter>; 41*6777b538SAndroid Build Coastguard Worker 42*6777b538SAndroid Build Coastguard Worker // Allocates initialized memory capable of holding `size` elements. No memory 43*6777b538SAndroid Build Coastguard Worker // is allocated for zero-sized arrays. WithSize(size_t size)44*6777b538SAndroid Build Coastguard Worker static HeapArray WithSize(size_t size) 45*6777b538SAndroid Build Coastguard Worker requires(std::constructible_from<T>) 46*6777b538SAndroid Build Coastguard Worker { 47*6777b538SAndroid Build Coastguard Worker if (!size) { 48*6777b538SAndroid Build Coastguard Worker return HeapArray(); 49*6777b538SAndroid Build Coastguard Worker } 50*6777b538SAndroid Build Coastguard Worker return HeapArray(std::unique_ptr<T[], deleter_type>(new T[size]()), size); 51*6777b538SAndroid Build Coastguard Worker } 52*6777b538SAndroid Build Coastguard Worker 53*6777b538SAndroid Build Coastguard Worker // Allocates uninitialized memory capable of holding `size` elements. T must 54*6777b538SAndroid Build Coastguard Worker // be trivially constructible and destructible. No memory is allocated for 55*6777b538SAndroid Build Coastguard Worker // zero-sized arrays. Uninit(size_t size)56*6777b538SAndroid Build Coastguard Worker static HeapArray Uninit(size_t size) 57*6777b538SAndroid Build Coastguard Worker requires(std::is_trivially_constructible_v<T> && 58*6777b538SAndroid Build Coastguard Worker std::is_trivially_destructible_v<T>) 59*6777b538SAndroid Build Coastguard Worker { 60*6777b538SAndroid Build Coastguard Worker if (!size) { 61*6777b538SAndroid Build Coastguard Worker return HeapArray(); 62*6777b538SAndroid Build Coastguard Worker } 63*6777b538SAndroid Build Coastguard Worker return HeapArray(std::unique_ptr<T[], deleter_type>(new T[size]), size); 64*6777b538SAndroid Build Coastguard Worker } 65*6777b538SAndroid Build Coastguard Worker CopiedFrom(base::span<const T> that)66*6777b538SAndroid Build Coastguard Worker static HeapArray CopiedFrom(base::span<const T> that) { 67*6777b538SAndroid Build Coastguard Worker auto result = HeapArray::Uninit(that.size()); 68*6777b538SAndroid Build Coastguard Worker result.copy_from(that); 69*6777b538SAndroid Build Coastguard Worker return result; 70*6777b538SAndroid Build Coastguard Worker } 71*6777b538SAndroid Build Coastguard Worker 72*6777b538SAndroid Build Coastguard Worker // Constructs a HeapArray from an existing pointer, taking ownership of the 73*6777b538SAndroid Build Coastguard Worker // pointer. 74*6777b538SAndroid Build Coastguard Worker // 75*6777b538SAndroid Build Coastguard Worker // # Safety 76*6777b538SAndroid Build Coastguard Worker // The pointer must be correctly aligned for type `T` and able to be deleted 77*6777b538SAndroid Build Coastguard Worker // through the `deleter_type`, which defaults to the `delete[]` operation. The 78*6777b538SAndroid Build Coastguard Worker // `ptr` must point to an array of at least `size` many elements. If these are 79*6777b538SAndroid Build Coastguard Worker // not met, then Undefined Behaviour can result. 80*6777b538SAndroid Build Coastguard Worker // 81*6777b538SAndroid Build Coastguard Worker // # Checks 82*6777b538SAndroid Build Coastguard Worker // When the `size` is zero, the `ptr` must be null. FromOwningPointer(T * ptr,size_t size)83*6777b538SAndroid Build Coastguard Worker UNSAFE_BUFFER_USAGE static HeapArray FromOwningPointer(T* ptr, size_t size) { 84*6777b538SAndroid Build Coastguard Worker if (!size) { 85*6777b538SAndroid Build Coastguard Worker CHECK_EQ(ptr, nullptr); 86*6777b538SAndroid Build Coastguard Worker return HeapArray(); 87*6777b538SAndroid Build Coastguard Worker } 88*6777b538SAndroid Build Coastguard Worker return HeapArray(std::unique_ptr<T[], deleter_type>(ptr), size); 89*6777b538SAndroid Build Coastguard Worker } 90*6777b538SAndroid Build Coastguard Worker 91*6777b538SAndroid Build Coastguard Worker // Constructs an empty array and does not allocate any memory. 92*6777b538SAndroid Build Coastguard Worker HeapArray() 93*6777b538SAndroid Build Coastguard Worker requires(std::constructible_from<T>) 94*6777b538SAndroid Build Coastguard Worker = default; 95*6777b538SAndroid Build Coastguard Worker 96*6777b538SAndroid Build Coastguard Worker // Move-only type since the memory is owned. 97*6777b538SAndroid Build Coastguard Worker HeapArray(const HeapArray&) = delete; 98*6777b538SAndroid Build Coastguard Worker HeapArray& operator=(const HeapArray&) = delete; 99*6777b538SAndroid Build Coastguard Worker 100*6777b538SAndroid Build Coastguard Worker // Move-construction leaves the moved-from object empty and containing 101*6777b538SAndroid Build Coastguard Worker // no allocated memory. HeapArray(HeapArray && that)102*6777b538SAndroid Build Coastguard Worker HeapArray(HeapArray&& that) 103*6777b538SAndroid Build Coastguard Worker : data_(std::move(that.data_)), size_(std::exchange(that.size_, 0u)) {} 104*6777b538SAndroid Build Coastguard Worker 105*6777b538SAndroid Build Coastguard Worker // Move-assigment leaves the moved-from object empty and containing 106*6777b538SAndroid Build Coastguard Worker // no allocated memory. 107*6777b538SAndroid Build Coastguard Worker HeapArray& operator=(HeapArray&& that) { 108*6777b538SAndroid Build Coastguard Worker data_ = std::move(that.data_); 109*6777b538SAndroid Build Coastguard Worker size_ = std::exchange(that.size_, 0u); 110*6777b538SAndroid Build Coastguard Worker return *this; 111*6777b538SAndroid Build Coastguard Worker } 112*6777b538SAndroid Build Coastguard Worker ~HeapArray() = default; 113*6777b538SAndroid Build Coastguard Worker empty()114*6777b538SAndroid Build Coastguard Worker bool empty() const { return size_ == 0u; } size()115*6777b538SAndroid Build Coastguard Worker size_t size() const { return size_; } 116*6777b538SAndroid Build Coastguard Worker 117*6777b538SAndroid Build Coastguard Worker // Prefer span-based methods below over data() where possible. The data() 118*6777b538SAndroid Build Coastguard Worker // method exists primarily to allow implicit constructions of spans. 119*6777b538SAndroid Build Coastguard Worker // Returns nullptr for a zero-sized (or moved-from) array. data()120*6777b538SAndroid Build Coastguard Worker T* data() ABSL_ATTRIBUTE_LIFETIME_BOUND { return data_.get(); } data()121*6777b538SAndroid Build Coastguard Worker const T* data() const ABSL_ATTRIBUTE_LIFETIME_BOUND { return data_.get(); } 122*6777b538SAndroid Build Coastguard Worker begin()123*6777b538SAndroid Build Coastguard Worker iterator begin() ABSL_ATTRIBUTE_LIFETIME_BOUND { return as_span().begin(); } begin()124*6777b538SAndroid Build Coastguard Worker const_iterator begin() const ABSL_ATTRIBUTE_LIFETIME_BOUND { 125*6777b538SAndroid Build Coastguard Worker return as_span().begin(); 126*6777b538SAndroid Build Coastguard Worker } 127*6777b538SAndroid Build Coastguard Worker end()128*6777b538SAndroid Build Coastguard Worker iterator end() ABSL_ATTRIBUTE_LIFETIME_BOUND { return as_span().end(); } end()129*6777b538SAndroid Build Coastguard Worker const_iterator end() const ABSL_ATTRIBUTE_LIFETIME_BOUND { 130*6777b538SAndroid Build Coastguard Worker return as_span().end(); 131*6777b538SAndroid Build Coastguard Worker } 132*6777b538SAndroid Build Coastguard Worker 133*6777b538SAndroid Build Coastguard Worker T& operator[](size_t idx) ABSL_ATTRIBUTE_LIFETIME_BOUND { 134*6777b538SAndroid Build Coastguard Worker return as_span()[idx]; 135*6777b538SAndroid Build Coastguard Worker } 136*6777b538SAndroid Build Coastguard Worker const T& operator[](size_t idx) const ABSL_ATTRIBUTE_LIFETIME_BOUND { 137*6777b538SAndroid Build Coastguard Worker return as_span()[idx]; 138*6777b538SAndroid Build Coastguard Worker } 139*6777b538SAndroid Build Coastguard Worker 140*6777b538SAndroid Build Coastguard Worker // Access the HeapArray via spans. Note that span<T> is implicilty 141*6777b538SAndroid Build Coastguard Worker // constructible from HeapArray<T>, so an explicit call to .as_span() is 142*6777b538SAndroid Build Coastguard Worker // most useful, say, when the compiler can't deduce a template 143*6777b538SAndroid Build Coastguard Worker // argument type. as_span()144*6777b538SAndroid Build Coastguard Worker base::span<T> as_span() ABSL_ATTRIBUTE_LIFETIME_BOUND { 145*6777b538SAndroid Build Coastguard Worker return base::span<T>(data_.get(), size_); 146*6777b538SAndroid Build Coastguard Worker } as_span()147*6777b538SAndroid Build Coastguard Worker base::span<const T> as_span() const ABSL_ATTRIBUTE_LIFETIME_BOUND { 148*6777b538SAndroid Build Coastguard Worker return base::span<const T>(data_.get(), size_); 149*6777b538SAndroid Build Coastguard Worker } 150*6777b538SAndroid Build Coastguard Worker 151*6777b538SAndroid Build Coastguard Worker // Convenience method to copy the contents of the entire array from a 152*6777b538SAndroid Build Coastguard Worker // span<>. Hard CHECK occurs in span<>::copy_from() if the HeapArray and 153*6777b538SAndroid Build Coastguard Worker // the span have different sizes. copy_from(base::span<const T> other)154*6777b538SAndroid Build Coastguard Worker void copy_from(base::span<const T> other) { as_span().copy_from(other); } 155*6777b538SAndroid Build Coastguard Worker 156*6777b538SAndroid Build Coastguard Worker // Convenience methods to slice the vector into spans. 157*6777b538SAndroid Build Coastguard Worker // Returns a span over the HeapArray starting at `offset` of `count` elements. 158*6777b538SAndroid Build Coastguard Worker // If `count` is unspecified, all remaining elements are included. A CHECK() 159*6777b538SAndroid Build Coastguard Worker // occurs if any of the parameters results in an out-of-range position in 160*6777b538SAndroid Build Coastguard Worker // the HeapArray. 161*6777b538SAndroid Build Coastguard Worker base::span<T> subspan(size_t offset, size_t count = base::dynamic_extent) 162*6777b538SAndroid Build Coastguard Worker ABSL_ATTRIBUTE_LIFETIME_BOUND { 163*6777b538SAndroid Build Coastguard Worker return as_span().subspan(offset, count); 164*6777b538SAndroid Build Coastguard Worker } 165*6777b538SAndroid Build Coastguard Worker base::span<const T> subspan(size_t offset, 166*6777b538SAndroid Build Coastguard Worker size_t count = base::dynamic_extent) const 167*6777b538SAndroid Build Coastguard Worker ABSL_ATTRIBUTE_LIFETIME_BOUND { 168*6777b538SAndroid Build Coastguard Worker return as_span().subspan(offset, count); 169*6777b538SAndroid Build Coastguard Worker } 170*6777b538SAndroid Build Coastguard Worker 171*6777b538SAndroid Build Coastguard Worker // Returns a span over the first `count` elements of the HeapArray. A CHECK() 172*6777b538SAndroid Build Coastguard Worker // occurs if the `count` is larger than size of the HeapArray. first(size_t count)173*6777b538SAndroid Build Coastguard Worker base::span<T> first(size_t count) ABSL_ATTRIBUTE_LIFETIME_BOUND { 174*6777b538SAndroid Build Coastguard Worker return as_span().first(count); 175*6777b538SAndroid Build Coastguard Worker } first(size_t count)176*6777b538SAndroid Build Coastguard Worker base::span<const T> first(size_t count) const ABSL_ATTRIBUTE_LIFETIME_BOUND { 177*6777b538SAndroid Build Coastguard Worker return as_span().first(count); 178*6777b538SAndroid Build Coastguard Worker } 179*6777b538SAndroid Build Coastguard Worker 180*6777b538SAndroid Build Coastguard Worker // Returns a span over the last `count` elements of the HeapArray. A CHECK() 181*6777b538SAndroid Build Coastguard Worker // occurs if the `count` is larger than size of the HeapArray. last(size_t count)182*6777b538SAndroid Build Coastguard Worker base::span<T> last(size_t count) ABSL_ATTRIBUTE_LIFETIME_BOUND { 183*6777b538SAndroid Build Coastguard Worker return as_span().last(count); 184*6777b538SAndroid Build Coastguard Worker } last(size_t count)185*6777b538SAndroid Build Coastguard Worker base::span<const T> last(size_t count) const ABSL_ATTRIBUTE_LIFETIME_BOUND { 186*6777b538SAndroid Build Coastguard Worker return as_span().last(count); 187*6777b538SAndroid Build Coastguard Worker } 188*6777b538SAndroid Build Coastguard Worker 189*6777b538SAndroid Build Coastguard Worker // Leaks the memory in the HeapArray so that it will never be freed, and 190*6777b538SAndroid Build Coastguard Worker // consumes the HeapArray, returning an unowning span that points to the 191*6777b538SAndroid Build Coastguard Worker // memory. leak()192*6777b538SAndroid Build Coastguard Worker base::span<T> leak() && { 193*6777b538SAndroid Build Coastguard Worker HeapArray<T> dropped = std::move(*this); 194*6777b538SAndroid Build Coastguard Worker T* leaked = dropped.data_.release(); 195*6777b538SAndroid Build Coastguard Worker return make_span(leaked, dropped.size_); 196*6777b538SAndroid Build Coastguard Worker } 197*6777b538SAndroid Build Coastguard Worker 198*6777b538SAndroid Build Coastguard Worker // Delete the memory previously obtained from leak(). Argument is a pointer 199*6777b538SAndroid Build Coastguard Worker // rather than a span to facilitate use by callers that have lost track of 200*6777b538SAndroid Build Coastguard Worker // size information, as may happen when being passed through a C-style 201*6777b538SAndroid Build Coastguard Worker // function callback. The void* argument type makes its signature compatible 202*6777b538SAndroid Build Coastguard Worker // with typical void (*cb)(void*) C-style deletion callback. DeleteLeakedData(void * ptr)203*6777b538SAndroid Build Coastguard Worker static void DeleteLeakedData(void* ptr) { 204*6777b538SAndroid Build Coastguard Worker // Memory is freed by unique ptr going out of scope. 205*6777b538SAndroid Build Coastguard Worker std::unique_ptr<T[], deleter_type> deleter(static_cast<T*>(ptr)); 206*6777b538SAndroid Build Coastguard Worker } 207*6777b538SAndroid Build Coastguard Worker 208*6777b538SAndroid Build Coastguard Worker private: HeapArray(std::unique_ptr<T[],deleter_type> data,size_t size)209*6777b538SAndroid Build Coastguard Worker HeapArray(std::unique_ptr<T[], deleter_type> data, size_t size) 210*6777b538SAndroid Build Coastguard Worker : data_(std::move(data)), size_(size) {} 211*6777b538SAndroid Build Coastguard Worker 212*6777b538SAndroid Build Coastguard Worker std::unique_ptr<T[], deleter_type> data_; 213*6777b538SAndroid Build Coastguard Worker size_t size_ = 0u; 214*6777b538SAndroid Build Coastguard Worker }; 215*6777b538SAndroid Build Coastguard Worker 216*6777b538SAndroid Build Coastguard Worker } // namespace base 217*6777b538SAndroid Build Coastguard Worker 218*6777b538SAndroid Build Coastguard Worker #endif // BASE_CONTAINERS_HEAP_ARRAY_H_ 219