template <typename Traits, bool AllowInsertOrFindCollision = true, bool AllowInsertOrReplaceCollision = true>struct WAVLTreeAugmentedInvariantObserver
Defined at line 54 of file ../../zircon/system/ulib/fbl/include/fbl/wavl_tree_augmented_invariant_observer.h
WAVLTreeAugmentedInvariantObserver
Definition of a WAVLTreeObserver which helps to automate the process of maintaining augmented
invariants inside of a WAVL tree.
Traits implementations should contain the following definitions:
struct Traits {
// Returns the invariant value for the given node.
static SubtreeValueType GetNodeValue(const Object
&
node) { ... }
// Returns the invariant value for the given node's subtree.
static SubtreeValueType GetSubtreeValue(const Object
&
node) { ... }
// Combines subtree and node invariant values to produce a new subtree invarant value.
static SubtreeValueType CombineValues(SubtreeValueType a, SubtreeValueType b) { ... }
// Sets the node's subtree invariant value.
static void SetSubtreeValue(Object
&
node, SubtreeValueType val) { ... }
// Resets the node's subtree invariant value.
static void ResetSubtreeValue(Object
&
target) { ... }
};
In addition to the traits which define the value to maintain, WAVLTreeAugmentedInvariantObserver
has two more boolean template parameters which can be used to control behavior:
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 subtree 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 WAVLTreeAugmentedInvariantObserver to fail a ZX_DEBUG_ASSERT in the case that associated
collision is ever encountered during operation.
Public Methods
template <typename Iter>void RecordInsert (Iter node)Initializes the subtree value of the node when it is first inserted as a leaf.
Defined at line 62 of file ../../zircon/system/ulib/fbl/include/fbl/wavl_tree_augmented_invariant_observer.h
template <typename T, typename Iter>void RecordInsertTraverse (T * node, Iter ancestor)Updates the subtree value of an ancestor node as it is traversed during insertion.
Defined at line 68 of file ../../zircon/system/ulib/fbl/include/fbl/wavl_tree_augmented_invariant_observer.h
template <typename T, typename Iter>void RecordInsertCollision (T * node, Iter collision)Fixes invalid invariants in nodes traversed along the path to the colliding node when a node is
not inserted into the tree due to the collision.
Defined at line 78 of file ../../zircon/system/ulib/fbl/include/fbl/wavl_tree_augmented_invariant_observer.h
template <typename Iter, typename T>void RecordInsertReplace (Iter node, T * replacement)Fixes invalid invariants in nodes traversed along the path to the colliding node when a node is
replace in the tree due to the collision.
Defined at line 91 of file ../../zircon/system/ulib/fbl/include/fbl/wavl_tree_augmented_invariant_observer.h
template <typename Iter>void RecordRotation (Iter pivot, Iter lr_child, Iter rl_child, Iter parent, Iter sibling)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 invariant 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.
Defined at line 123 of file ../../zircon/system/ulib/fbl/include/fbl/wavl_tree_augmented_invariant_observer.h
template <typename T, typename Iter>void RecordErase (T * node, Iter invalidated)Restores the subtree values of the invalidated ancestors from the point of removal up to the
root node.
Defined at line 148 of file ../../zircon/system/ulib/fbl/include/fbl/wavl_tree_augmented_invariant_observer.h
void RecordInsertPromote ()Promotion/Demotion/DoubleRotation count hooks are not needed to maintain subtree invariants.
Defined at line 154 of file ../../zircon/system/ulib/fbl/include/fbl/wavl_tree_augmented_invariant_observer.h
void RecordInsertRotation ()Defined at line 155 of file ../../zircon/system/ulib/fbl/include/fbl/wavl_tree_augmented_invariant_observer.h
void RecordInsertDoubleRotation ()Defined at line 156 of file ../../zircon/system/ulib/fbl/include/fbl/wavl_tree_augmented_invariant_observer.h
void RecordEraseDemote ()Defined at line 157 of file ../../zircon/system/ulib/fbl/include/fbl/wavl_tree_augmented_invariant_observer.h
void RecordEraseRotation ()Defined at line 158 of file ../../zircon/system/ulib/fbl/include/fbl/wavl_tree_augmented_invariant_observer.h
void RecordEraseDoubleRotation ()Defined at line 159 of file ../../zircon/system/ulib/fbl/include/fbl/wavl_tree_augmented_invariant_observer.h