xref: /aosp_15_r20/external/cronet/base/containers/heap_array.h (revision 6777b5387eb2ff775bb5750e3f5d96f37fb7352b)
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