libcxx/include/__iterator/static_bounded_iter.h

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef _LIBCPP___ITERATOR_STATIC_BOUNDED_ITER_H
  11 #define _LIBCPP___ITERATOR_STATIC_BOUNDED_ITER_H
  12
  13 #include <__assert>
  14 #include <__compare/ordering.h>
  15 #include <__compare/three_way_comparable.h>
  16 #include <__config>
  17 #include <__cstddef/size_t.h>
  18 #include <__iterator/iterator_traits.h>
  19 #include <__memory/pointer_traits.h>
  20 #include <__type_traits/conjunction.h>
  21 #include <__type_traits/disjunction.h>
  22 #include <__type_traits/enable_if.h>
  23 #include <__type_traits/integral_constant.h>
  24 #include <__type_traits/is_convertible.h>
  25 #include <__type_traits/is_same.h>
  26 #include <__type_traits/make_const_lvalue_ref.h>
  27 #include <__utility/move.h>
  28
  29 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  30 #  pragma GCC system_header
  31 #endif
  32
  33 _LIBCPP_PUSH_MACROS
  34 #include <__undef_macros>
  35
  36 _LIBCPP_BEGIN_NAMESPACE_STD
  37
  38 template <class _Iterator, size_t _Size>
  39 struct __static_bounded_iter_storage {
  40   _LIBCPP_HIDE_FROM_ABI __static_bounded_iter_storage() = default;
  41   _LIBCPP_HIDE_FROM_ABI
  42   _LIBCPP_CONSTEXPR_SINCE_CXX14 explicit __static_bounded_iter_storage(_Iterator __current, _Iterator __begin)
  43       : __current_(__current), __begin_(__begin) {}
  44
  45   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator& __current() _NOEXCEPT { return __current_; }
  46   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __current() const _NOEXCEPT { return __current_; }
  47   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __begin() const _NOEXCEPT { return __begin_; }
  48   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __end() const _NOEXCEPT { return __begin_ + _Size; }
  49
  50 private:
  51   _Iterator __current_; // current iterator
  52   _Iterator __begin_;   // start of the valid range, which is [__begin_, __begin_ + _Size)
  53 };
  54
  55 template <class _Iterator>
  56 struct __static_bounded_iter_storage<_Iterator, 0> {
  57   _LIBCPP_HIDE_FROM_ABI __static_bounded_iter_storage() = default;
  58   _LIBCPP_HIDE_FROM_ABI
  59   _LIBCPP_CONSTEXPR_SINCE_CXX14 explicit __static_bounded_iter_storage(_Iterator __current, _Iterator /* __begin */)
  60       : __current_(__current) {}
  61
  62   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator& __current() _NOEXCEPT { return __current_; }
  63   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __current() const _NOEXCEPT { return __current_; }
  64   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __begin() const _NOEXCEPT { return __current_; }
  65   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __end() const _NOEXCEPT { return __current_; }
  66
  67 private:
  68   _Iterator __current_; // current iterator
  69 };
  70
  71 // This is an iterator wrapper for contiguous iterators that points within a range
  72 // whose size is known at compile-time. This is very similar to `__bounded_iter`,
  73 // except that we don't have to store the end of the range in physical memory since
  74 // it can be computed from the start of the range.
  75 //
  76 // The operations on which this iterator wrapper traps are the same as `__bounded_iter`.
  77 template <class _Iterator, size_t _Size>
  78 struct __static_bounded_iter {
  79   static_assert(__libcpp_is_contiguous_iterator<_Iterator>::value,
  80                 "Only contiguous iterators can be adapted by __static_bounded_iter.");
  81
  82   using value_type        = typename iterator_traits<_Iterator>::value_type;
  83   using difference_type   = typename iterator_traits<_Iterator>::difference_type;
  84   using pointer           = typename iterator_traits<_Iterator>::pointer;
  85   using reference         = typename iterator_traits<_Iterator>::reference;
  86   using iterator_category = typename iterator_traits<_Iterator>::iterator_category;
  87 #if _LIBCPP_STD_VER >= 20
  88   using iterator_concept = contiguous_iterator_tag;
  89 #endif
  90
  91   // Create a singular iterator.
  92   //
  93   // Such an iterator points past the end of an empty range, so it is not dereferenceable.
  94   // Operations like comparison and assignment are valid.
  95   _LIBCPP_HIDE_FROM_ABI __static_bounded_iter() = default;
  96
  97   _LIBCPP_HIDE_FROM_ABI __static_bounded_iter(__static_bounded_iter const&) = default;
  98   _LIBCPP_HIDE_FROM_ABI __static_bounded_iter(__static_bounded_iter&&)      = default;
  99
 100   template <class _OtherIterator,
 101             __enable_if_t<
 102                 _And< is_convertible<const _OtherIterator&, _Iterator>,
 103                       _Or<is_same<reference, __iter_reference<_OtherIterator> >,
 104                           is_same<reference, __make_const_lvalue_ref<__iter_reference<_OtherIterator> > > > >::value,
 105                 int> = 0>
 106   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR
 107   __static_bounded_iter(__static_bounded_iter<_OtherIterator, _Size> const& __other) _NOEXCEPT
 108       : __storage_(__other.__storage_.__current(), __other.__storage_.__begin()) {}
 109
 110   // Assign a bounded iterator to another one, rebinding the bounds of the iterator as well.
 111   _LIBCPP_HIDE_FROM_ABI __static_bounded_iter& operator=(__static_bounded_iter const&) = default;
 112   _LIBCPP_HIDE_FROM_ABI __static_bounded_iter& operator=(__static_bounded_iter&&)      = default;
 113
 114 private:
 115   // Create an iterator wrapping the given iterator, and whose bounds are described
 116   // by the provided [begin, begin + _Size] range.
 117   _LIBCPP_HIDE_FROM_ABI
 118   _LIBCPP_CONSTEXPR_SINCE_CXX14 explicit __static_bounded_iter(_Iterator __current, _Iterator __begin)
 119       : __storage_(__current, __begin) {
 120     _LIBCPP_ASSERT_INTERNAL(
 121         __begin <= __current, "__static_bounded_iter(current, begin): current and begin are inconsistent");
 122     _LIBCPP_ASSERT_INTERNAL(
 123         __current <= __end(), "__static_bounded_iter(current, begin): current and (begin + Size) are inconsistent");
 124   }
 125
 126   template <size_t _Sz, class _It>
 127   friend _LIBCPP_CONSTEXPR __static_bounded_iter<_It, _Sz> __make_static_bounded_iter(_It, _It);
 128
 129 public:
 130   // Dereference and indexing operations.
 131   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 reference operator*() const _NOEXCEPT {
 132     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 133         __current() != __end(), "__static_bounded_iter::operator*: Attempt to dereference an iterator at the end");
 134     return *__current();
 135   }
 136
 137   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pointer operator->() const _NOEXCEPT {
 138     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 139         __current() != __end(), "__static_bounded_iter::operator->: Attempt to dereference an iterator at the end");
 140     return std::__to_address(__current());
 141   }
 142
 143   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 reference operator[](difference_type __n) const _NOEXCEPT {
 144     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 145         __n >= __begin() - __current(),
 146         "__static_bounded_iter::operator[]: Attempt to index an iterator past the start");
 147     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 148         __n < __end() - __current(),
 149         "__static_bounded_iter::operator[]: Attempt to index an iterator at or past the end");
 150     return __current()[__n];
 151   }
 152
 153   // Arithmetic operations.
 154   //
 155   // These operations check that the iterator remains within `[begin, end]`.
 156   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __static_bounded_iter& operator++() _NOEXCEPT {
 157     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 158         __current() != __end(), "__static_bounded_iter::operator++: Attempt to advance an iterator past the end");
 159     ++__current();
 160     return *this;
 161   }
 162   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __static_bounded_iter operator++(int) _NOEXCEPT {
 163     __static_bounded_iter __tmp(*this);
 164     ++*this;
 165     return __tmp;
 166   }
 167
 168   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __static_bounded_iter& operator--() _NOEXCEPT {
 169     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 170         __current() != __begin(), "__static_bounded_iter::operator--: Attempt to rewind an iterator past the start");
 171     --__current();
 172     return *this;
 173   }
 174   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __static_bounded_iter operator--(int) _NOEXCEPT {
 175     __static_bounded_iter __tmp(*this);
 176     --*this;
 177     return __tmp;
 178   }
 179
 180   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __static_bounded_iter& operator+=(difference_type __n) _NOEXCEPT {
 181     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 182         __n >= __begin() - __current(),
 183         "__static_bounded_iter::operator+=: Attempt to rewind an iterator past the start");
 184     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 185         __n <= __end() - __current(), "__static_bounded_iter::operator+=: Attempt to advance an iterator past the end");
 186     __current() += __n;
 187     return *this;
 188   }
 189   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __static_bounded_iter
 190   operator+(__static_bounded_iter const& __self, difference_type __n) _NOEXCEPT {
 191     __static_bounded_iter __tmp(__self);
 192     __tmp += __n;
 193     return __tmp;
 194   }
 195   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __static_bounded_iter
 196   operator+(difference_type __n, __static_bounded_iter const& __self) _NOEXCEPT {
 197     __static_bounded_iter __tmp(__self);
 198     __tmp += __n;
 199     return __tmp;
 200   }
 201
 202   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __static_bounded_iter& operator-=(difference_type __n) _NOEXCEPT {
 203     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 204         __n <= __current() - __begin(),
 205         "__static_bounded_iter::operator-=: Attempt to rewind an iterator past the start");
 206     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 207         __n >= __current() - __end(), "__static_bounded_iter::operator-=: Attempt to advance an iterator past the end");
 208     __current() -= __n;
 209     return *this;
 210   }
 211   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __static_bounded_iter
 212   operator-(__static_bounded_iter const& __self, difference_type __n) _NOEXCEPT {
 213     __static_bounded_iter __tmp(__self);
 214     __tmp -= __n;
 215     return __tmp;
 216   }
 217   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend difference_type
 218   operator-(__static_bounded_iter const& __x, __static_bounded_iter const& __y) _NOEXCEPT {
 219     return __x.__current() - __y.__current();
 220   }
 221
 222   // Comparison operations.
 223   //
 224   // These operations do not check whether the iterators are within their bounds.
 225   // The valid range for each iterator is also not considered as part of the comparison,
 226   // i.e. two iterators pointing to the same location will be considered equal even
 227   // if they have different validity ranges.
 228   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
 229   operator==(__static_bounded_iter const& __x, __static_bounded_iter const& __y) _NOEXCEPT {
 230     return __x.__current() == __y.__current();
 231   }
 232
 233 #if _LIBCPP_STD_VER <= 17
 234   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
 235   operator!=(__static_bounded_iter const& __x, __static_bounded_iter const& __y) _NOEXCEPT {
 236     return __x.__current() != __y.__current();
 237   }
 238
 239   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
 240   operator<(__static_bounded_iter const& __x, __static_bounded_iter const& __y) _NOEXCEPT {
 241     return __x.__current() < __y.__current();
 242   }
 243   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
 244   operator>(__static_bounded_iter const& __x, __static_bounded_iter const& __y) _NOEXCEPT {
 245     return __x.__current() > __y.__current();
 246   }
 247   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
 248   operator<=(__static_bounded_iter const& __x, __static_bounded_iter const& __y) _NOEXCEPT {
 249     return __x.__current() <= __y.__current();
 250   }
 251   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
 252   operator>=(__static_bounded_iter const& __x, __static_bounded_iter const& __y) _NOEXCEPT {
 253     return __x.__current() >= __y.__current();
 254   }
 255
 256 #else
 257   _LIBCPP_HIDE_FROM_ABI constexpr friend strong_ordering
 258   operator<=>(__static_bounded_iter const& __x, __static_bounded_iter const& __y) noexcept {
 259     if constexpr (three_way_comparable<_Iterator, strong_ordering>) {
 260       return __x.__current() <=> __y.__current();
 261     } else {
 262       if (__x.__current() < __y.__current())
 263         return strong_ordering::less;
 264
 265       if (__x.__current() == __y.__current())
 266         return strong_ordering::equal;
 267
 268       return strong_ordering::greater;
 269     }
 270   }
 271 #endif // _LIBCPP_STD_VER >= 20
 272
 273 private:
 274   template <class>
 275   friend struct pointer_traits;
 276   template <class, size_t>
 277   friend struct __static_bounded_iter;
 278   __static_bounded_iter_storage<_Iterator, _Size> __storage_;
 279
 280   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator& __current() _NOEXCEPT {
 281     return __storage_.__current();
 282   }
 283   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __current() const _NOEXCEPT {
 284     return __storage_.__current();
 285   }
 286   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __begin() const _NOEXCEPT {
 287     return __storage_.__begin();
 288   }
 289   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __end() const _NOEXCEPT { return __storage_.__end(); }
 290 };
 291
 292 template <size_t _Size, class _It>
 293 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __static_bounded_iter<_It, _Size>
 294 __make_static_bounded_iter(_It __it, _It __begin) {
 295   return __static_bounded_iter<_It, _Size>(std::move(__it), std::move(__begin));
 296 }
 297
 298 #if _LIBCPP_STD_VER <= 17
 299 template <class _Iterator, size_t _Size>
 300 struct __libcpp_is_contiguous_iterator<__static_bounded_iter<_Iterator, _Size> > : true_type {};
 301 #endif
 302
 303 template <class _Iterator, size_t _Size>
 304 struct pointer_traits<__static_bounded_iter<_Iterator, _Size> > {
 305   using pointer         = __static_bounded_iter<_Iterator, _Size>;
 306   using element_type    = typename pointer_traits<_Iterator>::element_type;
 307   using difference_type = typename pointer_traits<_Iterator>::difference_type;
 308
 309   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR static element_type* to_address(pointer __it) _NOEXCEPT {
 310     return std::__to_address(__it.__current());
 311   }
 312 };
 313
 314 _LIBCPP_END_NAMESPACE_STD
 315
 316 _LIBCPP_POP_MACROS
 317
 318 #endif // _LIBCPP___ITERATOR_STATIC_BOUNDED_ITER_H