| // Copyright 2021 The Fuchsia Authors |
| // |
| // Use of this source code is governed by a MIT-style |
| // license that can be found in the LICENSE file or at |
| // https://opensource.org/licenses/MIT |
| #ifndef FBL_WAVL_TREE_BEST_NODE_OBSERVER_H_ |
| #define FBL_WAVL_TREE_BEST_NODE_OBSERVER_H_ |
| |
| #include <zircon/assert.h> |
| |
| #include <fbl/macros.h> |
| |
| namespace fbl { |
| |
| // WAVLTreeBestNodeObserver |
| // |
| // Definition of a WAVLTreeObserver which helps to automate the process of |
| // maintaining a "best value in this subtree" invariant inside of a WAVL tree. |
| // |
| // For example, consider a set of objects, each of which has an "Priority" and |
| // an "Awesomeness" property. If a user is maintaining a collection of these |
| // objects indexed by "Priority", they may want to be able to easily answer |
| // questions about the maximum "Awesomeness" of sets of objects partitioned by |
| // priority. If every member in the tree also maintained a "maximum Awesomeness |
| // for my subtree" value, then the following questions can be easily answered. |
| // |
| // 1) What is the maximum awesomeness across all members of the tree? This is |
| // the maximum subtree awesomeness of the root node of the tree. |
| // 2) What is the maximum awesomeness across all members of the tree with a |
| // priority > X? This is the maximum subtree awesomeness of |
| // tree.upper_bound(X) (if such a node exists). |
| // |
| // WAVLTreeBestNodeObserver implements all of the observer hooks needed to |
| // maintain such an invariant based on a set of Traits defined by the user which |
| // allow the WAVLTreeBestNodeObserver to know when one node has a "better" value |
| // than another node, and to access the per-node storage which holds the "best" |
| // value for a subtree. |
| // |
| // Traits implementations should contain the following definitions: |
| // |
| // struct Traits { |
| // // TODO(johngro): When we are allowed to use C++20, make this a more formal |
| // // concept definition. |
| // // Returns a node's value. In the example above, this is the node's "awesomeness". |
| // static ValueType GetValue(const Object& node) { ... } |
| // |
| // // Returns the current "best" value of the subtree rooted at node. |
| // static ValueType GetSubtreeBest(const Object& node) { ... } |
| // |
| // // Compares two values, and returns true if |a| is "better" than |b|. Otherwise false. |
| // static bool Compare(ValueType a, ValueType b) { ... } |
| // |
| // // Assigns the value |val| to the node's subtree-best storage. |
| // static void AssignBest(Object& node, ValueType val) { ... } |
| // |
| // // Resets the value node's subtree-best storage. Called when nodes are |
| // // being removed from their tree. Note that users don't _have_ to make use |
| // // of this hook if they do not care about stale values being stored in their |
| // // subtree-best storage. |
| // static void ResetBest(Object& target) { ... } |
| // }; |
| // |
| // The Traits used for the "awesomness" example given above might look like the |
| // following if "awesomeness" was expressed as a strictly positive uint32_t: |
| // |
| // struct AwesomeObj { |
| // // ... |
| // constexpr uint32_t kInvalidAwesomeness = 0; |
| // uint32_t priority; |
| // uint32_t awesomeness; |
| // uint32_t subtree_best{kInvalidAwesomeness}; |
| // }; |
| // |
| // struct MaxAwesomeTraits { |
| // static uint32_t GetValue(const AwesomeObj& node) { return node.awesomness; } |
| // static uint32_t GetSubtreeBest(const AwesomeObj& node) { return node.subtree_best; } |
| // static bool Compare(uint32_t a, uint32_t b) { return a > b; } |
| // static void AssignBest(AwesomeObj& node, uint32_t val) { node.subtree_best = val; } |
| // static void ResetBest(AwesomeObj& target) { |
| // node.subtree_best = AwesomeObj::kInvalidAwesomeness; |
| // } |
| // }; |
| // |
| // using MaxAwesomeObserver = fbl::WAVLReeBestNodeObserver<MaxAwesomeTraits>; |
| // |
| // In addition to the traits which define the "best" value to maintain, |
| // WAVLTreeBestNodeObserver has two more boolean template parameters which can |
| // be used to control behavior. They are: |
| // |
| // AllowInsertOrFindCollision |
| // AllowInsertOrReplaceCollision |
| // |
| // By default, both of these values are |true|. If a collision happens during |
| // either an insert_or_find or an insert_or_replace operation, the "best value" |
| // invariant will be maintained. On the other hand, if a user knows that they |
| // will never encounter collisions as a result of one or the other (or both) of |
| // these operations, they may set the appropriate Allow template argument to |
| // false, causing the WAVLTreeBestNodeObserver to fail a ZX_DEBUG_ASSERT in the |
| // case that associated collision is ever encountered during operation. |
| // |
| template <typename Traits, bool AllowInsertOrFindCollision = true, |
| bool AllowInsertOrReplaceCollision = true> |
| struct WAVLTreeBestNodeObserver { |
| private: |
| DECLARE_HAS_MEMBER_FN(has_on_insert_collision, OnInsertCollision); |
| DECLARE_HAS_MEMBER_FN(has_on_insert_replace, OnInsertReplace); |
| |
| public: |
| template <typename Iter> |
| static void RecordInsert(Iter node) { |
| Traits::AssignBest(*node, Traits::GetValue(*node)); |
| } |
| |
| template <typename T, typename Iter> |
| static void RecordInsertCollision(T* node, Iter collision) { |
| // |node| did not actually end up getting inserted into the tree, but all of |
| // the node down until collision we updated during the descent during calls |
| // to RecordInsertTraverse. We need to restore the "best" invariant by |
| // re-computing the proper values starting from collision, up until we reach |
| // root. |
| ZX_DEBUG_ASSERT(AllowInsertOrFindCollision); |
| RecomputeUntilRoot(collision); |
| } |
| |
| template <typename Iter, typename T> |
| static void RecordInsertReplace(Iter node, T* replacement) { |
| // |node| is still in the tree, but it is about to be replaced by |
| // |replacement|. Update the value of |node| to hold the value of |
| // |replacement|, then propagate the value up the tree to the root (as we do |
| // in the case of an erase operation). Once we are finished, transfer the |
| // computed "best" value for for |node|'s subtree over to replacement, then |
| // reset the value of node (as it is just about to be removed from the tree, |
| // and replaced with |replacement|). |
| ZX_DEBUG_ASSERT(AllowInsertOrReplaceCollision); |
| UpdateBest(Traits::GetValue(*replacement), node); |
| RecomputeUntilRoot(node.parent()); |
| Traits::AssignBest(*replacement, Traits::GetSubtreeBest(*node)); |
| Traits::ResetBest(*node); |
| } |
| |
| template <typename T, typename Iter> |
| static void RecordInsertTraverse(T* node, Iter ancestor) { |
| // If the value of |node| is better than the value of the ancestor we just |
| // traversed, update the |ancestor| to hold |node|'s value. |
| const auto node_val = Traits::GetValue(*node); |
| if (Traits::Compare(node_val, Traits::GetSubtreeBest(*ancestor))) { |
| Traits::AssignBest(*ancestor, node_val); |
| } |
| } |
| |
| // Rotations are used to adjust the height of nodes that are out of balance. |
| // During a rotation, the pivot takes the position of the parent, and takes over |
| // storing the "best" value for the subtree, as all of the nodes in the |
| // overall subtree remain the same. The original parent inherits the lr_child |
| // of the pivot, potentially invalidating its new subtree and requiring an |
| // update. |
| // |
| // The following diagrams the relationship of the nodes in a left rotation: |
| // |
| // ::After:: ::Before:: | |
| // | |
| // pivot parent | |
| // / \ / \ | |
| // parent rl_child <----------- sibling pivot | |
| // / \ / \ | |
| // sibling lr_child lr_child rl_child | |
| // |
| // In a right rotation, all of the relationships are reflected. However, this |
| // does not affect the update logic. |
| template <typename Iter> |
| static void RecordRotation(Iter pivot, Iter lr_child, Iter rl_child, Iter parent, Iter sibling) { |
| // |pivot| is about to take |parent|'s place in the tree. The overall |
| // subtree maintains the same "best" value, so |pivot| can just take |
| // |parent|'s best value.. |
| Traits::AssignBest(*pivot, Traits::GetSubtreeBest(*parent)); |
| |
| // The descendents of |sibling|, |lr_child|, and |rl_child| are not |
| // changing, meaning that we do not need to take any action to update their |
| // current best subtree values. |
| // |
| // |parent|, on the other hand, is becoming the root of a new subtree with |
| // |sibling| and |lr_child| as its new children. Select the new best value |
| // for the subtree rooted at |parent| from these three options. |
| // |
| auto best = Traits::GetValue(*parent); |
| |
| if (sibling) { |
| const auto sibling_best = Traits::GetSubtreeBest(*sibling); |
| if (Traits::Compare(sibling_best, best)) { |
| best = sibling_best; |
| } |
| } |
| |
| if (lr_child) { |
| const auto lr_child_best = Traits::GetSubtreeBest(*lr_child); |
| if (Traits::Compare(lr_child_best, best)) { |
| best = lr_child_best; |
| } |
| } |
| |
| Traits::AssignBest(*parent, best); |
| } |
| |
| template <typename T, typename Iter> |
| static void RecordErase(T* node, Iter invalidated) { |
| // When a node is removed all of the ancestors become invalidated up to |
| // the root. Traverse up the tree from the point of invalidation and |
| // restore the subtree invariant. Note, there will be no invalidated node |
| // in the case that this was the last node removed. |
| RecomputeUntilRoot(invalidated); |
| |
| // |node| is leaving the tree. Give our Traits the opportunity to reset |
| // its "best" value. |
| Traits::ResetBest(*node); |
| } |
| |
| // Promotion/Demotion/DoubleRotation count hooks are not needed to maintain |
| // our "best" invariant. |
| static void RecordInsertPromote() {} |
| static void RecordInsertRotation() {} |
| static void RecordInsertDoubleRotation() {} |
| static void RecordEraseDemote() {} |
| static void RecordEraseRotation() {} |
| static void RecordEraseDoubleRotation() {} |
| |
| private: |
| template <typename Iter> |
| static void RecomputeUntilRoot(Iter current) { |
| for (; current; current = current.parent()) { |
| UpdateBest(Traits::GetValue(*current), current); |
| } |
| } |
| |
| template <typename ValueType, typename Iter> |
| static void UpdateBest(ValueType value, Iter node) { |
| if (Iter left = node.left(); left) { |
| ValueType left_best = Traits::GetSubtreeBest(*left); |
| if (Traits::Compare(left_best, value)) { |
| value = left_best; |
| } |
| } |
| |
| if (Iter right = node.right(); right) { |
| ValueType right_best = Traits::GetSubtreeBest(*right); |
| if (Traits::Compare(right_best, value)) { |
| value = right_best; |
| } |
| } |
| |
| Traits::AssignBest(*node, value); |
| } |
| }; |
| |
| } // namespace fbl |
| |
| #endif // FBL_WAVL_TREE_BEST_NODE_OBSERVER_H_ |