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