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