| 1 | //===----------------------------------------------------------------------===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | /// |
| 9 | /// \file |
| 10 | /// Standalone implementation of iterator utilities. |
| 11 | /// |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #ifndef LLVM_LIBC_SRC___SUPPORT_CPP_ITERATOR_H |
| 15 | #define LLVM_LIBC_SRC___SUPPORT_CPP_ITERATOR_H |
| 16 | |
| 17 | #include <stddef.h> // For ptrdiff_t |
| 18 | |
| 19 | #include "hdr/types/size_t.h" |
| 20 | #include "src/__support/CPP/type_traits/enable_if.h" |
| 21 | #include "src/__support/CPP/type_traits/is_convertible.h" |
| 22 | #include "src/__support/CPP/type_traits/is_same.h" |
| 23 | #include "src/__support/macros/attributes.h" |
| 24 | #include "src/__support/macros/config.h" |
| 25 | |
| 26 | namespace LIBC_NAMESPACE_DECL { |
| 27 | namespace cpp { |
| 28 | |
| 29 | struct input_iterator_tag {}; |
| 30 | struct random_access_iterator_tag : input_iterator_tag {}; |
| 31 | |
| 32 | template <typename T> struct iterator_traits; |
| 33 | template <typename T> struct iterator_traits<T *> { |
| 34 | using difference_type = ptrdiff_t; |
| 35 | using value_type = T; |
| 36 | using pointer = T *; |
| 37 | using reference = T &; |
| 38 | using iterator_category = random_access_iterator_tag; |
| 39 | }; |
| 40 | |
| 41 | template <typename Iter> class reverse_iterator { |
| 42 | Iter current; |
| 43 | |
| 44 | public: |
| 45 | using iterator_type = Iter; |
| 46 | using difference_type = typename iterator_traits<Iter>::difference_type; |
| 47 | using value_type = typename iterator_traits<Iter>::value_type; |
| 48 | using pointer = typename iterator_traits<Iter>::pointer; |
| 49 | using reference = typename iterator_traits<Iter>::reference; |
| 50 | |
| 51 | LIBC_INLINE constexpr reverse_iterator() : current() {} |
| 52 | LIBC_INLINE constexpr explicit reverse_iterator(Iter it) : current(it) {} |
| 53 | |
| 54 | template <typename Other, |
| 55 | cpp::enable_if_t<!cpp::is_same_v<Iter, Other> && |
| 56 | cpp::is_convertible_v<const Other &, Iter>, |
| 57 | int> = 0> |
| 58 | LIBC_INLINE constexpr reverse_iterator(const reverse_iterator<Other> &other) |
| 59 | : current(other.base()) {} |
| 60 | |
| 61 | template <typename Other, |
| 62 | cpp::enable_if_t<!cpp::is_same_v<Iter, Other> && |
| 63 | cpp::is_convertible_v<const Other &, Iter>, |
| 64 | int> = 0> |
| 65 | LIBC_INLINE constexpr explicit reverse_iterator(const Other &it) |
| 66 | : current(it) {} |
| 67 | |
| 68 | LIBC_INLINE friend constexpr bool operator==(const reverse_iterator &lhs, |
| 69 | const reverse_iterator &rhs) { |
| 70 | return lhs.base() == rhs.base(); |
| 71 | } |
| 72 | |
| 73 | LIBC_INLINE friend constexpr bool operator!=(const reverse_iterator &lhs, |
| 74 | const reverse_iterator &rhs) { |
| 75 | return lhs.base() != rhs.base(); |
| 76 | } |
| 77 | |
| 78 | LIBC_INLINE friend constexpr bool operator<(const reverse_iterator &lhs, |
| 79 | const reverse_iterator &rhs) { |
| 80 | return lhs.base() > rhs.base(); |
| 81 | } |
| 82 | |
| 83 | LIBC_INLINE friend constexpr bool operator<=(const reverse_iterator &lhs, |
| 84 | const reverse_iterator &rhs) { |
| 85 | return lhs.base() >= rhs.base(); |
| 86 | } |
| 87 | |
| 88 | LIBC_INLINE friend constexpr bool operator>(const reverse_iterator &lhs, |
| 89 | const reverse_iterator &rhs) { |
| 90 | return lhs.base() < rhs.base(); |
| 91 | } |
| 92 | |
| 93 | LIBC_INLINE friend constexpr bool operator>=(const reverse_iterator &lhs, |
| 94 | const reverse_iterator &rhs) { |
| 95 | return lhs.base() <= rhs.base(); |
| 96 | } |
| 97 | |
| 98 | LIBC_INLINE constexpr iterator_type base() const { return current; } |
| 99 | |
| 100 | LIBC_INLINE constexpr reference operator*() const { |
| 101 | Iter tmp = current; |
| 102 | return *--tmp; |
| 103 | } |
| 104 | |
| 105 | LIBC_INLINE constexpr pointer operator->() const { |
| 106 | Iter tmp = current; |
| 107 | return --tmp; |
| 108 | } |
| 109 | |
| 110 | LIBC_INLINE constexpr reference operator[](difference_type n) const { |
| 111 | return *(*this + n); |
| 112 | } |
| 113 | |
| 114 | LIBC_INLINE constexpr reverse_iterator &operator--() { |
| 115 | ++current; |
| 116 | return *this; |
| 117 | } |
| 118 | |
| 119 | LIBC_INLINE constexpr reverse_iterator operator--(int) { |
| 120 | reverse_iterator tmp(*this); |
| 121 | ++current; |
| 122 | return tmp; |
| 123 | } |
| 124 | |
| 125 | LIBC_INLINE constexpr reverse_iterator &operator++() { |
| 126 | --current; |
| 127 | return *this; |
| 128 | } |
| 129 | |
| 130 | LIBC_INLINE constexpr reverse_iterator operator++(int) { |
| 131 | reverse_iterator tmp(*this); |
| 132 | --current; |
| 133 | return tmp; |
| 134 | } |
| 135 | |
| 136 | LIBC_INLINE constexpr reverse_iterator operator+(difference_type n) const { |
| 137 | return reverse_iterator(current - n); |
| 138 | } |
| 139 | |
| 140 | LIBC_INLINE constexpr reverse_iterator &operator+=(difference_type n) { |
| 141 | current -= n; |
| 142 | return *this; |
| 143 | } |
| 144 | |
| 145 | LIBC_INLINE constexpr reverse_iterator operator-(difference_type n) const { |
| 146 | return reverse_iterator(current + n); |
| 147 | } |
| 148 | |
| 149 | LIBC_INLINE constexpr reverse_iterator &operator-=(difference_type n) { |
| 150 | current += n; |
| 151 | return *this; |
| 152 | } |
| 153 | |
| 154 | LIBC_INLINE friend constexpr difference_type |
| 155 | operator-(const reverse_iterator &lhs, const reverse_iterator &rhs) { |
| 156 | return rhs.base() - lhs.base(); |
| 157 | } |
| 158 | }; |
| 159 | |
| 160 | namespace cpp_internal { |
| 161 | |
| 162 | template <typename It> |
| 163 | LIBC_INLINE constexpr size_t distance(It first, It last, |
| 164 | random_access_iterator_tag) { |
| 165 | return last - first; |
| 166 | } |
| 167 | |
| 168 | template <typename It> |
| 169 | LIBC_INLINE constexpr auto distance(It first, It last, input_iterator_tag) { |
| 170 | size_t n = 0; |
| 171 | for (; first != last; ++first) |
| 172 | ++n; |
| 173 | return n; |
| 174 | } |
| 175 | |
| 176 | } // namespace cpp_internal |
| 177 | |
| 178 | template <typename It> LIBC_INLINE constexpr auto distance(It first, It last) { |
| 179 | return cpp_internal::distance( |
| 180 | first, last, typename iterator_traits<It>::iterator_category{}); |
| 181 | } |
| 182 | |
| 183 | } // namespace cpp |
| 184 | } // namespace LIBC_NAMESPACE_DECL |
| 185 | |
| 186 | #endif // LLVM_LIBC_SRC___SUPPORT_CPP_ITERATOR_H |
| 187 | |