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
16namespace base {
17namespace 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.
36template <typename T>
37class 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
46  VectorBuffer(size_t count)
47      : buffer_(reinterpret_cast<T*>(malloc(sizeof(T) * count))),
48        capacity_(count) {
49  }
50  VectorBuffer(VectorBuffer&& other) noexcept
51      : buffer_(other.buffer_), capacity_(other.capacity_) {
52    other.buffer_ = nullptr;
53    other.capacity_ = 0;
54  }
55
56  ~VectorBuffer() { free(buffer_); }
57
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
68  size_t capacity() const { return capacity_; }
69
70  T& operator[](size_t i) { return buffer_[i]; }
71  const T& operator[](size_t i) const { return buffer_[i]; }
72  T* begin() { return buffer_; }
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>
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>
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>
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>
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>
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:
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