319 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___ITERATOR_STATIC_BOUNDED_ITER_H11#define _LIBCPP___ITERATOR_STATIC_BOUNDED_ITER_H12 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_header31#endif32 33_LIBCPP_PUSH_MACROS34#include <__undef_macros>35 36_LIBCPP_BEGIN_NAMESPACE_STD37 38template <class _Iterator, size_t _Size>39struct __static_bounded_iter_storage {40 _LIBCPP_HIDE_FROM_ABI __static_bounded_iter_storage() = default;41 _LIBCPP_HIDE_FROM_ABI42 _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 50private:51 _Iterator __current_; // current iterator52 _Iterator __begin_; // start of the valid range, which is [__begin_, __begin_ + _Size)53};54 55template <class _Iterator>56struct __static_bounded_iter_storage<_Iterator, 0> {57 _LIBCPP_HIDE_FROM_ABI __static_bounded_iter_storage() = default;58 _LIBCPP_HIDE_FROM_ABI59 _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 67private:68 _Iterator __current_; // current iterator69};70 71// This is an iterator wrapper for contiguous iterators that points within a range72// 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 since74// 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`.77template <class _Iterator, size_t _Size>78struct __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 >= 2088 using iterator_concept = contiguous_iterator_tag;89#endif90 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, __iterator_reference<_OtherIterator> >,104 is_same<reference, __make_const_lvalue_ref<__iterator_reference<_OtherIterator> > > > >::value,105 int> = 0>106 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR107 __static_bounded_iter(__static_bounded_iter<_OtherIterator, _Size> const& __other) _NOEXCEPT108 : __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 114private:115 // Create an iterator wrapping the given iterator, and whose bounds are described116 // by the provided [begin, begin + _Size] range.117 _LIBCPP_HIDE_FROM_ABI118 _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 129public: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_iter190 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_iter196 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_iter212 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_type218 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 even227 // if they have different validity ranges.228 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool229 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 <= 17234 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool235 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 bool240 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 bool244 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 bool248 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 bool252 operator>=(__static_bounded_iter const& __x, __static_bounded_iter const& __y) _NOEXCEPT {253 return __x.__current() >= __y.__current();254 }255 256#else257 _LIBCPP_HIDE_FROM_ABI constexpr friend strong_ordering258 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 >= 20272 273private: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 292template <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 <= 17299template <class _Iterator, size_t _Size>300struct __libcpp_is_contiguous_iterator<__static_bounded_iter<_Iterator, _Size> > : true_type {};301#endif302 303template <class _Iterator, size_t _Size>304struct 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_STD315 316_LIBCPP_POP_MACROS317 318#endif // _LIBCPP___ITERATOR_STATIC_BOUNDED_ITER_H319