v1/__iterator/static_bounded_iter.h

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___ITERATOR_STATIC_BOUNDED_ITER_H
0011 #define _LIBCPP___ITERATOR_STATIC_BOUNDED_ITER_H
0012
0013 #include <__assert>
0014 #include <__compare/ordering.h>
0015 #include <__compare/three_way_comparable.h>
0016 #include <__config>
0017 #include <__cstddef/size_t.h>
0018 #include <__iterator/iterator_traits.h>
0019 #include <__memory/pointer_traits.h>
0020 #include <__type_traits/conjunction.h>
0021 #include <__type_traits/disjunction.h>
0022 #include <__type_traits/enable_if.h>
0023 #include <__type_traits/integral_constant.h>
0024 #include <__type_traits/is_convertible.h>
0025 #include <__type_traits/is_same.h>
0026 #include <__type_traits/make_const_lvalue_ref.h>
0027 #include <__utility/move.h>
0028
0029 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0030 #  pragma GCC system_header
0031 #endif
0032
0033 _LIBCPP_PUSH_MACROS
0034 #include <__undef_macros>
0035
0036 _LIBCPP_BEGIN_NAMESPACE_STD
0037
0038 template <class _Iterator, size_t _Size>
0039 struct __static_bounded_iter_storage {
0040   _LIBCPP_HIDE_FROM_ABI __static_bounded_iter_storage() = default;
0041   _LIBCPP_HIDE_FROM_ABI
0042   _LIBCPP_CONSTEXPR_SINCE_CXX14 explicit __static_bounded_iter_storage(_Iterator __current, _Iterator __begin)
0043       : __current_(__current), __begin_(__begin) {}
0044
0045   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator& __current() _NOEXCEPT { return __current_; }
0046   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __current() const _NOEXCEPT { return __current_; }
0047   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __begin() const _NOEXCEPT { return __begin_; }
0048   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __end() const _NOEXCEPT { return __begin_ + _Size; }
0049
0050 private:
0051   _Iterator __current_; // current iterator
0052   _Iterator __begin_;   // start of the valid range, which is [__begin_, __begin_ + _Size)
0053 };
0054
0055 template <class _Iterator>
0056 struct __static_bounded_iter_storage<_Iterator, 0> {
0057   _LIBCPP_HIDE_FROM_ABI __static_bounded_iter_storage() = default;
0058   _LIBCPP_HIDE_FROM_ABI
0059   _LIBCPP_CONSTEXPR_SINCE_CXX14 explicit __static_bounded_iter_storage(_Iterator __current, _Iterator /* __begin */)
0060       : __current_(__current) {}
0061
0062   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator& __current() _NOEXCEPT { return __current_; }
0063   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __current() const _NOEXCEPT { return __current_; }
0064   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __begin() const _NOEXCEPT { return __current_; }
0065   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __end() const _NOEXCEPT { return __current_; }
0066
0067 private:
0068   _Iterator __current_; // current iterator
0069 };
0070
0071 // This is an iterator wrapper for contiguous iterators that points within a range
0072 // whose size is known at compile-time. This is very similar to `__bounded_iter`,
0073 // except that we don't have to store the end of the range in physical memory since
0074 // it can be computed from the start of the range.
0075 //
0076 // The operations on which this iterator wrapper traps are the same as `__bounded_iter`.
0077 template <class _Iterator, size_t _Size>
0078 struct __static_bounded_iter {
0079   static_assert(__libcpp_is_contiguous_iterator<_Iterator>::value,
0080                 "Only contiguous iterators can be adapted by __static_bounded_iter.");
0081
0082   using value_type        = typename iterator_traits<_Iterator>::value_type;
0083   using difference_type   = typename iterator_traits<_Iterator>::difference_type;
0084   using pointer           = typename iterator_traits<_Iterator>::pointer;
0085   using reference         = typename iterator_traits<_Iterator>::reference;
0086   using iterator_category = typename iterator_traits<_Iterator>::iterator_category;
0087 #if _LIBCPP_STD_VER >= 20
0088   using iterator_concept = contiguous_iterator_tag;
0089 #endif
0090
0091   // Create a singular iterator.
0092   //
0093   // Such an iterator points past the end of an empty range, so it is not dereferenceable.
0094   // Operations like comparison and assignment are valid.
0095   _LIBCPP_HIDE_FROM_ABI __static_bounded_iter() = default;
0096
0097   _LIBCPP_HIDE_FROM_ABI __static_bounded_iter(__static_bounded_iter const&) = default;
0098   _LIBCPP_HIDE_FROM_ABI __static_bounded_iter(__static_bounded_iter&&)      = default;
0099
0100   template <class _OtherIterator,
0101             __enable_if_t<
0102                 _And< is_convertible<const _OtherIterator&, _Iterator>,
0103                       _Or<is_same<reference, __iter_reference<_OtherIterator> >,
0104                           is_same<reference, __make_const_lvalue_ref<__iter_reference<_OtherIterator> > > > >::value,
0105                 int> = 0>
0106   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR
0107   __static_bounded_iter(__static_bounded_iter<_OtherIterator, _Size> const& __other) _NOEXCEPT
0108       : __storage_(__other.__storage_.__current(), __other.__storage_.__begin()) {}
0109
0110   // Assign a bounded iterator to another one, rebinding the bounds of the iterator as well.
0111   _LIBCPP_HIDE_FROM_ABI __static_bounded_iter& operator=(__static_bounded_iter const&) = default;
0112   _LIBCPP_HIDE_FROM_ABI __static_bounded_iter& operator=(__static_bounded_iter&&)      = default;
0113
0114 private:
0115   // Create an iterator wrapping the given iterator, and whose bounds are described
0116   // by the provided [begin, begin + _Size] range.
0117   _LIBCPP_HIDE_FROM_ABI
0118   _LIBCPP_CONSTEXPR_SINCE_CXX14 explicit __static_bounded_iter(_Iterator __current, _Iterator __begin)
0119       : __storage_(__current, __begin) {
0120     _LIBCPP_ASSERT_INTERNAL(
0121         __begin <= __current, "__static_bounded_iter(current, begin): current and begin are inconsistent");
0122     _LIBCPP_ASSERT_INTERNAL(
0123         __current <= __end(), "__static_bounded_iter(current, begin): current and (begin + Size) are inconsistent");
0124   }
0125
0126   template <size_t _Sz, class _It>
0127   friend _LIBCPP_CONSTEXPR __static_bounded_iter<_It, _Sz> __make_static_bounded_iter(_It, _It);
0128
0129 public:
0130   // Dereference and indexing operations.
0131   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 reference operator*() const _NOEXCEPT {
0132     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0133         __current() != __end(), "__static_bounded_iter::operator*: Attempt to dereference an iterator at the end");
0134     return *__current();
0135   }
0136
0137   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pointer operator->() const _NOEXCEPT {
0138     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0139         __current() != __end(), "__static_bounded_iter::operator->: Attempt to dereference an iterator at the end");
0140     return std::__to_address(__current());
0141   }
0142
0143   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 reference operator[](difference_type __n) const _NOEXCEPT {
0144     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0145         __n >= __begin() - __current(),
0146         "__static_bounded_iter::operator[]: Attempt to index an iterator past the start");
0147     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0148         __n < __end() - __current(),
0149         "__static_bounded_iter::operator[]: Attempt to index an iterator at or past the end");
0150     return __current()[__n];
0151   }
0152
0153   // Arithmetic operations.
0154   //
0155   // These operations check that the iterator remains within `[begin, end]`.
0156   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __static_bounded_iter& operator++() _NOEXCEPT {
0157     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0158         __current() != __end(), "__static_bounded_iter::operator++: Attempt to advance an iterator past the end");
0159     ++__current();
0160     return *this;
0161   }
0162   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __static_bounded_iter operator++(int) _NOEXCEPT {
0163     __static_bounded_iter __tmp(*this);
0164     ++*this;
0165     return __tmp;
0166   }
0167
0168   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __static_bounded_iter& operator--() _NOEXCEPT {
0169     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0170         __current() != __begin(), "__static_bounded_iter::operator--: Attempt to rewind an iterator past the start");
0171     --__current();
0172     return *this;
0173   }
0174   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __static_bounded_iter operator--(int) _NOEXCEPT {
0175     __static_bounded_iter __tmp(*this);
0176     --*this;
0177     return __tmp;
0178   }
0179
0180   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __static_bounded_iter& operator+=(difference_type __n) _NOEXCEPT {
0181     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0182         __n >= __begin() - __current(),
0183         "__static_bounded_iter::operator+=: Attempt to rewind an iterator past the start");
0184     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0185         __n <= __end() - __current(), "__static_bounded_iter::operator+=: Attempt to advance an iterator past the end");
0186     __current() += __n;
0187     return *this;
0188   }
0189   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __static_bounded_iter
0190   operator+(__static_bounded_iter const& __self, difference_type __n) _NOEXCEPT {
0191     __static_bounded_iter __tmp(__self);
0192     __tmp += __n;
0193     return __tmp;
0194   }
0195   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __static_bounded_iter
0196   operator+(difference_type __n, __static_bounded_iter const& __self) _NOEXCEPT {
0197     __static_bounded_iter __tmp(__self);
0198     __tmp += __n;
0199     return __tmp;
0200   }
0201
0202   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __static_bounded_iter& operator-=(difference_type __n) _NOEXCEPT {
0203     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0204         __n <= __current() - __begin(),
0205         "__static_bounded_iter::operator-=: Attempt to rewind an iterator past the start");
0206     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0207         __n >= __current() - __end(), "__static_bounded_iter::operator-=: Attempt to advance an iterator past the end");
0208     __current() -= __n;
0209     return *this;
0210   }
0211   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __static_bounded_iter
0212   operator-(__static_bounded_iter const& __self, difference_type __n) _NOEXCEPT {
0213     __static_bounded_iter __tmp(__self);
0214     __tmp -= __n;
0215     return __tmp;
0216   }
0217   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend difference_type
0218   operator-(__static_bounded_iter const& __x, __static_bounded_iter const& __y) _NOEXCEPT {
0219     return __x.__current() - __y.__current();
0220   }
0221
0222   // Comparison operations.
0223   //
0224   // These operations do not check whether the iterators are within their bounds.
0225   // The valid range for each iterator is also not considered as part of the comparison,
0226   // i.e. two iterators pointing to the same location will be considered equal even
0227   // if they have different validity ranges.
0228   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
0229   operator==(__static_bounded_iter const& __x, __static_bounded_iter const& __y) _NOEXCEPT {
0230     return __x.__current() == __y.__current();
0231   }
0232
0233 #if _LIBCPP_STD_VER <= 17
0234   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
0235   operator!=(__static_bounded_iter const& __x, __static_bounded_iter const& __y) _NOEXCEPT {
0236     return __x.__current() != __y.__current();
0237   }
0238
0239   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
0240   operator<(__static_bounded_iter const& __x, __static_bounded_iter const& __y) _NOEXCEPT {
0241     return __x.__current() < __y.__current();
0242   }
0243   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
0244   operator>(__static_bounded_iter const& __x, __static_bounded_iter const& __y) _NOEXCEPT {
0245     return __x.__current() > __y.__current();
0246   }
0247   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
0248   operator<=(__static_bounded_iter const& __x, __static_bounded_iter const& __y) _NOEXCEPT {
0249     return __x.__current() <= __y.__current();
0250   }
0251   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
0252   operator>=(__static_bounded_iter const& __x, __static_bounded_iter const& __y) _NOEXCEPT {
0253     return __x.__current() >= __y.__current();
0254   }
0255
0256 #else
0257   _LIBCPP_HIDE_FROM_ABI constexpr friend strong_ordering
0258   operator<=>(__static_bounded_iter const& __x, __static_bounded_iter const& __y) noexcept {
0259     if constexpr (three_way_comparable<_Iterator, strong_ordering>) {
0260       return __x.__current() <=> __y.__current();
0261     } else {
0262       if (__x.__current() < __y.__current())
0263         return strong_ordering::less;
0264
0265       if (__x.__current() == __y.__current())
0266         return strong_ordering::equal;
0267
0268       return strong_ordering::greater;
0269     }
0270   }
0271 #endif // _LIBCPP_STD_VER >= 20
0272
0273 private:
0274   template <class>
0275   friend struct pointer_traits;
0276   template <class, size_t>
0277   friend struct __static_bounded_iter;
0278   __static_bounded_iter_storage<_Iterator, _Size> __storage_;
0279
0280   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator& __current() _NOEXCEPT {
0281     return __storage_.__current();
0282   }
0283   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __current() const _NOEXCEPT {
0284     return __storage_.__current();
0285   }
0286   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __begin() const _NOEXCEPT {
0287     return __storage_.__begin();
0288   }
0289   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator __end() const _NOEXCEPT { return __storage_.__end(); }
0290 };
0291
0292 template <size_t _Size, class _It>
0293 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __static_bounded_iter<_It, _Size>
0294 __make_static_bounded_iter(_It __it, _It __begin) {
0295   return __static_bounded_iter<_It, _Size>(std::move(__it), std::move(__begin));
0296 }
0297
0298 #if _LIBCPP_STD_VER <= 17
0299 template <class _Iterator, size_t _Size>
0300 struct __libcpp_is_contiguous_iterator<__static_bounded_iter<_Iterator, _Size> > : true_type {};
0301 #endif
0302
0303 template <class _Iterator, size_t _Size>
0304 struct pointer_traits<__static_bounded_iter<_Iterator, _Size> > {
0305   using pointer         = __static_bounded_iter<_Iterator, _Size>;
0306   using element_type    = typename pointer_traits<_Iterator>::element_type;
0307   using difference_type = typename pointer_traits<_Iterator>::difference_type;
0308
0309   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR static element_type* to_address(pointer __it) _NOEXCEPT {
0310     return std::__to_address(__it.__current());
0311   }
0312 };
0313
0314 _LIBCPP_END_NAMESPACE_STD
0315
0316 _LIBCPP_POP_MACROS
0317
0318 #endif // _LIBCPP___ITERATOR_STATIC_BOUNDED_ITER_H