Changeset View
Changeset View
Standalone View
Standalone View
share/man/man3/tree.3
Show First 20 Lines • Show All 94 Lines • ▼ Show 20 Lines | |||||||||||
.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, | |||||||||||
.Nm RB_UPDATE_AUGMENT | .Nm RB_UPDATE_AUGMENT | ||||||||||
.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 | ||||||||||
▲ Show 20 Lines • Show All 81 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" | |||||||||||
.Ft "void" | .Ft "void" | ||||||||||
.Fn RB_UPDATE_AUGMENT NAME "struct TYPE *elm" | .Fn RB_UPDATE_AUGMENT 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 | ||||||||||
▲ Show 20 Lines • Show All 403 Lines • ▼ Show 20 Lines | |||||||||||
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 | If | ||||||||||
.Fn RB_AUGMENT | .Fn RB_AUGMENT | ||||||||||
is defined by the RB user, then when an element is inserted or removed | is defined by the RB user, then when an element is inserted or removed | ||||||||||
from the tree, it is invoked for every element in the tree that is the | 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 | root of an altered subtree, working from the bottom of the tree up to | ||||||||||
the top. | 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. | |||||||||||
alcUnsubmitted Done Inline Actions
alc: | |||||||||||
If RB_AUGMENT_CHECK is defined, then when an element is inserted or | |||||||||||
Done Inline Actions
kib: | |||||||||||
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. | ||||||||||
.Pp | .Pp | ||||||||||
The | The | ||||||||||
.Fn RB_UPDATE_AUGMENT | .Fn RB_UPDATE_AUGMENT | ||||||||||
macro updates augmentation data of the element | macro updates augmentation data of the element | ||||||||||
.Fa elm | .Fa elm | ||||||||||
and its ancestors in the tree. | and its ancestors in the tree. | ||||||||||
▲ Show 20 Lines • Show All 155 Lines • Show Last 20 Lines |