1 // Copyright 2024 The Pigweed Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 4 // use this file except in compliance with the License. You may obtain a copy of 5 // the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 12 // License for the specific language governing permissions and limitations under 13 // the License. 14 #pragma once 15 16 #include <iterator> 17 #include <type_traits> 18 19 namespace pw { 20 21 // Forward declaration for friending. 22 template <typename> 23 class IntrusiveForwardList; 24 25 namespace containers { 26 namespace future { 27 28 template <typename> 29 class IntrusiveList; 30 31 } // namespace future 32 33 namespace internal { 34 35 // Mixin for iterators that can dereference and compare items. 36 template <typename Derived, typename T, typename I> 37 class IteratorBase { 38 public: 39 constexpr const T& operator*() const { return *(downcast()); } 40 constexpr T& operator*() { return *(downcast()); } 41 42 constexpr const T* operator->() const { return downcast(); } 43 constexpr T* operator->() { return downcast(); } 44 45 template <typename D2, 46 typename T2, 47 typename I2, 48 typename = std::enable_if_t< 49 std::is_same_v<std::remove_cv_t<T>, std::remove_cv_t<T2>>>> 50 constexpr bool operator==(const IteratorBase<D2, T2, I2>& rhs) const { 51 return static_cast<const I*>(derived().item_) == 52 static_cast<const I2*>(rhs.derived().item_); 53 } 54 55 template <typename D2, 56 typename T2, 57 typename I2, 58 typename = std::enable_if_t< 59 std::is_same_v<std::remove_cv_t<T>, std::remove_cv_t<T2>>>> 60 constexpr bool operator!=(const IteratorBase<D2, T2, I2>& rhs) const { 61 return !operator==(rhs); 62 } 63 64 private: 65 template <typename, typename, typename> 66 friend class IteratorBase; 67 derived()68 Derived& derived() { return static_cast<Derived&>(*this); } derived()69 const Derived& derived() const { return static_cast<const Derived&>(*this); } 70 downcast()71 T* downcast() { return static_cast<T*>(derived().item_); } downcast()72 const T* downcast() const { return static_cast<const T*>(derived().item_); } 73 }; 74 75 // Mixin for iterators that can advance to a subsequent item. 76 template <typename Derived, typename I> 77 class Incrementable { 78 public: 79 constexpr Derived& operator++() { 80 auto* derived = static_cast<Derived*>(this); 81 derived->item_ = static_cast<I*>(derived->item_->next_); 82 return *derived; 83 } 84 85 constexpr Derived operator++(int) { 86 Derived copy(static_cast<Derived&>(*this)); 87 operator++(); 88 return copy; 89 } 90 }; 91 92 // Mixin for iterators that can reverse to a previous item. 93 template <typename Derived, typename I> 94 class Decrementable { 95 public: 96 constexpr Derived& operator--() { 97 auto* derived = static_cast<Derived*>(this); 98 derived->item_ = static_cast<I*>(derived->item_->previous()); 99 return *derived; 100 } 101 102 constexpr Derived operator--(int) { 103 Derived copy(static_cast<Derived&>(*this)); 104 operator--(); 105 return copy; 106 } 107 }; 108 109 /// Forward iterator that has the ability to advance over a sequence of items. 110 /// 111 /// This is roughly equivalent to std::forward_iterator<T>, but for intrusive 112 /// lists. 113 template <typename T, typename I> 114 class ForwardIterator : public IteratorBase<ForwardIterator<T, I>, T, I>, 115 public Incrementable<ForwardIterator<T, I>, I> { 116 public: 117 using difference_type = std::ptrdiff_t; 118 using value_type = std::remove_cv_t<T>; 119 using pointer = T*; 120 using reference = T&; 121 using iterator_category = std::forward_iterator_tag; 122 123 constexpr ForwardIterator() = default; 124 125 // Allow creating const_iterators from iterators. 126 template <typename U> ForwardIterator(const ForwardIterator<U,std::remove_cv_t<I>> & other)127 ForwardIterator(const ForwardIterator<U, std::remove_cv_t<I>>& other) 128 : item_(other.item_) {} 129 130 private: 131 template <typename, typename, typename> 132 friend class IteratorBase; 133 134 friend class Incrementable<ForwardIterator<T, I>, I>; 135 136 template <typename, typename> 137 friend class ForwardIterator; 138 139 template <typename> 140 friend class ::pw::IntrusiveForwardList; 141 142 // Only allow IntrusiveForwardList to create iterators that point to 143 // something. ForwardIterator(I * item)144 constexpr explicit ForwardIterator(I* item) : item_{item} {} 145 146 I* item_ = nullptr; 147 }; 148 149 /// Iterator that has the ability to advance forwards or backwards over a 150 /// sequence of items. 151 /// 152 /// This is roughly equivalent to std::bidirectional_iterator<T>, but for 153 /// intrusive lists. 154 template <typename T, typename I> 155 class BidirectionalIterator 156 : public IteratorBase<BidirectionalIterator<T, I>, T, I>, 157 public Decrementable<BidirectionalIterator<T, I>, I>, 158 public Incrementable<BidirectionalIterator<T, I>, I> { 159 public: 160 using difference_type = std::ptrdiff_t; 161 using value_type = std::remove_cv_t<T>; 162 using pointer = T*; 163 using reference = T&; 164 using iterator_category = std::bidirectional_iterator_tag; 165 166 constexpr BidirectionalIterator() = default; 167 168 // Allow creating const_iterators from iterators. 169 template <typename U> BidirectionalIterator(const BidirectionalIterator<U,std::remove_cv_t<I>> & other)170 BidirectionalIterator( 171 const BidirectionalIterator<U, std::remove_cv_t<I>>& other) 172 : item_(other.item_) {} 173 174 private: 175 template <typename, typename, typename> 176 friend class IteratorBase; 177 178 friend class Decrementable<BidirectionalIterator<T, I>, I>; 179 friend class Incrementable<BidirectionalIterator<T, I>, I>; 180 181 template <typename, typename> 182 friend class BidirectionalIterator; 183 184 template <typename> 185 friend class ::pw::containers::future::IntrusiveList; 186 187 // Only allow IntrusiveList to create iterators that point to something. BidirectionalIterator(I * item)188 constexpr explicit BidirectionalIterator(I* item) : item_{item} {} 189 190 I* item_ = nullptr; 191 }; 192 193 } // namespace internal 194 } // namespace containers 195 } // namespace pw 196