Changeset View
Changeset View
Standalone View
Standalone View
share/man/man3/tree.3
Context not available. | |||||
.Nm RB_INIT , | .Nm RB_INIT , | ||||
.Nm RB_INSERT , | .Nm RB_INSERT , | ||||
.Nm RB_REMOVE , | .Nm RB_REMOVE , | ||||
.Nm RB_REINSERT | .Nm RB_REINSERT , | ||||
.Nm RB_AUGMENT , | |||||
.Nm RB_AUGMENT_CHECK | |||||
.Nd "implementations of splay and rank-balanced (wavl) trees" | .Nd "implementations of splay and rank-balanced (wavl) trees" | ||||
.Sh SYNOPSIS | .Sh SYNOPSIS | ||||
.In sys/tree.h | .In sys/tree.h | ||||
Context not available. | |||||
.Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm" | .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm" | ||||
.Ft "struct TYPE *" | .Ft "struct TYPE *" | ||||
.Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm" | .Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm" | ||||
.Ft "void" | |||||
.Fn RB_AUGMENT NAME "struct TYPE *elm" | |||||
.Ft "bool" | |||||
.Fn RB_AUGMENT_CHECK NAME "struct TYPE *elm" | |||||
.Sh DESCRIPTION | .Sh DESCRIPTION | ||||
These macros define data structures for different types of trees: | These macros define data structures for different types of trees: | ||||
splay trees and rank-balanced (wavl) trees. | splay trees and rank-balanced (wavl) trees. | ||||
Context not available. | |||||
a node's key. | a node's key. | ||||
This is a lower overhead alternative to removing the element | This is a lower overhead alternative to removing the element | ||||
and reinserting it again. | and reinserting it again. | ||||
.Pp | |||||
The | |||||
.Fn RB_AUGMENT | |||||
macro updates augmentation data of the element | |||||
.Fa elm | |||||
in the tree. | |||||
By default, it has no effect. | |||||
If RB_AUGMENT is defined, then when an element is inserted or removed | |||||
from the tree, it is invoked for every element in the tree that is the | |||||
root of an altered subtree, working from the bottom of the tree up to | |||||
the top. | |||||
It is typically used to maintain some associative accumulation of tree | |||||
elements, such as sums, minima, maxima, and the like. | |||||
.Pp | |||||
The | |||||
.Fn RB_AUGMENT_CHECK | |||||
macro updates augmentation data of the element | |||||
.Fa elm | |||||
in the tree. | |||||
By default, does nothing and returns false. | |||||
If RB_AUGMENT_CHECK is defined, then when an element is inserted or | |||||
removed from the tree, it is invoked for every element in the tree | |||||
that is the root of an altered subtree, working from the bottom of the | |||||
tree up toward the top, until it returns false to indicate that it did | |||||
not change the element and so working further up the tree would | |||||
change nothing. | |||||
It is typically used to maintain some associative accumulation of tree | |||||
elements, such as sums, minima, maxima, and the like. | |||||
.Sh EXAMPLES | .Sh EXAMPLES | ||||
The following example demonstrates how to declare a rank-balanced tree | The following example demonstrates how to declare a rank-balanced tree | ||||
holding integers. | holding integers. | ||||
Context not available. |