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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
|
// Copyright 2018 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_CHECKED_ITERATORS_H_
#define BASE_CONTAINERS_CHECKED_ITERATORS_H_
#include <iterator>
#include <memory>
#include <type_traits>
#include "base/check_op.h"
#include "base/containers/util.h"
namespace base {
template <typename T>
class CheckedContiguousIterator {
public:
using difference_type = std::ptrdiff_t;
using value_type = std::remove_cv_t<T>;
using pointer = T*;
using reference = T&;
using iterator_category = std::random_access_iterator_tag;
// Required for converting constructor below.
template <typename U>
friend class CheckedContiguousIterator;
constexpr CheckedContiguousIterator() = default;
#if defined(_LIBCPP_VERSION)
// The following using declaration, single argument implicit constructor and
// friended `__unwrap_iter` overload are required to use an optimized code
// path when using a CheckedContiguousIterator with libc++ algorithms such as
// std::copy(first, last, result), std::copy_backward(first, last, result),
// std::move(first, last, result) and std::move_backward(first, last, result).
//
// Each of these algorithms dispatches to a std::memmove if this is safe to do
// so, i.e. when all of `first`, `last` and `result` are iterators over
// contiguous storage of the same type modulo const qualifiers.
//
// libc++ implements this for its contiguous iterators by invoking the
// unqualified __unwrap_iter, which returns the underlying pointer for
// iterators over std::vector and std::string, and returns the original
// iterator otherwise.
//
// Thus in order to opt into this optimization for CCI, we need to provide our
// own __unwrap_iter, returning the underlying raw pointer if it is safe to do
// so.
//
// Furthermore, considering that std::copy is implemented as follows, the
// return type of __unwrap_iter(CCI) needs to be convertible to CCI, which is
// why an appropriate implicit single argument constructor is provided for the
// optimized case:
//
// template <class InIter, class OutIter>
// OutIter copy(InIter first, InIter last, OutIter result) {
// return __copy(__unwrap_iter(first), __unwrap_iter(last),
// __unwrap_iter(result));
// }
//
// Unoptimized __copy() signature:
// template <class InIter, class OutIter>
// OutIter __copy(InIter first, InIter last, OutIter result);
//
// Optimized __copy() signature:
// template <class T, class U>
// U* __copy(T* first, T* last, U* result);
//
// Finally, this single argument constructor sets all internal fields to the
// passed in pointer. This allows the resulting CCI to be used in other
// optimized calls to std::copy (or std::move, std::copy_backward,
// std::move_backward). However, it should not be used otherwise, since
// invoking any of its public API will result in a CHECK failure. This also
// means that callers should never use the single argument constructor
// directly.
template <typename U>
using PtrIfSafeToMemmove = std::enable_if_t<
std::is_trivially_copy_assignable<std::remove_const_t<U>>::value,
U*>;
template <int&... ExplicitArgumentBarrier, typename U = T>
constexpr CheckedContiguousIterator(PtrIfSafeToMemmove<U> ptr)
: start_(ptr), current_(ptr), end_(ptr) {}
template <int&... ExplicitArgumentBarrier, typename U = T>
friend constexpr PtrIfSafeToMemmove<U> __unwrap_iter(
CheckedContiguousIterator iter) {
return iter.current_;
}
#endif
constexpr CheckedContiguousIterator(T* start, const T* end)
: CheckedContiguousIterator(start, start, end) {}
constexpr CheckedContiguousIterator(const T* start, T* current, const T* end)
: start_(start), current_(current), end_(end) {
CHECK_LE(start, current);
CHECK_LE(current, end);
}
constexpr CheckedContiguousIterator(const CheckedContiguousIterator& other) =
default;
// Converting constructor allowing conversions like CCI<T> to CCI<const T>,
// but disallowing CCI<const T> to CCI<T> or CCI<Derived> to CCI<Base>, which
// are unsafe. Furthermore, this is the same condition as used by the
// converting constructors of std::span<T> and std::unique_ptr<T[]>.
// See https://wg21.link/n4042 for details.
template <
typename U,
std::enable_if_t<std::is_convertible<U (*)[], T (*)[]>::value>* = nullptr>
constexpr CheckedContiguousIterator(const CheckedContiguousIterator<U>& other)
: start_(other.start_), current_(other.current_), end_(other.end_) {
// We explicitly don't delegate to the 3-argument constructor here. Its
// CHECKs would be redundant, since we expect |other| to maintain its own
// invariant. However, DCHECKs never hurt anybody. Presumably.
DCHECK_LE(other.start_, other.current_);
DCHECK_LE(other.current_, other.end_);
}
~CheckedContiguousIterator() = default;
constexpr CheckedContiguousIterator& operator=(
const CheckedContiguousIterator& other) = default;
friend constexpr bool operator==(const CheckedContiguousIterator& lhs,
const CheckedContiguousIterator& rhs) {
lhs.CheckComparable(rhs);
return lhs.current_ == rhs.current_;
}
friend constexpr bool operator!=(const CheckedContiguousIterator& lhs,
const CheckedContiguousIterator& rhs) {
lhs.CheckComparable(rhs);
return lhs.current_ != rhs.current_;
}
friend constexpr bool operator<(const CheckedContiguousIterator& lhs,
const CheckedContiguousIterator& rhs) {
lhs.CheckComparable(rhs);
return lhs.current_ < rhs.current_;
}
friend constexpr bool operator<=(const CheckedContiguousIterator& lhs,
const CheckedContiguousIterator& rhs) {
lhs.CheckComparable(rhs);
return lhs.current_ <= rhs.current_;
}
friend constexpr bool operator>(const CheckedContiguousIterator& lhs,
const CheckedContiguousIterator& rhs) {
lhs.CheckComparable(rhs);
return lhs.current_ > rhs.current_;
}
friend constexpr bool operator>=(const CheckedContiguousIterator& lhs,
const CheckedContiguousIterator& rhs) {
lhs.CheckComparable(rhs);
return lhs.current_ >= rhs.current_;
}
constexpr CheckedContiguousIterator& operator++() {
CHECK_NE(current_, end_);
++current_;
return *this;
}
constexpr CheckedContiguousIterator operator++(int) {
CheckedContiguousIterator old = *this;
++*this;
return old;
}
constexpr CheckedContiguousIterator& operator--() {
CHECK_NE(current_, start_);
--current_;
return *this;
}
constexpr CheckedContiguousIterator operator--(int) {
CheckedContiguousIterator old = *this;
--*this;
return old;
}
constexpr CheckedContiguousIterator& operator+=(difference_type rhs) {
if (rhs > 0) {
CHECK_LE(rhs, end_ - current_);
} else {
CHECK_LE(-rhs, current_ - start_);
}
current_ += rhs;
return *this;
}
constexpr CheckedContiguousIterator operator+(difference_type rhs) const {
CheckedContiguousIterator it = *this;
it += rhs;
return it;
}
constexpr CheckedContiguousIterator& operator-=(difference_type rhs) {
if (rhs < 0) {
CHECK_LE(-rhs, end_ - current_);
} else {
CHECK_LE(rhs, current_ - start_);
}
current_ -= rhs;
return *this;
}
constexpr CheckedContiguousIterator operator-(difference_type rhs) const {
CheckedContiguousIterator it = *this;
it -= rhs;
return it;
}
constexpr friend difference_type operator-(
const CheckedContiguousIterator& lhs,
const CheckedContiguousIterator& rhs) {
lhs.CheckComparable(rhs);
return lhs.current_ - rhs.current_;
}
constexpr reference operator*() const {
CHECK_NE(current_, end_);
return *current_;
}
constexpr pointer operator->() const {
CHECK_NE(current_, end_);
return current_;
}
constexpr reference operator[](difference_type rhs) const {
CHECK_GE(rhs, 0);
CHECK_LT(rhs, end_ - current_);
return current_[rhs];
}
static bool IsRangeMoveSafe(const CheckedContiguousIterator& from_begin,
const CheckedContiguousIterator& from_end,
const CheckedContiguousIterator& to)
WARN_UNUSED_RESULT {
if (from_end < from_begin)
return false;
const auto from_begin_uintptr = get_uintptr(from_begin.current_);
const auto from_end_uintptr = get_uintptr(from_end.current_);
const auto to_begin_uintptr = get_uintptr(to.current_);
const auto to_end_uintptr =
get_uintptr((to + std::distance(from_begin, from_end)).current_);
return to_begin_uintptr >= from_end_uintptr ||
to_end_uintptr <= from_begin_uintptr;
}
private:
constexpr void CheckComparable(const CheckedContiguousIterator& other) const {
CHECK_EQ(start_, other.start_);
CHECK_EQ(end_, other.end_);
}
const T* start_ = nullptr;
T* current_ = nullptr;
const T* end_ = nullptr;
};
template <typename T>
using CheckedContiguousConstIterator = CheckedContiguousIterator<const T>;
} // namespace base
#endif // BASE_CONTAINERS_CHECKED_ITERATORS_H_
|