Changeset View
Changeset View
Standalone View
Standalone View
share/man/man3/tree.3
Show First 20 Lines • Show All 517 Lines • ▼ Show 20 Lines | |||||
from the tree pointed by | from the tree pointed by | ||||
.Fa head . | .Fa head . | ||||
.Pp | .Pp | ||||
The | The | ||||
.Fn RB_FIND | .Fn RB_FIND | ||||
and | and | ||||
.Fn RB_NFIND | .Fn RB_NFIND | ||||
macros can be used to find a particular element in the tree. | macros can be used to find a particular element in the tree. | ||||
.Pp | |||||
The | |||||
.Fn RB_FIND | |||||
macro returns the element in the tree equal to the provided | |||||
dougm: macro returns the element in the tree equal to the provided
key, or
.Dv NULL
if there is no… | |||||
key, or | |||||
.Dv NULL | |||||
if there is no such element. | |||||
.Pp | |||||
The | |||||
.Fn RB_NFIND | |||||
macro returns the least element greater than or equal to the provided | |||||
Done Inline ActionsNot just any element, but the least (or first) element. dougm: Not just any element, but the least (or first) element. | |||||
Done Inline Actionsmacro returns the least element greater than or equal to the provided dougm: macro returns the least element greater than or equal to the provided
key, or
.Dv NULL
if there… | |||||
key, or | |||||
.Dv NULL | |||||
if there is no such element. | |||||
.Bd -literal -offset indent | .Bd -literal -offset indent | ||||
struct TYPE find, *res; | struct TYPE find, *res, *resn; | ||||
find.key = 30; | find.key = 30; | ||||
res = RB_FIND(NAME, head, &find); | res = RB_FIND(NAME, head, &find); | ||||
resn = RB_NFIND(NAME, head, &find); | |||||
.Ed | .Ed | ||||
.Pp | .Pp | ||||
The | The | ||||
.Fn RB_ROOT , | .Fn RB_ROOT , | ||||
.Fn RB_MIN , | .Fn RB_MIN , | ||||
.Fn RB_MAX , | .Fn RB_MAX , | ||||
.Fn RB_NEXT , | .Fn RB_NEXT , | ||||
and | and | ||||
▲ Show 20 Lines • Show All 66 Lines • ▼ Show 20 Lines | |||||
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. | ||||
If RB_AUGMENT is defined by the RB user, then when an element in the | If | ||||
.Fn RB_AUGMENT | |||||
is defined by the RB user, then when an element in the | |||||
tree is changed, without changing the order of items in the tree, | tree is changed, without changing the order of items in the tree, | ||||
invoking this function on that element restores consistency of the | invoking this function on that element restores consistency of the | ||||
augmentation state of the tree as if the element had been removed and | augmentation state of the tree as if the element had been removed and | ||||
inserted again. | inserted again. | ||||
.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 | ||||
▲ Show 20 Lines • Show All 144 Lines • Show Last 20 Lines |
macro returns the element in the tree equal to the provided
key, or
.Dv NULL
if there is no such element.