struct DefaultWAVLTreeObserver
Defined at line 36 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree_internal.h
Definition of the default (no-op) Observer.
Observers are used by the test framework to record the number of insert,
erase, rank-promote, rank-demote and rotation operations performed during
usage. The DefaultWAVLTreeObserver does nothing and should fall out of the
code during template expansion.
Observers may also be used to maintain additional application-specific per-
node invariants. For example, maintaining subtree min/max values is useful
for multikey partition searching.
Note: Records of promotions and demotions are used by tests to demonstrate
that the computational complexity of insert/erase rebalancing is amortized
constant. Promotions and demotions which are side effects of the rotation
phase of rebalancing are considered to be part of the cost of rotation and
are not tallied in the overall promote/demote accounting.
Public Methods
template <typename Iter>void RecordInsert (Iter node)Invoked on the newly inserted node before rebalancing.
Defined at line 39 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree_internal.h
template <typename T, typename Iter>void RecordInsertTraverse (T * node, Iter ancestor)Invoked on the node to be inserted and each ancestor node while traversing
the tree to find the initial insertion point.
Defined at line 44 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree_internal.h
template <typename T, typename Iter>void RecordInsertCollision (T * node, Iter collision)Invoked on the node to be inserted and the colliding node with the same
key, during an insert_or_find operation. This method is mutually exclusive
with RecordInsertReplace, only one or the other is invoked during an
insert operation.
Defined at line 51 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree_internal.h
template <typename Iter, typename T>void RecordInsertReplace (Iter node, T * replacement)Invoked on an existing node and its replacement, before swapping the
replacement into the tree, during an insert_or_replace operation. This
method is mutually exclusive with RecordInsertCollision, only one or the
other is invoked during an insert operation.
Defined at line 58 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree_internal.h
void RecordInsertPromote ()Invoked after each promotion during post-insert rebalancing.
Defined at line 61 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree_internal.h
void RecordInsertRotation ()Invoked after a single rotation during post-insert rebalancing.
Defined at line 64 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree_internal.h
void RecordInsertDoubleRotation ()Invoked after a double rotation during post-insert rebalancing.
Defined at line 67 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree_internal.h
template <typename Iter>void RecordRotation (Iter pivot, Iter lr_child, Iter rl_child, Iter parent, Iter sibling)Invoked on the pivot node, its parent, children, and sibling before a
rotation, just before updating the pointers in the relevant nodes. The
chirality of the children and sibling is relative to the direction of
rotation. The direction of rotation can be determined by comparing these
arguments with the values returned by the left() and right() iterator
methods of the pivot or parent arguments.
The following diagrams the relationship of the nodes in a left rotation:
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, the
left() and right() iterator methods of each node return unreflected values.
Defined at line 88 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree_internal.h
template <typename T, typename Iter>void RecordErase (T * node, Iter invalidated)Invoked on the node to be erased and the node in the tree where the
augmented invariants become invalid, leading up to the root. Called just
after updating the pointers in the relevant nodes, but before rebalancing.
The following diagrams the relationship of the erased and invalidated
nodes:
root |
/
\
|
A B
<
---- Invalidated starting here on up to the root |
/
\
/
\
|
C D E F
<
---- Erased node |
When the node to be erased has two children, it is first swapped with the
leftmost child of the righthand subtree. In this case the invalidated node
is the parent of the original leftmost child of the righthand subtree, as
this is the deepest node to change after erasure.
root root |
/
\
/
\
|
A B A B |
/
\
/
\
/
\
/
\
|
C D E F
<
--+ C D E H
<
---- Invalidated starting here |
/
\
| Swap /
\
|
G H
<
-+ G F
<
---- Erased node |
Defined at line 117 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree_internal.h
void RecordEraseDemote ()Invoked after each demotion during post-erase rebalancing.
Defined at line 120 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree_internal.h
void RecordEraseRotation ()Invoked after each single rotation during post-erase rebalancing.
Defined at line 123 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree_internal.h
void RecordEraseDoubleRotation ()Invoked after each dobule rotation during post-erase rebalancing.
Defined at line 126 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree_internal.h
template <typename TreeType>void VerifyRankRule (const TreeType & tree, typename TreeType::RawPtrType node)Defined at line 129 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree_internal.h
template <typename TreeType>void VerifyBalance (const TreeType & tree, uint64_t depth)Defined at line 132 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree_internal.h