Lines Matching +full:in +full:- +full:tree

1 .\"	$OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $
4 .\" Copyright 2018-2019 Netflix, Inc.
7 .\" Redistribution and use in source and binary forms, with or without
12 .\" 2. Redistributions in binary form must reproduce the above copyright
13 .\"    notice, this list of conditions and the following disclaimer in the
24 .\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
28 .\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
98 .Nd "array-based red-black trees"
185 These macros define data structures for and array-based red-black trees.
187 e.g., when the tree needs to be transferred between userspace and kernel.
203 has to be a unique name prefix for every tree that is defined.
215 A red-black tree is a binary search tree with the node color as an
218 .Bl -enum -offset indent
228 Every operation on a red-black tree is bounded as
230 The maximum height of a red-black tree is
238 tree entries is therefore constrained by the minimum of array size and choice of
244 A red-black tree is headed by a structure defined by the
249 .Bd -ragged -offset indent
258 is the type of the elements to be inserted into the tree.
263 .Pq in bits
267 creates a red-black tree head structure with 8-bit signed array indices capable
272 macro declares a structure that allows elements to be connected in the tree.
278 .Pq in bits
280 Entries should use the same number of bits as the tree head structure they will
283 In order to use the functions that manipulate the tree structure,
291 is a unique identifier for this particular tree.
295 by the tree.
352 argument is the name of a function used to compare tree nodes
361 function defines the order of the tree elements.
365 macro initializes the tree referenced by
370 The red-black tree can also be initialized statically by using the
373 .Bd -ragged -offset indent
384 into the tree.
390 from the tree pointed by
397 macros can be used to find a particular element in the tree.
398 .Bd -literal -offset indent
411 macros can be used to traverse the tree:
420 .Bd -ragged -offset indent
428 traverse the tree referenced by head
430 assigning each element in turn to np.
449 macro should be used to check whether a red-black tree is empty.
452 some ARB-specific additional macros are defined.
455 macro returns a boolean indicating whether the current number of tree entries
456 equals the tree's maximum.
464 macro returns a pointer to the next free entry in the array of entries, ready to
465 be linked into the tree.
470 if the element was inserted in the tree successfully, otherwise they
483 in the tree.
485 .Nm tree
486 is modified in a way that affects comparison, such as by modifying
493 macro discards the tree topology.
497 .Xr tree 3
501 macros first appeared in
509 .Xr tree 3