Changeset View
Changeset View
Standalone View
Standalone View
share/man/man3/tree.3
Show First 20 Lines • Show All 93 Lines • ▼ Show 20 Lines | |||||
.Nm RB_FOREACH_SAFE , | .Nm RB_FOREACH_SAFE , | ||||
.Nm RB_FOREACH_REVERSE , | .Nm RB_FOREACH_REVERSE , | ||||
.Nm RB_FOREACH_REVERSE_FROM , | .Nm RB_FOREACH_REVERSE_FROM , | ||||
.Nm RB_FOREACH_REVERSE_SAFE , | .Nm RB_FOREACH_REVERSE_SAFE , | ||||
.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 , | ||||
.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 | ||||
.Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP | .Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP | ||||
.Fn SPLAY_GENERATE NAME TYPE FIELD CMP | .Fn SPLAY_GENERATE NAME TYPE FIELD CMP | ||||
.Fn SPLAY_ENTRY TYPE | .Fn SPLAY_ENTRY TYPE | ||||
.Fn SPLAY_HEAD HEADNAME TYPE | .Fn SPLAY_HEAD HEADNAME TYPE | ||||
.Ft "struct TYPE *" | .Ft "struct TYPE *" | ||||
▲ Show 20 Lines • Show All 80 Lines • ▼ Show 20 Lines | |||||
.Ft "struct TYPE *" | .Ft "struct TYPE *" | ||||
.Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm" | .Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm" | ||||
.Ft "struct TYPE *" | .Ft "struct TYPE *" | ||||
.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" | .Ft "void" | ||||
.Fn RB_AUGMENT NAME "struct TYPE *elm" | .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. | ||||
.Pp | .Pp | ||||
In the macro definitions, | In the macro definitions, | ||||
.Fa TYPE | .Fa TYPE | ||||
is the name tag of a user defined structure that must contain a field of type | is the name tag of a user defined structure that must contain a field of type | ||||
.Vt SPLAY_ENTRY , | .Vt SPLAY_ENTRY , | ||||
▲ Show 20 Lines • Show All 384 Lines • ▼ Show 20 Lines | |||||
.Fa elm | .Fa elm | ||||
in the tree. | in the tree. | ||||
By default, it has no effect. | By default, it has no effect. | ||||
It is not meant to be invoked by the RB user. | It is not meant to be invoked by the RB user. | ||||
If RB_AUGMENT is defined by the RB user, then when an element is | If RB_AUGMENT is defined by the RB user, then when an element is | ||||
inserted or removed from the tree, it is invoked for every element in | 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 | the tree that is the root of an altered subtree, working from the | ||||
bottom of the tree up to the top. | 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 | It is typically used to maintain some associative accumulation of tree | ||||
elements, such as sums, minima, maxima, and the like. | 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. | ||||
Values are inserted into it and the contents of the tree are printed | Values are inserted into it and the contents of the tree are printed | ||||
in order. | in order. | ||||
To maintain the sum of the values in the tree, each element maintains | To maintain the sum of the values in the tree, each element maintains | ||||
▲ Show 20 Lines • Show All 142 Lines • Show Last 20 Lines |