1 // Copyright 2018 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_CHECKED_ITERATORS_H_ 6 #define BASE_CONTAINERS_CHECKED_ITERATORS_H_ 7 8 #include <iterator> 9 #include <memory> 10 #include <type_traits> 11 12 #include "base/containers/util.h" 13 #include "base/logging.h" 14 15 namespace base { 16 17 template <typename T> 18 class CheckedContiguousIterator { 19 public: 20 using difference_type = std::ptrdiff_t; 21 using value_type = std::remove_cv_t<T>; 22 using pointer = T*; 23 using reference = T&; 24 using iterator_category = std::random_access_iterator_tag; 25 26 // Required for converting constructor below. 27 template <typename U> 28 friend class CheckedContiguousIterator; 29 30 constexpr CheckedContiguousIterator() = default; CheckedContiguousIterator(T * start,const T * end)31 constexpr CheckedContiguousIterator(T* start, const T* end) 32 : CheckedContiguousIterator(start, start, end) {} CheckedContiguousIterator(const T * start,T * current,const T * end)33 constexpr CheckedContiguousIterator(const T* start, T* current, const T* end) 34 : start_(start), current_(current), end_(end) { 35 CHECK_LE(start, current); 36 CHECK_LE(current, end); 37 } 38 constexpr CheckedContiguousIterator(const CheckedContiguousIterator& other) = 39 default; 40 41 // Converting constructor allowing conversions like CCI<T> to CCI<const T>, 42 // but disallowing CCI<const T> to CCI<T> or CCI<Derived> to CCI<Base>, which 43 // are unsafe. Furthermore, this is the same condition as used by the 44 // converting constructors of std::span<T> and std::unique_ptr<T[]>. 45 // See https://wg21.link/n4042 for details. 46 template < 47 typename U, 48 std::enable_if_t<std::is_convertible<U (*)[], T (*)[]>::value>* = nullptr> CheckedContiguousIterator(const CheckedContiguousIterator<U> & other)49 constexpr CheckedContiguousIterator(const CheckedContiguousIterator<U>& other) 50 : start_(other.start_), current_(other.current_), end_(other.end_) { 51 // We explicitly don't delegate to the 3-argument constructor here. Its 52 // CHECKs would be redundant, since we expect |other| to maintain its own 53 // invariant. However, DCHECKs never hurt anybody. Presumably. 54 DCHECK_LE(other.start_, other.current_); 55 DCHECK_LE(other.current_, other.end_); 56 } 57 58 ~CheckedContiguousIterator() = default; 59 60 constexpr CheckedContiguousIterator& operator=( 61 const CheckedContiguousIterator& other) = default; 62 63 constexpr bool operator==(const CheckedContiguousIterator& other) const { 64 CheckComparable(other); 65 return current_ == other.current_; 66 } 67 68 constexpr bool operator!=(const CheckedContiguousIterator& other) const { 69 CheckComparable(other); 70 return current_ != other.current_; 71 } 72 73 constexpr bool operator<(const CheckedContiguousIterator& other) const { 74 CheckComparable(other); 75 return current_ < other.current_; 76 } 77 78 constexpr bool operator<=(const CheckedContiguousIterator& other) const { 79 CheckComparable(other); 80 return current_ <= other.current_; 81 } 82 83 constexpr bool operator>(const CheckedContiguousIterator& other) const { 84 CheckComparable(other); 85 return current_ > other.current_; 86 } 87 88 constexpr bool operator>=(const CheckedContiguousIterator& other) const { 89 CheckComparable(other); 90 return current_ >= other.current_; 91 } 92 93 constexpr CheckedContiguousIterator& operator++() { 94 CHECK_NE(current_, end_); 95 ++current_; 96 return *this; 97 } 98 99 constexpr CheckedContiguousIterator operator++(int) { 100 CheckedContiguousIterator old = *this; 101 ++*this; 102 return old; 103 } 104 105 constexpr CheckedContiguousIterator& operator--() { 106 CHECK_NE(current_, start_); 107 --current_; 108 return *this; 109 } 110 111 constexpr CheckedContiguousIterator operator--(int) { 112 CheckedContiguousIterator old = *this; 113 --*this; 114 return old; 115 } 116 117 constexpr CheckedContiguousIterator& operator+=(difference_type rhs) { 118 if (rhs > 0) { 119 CHECK_LE(rhs, end_ - current_); 120 } else { 121 CHECK_LE(-rhs, current_ - start_); 122 } 123 current_ += rhs; 124 return *this; 125 } 126 127 constexpr CheckedContiguousIterator operator+(difference_type rhs) const { 128 CheckedContiguousIterator it = *this; 129 it += rhs; 130 return it; 131 } 132 133 constexpr CheckedContiguousIterator& operator-=(difference_type rhs) { 134 if (rhs < 0) { 135 CHECK_LE(-rhs, end_ - current_); 136 } else { 137 CHECK_LE(rhs, current_ - start_); 138 } 139 current_ -= rhs; 140 return *this; 141 } 142 143 constexpr CheckedContiguousIterator operator-(difference_type rhs) const { 144 CheckedContiguousIterator it = *this; 145 it -= rhs; 146 return it; 147 } 148 149 constexpr friend difference_type operator-( 150 const CheckedContiguousIterator& lhs, 151 const CheckedContiguousIterator& rhs) { 152 CHECK_EQ(lhs.start_, rhs.start_); 153 CHECK_EQ(lhs.end_, rhs.end_); 154 return lhs.current_ - rhs.current_; 155 } 156 157 constexpr reference operator*() const { 158 CHECK_NE(current_, end_); 159 return *current_; 160 } 161 162 constexpr pointer operator->() const { 163 CHECK_NE(current_, end_); 164 return current_; 165 } 166 167 constexpr reference operator[](difference_type rhs) const { 168 CHECK_GE(rhs, 0); 169 CHECK_LT(rhs, end_ - current_); 170 return current_[rhs]; 171 } 172 IsRangeMoveSafe(const CheckedContiguousIterator & from_begin,const CheckedContiguousIterator & from_end,const CheckedContiguousIterator & to)173 static bool IsRangeMoveSafe(const CheckedContiguousIterator& from_begin, 174 const CheckedContiguousIterator& from_end, 175 const CheckedContiguousIterator& to) 176 WARN_UNUSED_RESULT { 177 if (from_end < from_begin) 178 return false; 179 const auto from_begin_uintptr = get_uintptr(from_begin.current_); 180 const auto from_end_uintptr = get_uintptr(from_end.current_); 181 const auto to_begin_uintptr = get_uintptr(to.current_); 182 const auto to_end_uintptr = 183 get_uintptr((to + std::distance(from_begin, from_end)).current_); 184 185 return to_begin_uintptr >= from_end_uintptr || 186 to_end_uintptr <= from_begin_uintptr; 187 } 188 189 private: CheckComparable(const CheckedContiguousIterator & other)190 constexpr void CheckComparable(const CheckedContiguousIterator& other) const { 191 CHECK_EQ(start_, other.start_); 192 CHECK_EQ(end_, other.end_); 193 } 194 195 const T* start_ = nullptr; 196 T* current_ = nullptr; 197 const T* end_ = nullptr; 198 }; 199 200 template <typename T> 201 using CheckedContiguousConstIterator = CheckedContiguousIterator<const T>; 202 203 } // namespace base 204 205 #endif // BASE_CONTAINERS_CHECKED_ITERATORS_H_ 206