Differential D36001 Diff 108850 share/man/man3/tree.3

Changeset 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
				dougmUnsubmitted Done Inline Actions macro returns the element in the tree equal to the provided key, or .Dv NULL if there is no such element. 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
				dougmUnsubmitted Done Inline Actions Not just any element, but the least (or first) element. dougm: Not just any element, but the least (or first) element.
				dougmUnsubmitted Done Inline Actions macro returns the least element greater than or equal to the provided key, or .Dv NULL if there is no such element. 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