vector_buffer.h 6.6 KB

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