xref: /freebsd/share/man/man3/arb.3 (revision a5adff0eebb383985cd41fa117ee9381cbed7f8e) 
1fad4b12bSEdward Tomasz Napierala.\"	$OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $
2fad4b12bSEdward Tomasz Napierala.\"
3fad4b12bSEdward Tomasz Napierala.\" Copyright 2002 Niels Provos <provos@citi.umich.edu>
4fad4b12bSEdward Tomasz Napierala.\" All rights reserved.
5fad4b12bSEdward Tomasz Napierala.\"
6fad4b12bSEdward Tomasz Napierala.\" Redistribution and use in source and binary forms, with or without
7fad4b12bSEdward Tomasz Napierala.\" modification, are permitted provided that the following conditions
8fad4b12bSEdward Tomasz Napierala.\" are met:
9fad4b12bSEdward Tomasz Napierala.\" 1. Redistributions of source code must retain the above copyright
10fad4b12bSEdward Tomasz Napierala.\"    notice, this list of conditions and the following disclaimer.
11fad4b12bSEdward Tomasz Napierala.\" 2. Redistributions in binary form must reproduce the above copyright
12fad4b12bSEdward Tomasz Napierala.\"    notice, this list of conditions and the following disclaimer in the
13fad4b12bSEdward Tomasz Napierala.\"    documentation and/or other materials provided with the distribution.
14fad4b12bSEdward Tomasz Napierala.\" 3. All advertising materials mentioning features or use of this software
15fad4b12bSEdward Tomasz Napierala.\"    must display the following acknowledgement:
16fad4b12bSEdward Tomasz Napierala.\"      This product includes software developed by Niels Provos.
17fad4b12bSEdward Tomasz Napierala.\" 4. The name of the author may not be used to endorse or promote products
18fad4b12bSEdward Tomasz Napierala.\"    derived from this software without specific prior written permission.
19fad4b12bSEdward Tomasz Napierala.\"
20fad4b12bSEdward Tomasz Napierala.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
21fad4b12bSEdward Tomasz Napierala.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
22fad4b12bSEdward Tomasz Napierala.\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
23fad4b12bSEdward Tomasz Napierala.\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
24fad4b12bSEdward Tomasz Napierala.\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
25fad4b12bSEdward Tomasz Napierala.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26fad4b12bSEdward Tomasz Napierala.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27fad4b12bSEdward Tomasz Napierala.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28fad4b12bSEdward Tomasz Napierala.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
29fad4b12bSEdward Tomasz Napierala.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30fad4b12bSEdward Tomasz Napierala.\"
31fad4b12bSEdward Tomasz Napierala.\" $FreeBSD$
32fad4b12bSEdward Tomasz Napierala.\"
33*a5adff0eSEdward Tomasz Napierala.Dd September 28, 2019
34fad4b12bSEdward Tomasz Napierala.Dt ARB 3
35fad4b12bSEdward Tomasz Napierala.Os
36fad4b12bSEdward Tomasz Napierala.Sh NAME
37fad4b12bSEdward Tomasz Napierala.Nm ARB_PROTOTYPE ,
38fad4b12bSEdward Tomasz Napierala.Nm ARB_PROTOTYPE_STATIC ,
39fad4b12bSEdward Tomasz Napierala.Nm ARB_PROTOTYPE_INSERT ,
40fad4b12bSEdward Tomasz Napierala.Nm ARB_PROTOTYPE_INSERT_COLOR ,
41fad4b12bSEdward Tomasz Napierala.Nm ARB_PROTOTYPE_REMOVE ,
42fad4b12bSEdward Tomasz Napierala.Nm ARB_PROTOTYPE_REMOVE_COLOR ,
43fad4b12bSEdward Tomasz Napierala.Nm ARB_PROTOTYPE_FIND ,
44fad4b12bSEdward Tomasz Napierala.Nm ARB_PROTOTYPE_NFIND ,
45fad4b12bSEdward Tomasz Napierala.Nm ARB_PROTOTYPE_NEXT ,
46fad4b12bSEdward Tomasz Napierala.Nm ARB_PROTOTYPE_PREV ,
47fad4b12bSEdward Tomasz Napierala.Nm ARB_PROTOTYPE_MINMAX ,
48*a5adff0eSEdward Tomasz Napierala.Nm ARB_PROTOTYPE_REINSERT ,
49fad4b12bSEdward Tomasz Napierala.Nm ARB_GENERATE ,
50fad4b12bSEdward Tomasz Napierala.Nm ARB_GENERATE_STATIC ,
51fad4b12bSEdward Tomasz Napierala.Nm ARB_GENERATE_INSERT ,
52fad4b12bSEdward Tomasz Napierala.Nm ARB_GENERATE_INSERT_COLOR ,
53fad4b12bSEdward Tomasz Napierala.Nm ARB_GENERATE_REMOVE ,
54fad4b12bSEdward Tomasz Napierala.Nm ARB_GENERATE_REMOVE_COLOR ,
55fad4b12bSEdward Tomasz Napierala.Nm ARB_GENERATE_FIND ,
56fad4b12bSEdward Tomasz Napierala.Nm ARB_GENERATE_NFIND ,
57fad4b12bSEdward Tomasz Napierala.Nm ARB_GENERATE_NEXT ,
58fad4b12bSEdward Tomasz Napierala.Nm ARB_GENERATE_PREV ,
59fad4b12bSEdward Tomasz Napierala.Nm ARB_GENERATE_MINMAX ,
60*a5adff0eSEdward Tomasz Napierala.Nm ARB_GENERATE_REINSERT ,
61fad4b12bSEdward Tomasz Napierala.Nm ARB8_ENTRY ,
62fad4b12bSEdward Tomasz Napierala.Nm ARB16_ENTRY ,
63fad4b12bSEdward Tomasz Napierala.Nm ARB32_ENTRY ,
64fad4b12bSEdward Tomasz Napierala.Nm ARB8_HEAD ,
65fad4b12bSEdward Tomasz Napierala.Nm ARB16_HEAD ,
66fad4b12bSEdward Tomasz Napierala.Nm ARB32_HEAD ,
67fad4b12bSEdward Tomasz Napierala.Nm ARB_ALLOCSIZE ,
68fad4b12bSEdward Tomasz Napierala.Nm ARB_INITIALIZER ,
69fad4b12bSEdward Tomasz Napierala.Nm ARB_ROOT ,
70fad4b12bSEdward Tomasz Napierala.Nm ARB_EMPTY ,
71fad4b12bSEdward Tomasz Napierala.Nm ARB_FULL ,
72fad4b12bSEdward Tomasz Napierala.Nm ARB_CURNODES ,
73fad4b12bSEdward Tomasz Napierala.Nm ARB_MAXNODES ,
74fad4b12bSEdward Tomasz Napierala.Nm ARB_NEXT ,
75fad4b12bSEdward Tomasz Napierala.Nm ARB_PREV ,
76fad4b12bSEdward Tomasz Napierala.Nm ARB_MIN ,
77fad4b12bSEdward Tomasz Napierala.Nm ARB_MAX ,
78fad4b12bSEdward Tomasz Napierala.Nm ARB_FIND ,
79fad4b12bSEdward Tomasz Napierala.Nm ARB_NFIND ,
80fad4b12bSEdward Tomasz Napierala.Nm ARB_LEFT ,
81fad4b12bSEdward Tomasz Napierala.Nm ARB_LEFTIDX ,
82fad4b12bSEdward Tomasz Napierala.Nm ARB_RIGHT ,
83fad4b12bSEdward Tomasz Napierala.Nm ARB_RIGHTIDX ,
84fad4b12bSEdward Tomasz Napierala.Nm ARB_PARENT ,
85fad4b12bSEdward Tomasz Napierala.Nm ARB_PARENTIDX ,
86fad4b12bSEdward Tomasz Napierala.Nm ARB_GETFREE ,
87fad4b12bSEdward Tomasz Napierala.Nm ARB_FREEIDX ,
88fad4b12bSEdward Tomasz Napierala.Nm ARB_FOREACH ,
89fad4b12bSEdward Tomasz Napierala.Nm ARB_FOREACH_FROM ,
90fad4b12bSEdward Tomasz Napierala.Nm ARB_FOREACH_SAFE ,
91fad4b12bSEdward Tomasz Napierala.Nm ARB_FOREACH_REVERSE ,
92fad4b12bSEdward Tomasz Napierala.Nm ARB_FOREACH_REVERSE_FROM ,
93fad4b12bSEdward Tomasz Napierala.Nm ARB_FOREACH_REVERSE_SAFE ,
94fad4b12bSEdward Tomasz Napierala.Nm ARB_INIT ,
95fad4b12bSEdward Tomasz Napierala.Nm ARB_INSERT ,
96*a5adff0eSEdward Tomasz Napierala.Nm ARB_REMOVE ,
97*a5adff0eSEdward Tomasz Napierala.Nm ARB_REINSERT
98fad4b12bSEdward Tomasz Napierala.Nd "array-based red-black trees"
99fad4b12bSEdward Tomasz Napierala.Sh SYNOPSIS
100fad4b12bSEdward Tomasz Napierala.In sys/arb.h
101fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE NAME TYPE FIELD CMP
102fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
103fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_INSERT NAME TYPE ATTR
104fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR
105fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_REMOVE NAME TYPE ATTR
106fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR
107fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_FIND NAME TYPE ATTR
108fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_NFIND NAME TYPE ATTR
109fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_NEXT NAME TYPE ATTR
110fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_PREV NAME TYPE ATTR
111fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_MINMAX NAME TYPE ATTR
112*a5adff0eSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_REINSERT NAME TYPE ATTR
113fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE NAME TYPE FIELD CMP
114fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_STATIC NAME TYPE FIELD CMP
115fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR
116fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR
117fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_REMOVE NAME TYPE FIELD ATTR
118fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR
119fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_FIND NAME TYPE FIELD CMP ATTR
120fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR
121fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_NEXT NAME TYPE FIELD ATTR
122fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_PREV NAME TYPE FIELD ATTR
123fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_MINMAX NAME TYPE FIELD ATTR
124*a5adff0eSEdward Tomasz Napierala.Fn ARB_GENERATE_REINSERT NAME TYPE FIELD CMP ATTR
125fad4b12bSEdward Tomasz Napierala.Fn ARB<8|16|32>_ENTRY
126fad4b12bSEdward Tomasz Napierala.Fn ARB<8|16|32>_HEAD HEADNAME TYPE
127fad4b12bSEdward Tomasz Napierala.Ft "size_t"
128fad4b12bSEdward Tomasz Napierala.Fn ARB_ALLOCSIZE "ARB_HEAD *head" "int<8|16|32>_t maxnodes" "struct TYPE *elm"
129fad4b12bSEdward Tomasz Napierala.Fn ARB_INITIALIZER "ARB_HEAD *head" "int<8|16|32>_t maxnodes"
130fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
131fad4b12bSEdward Tomasz Napierala.Fn ARB_ROOT "ARB_HEAD *head"
132fad4b12bSEdward Tomasz Napierala.Ft "bool"
133fad4b12bSEdward Tomasz Napierala.Fn ARB_EMPTY "ARB_HEAD *head"
134fad4b12bSEdward Tomasz Napierala.Ft "bool"
135fad4b12bSEdward Tomasz Napierala.Fn ARB_FULL "ARB_HEAD *head"
136fad4b12bSEdward Tomasz Napierala.Ft "int<8|16|32>_t"
137fad4b12bSEdward Tomasz Napierala.Fn ARB_CURNODES "ARB_HEAD *head"
138fad4b12bSEdward Tomasz Napierala.Ft "int<8|16|32>_t"
139fad4b12bSEdward Tomasz Napierala.Fn ARB_MAXNODES "ARB_HEAD *head"
140fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
141fad4b12bSEdward Tomasz Napierala.Fn ARB_NEXT NAME "ARB_HEAD *head" "struct TYPE *elm"
142fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
143fad4b12bSEdward Tomasz Napierala.Fn ARB_PREV NAME "ARB_HEAD *head" "struct TYPE *elm"
144fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
145fad4b12bSEdward Tomasz Napierala.Fn ARB_MIN NAME "ARB_HEAD *head"
146fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
147fad4b12bSEdward Tomasz Napierala.Fn ARB_MAX NAME "ARB_HEAD *head"
148fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
149fad4b12bSEdward Tomasz Napierala.Fn ARB_FIND NAME "ARB_HEAD *head" "struct TYPE *elm"
150fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
151fad4b12bSEdward Tomasz Napierala.Fn ARB_NFIND NAME "ARB_HEAD *head" "struct TYPE *elm"
152fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
153fad4b12bSEdward Tomasz Napierala.Fn ARB_LEFT "struct TYPE *elm" "ARB_ENTRY NAME"
154fad4b12bSEdward Tomasz Napierala.Ft "int<8|16|32>_t"
155fad4b12bSEdward Tomasz Napierala.Fn ARB_LEFTIDX "struct TYPE *elm" "ARB_ENTRY NAME"
156fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
157fad4b12bSEdward Tomasz Napierala.Fn ARB_RIGHT "struct TYPE *elm" "ARB_ENTRY NAME"
158fad4b12bSEdward Tomasz Napierala.Ft "int<8|16|32>_t"
159fad4b12bSEdward Tomasz Napierala.Fn ARB_RIGHTIDX "struct TYPE *elm" "ARB_ENTRY NAME"
160fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
161fad4b12bSEdward Tomasz Napierala.Fn ARB_PARENT "struct TYPE *elm" "ARB_ENTRY NAME"
162fad4b12bSEdward Tomasz Napierala.Ft "int<8|16|32>_t"
163fad4b12bSEdward Tomasz Napierala.Fn ARB_PARENTIDX "struct TYPE *elm" "ARB_ENTRY NAME"
164fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
165fad4b12bSEdward Tomasz Napierala.Fn ARB_GETFREE "ARB_HEAD *head" "FIELD"
166fad4b12bSEdward Tomasz Napierala.Ft "int<8|16|32>_t"
167fad4b12bSEdward Tomasz Napierala.Fn ARB_FREEIDX "ARB_HEAD *head"
168fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH VARNAME NAME "ARB_HEAD *head"
169fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME"
170fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_SAFE "VARNAME" "NAME" "ARB_HEAD *head" "TEMP_VARNAME"
171fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_REVERSE VARNAME NAME "ARB_HEAD *head"
172fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME"
173fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "ARB_HEAD *head" "TEMP_VARNAME"
174fad4b12bSEdward Tomasz Napierala.Ft void
175fad4b12bSEdward Tomasz Napierala.Fn ARB_INIT "struct TYPE *elm" "FIELD" "ARB_HEAD *head" "int<8|16|32>_t maxnodes"
176fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
177fad4b12bSEdward Tomasz Napierala.Fn ARB_INSERT NAME "ARB_HEAD *head" "struct TYPE *elm"
178fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
179fad4b12bSEdward Tomasz Napierala.Fn ARB_REMOVE NAME "ARB_HEAD *head" "struct TYPE *elm"
180*a5adff0eSEdward Tomasz Napierala.Ft "struct TYPE *"
181*a5adff0eSEdward Tomasz Napierala.Fn ARB_REINSERT NAME "ARB_HEAD *head" "struct TYPE *elm"
182fad4b12bSEdward Tomasz Napierala.Sh DESCRIPTION
183fad4b12bSEdward Tomasz NapieralaThese macros define data structures for and array-based red-black trees.
184fad4b12bSEdward Tomasz NapieralaThey use a single, continuous chunk of memory, and are useful
185fad4b12bSEdward Tomasz Napieralae.g., when the tree needs to be transferred between userspace and kernel.
186fad4b12bSEdward Tomasz Napierala.Pp
187fad4b12bSEdward Tomasz NapieralaIn the macro definitions,
188fad4b12bSEdward Tomasz Napierala.Fa TYPE
189fad4b12bSEdward Tomasz Napieralais the name tag of a user defined structure that must contain a field of type
190fad4b12bSEdward Tomasz Napierala.Vt ARB_ENTRY ,
191fad4b12bSEdward Tomasz Napieralanamed
192fad4b12bSEdward Tomasz Napierala.Fa ENTRYNAME .
193fad4b12bSEdward Tomasz NapieralaThe argument
194fad4b12bSEdward Tomasz Napierala.Fa HEADNAME
195fad4b12bSEdward Tomasz Napieralais the name tag of a user defined structure that must be declared
196fad4b12bSEdward Tomasz Napieralausing the
197fad4b12bSEdward Tomasz Napierala.Fn ARB_HEAD
198fad4b12bSEdward Tomasz Napieralamacro.
199fad4b12bSEdward Tomasz NapieralaThe argument
200fad4b12bSEdward Tomasz Napierala.Fa NAME
201fad4b12bSEdward Tomasz Napieralahas to be a unique name prefix for every tree that is defined.
202fad4b12bSEdward Tomasz Napierala.Pp
203fad4b12bSEdward Tomasz NapieralaThe function prototypes are declared with
204fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE ,
205fad4b12bSEdward Tomasz Napieralaor
206fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_STATIC .
207fad4b12bSEdward Tomasz NapieralaThe function bodies are generated with
208fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE ,
209fad4b12bSEdward Tomasz Napieralaor
210fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_STATIC .
211fad4b12bSEdward Tomasz NapieralaSee the examples below for further explanation of how these macros are used.
212fad4b12bSEdward Tomasz Napierala.Pp
213fad4b12bSEdward Tomasz NapieralaA red-black tree is a binary search tree with the node color as an
214fad4b12bSEdward Tomasz Napieralaextra attribute.
215fad4b12bSEdward Tomasz NapieralaIt fulfills a set of conditions:
216fad4b12bSEdward Tomasz Napierala.Bl -enum -offset indent
217fad4b12bSEdward Tomasz Napierala.It
218fad4b12bSEdward Tomasz NapieralaEvery search path from the root to a leaf consists of the same number of
219fad4b12bSEdward Tomasz Napieralablack nodes.
220fad4b12bSEdward Tomasz Napierala.It
221fad4b12bSEdward Tomasz NapieralaEach red node (except for the root) has a black parent.
222fad4b12bSEdward Tomasz Napierala.It
223fad4b12bSEdward Tomasz NapieralaEach leaf node is black.
224fad4b12bSEdward Tomasz Napierala.El
225fad4b12bSEdward Tomasz Napierala.Pp
226fad4b12bSEdward Tomasz NapieralaEvery operation on a red-black tree is bounded as
227fad4b12bSEdward Tomasz Napierala.Fn O "lg n" .
228fad4b12bSEdward Tomasz NapieralaThe maximum height of a red-black tree is
229fad4b12bSEdward Tomasz Napierala.Fn 2lg "n + 1" .
230fad4b12bSEdward Tomasz Napierala.Pp
231fad4b12bSEdward Tomasz Napierala.Fn ARB_*
232fad4b12bSEdward Tomasz Napieralatrees require entries to be allocated as an array, and uses array
233fad4b12bSEdward Tomasz Napieralaindices to link entries together.
234fad4b12bSEdward Tomasz NapieralaThe maximum number of
235fad4b12bSEdward Tomasz Napierala.Fn ARB_*
236fad4b12bSEdward Tomasz Napieralatree entries is therefore constrained by the minimum of array size and choice of
237fad4b12bSEdward Tomasz Napieralasigned integer data type used to store array indices.
238fad4b12bSEdward Tomasz NapieralaUse
239fad4b12bSEdward Tomasz Napierala.Fn ARB_ALLOCSIZE
240fad4b12bSEdward Tomasz Napieralato compute the size of memory chunk to allocate.
241fad4b12bSEdward Tomasz Napierala.Pp
242fad4b12bSEdward Tomasz NapieralaA red-black tree is headed by a structure defined by the
243fad4b12bSEdward Tomasz Napierala.Fn ARB_HEAD
244fad4b12bSEdward Tomasz Napieralamacro.
245fad4b12bSEdward Tomasz NapieralaA
246fad4b12bSEdward Tomasz Napieralastructure is declared with either of the following:
247fad4b12bSEdward Tomasz Napierala.Bd -ragged -offset indent
248fad4b12bSEdward Tomasz Napierala.Fn ARB<8|16|32>_HEAD HEADNAME TYPE
249fad4b12bSEdward Tomasz Napierala.Va head ;
250fad4b12bSEdward Tomasz Napierala.Ed
251fad4b12bSEdward Tomasz Napierala.Pp
252fad4b12bSEdward Tomasz Napieralawhere
253fad4b12bSEdward Tomasz Napierala.Fa HEADNAME
254fad4b12bSEdward Tomasz Napieralais the name of the structure to be defined, and struct
255fad4b12bSEdward Tomasz Napierala.Fa TYPE
256fad4b12bSEdward Tomasz Napieralais the type of the elements to be inserted into the tree.
257fad4b12bSEdward Tomasz Napierala.Pp
258fad4b12bSEdward Tomasz NapieralaThe
259fad4b12bSEdward Tomasz Napierala.Fn ARB_HEAD
260fad4b12bSEdward Tomasz Napieralavariant includes a suffix denoting the signed integer data type size
261fad4b12bSEdward Tomasz Napierala.Pq in bits
262fad4b12bSEdward Tomasz Napieralaused to store array indices.
263fad4b12bSEdward Tomasz NapieralaFor example,
264fad4b12bSEdward Tomasz Napierala.Fn ARB_HEAD8
265fad4b12bSEdward Tomasz Napieralacreates a red-black tree head strucutre with 8-bit signed array indices capable
266fad4b12bSEdward Tomasz Napieralaof indexing up to 128 entries.
267fad4b12bSEdward Tomasz Napierala.Pp
268fad4b12bSEdward Tomasz NapieralaThe
269fad4b12bSEdward Tomasz Napierala.Fn ARB_ENTRY
270fad4b12bSEdward Tomasz Napieralamacro declares a structure that allows elements to be connected in the tree.
271fad4b12bSEdward Tomasz NapieralaSimilarly to the
272fad4b12bSEdward Tomasz Napierala.Fn ARB<8|16|32>_HEAD
273fad4b12bSEdward Tomasz Napieralamacro, the
274fad4b12bSEdward Tomasz Napierala.Fn ARB_ENTRY
275fad4b12bSEdward Tomasz Napieralavariant includes a suffix denoting the signed integer data type size
276fad4b12bSEdward Tomasz Napierala.Pq in bits
277fad4b12bSEdward Tomasz Napieralaused to store array indices.
278fad4b12bSEdward Tomasz NapieralaEntries should use the same number of bits as the tree head structure they will
279fad4b12bSEdward Tomasz Napieralabe linked into.
280fad4b12bSEdward Tomasz Napierala.Pp
281fad4b12bSEdward Tomasz NapieralaIn order to use the functions that manipulate the tree structure,
282fad4b12bSEdward Tomasz Napieralatheir prototypes need to be declared with the
283fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE
284fad4b12bSEdward Tomasz Napieralaor
285fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_STATIC
286fad4b12bSEdward Tomasz Napieralamacro,
287fad4b12bSEdward Tomasz Napieralawhere
288fad4b12bSEdward Tomasz Napierala.Fa NAME
289fad4b12bSEdward Tomasz Napieralais a unique identifier for this particular tree.
290fad4b12bSEdward Tomasz NapieralaThe
291fad4b12bSEdward Tomasz Napierala.Fa TYPE
292fad4b12bSEdward Tomasz Napieralaargument is the type of the structure that is being managed
293fad4b12bSEdward Tomasz Napieralaby the tree.
294fad4b12bSEdward Tomasz NapieralaThe
295fad4b12bSEdward Tomasz Napierala.Fa FIELD
296fad4b12bSEdward Tomasz Napieralaargument is the name of the element defined by
297fad4b12bSEdward Tomasz Napierala.Fn ARB_ENTRY .
298fad4b12bSEdward Tomasz NapieralaIndividual prototypes can be declared with
299fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_INSERT ,
300fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_INSERT_COLOR ,
301fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_REMOVE ,
302fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_REMOVE_COLOR ,
303fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_FIND ,
304fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_NFIND ,
305fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_NEXT ,
306fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_PREV ,
307*a5adff0eSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_MINMAX ,
308fad4b12bSEdward Tomasz Napieralaand
309*a5adff0eSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_REINSERT
310fad4b12bSEdward Tomasz Napieralain case not all functions are required.
311fad4b12bSEdward Tomasz NapieralaThe individual prototype macros expect
312fad4b12bSEdward Tomasz Napierala.Fa NAME ,
313fad4b12bSEdward Tomasz Napierala.Fa TYPE ,
314fad4b12bSEdward Tomasz Napieralaand
315fad4b12bSEdward Tomasz Napierala.Fa ATTR
316fad4b12bSEdward Tomasz Napieralaarguments.
317fad4b12bSEdward Tomasz NapieralaThe
318fad4b12bSEdward Tomasz Napierala.Fa ATTR
319fad4b12bSEdward Tomasz Napieralaargument must be empty for global functions or
320fad4b12bSEdward Tomasz Napierala.Fa static
321fad4b12bSEdward Tomasz Napieralafor static functions.
322fad4b12bSEdward Tomasz Napierala.Pp
323fad4b12bSEdward Tomasz NapieralaThe function bodies are generated with the
324fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE
325fad4b12bSEdward Tomasz Napieralaor
326fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_STATIC
327fad4b12bSEdward Tomasz Napieralamacro.
328fad4b12bSEdward Tomasz NapieralaThese macros take the same arguments as the
329fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE
330fad4b12bSEdward Tomasz Napieralaand
331fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_STATIC
332fad4b12bSEdward Tomasz Napieralamacros, but should be used only once.
333fad4b12bSEdward Tomasz NapieralaAs an alternative individual function bodies are generated with the
334fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_INSERT ,
335fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_INSERT_COLOR ,
336fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_REMOVE ,
337fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_REMOVE_COLOR ,
338fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_FIND ,
339fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_NFIND ,
340fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_NEXT ,
341fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_PREV ,
342*a5adff0eSEdward Tomasz Napierala.Fn ARB_GENERATE_MINMAX ,
343fad4b12bSEdward Tomasz Napieralaand
344*a5adff0eSEdward Tomasz Napierala.Fn ARB_GENERATE_REINSERT
345fad4b12bSEdward Tomasz Napieralamacros.
346fad4b12bSEdward Tomasz Napierala.Pp
347fad4b12bSEdward Tomasz NapieralaFinally,
348fad4b12bSEdward Tomasz Napieralathe
349fad4b12bSEdward Tomasz Napierala.Fa CMP
350fad4b12bSEdward Tomasz Napieralaargument is the name of a function used to compare tree nodes
351fad4b12bSEdward Tomasz Napieralawith each other.
352fad4b12bSEdward Tomasz NapieralaThe function takes two arguments of type
353fad4b12bSEdward Tomasz Napierala.Vt "struct TYPE *" .
354fad4b12bSEdward Tomasz NapieralaIf the first argument is smaller than the second, the function returns a
355fad4b12bSEdward Tomasz Napieralavalue smaller than zero.
356fad4b12bSEdward Tomasz NapieralaIf they are equal, the function returns zero.
357fad4b12bSEdward Tomasz NapieralaOtherwise, it should return a value greater than zero.
358fad4b12bSEdward Tomasz NapieralaThe compare
359fad4b12bSEdward Tomasz Napieralafunction defines the order of the tree elements.
360fad4b12bSEdward Tomasz Napierala.Pp
361fad4b12bSEdward Tomasz NapieralaThe
362fad4b12bSEdward Tomasz Napierala.Fn ARB_INIT
363fad4b12bSEdward Tomasz Napieralamacro initializes the tree referenced by
364fad4b12bSEdward Tomasz Napierala.Fa head ,
365fad4b12bSEdward Tomasz Napieralawith the array length of
366fad4b12bSEdward Tomasz Napierala.Fa maxnodes .
367fad4b12bSEdward Tomasz Napierala.Pp
368fad4b12bSEdward Tomasz NapieralaThe red-black tree can also be initialized statically by using the
369fad4b12bSEdward Tomasz Napierala.Fn ARB_INITIALIZER
370fad4b12bSEdward Tomasz Napieralamacro:
371fad4b12bSEdward Tomasz Napierala.Bd -ragged -offset indent
372fad4b12bSEdward Tomasz Napierala.Fn ARB<8|16|32>_HEAD HEADNAME TYPE
373fad4b12bSEdward Tomasz Napierala.Va head
374fad4b12bSEdward Tomasz Napierala=
375fad4b12bSEdward Tomasz Napierala.Fn ARB_INITIALIZER &head maxnodes ;
376fad4b12bSEdward Tomasz Napierala.Ed
377fad4b12bSEdward Tomasz Napierala.Pp
378fad4b12bSEdward Tomasz NapieralaThe
379fad4b12bSEdward Tomasz Napierala.Fn ARB_INSERT
380fad4b12bSEdward Tomasz Napieralamacro inserts the new element
381fad4b12bSEdward Tomasz Napierala.Fa elm
382fad4b12bSEdward Tomasz Napieralainto the tree.
383fad4b12bSEdward Tomasz Napierala.Pp
384fad4b12bSEdward Tomasz NapieralaThe
385fad4b12bSEdward Tomasz Napierala.Fn ARB_REMOVE
386fad4b12bSEdward Tomasz Napieralamacro removes the element
387fad4b12bSEdward Tomasz Napierala.Fa elm
388fad4b12bSEdward Tomasz Napieralafrom the tree pointed by
389fad4b12bSEdward Tomasz Napierala.Fa head .
390fad4b12bSEdward Tomasz Napierala.Pp
391fad4b12bSEdward Tomasz NapieralaThe
392fad4b12bSEdward Tomasz Napierala.Fn ARB_FIND
393fad4b12bSEdward Tomasz Napieralaand
394fad4b12bSEdward Tomasz Napierala.Fn ARB_NFIND
395fad4b12bSEdward Tomasz Napieralamacros can be used to find a particular element in the tree.
396fad4b12bSEdward Tomasz Napierala.Bd -literal -offset indent
397fad4b12bSEdward Tomasz Napieralastruct TYPE find, *res;
398fad4b12bSEdward Tomasz Napieralafind.key = 30;
399fad4b12bSEdward Tomasz Napieralares = RB_FIND(NAME, head, &find);
400fad4b12bSEdward Tomasz Napierala.Ed
401fad4b12bSEdward Tomasz Napierala.Pp
402fad4b12bSEdward Tomasz NapieralaThe
403fad4b12bSEdward Tomasz Napierala.Fn ARB_ROOT ,
404fad4b12bSEdward Tomasz Napierala.Fn ARB_MIN ,
405fad4b12bSEdward Tomasz Napierala.Fn ARB_MAX ,
406fad4b12bSEdward Tomasz Napierala.Fn ARB_NEXT ,
407fad4b12bSEdward Tomasz Napieralaand
408fad4b12bSEdward Tomasz Napierala.Fn ARB_PREV
409fad4b12bSEdward Tomasz Napieralamacros can be used to traverse the tree:
410fad4b12bSEdward Tomasz Napierala.Pp
411fad4b12bSEdward Tomasz Napierala.Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))"
412fad4b12bSEdward Tomasz Napierala.Pp
413fad4b12bSEdward Tomasz NapieralaOr, for simplicity, one can use the
414fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH
415fad4b12bSEdward Tomasz Napieralaor
416fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_REVERSE
417fad4b12bSEdward Tomasz Napieralamacro:
418fad4b12bSEdward Tomasz Napierala.Bd -ragged -offset indent
419fad4b12bSEdward Tomasz Napierala.Fn RB_FOREACH np NAME head
420fad4b12bSEdward Tomasz Napierala.Ed
421fad4b12bSEdward Tomasz Napierala.Pp
422fad4b12bSEdward Tomasz NapieralaThe macros
423fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_SAFE
424fad4b12bSEdward Tomasz Napieralaand
425fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_REVERSE_SAFE
426fad4b12bSEdward Tomasz Napieralatraverse the tree referenced by head
427fad4b12bSEdward Tomasz Napieralain a forward or reverse direction respectively,
428fad4b12bSEdward Tomasz Napieralaassigning each element in turn to np.
429fad4b12bSEdward Tomasz NapieralaHowever, unlike their unsafe counterparts,
430fad4b12bSEdward Tomasz Napieralathey permit both the removal of np
431fad4b12bSEdward Tomasz Napieralaas well as freeing it from within the loop safely
432fad4b12bSEdward Tomasz Napieralawithout interfering with the traversal.
433fad4b12bSEdward Tomasz Napierala.Pp
434fad4b12bSEdward Tomasz NapieralaBoth
435fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_FROM
436fad4b12bSEdward Tomasz Napieralaand
437fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_REVERSE_FROM
438fad4b12bSEdward Tomasz Napieralamay be used to continue an interrupted traversal
439fad4b12bSEdward Tomasz Napieralain a forward or reverse direction respectively.
440fad4b12bSEdward Tomasz NapieralaThe head pointer is not required.
441fad4b12bSEdward Tomasz NapieralaThe pointer to the node from where to resume the traversal
442fad4b12bSEdward Tomasz Napieralashould be passed as their last argument,
443fad4b12bSEdward Tomasz Napieralaand will be overwritten to provide safe traversal.
444fad4b12bSEdward Tomasz Napierala.Pp
445fad4b12bSEdward Tomasz NapieralaThe
446fad4b12bSEdward Tomasz Napierala.Fn ARB_EMPTY
447fad4b12bSEdward Tomasz Napieralamacro should be used to check whether a red-black tree is empty.
448fad4b12bSEdward Tomasz Napierala.Pp
449fad4b12bSEdward Tomasz NapieralaGiven that ARB trees have an intrinsic upper bound on the number of entries,
450fad4b12bSEdward Tomasz Napieralasome ARB-specific additional macros are defined.
451fad4b12bSEdward Tomasz NapieralaThe
452fad4b12bSEdward Tomasz Napierala.Fn ARB_FULL
453fad4b12bSEdward Tomasz Napieralamacro returns a boolean indicating whether the current number of tree entries
454fad4b12bSEdward Tomasz Napieralaequals the tree's maximum.
455fad4b12bSEdward Tomasz NapieralaThe
456fad4b12bSEdward Tomasz Napierala.Fn ARB_CURNODES
457fad4b12bSEdward Tomasz Napieralaand
458fad4b12bSEdward Tomasz Napierala.Fn ARB_MAXNODES
459fad4b12bSEdward Tomasz Napieralamacros return the current and maximum number of entries respectively.
460fad4b12bSEdward Tomasz NapieralaThe
461fad4b12bSEdward Tomasz Napierala.Fn ARB_GETFREE
462fad4b12bSEdward Tomasz Napieralamacro returns a pointer to the next free entry in the array of entries, ready to
463fad4b12bSEdward Tomasz Napieralabe linked into the tree.
464fad4b12bSEdward Tomasz NapieralaThe
465fad4b12bSEdward Tomasz Napierala.Fn ARB_INSERT
466fad4b12bSEdward Tomasz Napieralareturns
467fad4b12bSEdward Tomasz Napierala.Dv NULL
468fad4b12bSEdward Tomasz Napieralaif the element was inserted in the tree successfully, otherwise they
469fad4b12bSEdward Tomasz Napieralareturn a pointer to the element with the colliding key.
470fad4b12bSEdward Tomasz Napierala.Pp
471fad4b12bSEdward Tomasz NapieralaAccordingly,
472fad4b12bSEdward Tomasz Napierala.Fn ARB_REMOVE
473fad4b12bSEdward Tomasz Napieralareturns the pointer to the removed element otherwise they return
474fad4b12bSEdward Tomasz Napierala.Dv NULL
475fad4b12bSEdward Tomasz Napieralato indicate an error.
476*a5adff0eSEdward Tomasz Napierala.Pp
477*a5adff0eSEdward Tomasz NapieralaThe
478*a5adff0eSEdward Tomasz Napierala.Fn RB_REINSERT
479*a5adff0eSEdward Tomasz Napieralamacro updates the position of the element
480*a5adff0eSEdward Tomasz Napierala.Fa elm
481*a5adff0eSEdward Tomasz Napieralain the tree.
482*a5adff0eSEdward Tomasz NapieralaThis must be called if a member of a
483*a5adff0eSEdward Tomasz Napierala.Nm tree
484*a5adff0eSEdward Tomasz Napieralais modified in a way that affects comparison, such as by modifying
485*a5adff0eSEdward Tomasz Napieralaa node's key.
486*a5adff0eSEdward Tomasz NapieralaThis is a lower overhead alternative to removing the element
487*a5adff0eSEdward Tomasz Napieralaand reinserting it again.
488fad4b12bSEdward Tomasz Napierala.Sh SEE ALSO
489fad4b12bSEdward Tomasz Napierala.Xr queue 3 ,
490fad4b12bSEdward Tomasz Napierala.Xr tree 3
491fad4b12bSEdward Tomasz Napierala.Sh HISTORY
492fad4b12bSEdward Tomasz NapieralaThe
493fad4b12bSEdward Tomasz Napierala.Nm ARB
494fad4b12bSEdward Tomasz Napieralamacros first appeared in
495fad4b12bSEdward Tomasz Napierala.Fx 13.0 .
496fad4b12bSEdward Tomasz Napierala.Sh AUTHORS
497fad4b12bSEdward Tomasz NapieralaThe
498fad4b12bSEdward Tomasz Napierala.Nm ARB
499fad4b12bSEdward Tomasz Napieralamacros were implemented by
500fad4b12bSEdward Tomasz Napierala.An Lawrence Stewart Aq Mt lstewart@FreeBSD.org ,
501fad4b12bSEdward Tomasz Napieralabased on
502fad4b12bSEdward Tomasz Napierala.Xr tree 3
503fad4b12bSEdward Tomasz Napieralamacros written by
504fad4b12bSEdward Tomasz Napierala.An Niels Provos .
505