xref: /aosp_15_r20/external/cronet/base/containers/vector_buffer.h (revision 6777b5387eb2ff775bb5750e3f5d96f37fb7352b)
1 // Copyright 2017 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #ifndef BASE_CONTAINERS_VECTOR_BUFFER_H_
6 #define BASE_CONTAINERS_VECTOR_BUFFER_H_
7 
8 #include <stdlib.h>
9 #include <string.h>
10 
11 #include <type_traits>
12 #include <utility>
13 
14 #include "base/check.h"
15 #include "base/check_op.h"
16 #include "base/compiler_specific.h"
17 #include "base/containers/util.h"
18 #include "base/memory/raw_ptr_exclusion.h"
19 #include "base/numerics/checked_math.h"
20 
21 namespace base::internal {
22 
23 // Internal implementation detail of base/containers.
24 //
25 // Implements a vector-like buffer that holds a certain capacity of T. Unlike
26 // std::vector, VectorBuffer never constructs or destructs its arguments, and
27 // can't change sizes. But it does implement templates to assist in efficient
28 // moving and destruction of those items manually.
29 //
30 // In particular, the destructor function does not iterate over the items if
31 // there is no destructor. Moves should be implemented as a memcpy/memmove for
32 // trivially copyable objects (POD) otherwise, it should be a std::move if
33 // possible, and as a last resort it falls back to a copy. This behavior is
34 // similar to std::vector.
35 //
36 // No special consideration is done for noexcept move constructors since
37 // we compile without exceptions.
38 //
39 // The current API does not support moving overlapping ranges.
40 template <typename T>
41 class VectorBuffer {
42  public:
43   constexpr VectorBuffer() = default;
44 
45 #if defined(__clang__) && !defined(__native_client__)
46   // This constructor converts an uninitialized void* to a T* which triggers
47   // clang Control Flow Integrity. Since this is as-designed, disable.
48   __attribute__((no_sanitize("cfi-unrelated-cast", "vptr")))
49 #endif
VectorBuffer(size_t count)50   VectorBuffer(size_t count)
51       : buffer_(reinterpret_cast<T*>(
52             malloc(CheckMul(sizeof(T), count).ValueOrDie()))),
53         capacity_(count) {
54   }
VectorBuffer(VectorBuffer && other)55   VectorBuffer(VectorBuffer&& other) noexcept
56       : buffer_(other.buffer_), capacity_(other.capacity_) {
57     other.buffer_ = nullptr;
58     other.capacity_ = 0;
59   }
60 
61   VectorBuffer(const VectorBuffer&) = delete;
62   VectorBuffer& operator=(const VectorBuffer&) = delete;
63 
~VectorBuffer()64   ~VectorBuffer() { free(buffer_); }
65 
66   VectorBuffer& operator=(VectorBuffer&& other) {
67     free(buffer_);
68     buffer_ = other.buffer_;
69     capacity_ = other.capacity_;
70 
71     other.buffer_ = nullptr;
72     other.capacity_ = 0;
73     return *this;
74   }
75 
capacity()76   size_t capacity() const { return capacity_; }
77 
78   T& operator[](size_t i) {
79     // TODO(crbug.com/817982): Some call sites (at least circular_deque.h) are
80     // calling this with `i == capacity_` as a way of getting `end()`. Therefore
81     // we have to allow this for now (`i <= capacity_`), until we fix those call
82     // sites to use real iterators. This comment applies here and to `const T&
83     // operator[]`, below.
84     CHECK_LE(i, capacity_);
85     return buffer_[i];
86   }
87 
88   const T& operator[](size_t i) const {
89     CHECK_LE(i, capacity_);
90     return buffer_[i];
91   }
92 
begin()93   T* begin() { return buffer_; }
end()94   T* end() { return &buffer_[capacity_]; }
95 
96   // DestructRange ------------------------------------------------------------
97 
DestructRange(T * begin,T * end)98   void DestructRange(T* begin, T* end) {
99     // Trivially destructible objects need not have their destructors called.
100     if constexpr (!std::is_trivially_destructible_v<T>) {
101       CHECK_LE(begin, end);
102       while (begin != end) {
103         begin->~T();
104         begin++;
105       }
106     }
107   }
108 
109   // MoveRange ----------------------------------------------------------------
110   //
111   // The destructor will be called (as necessary) for all moved types. The
112   // ranges must not overlap.
113   //
114   // The parameters and begin and end (one past the last) of the input buffer,
115   // and the address of the first element to copy to. There must be sufficient
116   // room in the destination for all items in the range [begin, end).
117 
118   // Trivially copyable types can use memcpy. Trivially copyable implies
119   // that there is a trivial destructor as we don't have to call it.
120 
121   // Trivially relocatable types can also use memcpy. Trivially relocatable
122   // imples that memcpy is equivalent to move + destroy.
123 
124   template <typename T2>
125   static inline constexpr bool is_trivially_copyable_or_relocatable =
126       std::is_trivially_copyable_v<T2> || IS_TRIVIALLY_RELOCATABLE(T2);
127 
MoveRange(T * from_begin,T * from_end,T * to)128   static void MoveRange(T* from_begin, T* from_end, T* to) {
129     CHECK(!RangesOverlap(from_begin, from_end, to));
130 
131     if constexpr (is_trivially_copyable_or_relocatable<T>) {
132       memcpy(to, from_begin,
133              CheckSub(get_uintptr(from_end), get_uintptr(from_begin))
134                  .ValueOrDie());
135     } else {
136       while (from_begin != from_end) {
137         if constexpr (std::move_constructible<T>) {
138           new (to) T(std::move(*from_begin));
139         } else {
140           new (to) T(*from_begin);
141         }
142         from_begin->~T();
143         from_begin++;
144         to++;
145       }
146     }
147   }
148 
149  private:
RangesOverlap(const T * from_begin,const T * from_end,const T * to)150   static bool RangesOverlap(const T* from_begin,
151                             const T* from_end,
152                             const T* to) {
153     const auto from_begin_uintptr = get_uintptr(from_begin);
154     const auto from_end_uintptr = get_uintptr(from_end);
155     const auto to_uintptr = get_uintptr(to);
156     return !(
157         to >= from_end ||
158         CheckAdd(to_uintptr, CheckSub(from_end_uintptr, from_begin_uintptr))
159                 .ValueOrDie() <= from_begin_uintptr);
160   }
161 
162   // `buffer_` is not a raw_ptr<...> for performance reasons (based on analysis
163   // of sampling profiler data and tab_search:top100:2020).
164   RAW_PTR_EXCLUSION T* buffer_ = nullptr;
165   size_t capacity_ = 0;
166 };
167 
168 }  // namespace base::internal
169 
170 #endif  // BASE_CONTAINERS_VECTOR_BUFFER_H_
171