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 <cstdint> 17 #include <iterator> 18 #include <type_traits> 19 20 #include "pw_containers/internal/aa_tree_item.h" 21 22 namespace pw::containers::internal { 23 24 /// Iterator that has the ability to advance forwards or backwards over a 25 /// sequence of items. 26 /// 27 /// This is roughly equivalent to std::bidirectional_iterator<T>, but for 28 /// intrusive maps. 29 template <typename T = AATreeItem> 30 class AATreeIterator { 31 public: 32 using difference_type = std::ptrdiff_t; 33 using value_type = std::remove_cv_t<T>; 34 using pointer = T*; 35 using reference = T&; 36 using iterator_category = std::bidirectional_iterator_tag; 37 AATreeIterator(const AATreeIterator<AATreeItem> & other)38 constexpr AATreeIterator(const AATreeIterator<AATreeItem>& other) { 39 *this = other; 40 } 41 42 constexpr AATreeIterator& operator=(const AATreeIterator<AATreeItem>& other) { 43 root_ = other.root_; 44 item_ = other.item_; 45 return *this; 46 } 47 48 constexpr const T& operator*() const { return *(downcast()); } 49 constexpr T& operator*() { return *(downcast()); } 50 51 constexpr const T* operator->() const { return downcast(); } 52 constexpr T* operator->() { return downcast(); } 53 54 template <typename T2, 55 typename = std::enable_if_t< 56 std::is_same_v<std::remove_cv_t<T>, std::remove_cv_t<T2>>>> 57 constexpr bool operator==(const AATreeIterator<T2>& rhs) const { 58 return root_ == rhs.root_ && item_ == rhs.item_; 59 } 60 61 template <typename T2, 62 typename = std::enable_if_t< 63 std::is_same_v<std::remove_cv_t<T>, std::remove_cv_t<T2>>>> 64 constexpr bool operator!=(const AATreeIterator<T2>& rhs) const { 65 return !operator==(rhs); 66 } 67 68 constexpr AATreeIterator& operator++() { 69 if (item_ != nullptr) { 70 item_ = item_->GetSuccessor(); 71 } else { 72 PW_DASSERT(root_ != nullptr); 73 PW_DASSERT(*root_ != nullptr); 74 item_ = (*root_)->GetLeftmost(); 75 } 76 return *this; 77 } 78 79 constexpr AATreeIterator operator++(int) { 80 AATreeIterator copy = *this; 81 operator++(); 82 return copy; 83 } 84 85 constexpr AATreeIterator& operator--() { 86 if (item_ != nullptr) { 87 item_ = item_->GetPredecessor(); 88 } else { 89 PW_DASSERT(root_ != nullptr); 90 PW_DASSERT(*root_ != nullptr); 91 item_ = (*root_)->GetRightmost(); 92 } 93 return *this; 94 } 95 96 constexpr AATreeIterator operator--(int) { 97 AATreeIterator copy = *this; 98 operator--(); 99 return copy; 100 } 101 102 private: 103 template <typename> 104 friend class AATreeIterator; 105 106 friend class GenericAATree; 107 108 template <typename, typename> 109 friend class AATree; 110 111 // Only the generic and derived AA trees can create iterators that actually 112 // point to something. They provides a pointer to its pointer to the root of 113 // tree. The root item may change, but the pointer to it remains the same for 114 // the life of the tree. AATreeIterator(AATreeItem ** root)115 constexpr explicit AATreeIterator(AATreeItem** root) : root_(root) {} AATreeIterator(AATreeItem ** root,AATreeItem * item)116 constexpr AATreeIterator(AATreeItem** root, AATreeItem* item) 117 : root_(root), item_(item) {} 118 downcast()119 T* downcast() { return static_cast<T*>(item_); } 120 121 AATreeItem** root_; 122 mutable AATreeItem* item_ = nullptr; 123 }; 124 125 } // namespace pw::containers::internal 126