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