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 <cstddef> 17 18 #include "pw_bytes/packed_ptr.h" 19 20 namespace pw::containers::internal { 21 22 /// Base type for items stored in an AA tree, as described by Arne Andersson in 23 /// https://user.it.uu.se/~arneande/ps/simp.pdf. AA trees are simplified 24 /// red-black which offer almost as much performance with much simpler and 25 /// smaller code. 26 /// 27 /// The major difference between the nodes described by Andersson and this 28 /// implementation is the addition of a back-reference from an item to its 29 /// parent, allowing additional methods that operate on ranges of nodes. This 30 /// allows methods that more closely match the interfaces of `std::map` and 31 /// `std::multimap`. 32 class AATreeItem { 33 public: 34 /// Destructor. An item cannot be part of a tree when it is destroyed. ~AATreeItem()35 ~AATreeItem() { PW_ASSERT(!IsMapped()); } 36 37 // AATreeItems are not copyable. 38 AATreeItem(const AATreeItem&) = delete; 39 AATreeItem& operator=(const AATreeItem&) = delete; 40 41 protected: 42 constexpr explicit AATreeItem() = default; 43 44 private: 45 // Allow the tree and its iterators to walk and maniplate the node-related 46 // fields of items. 47 friend class GenericAATree; 48 49 template <typename, typename> 50 friend class AATree; 51 52 template <typename> 53 friend class AATreeIterator; 54 55 /// Gets the level of an item, i.e. its depth in the tree. 56 uint8_t GetLevel() const; 57 58 /// Sets the level of an item, i.e. its depth in the tree. 59 void SetLevel(uint8_t level); 60 61 /// Returns whether this node is part of any tree. 62 [[nodiscard]] bool IsMapped() const; 63 64 /// Returns the number of items in the subtree rooted by this item, 65 /// including this one. 66 size_t GetTreeSize(); 67 68 /// Returns the item at the root of the overall tree. 69 AATreeItem* GetRoot(); 70 71 /// Returns the item in this item's subtree that is furthest to the left, or 72 /// null if this item is a leaf node. 73 AATreeItem* GetLeftmost(); 74 75 /// Returns the item in this item's subtree that is furthest to the right, 76 /// or null if this item is a leaf node. 77 AATreeItem* GetRightmost(); 78 79 /// Returns the rightmost item to the left of this item in its overall tree, 80 /// or null if this item is the tree's leftmost item. 81 AATreeItem* GetPredecessor(); 82 83 /// Returns the leftmost item to the right of this item in its overall tree, 84 /// or null if this item is the tree's leftmost item. 85 AATreeItem* GetSuccessor(); 86 87 /// Removes this item from its overall tree. 88 /// 89 /// This method creates a balanced subtree with the same items as this 90 /// item's subtree, except for the item itself. 91 /// 92 /// Calling this method on an item that is not part of a tree has no effect. 93 /// 94 /// @returns An item with a balanced subtree. 95 AATreeItem* Unmap(); 96 97 /// Sets the left child of this item, and sets that child's parent to this 98 /// item. 99 void SetLeft(AATreeItem* left); 100 101 /// Sets the right child of this item, and sets that child's parent to this 102 /// item. 103 void SetRight(AATreeItem* right); 104 105 /// Sets either the left or right child of this node to `new_child` if it 106 /// is currently `old_child`. 107 void Replace(AATreeItem* old_child, AATreeItem* new_child); 108 109 /// Performs a right rotation on this item's subtree, if necessary. This 110 /// removes horizontal left links, where a horizontal link is between two 111 /// items of the same level. 112 /// 113 /// @returns A subtree with left horizontal links removed. 114 AATreeItem* Skew(); 115 116 /// Performs a left rotation on this item's subtree, if necessary. This 117 /// removes consectuive horizontal right links, where a horizontal link is 118 /// between two items of the same level. 119 /// 120 /// @returns A subtree with consecutive right horizontal links removed. 121 AATreeItem* Split(); 122 123 /// Walks up the overall tree from this node, skewing and splitting as 124 /// needed to produce a balanced AA tree. 125 /// 126 /// @returns An item representing the root of a balanced AA tree. 127 AATreeItem* Rebalance(); 128 129 /// Removes the current item and all the items in its subtree from its 130 /// overall tree. 131 void Clear(); 132 133 /// Restores all the fields of this item except its key to their default 134 /// values. Has no effect on any other item. 135 void Reset(); 136 137 PackedPtr<AATreeItem> parent_; 138 mutable PackedPtr<AATreeItem> left_; 139 mutable PackedPtr<AATreeItem> right_; 140 }; 141 142 } // namespace pw::containers::internal 143