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