123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265 |
- // 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"
- #include "build/build_config.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;
- // Required for certain libc++ algorithm optimizations that are not available
- // for NaCl.
- #if defined(_LIBCPP_VERSION) && !BUILDFLAG(IS_NACL)
- template <typename Ptr>
- friend struct std::pointer_traits;
- #endif
- constexpr CheckedContiguousIterator() = default;
- 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];
- }
- [[nodiscard]] static bool IsRangeMoveSafe(
- const CheckedContiguousIterator& from_begin,
- const CheckedContiguousIterator& from_end,
- const CheckedContiguousIterator& to) {
- 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
- #if defined(_LIBCPP_VERSION) && !BUILDFLAG(IS_NACL)
- // Specialize both std::__is_cpp17_contiguous_iterator and std::pointer_traits
- // for CCI in case we compile with libc++ outside of NaCl. The former is
- // required to enable certain algorithm optimizations (e.g. std::copy can be a
- // simple std::memmove under certain circumstances), and is a precursor to
- // C++20's std::contiguous_iterator concept [1]. Once we actually use C++20 it
- // will be enough to add `using iterator_concept = std::contiguous_iterator_tag`
- // to the iterator class [2], and we can get rid of this non-standard
- // specialization.
- //
- // The latter is required to obtain the underlying raw pointer without resulting
- // in CHECK failures. The important bit is the `to_address(pointer)` overload,
- // which is the standard blessed way to customize `std::to_address(pointer)` in
- // C++20 [3].
- //
- // [1] https://wg21.link/iterator.concept.contiguous
- // [2] https://wg21.link/std.iterator.tags
- // [3] https://wg21.link/pointer.traits.optmem
- namespace std {
- template <typename T>
- struct __is_cpp17_contiguous_iterator<::base::CheckedContiguousIterator<T>>
- : true_type {};
- template <typename T>
- struct pointer_traits<::base::CheckedContiguousIterator<T>> {
- using pointer = ::base::CheckedContiguousIterator<T>;
- using element_type = T;
- using difference_type = ptrdiff_t;
- template <typename U>
- using rebind = ::base::CheckedContiguousIterator<U>;
- static constexpr pointer pointer_to(element_type& r) noexcept {
- return pointer(&r, &r);
- }
- static constexpr element_type* to_address(pointer p) noexcept {
- return p.current_;
- }
- };
- } // namespace std
- #endif
- #endif // BASE_CONTAINERS_CHECKED_ITERATORS_H_
|