xref: /freebsd/share/man/man3/arb.3 (revision 1a13f2e6b444dd8048aebd2ac1f0b8fae9e3088f) 
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*1a13f2e6SEdward Tomasz Napierala.Dd October 2, 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 ,
48a5adff0eSEdward 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 ,
60a5adff0eSEdward 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 ,
96a5adff0eSEdward Tomasz Napierala.Nm ARB_REMOVE ,
97*1a13f2e6SEdward Tomasz Napierala.Nm ARB_REINSERT ,
98*1a13f2e6SEdward Tomasz Napierala.Nm ARB_RESET_TREE
99fad4b12bSEdward Tomasz Napierala.Nd "array-based red-black trees"
100fad4b12bSEdward Tomasz Napierala.Sh SYNOPSIS
101fad4b12bSEdward Tomasz Napierala.In sys/arb.h
102fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE NAME TYPE FIELD CMP
103fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
104fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_INSERT NAME TYPE ATTR
105fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR
106fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_REMOVE NAME TYPE ATTR
107fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR
108fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_FIND NAME TYPE ATTR
109fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_NFIND NAME TYPE ATTR
110fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_NEXT NAME TYPE ATTR
111fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_PREV NAME TYPE ATTR
112fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_MINMAX NAME TYPE ATTR
113a5adff0eSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_REINSERT NAME TYPE ATTR
114fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE NAME TYPE FIELD CMP
115fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_STATIC NAME TYPE FIELD CMP
116fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR
117fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR
118fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_REMOVE NAME TYPE FIELD ATTR
119fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR
120fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_FIND NAME TYPE FIELD CMP ATTR
121fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR
122fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_NEXT NAME TYPE FIELD ATTR
123fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_PREV NAME TYPE FIELD ATTR
124fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_MINMAX NAME TYPE FIELD ATTR
125a5adff0eSEdward Tomasz Napierala.Fn ARB_GENERATE_REINSERT NAME TYPE FIELD CMP ATTR
126fad4b12bSEdward Tomasz Napierala.Fn ARB<8|16|32>_ENTRY
127fad4b12bSEdward Tomasz Napierala.Fn ARB<8|16|32>_HEAD HEADNAME TYPE
128fad4b12bSEdward Tomasz Napierala.Ft "size_t"
129fad4b12bSEdward Tomasz Napierala.Fn ARB_ALLOCSIZE "ARB_HEAD *head" "int<8|16|32>_t maxnodes" "struct TYPE *elm"
130fad4b12bSEdward Tomasz Napierala.Fn ARB_INITIALIZER "ARB_HEAD *head" "int<8|16|32>_t maxnodes"
131fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
132fad4b12bSEdward Tomasz Napierala.Fn ARB_ROOT "ARB_HEAD *head"
133fad4b12bSEdward Tomasz Napierala.Ft "bool"
134fad4b12bSEdward Tomasz Napierala.Fn ARB_EMPTY "ARB_HEAD *head"
135fad4b12bSEdward Tomasz Napierala.Ft "bool"
136fad4b12bSEdward Tomasz Napierala.Fn ARB_FULL "ARB_HEAD *head"
137fad4b12bSEdward Tomasz Napierala.Ft "int<8|16|32>_t"
138fad4b12bSEdward Tomasz Napierala.Fn ARB_CURNODES "ARB_HEAD *head"
139fad4b12bSEdward Tomasz Napierala.Ft "int<8|16|32>_t"
140fad4b12bSEdward Tomasz Napierala.Fn ARB_MAXNODES "ARB_HEAD *head"
141fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
142fad4b12bSEdward Tomasz Napierala.Fn ARB_NEXT NAME "ARB_HEAD *head" "struct TYPE *elm"
143fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
144fad4b12bSEdward Tomasz Napierala.Fn ARB_PREV NAME "ARB_HEAD *head" "struct TYPE *elm"
145fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
146fad4b12bSEdward Tomasz Napierala.Fn ARB_MIN NAME "ARB_HEAD *head"
147fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
148fad4b12bSEdward Tomasz Napierala.Fn ARB_MAX NAME "ARB_HEAD *head"
149fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
150fad4b12bSEdward Tomasz Napierala.Fn ARB_FIND NAME "ARB_HEAD *head" "struct TYPE *elm"
151fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
152fad4b12bSEdward Tomasz Napierala.Fn ARB_NFIND NAME "ARB_HEAD *head" "struct TYPE *elm"
153fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
154fad4b12bSEdward Tomasz Napierala.Fn ARB_LEFT "struct TYPE *elm" "ARB_ENTRY NAME"
155fad4b12bSEdward Tomasz Napierala.Ft "int<8|16|32>_t"
156fad4b12bSEdward Tomasz Napierala.Fn ARB_LEFTIDX "struct TYPE *elm" "ARB_ENTRY NAME"
157fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
158fad4b12bSEdward Tomasz Napierala.Fn ARB_RIGHT "struct TYPE *elm" "ARB_ENTRY NAME"
159fad4b12bSEdward Tomasz Napierala.Ft "int<8|16|32>_t"
160fad4b12bSEdward Tomasz Napierala.Fn ARB_RIGHTIDX "struct TYPE *elm" "ARB_ENTRY NAME"
161fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
162fad4b12bSEdward Tomasz Napierala.Fn ARB_PARENT "struct TYPE *elm" "ARB_ENTRY NAME"
163fad4b12bSEdward Tomasz Napierala.Ft "int<8|16|32>_t"
164fad4b12bSEdward Tomasz Napierala.Fn ARB_PARENTIDX "struct TYPE *elm" "ARB_ENTRY NAME"
165fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
166fad4b12bSEdward Tomasz Napierala.Fn ARB_GETFREE "ARB_HEAD *head" "FIELD"
167fad4b12bSEdward Tomasz Napierala.Ft "int<8|16|32>_t"
168fad4b12bSEdward Tomasz Napierala.Fn ARB_FREEIDX "ARB_HEAD *head"
169fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH VARNAME NAME "ARB_HEAD *head"
170fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME"
171fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_SAFE "VARNAME" "NAME" "ARB_HEAD *head" "TEMP_VARNAME"
172fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_REVERSE VARNAME NAME "ARB_HEAD *head"
173fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME"
174fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "ARB_HEAD *head" "TEMP_VARNAME"
175fad4b12bSEdward Tomasz Napierala.Ft void
176fad4b12bSEdward Tomasz Napierala.Fn ARB_INIT "struct TYPE *elm" "FIELD" "ARB_HEAD *head" "int<8|16|32>_t maxnodes"
177fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
178fad4b12bSEdward Tomasz Napierala.Fn ARB_INSERT NAME "ARB_HEAD *head" "struct TYPE *elm"
179fad4b12bSEdward Tomasz Napierala.Ft "struct TYPE *"
180fad4b12bSEdward Tomasz Napierala.Fn ARB_REMOVE NAME "ARB_HEAD *head" "struct TYPE *elm"
181a5adff0eSEdward Tomasz Napierala.Ft "struct TYPE *"
182a5adff0eSEdward Tomasz Napierala.Fn ARB_REINSERT NAME "ARB_HEAD *head" "struct TYPE *elm"
183*1a13f2e6SEdward Tomasz Napierala.Ft void
184*1a13f2e6SEdward Tomasz Napierala.Fn ARB_RESET_TREE "ARB_HEAD *head" NAME "int<8|16|32>_t maxnodes"
185fad4b12bSEdward Tomasz Napierala.Sh DESCRIPTION
186fad4b12bSEdward Tomasz NapieralaThese macros define data structures for and array-based red-black trees.
187fad4b12bSEdward Tomasz NapieralaThey use a single, continuous chunk of memory, and are useful
188fad4b12bSEdward Tomasz Napieralae.g., when the tree needs to be transferred between userspace and kernel.
189fad4b12bSEdward Tomasz Napierala.Pp
190fad4b12bSEdward Tomasz NapieralaIn the macro definitions,
191fad4b12bSEdward Tomasz Napierala.Fa TYPE
192fad4b12bSEdward Tomasz Napieralais the name tag of a user defined structure that must contain a field of type
193fad4b12bSEdward Tomasz Napierala.Vt ARB_ENTRY ,
194fad4b12bSEdward Tomasz Napieralanamed
195fad4b12bSEdward Tomasz Napierala.Fa ENTRYNAME .
196fad4b12bSEdward Tomasz NapieralaThe argument
197fad4b12bSEdward Tomasz Napierala.Fa HEADNAME
198fad4b12bSEdward Tomasz Napieralais the name tag of a user defined structure that must be declared
199fad4b12bSEdward Tomasz Napieralausing the
200fad4b12bSEdward Tomasz Napierala.Fn ARB_HEAD
201fad4b12bSEdward Tomasz Napieralamacro.
202fad4b12bSEdward Tomasz NapieralaThe argument
203fad4b12bSEdward Tomasz Napierala.Fa NAME
204fad4b12bSEdward Tomasz Napieralahas to be a unique name prefix for every tree that is defined.
205fad4b12bSEdward Tomasz Napierala.Pp
206fad4b12bSEdward Tomasz NapieralaThe function prototypes are declared with
207fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE ,
208fad4b12bSEdward Tomasz Napieralaor
209fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_STATIC .
210fad4b12bSEdward Tomasz NapieralaThe function bodies are generated with
211fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE ,
212fad4b12bSEdward Tomasz Napieralaor
213fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_STATIC .
214fad4b12bSEdward Tomasz NapieralaSee the examples below for further explanation of how these macros are used.
215fad4b12bSEdward Tomasz Napierala.Pp
216fad4b12bSEdward Tomasz NapieralaA red-black tree is a binary search tree with the node color as an
217fad4b12bSEdward Tomasz Napieralaextra attribute.
218fad4b12bSEdward Tomasz NapieralaIt fulfills a set of conditions:
219fad4b12bSEdward Tomasz Napierala.Bl -enum -offset indent
220fad4b12bSEdward Tomasz Napierala.It
221fad4b12bSEdward Tomasz NapieralaEvery search path from the root to a leaf consists of the same number of
222fad4b12bSEdward Tomasz Napieralablack nodes.
223fad4b12bSEdward Tomasz Napierala.It
224fad4b12bSEdward Tomasz NapieralaEach red node (except for the root) has a black parent.
225fad4b12bSEdward Tomasz Napierala.It
226fad4b12bSEdward Tomasz NapieralaEach leaf node is black.
227fad4b12bSEdward Tomasz Napierala.El
228fad4b12bSEdward Tomasz Napierala.Pp
229fad4b12bSEdward Tomasz NapieralaEvery operation on a red-black tree is bounded as
230fad4b12bSEdward Tomasz Napierala.Fn O "lg n" .
231fad4b12bSEdward Tomasz NapieralaThe maximum height of a red-black tree is
232fad4b12bSEdward Tomasz Napierala.Fn 2lg "n + 1" .
233fad4b12bSEdward Tomasz Napierala.Pp
234fad4b12bSEdward Tomasz Napierala.Fn ARB_*
235fad4b12bSEdward Tomasz Napieralatrees require entries to be allocated as an array, and uses array
236fad4b12bSEdward Tomasz Napieralaindices to link entries together.
237fad4b12bSEdward Tomasz NapieralaThe maximum number of
238fad4b12bSEdward Tomasz Napierala.Fn ARB_*
239fad4b12bSEdward Tomasz Napieralatree entries is therefore constrained by the minimum of array size and choice of
240fad4b12bSEdward Tomasz Napieralasigned integer data type used to store array indices.
241fad4b12bSEdward Tomasz NapieralaUse
242fad4b12bSEdward Tomasz Napierala.Fn ARB_ALLOCSIZE
243fad4b12bSEdward Tomasz Napieralato compute the size of memory chunk to allocate.
244fad4b12bSEdward Tomasz Napierala.Pp
245fad4b12bSEdward Tomasz NapieralaA red-black tree is headed by a structure defined by the
246fad4b12bSEdward Tomasz Napierala.Fn ARB_HEAD
247fad4b12bSEdward Tomasz Napieralamacro.
248fad4b12bSEdward Tomasz NapieralaA
249fad4b12bSEdward Tomasz Napieralastructure is declared with either of the following:
250fad4b12bSEdward Tomasz Napierala.Bd -ragged -offset indent
251fad4b12bSEdward Tomasz Napierala.Fn ARB<8|16|32>_HEAD HEADNAME TYPE
252fad4b12bSEdward Tomasz Napierala.Va head ;
253fad4b12bSEdward Tomasz Napierala.Ed
254fad4b12bSEdward Tomasz Napierala.Pp
255fad4b12bSEdward Tomasz Napieralawhere
256fad4b12bSEdward Tomasz Napierala.Fa HEADNAME
257fad4b12bSEdward Tomasz Napieralais the name of the structure to be defined, and struct
258fad4b12bSEdward Tomasz Napierala.Fa TYPE
259fad4b12bSEdward Tomasz Napieralais the type of the elements to be inserted into the tree.
260fad4b12bSEdward Tomasz Napierala.Pp
261fad4b12bSEdward Tomasz NapieralaThe
262fad4b12bSEdward Tomasz Napierala.Fn ARB_HEAD
263fad4b12bSEdward Tomasz Napieralavariant includes a suffix denoting the signed integer data type size
264fad4b12bSEdward Tomasz Napierala.Pq in bits
265fad4b12bSEdward Tomasz Napieralaused to store array indices.
266fad4b12bSEdward Tomasz NapieralaFor example,
267fad4b12bSEdward Tomasz Napierala.Fn ARB_HEAD8
268fad4b12bSEdward Tomasz Napieralacreates a red-black tree head strucutre with 8-bit signed array indices capable
269fad4b12bSEdward Tomasz Napieralaof indexing up to 128 entries.
270fad4b12bSEdward Tomasz Napierala.Pp
271fad4b12bSEdward Tomasz NapieralaThe
272fad4b12bSEdward Tomasz Napierala.Fn ARB_ENTRY
273fad4b12bSEdward Tomasz Napieralamacro declares a structure that allows elements to be connected in the tree.
274fad4b12bSEdward Tomasz NapieralaSimilarly to the
275fad4b12bSEdward Tomasz Napierala.Fn ARB<8|16|32>_HEAD
276fad4b12bSEdward Tomasz Napieralamacro, the
277fad4b12bSEdward Tomasz Napierala.Fn ARB_ENTRY
278fad4b12bSEdward Tomasz Napieralavariant includes a suffix denoting the signed integer data type size
279fad4b12bSEdward Tomasz Napierala.Pq in bits
280fad4b12bSEdward Tomasz Napieralaused to store array indices.
281fad4b12bSEdward Tomasz NapieralaEntries should use the same number of bits as the tree head structure they will
282fad4b12bSEdward Tomasz Napieralabe linked into.
283fad4b12bSEdward Tomasz Napierala.Pp
284fad4b12bSEdward Tomasz NapieralaIn order to use the functions that manipulate the tree structure,
285fad4b12bSEdward Tomasz Napieralatheir prototypes need to be declared with the
286fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE
287fad4b12bSEdward Tomasz Napieralaor
288fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_STATIC
289fad4b12bSEdward Tomasz Napieralamacro,
290fad4b12bSEdward Tomasz Napieralawhere
291fad4b12bSEdward Tomasz Napierala.Fa NAME
292fad4b12bSEdward Tomasz Napieralais a unique identifier for this particular tree.
293fad4b12bSEdward Tomasz NapieralaThe
294fad4b12bSEdward Tomasz Napierala.Fa TYPE
295fad4b12bSEdward Tomasz Napieralaargument is the type of the structure that is being managed
296fad4b12bSEdward Tomasz Napieralaby the tree.
297fad4b12bSEdward Tomasz NapieralaThe
298fad4b12bSEdward Tomasz Napierala.Fa FIELD
299fad4b12bSEdward Tomasz Napieralaargument is the name of the element defined by
300fad4b12bSEdward Tomasz Napierala.Fn ARB_ENTRY .
301fad4b12bSEdward Tomasz NapieralaIndividual prototypes can be declared with
302fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_INSERT ,
303fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_INSERT_COLOR ,
304fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_REMOVE ,
305fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_REMOVE_COLOR ,
306fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_FIND ,
307fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_NFIND ,
308fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_NEXT ,
309fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_PREV ,
310a5adff0eSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_MINMAX ,
311fad4b12bSEdward Tomasz Napieralaand
312a5adff0eSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_REINSERT
313fad4b12bSEdward Tomasz Napieralain case not all functions are required.
314fad4b12bSEdward Tomasz NapieralaThe individual prototype macros expect
315fad4b12bSEdward Tomasz Napierala.Fa NAME ,
316fad4b12bSEdward Tomasz Napierala.Fa TYPE ,
317fad4b12bSEdward Tomasz Napieralaand
318fad4b12bSEdward Tomasz Napierala.Fa ATTR
319fad4b12bSEdward Tomasz Napieralaarguments.
320fad4b12bSEdward Tomasz NapieralaThe
321fad4b12bSEdward Tomasz Napierala.Fa ATTR
322fad4b12bSEdward Tomasz Napieralaargument must be empty for global functions or
323fad4b12bSEdward Tomasz Napierala.Fa static
324fad4b12bSEdward Tomasz Napieralafor static functions.
325fad4b12bSEdward Tomasz Napierala.Pp
326fad4b12bSEdward Tomasz NapieralaThe function bodies are generated with the
327fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE
328fad4b12bSEdward Tomasz Napieralaor
329fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_STATIC
330fad4b12bSEdward Tomasz Napieralamacro.
331fad4b12bSEdward Tomasz NapieralaThese macros take the same arguments as the
332fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE
333fad4b12bSEdward Tomasz Napieralaand
334fad4b12bSEdward Tomasz Napierala.Fn ARB_PROTOTYPE_STATIC
335fad4b12bSEdward Tomasz Napieralamacros, but should be used only once.
336fad4b12bSEdward Tomasz NapieralaAs an alternative individual function bodies are generated with the
337fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_INSERT ,
338fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_INSERT_COLOR ,
339fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_REMOVE ,
340fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_REMOVE_COLOR ,
341fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_FIND ,
342fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_NFIND ,
343fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_NEXT ,
344fad4b12bSEdward Tomasz Napierala.Fn ARB_GENERATE_PREV ,
345a5adff0eSEdward Tomasz Napierala.Fn ARB_GENERATE_MINMAX ,
346fad4b12bSEdward Tomasz Napieralaand
347a5adff0eSEdward Tomasz Napierala.Fn ARB_GENERATE_REINSERT
348fad4b12bSEdward Tomasz Napieralamacros.
349fad4b12bSEdward Tomasz Napierala.Pp
350fad4b12bSEdward Tomasz NapieralaFinally,
351fad4b12bSEdward Tomasz Napieralathe
352fad4b12bSEdward Tomasz Napierala.Fa CMP
353fad4b12bSEdward Tomasz Napieralaargument is the name of a function used to compare tree nodes
354fad4b12bSEdward Tomasz Napieralawith each other.
355fad4b12bSEdward Tomasz NapieralaThe function takes two arguments of type
356fad4b12bSEdward Tomasz Napierala.Vt "struct TYPE *" .
357fad4b12bSEdward Tomasz NapieralaIf the first argument is smaller than the second, the function returns a
358fad4b12bSEdward Tomasz Napieralavalue smaller than zero.
359fad4b12bSEdward Tomasz NapieralaIf they are equal, the function returns zero.
360fad4b12bSEdward Tomasz NapieralaOtherwise, it should return a value greater than zero.
361fad4b12bSEdward Tomasz NapieralaThe compare
362fad4b12bSEdward Tomasz Napieralafunction defines the order of the tree elements.
363fad4b12bSEdward Tomasz Napierala.Pp
364fad4b12bSEdward Tomasz NapieralaThe
365fad4b12bSEdward Tomasz Napierala.Fn ARB_INIT
366fad4b12bSEdward Tomasz Napieralamacro initializes the tree referenced by
367fad4b12bSEdward Tomasz Napierala.Fa head ,
368fad4b12bSEdward Tomasz Napieralawith the array length of
369fad4b12bSEdward Tomasz Napierala.Fa maxnodes .
370fad4b12bSEdward Tomasz Napierala.Pp
371fad4b12bSEdward Tomasz NapieralaThe red-black tree can also be initialized statically by using the
372fad4b12bSEdward Tomasz Napierala.Fn ARB_INITIALIZER
373fad4b12bSEdward Tomasz Napieralamacro:
374fad4b12bSEdward Tomasz Napierala.Bd -ragged -offset indent
375fad4b12bSEdward Tomasz Napierala.Fn ARB<8|16|32>_HEAD HEADNAME TYPE
376fad4b12bSEdward Tomasz Napierala.Va head
377fad4b12bSEdward Tomasz Napierala=
378fad4b12bSEdward Tomasz Napierala.Fn ARB_INITIALIZER &head maxnodes ;
379fad4b12bSEdward Tomasz Napierala.Ed
380fad4b12bSEdward Tomasz Napierala.Pp
381fad4b12bSEdward Tomasz NapieralaThe
382fad4b12bSEdward Tomasz Napierala.Fn ARB_INSERT
383fad4b12bSEdward Tomasz Napieralamacro inserts the new element
384fad4b12bSEdward Tomasz Napierala.Fa elm
385fad4b12bSEdward Tomasz Napieralainto the tree.
386fad4b12bSEdward Tomasz Napierala.Pp
387fad4b12bSEdward Tomasz NapieralaThe
388fad4b12bSEdward Tomasz Napierala.Fn ARB_REMOVE
389fad4b12bSEdward Tomasz Napieralamacro removes the element
390fad4b12bSEdward Tomasz Napierala.Fa elm
391fad4b12bSEdward Tomasz Napieralafrom the tree pointed by
392fad4b12bSEdward Tomasz Napierala.Fa head .
393fad4b12bSEdward Tomasz Napierala.Pp
394fad4b12bSEdward Tomasz NapieralaThe
395fad4b12bSEdward Tomasz Napierala.Fn ARB_FIND
396fad4b12bSEdward Tomasz Napieralaand
397fad4b12bSEdward Tomasz Napierala.Fn ARB_NFIND
398fad4b12bSEdward Tomasz Napieralamacros can be used to find a particular element in the tree.
399fad4b12bSEdward Tomasz Napierala.Bd -literal -offset indent
400fad4b12bSEdward Tomasz Napieralastruct TYPE find, *res;
401fad4b12bSEdward Tomasz Napieralafind.key = 30;
402fad4b12bSEdward Tomasz Napieralares = RB_FIND(NAME, head, &find);
403fad4b12bSEdward Tomasz Napierala.Ed
404fad4b12bSEdward Tomasz Napierala.Pp
405fad4b12bSEdward Tomasz NapieralaThe
406fad4b12bSEdward Tomasz Napierala.Fn ARB_ROOT ,
407fad4b12bSEdward Tomasz Napierala.Fn ARB_MIN ,
408fad4b12bSEdward Tomasz Napierala.Fn ARB_MAX ,
409fad4b12bSEdward Tomasz Napierala.Fn ARB_NEXT ,
410fad4b12bSEdward Tomasz Napieralaand
411fad4b12bSEdward Tomasz Napierala.Fn ARB_PREV
412fad4b12bSEdward Tomasz Napieralamacros can be used to traverse the tree:
413fad4b12bSEdward Tomasz Napierala.Pp
414fad4b12bSEdward Tomasz Napierala.Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))"
415fad4b12bSEdward Tomasz Napierala.Pp
416fad4b12bSEdward Tomasz NapieralaOr, for simplicity, one can use the
417fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH
418fad4b12bSEdward Tomasz Napieralaor
419fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_REVERSE
420fad4b12bSEdward Tomasz Napieralamacro:
421fad4b12bSEdward Tomasz Napierala.Bd -ragged -offset indent
422fad4b12bSEdward Tomasz Napierala.Fn RB_FOREACH np NAME head
423fad4b12bSEdward Tomasz Napierala.Ed
424fad4b12bSEdward Tomasz Napierala.Pp
425fad4b12bSEdward Tomasz NapieralaThe macros
426fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_SAFE
427fad4b12bSEdward Tomasz Napieralaand
428fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_REVERSE_SAFE
429fad4b12bSEdward Tomasz Napieralatraverse the tree referenced by head
430fad4b12bSEdward Tomasz Napieralain a forward or reverse direction respectively,
431fad4b12bSEdward Tomasz Napieralaassigning each element in turn to np.
432fad4b12bSEdward Tomasz NapieralaHowever, unlike their unsafe counterparts,
433fad4b12bSEdward Tomasz Napieralathey permit both the removal of np
434fad4b12bSEdward Tomasz Napieralaas well as freeing it from within the loop safely
435fad4b12bSEdward Tomasz Napieralawithout interfering with the traversal.
436fad4b12bSEdward Tomasz Napierala.Pp
437fad4b12bSEdward Tomasz NapieralaBoth
438fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_FROM
439fad4b12bSEdward Tomasz Napieralaand
440fad4b12bSEdward Tomasz Napierala.Fn ARB_FOREACH_REVERSE_FROM
441fad4b12bSEdward Tomasz Napieralamay be used to continue an interrupted traversal
442fad4b12bSEdward Tomasz Napieralain a forward or reverse direction respectively.
443fad4b12bSEdward Tomasz NapieralaThe head pointer is not required.
444fad4b12bSEdward Tomasz NapieralaThe pointer to the node from where to resume the traversal
445fad4b12bSEdward Tomasz Napieralashould be passed as their last argument,
446fad4b12bSEdward Tomasz Napieralaand will be overwritten to provide safe traversal.
447fad4b12bSEdward Tomasz Napierala.Pp
448fad4b12bSEdward Tomasz NapieralaThe
449fad4b12bSEdward Tomasz Napierala.Fn ARB_EMPTY
450fad4b12bSEdward Tomasz Napieralamacro should be used to check whether a red-black tree is empty.
451fad4b12bSEdward Tomasz Napierala.Pp
452fad4b12bSEdward Tomasz NapieralaGiven that ARB trees have an intrinsic upper bound on the number of entries,
453fad4b12bSEdward Tomasz Napieralasome ARB-specific additional macros are defined.
454fad4b12bSEdward Tomasz NapieralaThe
455fad4b12bSEdward Tomasz Napierala.Fn ARB_FULL
456fad4b12bSEdward Tomasz Napieralamacro returns a boolean indicating whether the current number of tree entries
457fad4b12bSEdward Tomasz Napieralaequals the tree's maximum.
458fad4b12bSEdward Tomasz NapieralaThe
459fad4b12bSEdward Tomasz Napierala.Fn ARB_CURNODES
460fad4b12bSEdward Tomasz Napieralaand
461fad4b12bSEdward Tomasz Napierala.Fn ARB_MAXNODES
462fad4b12bSEdward Tomasz Napieralamacros return the current and maximum number of entries respectively.
463fad4b12bSEdward Tomasz NapieralaThe
464fad4b12bSEdward Tomasz Napierala.Fn ARB_GETFREE
465fad4b12bSEdward Tomasz Napieralamacro returns a pointer to the next free entry in the array of entries, ready to
466fad4b12bSEdward Tomasz Napieralabe linked into the tree.
467fad4b12bSEdward Tomasz NapieralaThe
468fad4b12bSEdward Tomasz Napierala.Fn ARB_INSERT
469fad4b12bSEdward Tomasz Napieralareturns
470fad4b12bSEdward Tomasz Napierala.Dv NULL
471fad4b12bSEdward Tomasz Napieralaif the element was inserted in the tree successfully, otherwise they
472fad4b12bSEdward Tomasz Napieralareturn a pointer to the element with the colliding key.
473fad4b12bSEdward Tomasz Napierala.Pp
474fad4b12bSEdward Tomasz NapieralaAccordingly,
475fad4b12bSEdward Tomasz Napierala.Fn ARB_REMOVE
476fad4b12bSEdward Tomasz Napieralareturns the pointer to the removed element otherwise they return
477fad4b12bSEdward Tomasz Napierala.Dv NULL
478fad4b12bSEdward Tomasz Napieralato indicate an error.
479a5adff0eSEdward Tomasz Napierala.Pp
480a5adff0eSEdward Tomasz NapieralaThe
481*1a13f2e6SEdward Tomasz Napierala.Fn ARB_REINSERT
482a5adff0eSEdward Tomasz Napieralamacro updates the position of the element
483a5adff0eSEdward Tomasz Napierala.Fa elm
484a5adff0eSEdward Tomasz Napieralain the tree.
485a5adff0eSEdward Tomasz NapieralaThis must be called if a member of a
486a5adff0eSEdward Tomasz Napierala.Nm tree
487a5adff0eSEdward Tomasz Napieralais modified in a way that affects comparison, such as by modifying
488a5adff0eSEdward Tomasz Napieralaa node's key.
489a5adff0eSEdward Tomasz NapieralaThis is a lower overhead alternative to removing the element
490a5adff0eSEdward Tomasz Napieralaand reinserting it again.
491*1a13f2e6SEdward Tomasz Napierala.Pp
492*1a13f2e6SEdward Tomasz NapieralaThe
493*1a13f2e6SEdward Tomasz Napierala.Fn ARB_RESET_TREE
494*1a13f2e6SEdward Tomasz Napieralamacro discards the tree topology.
495*1a13f2e6SEdward Tomasz NapieralaIt does not modify embedded object values or the free list.
496fad4b12bSEdward Tomasz Napierala.Sh SEE ALSO
497fad4b12bSEdward Tomasz Napierala.Xr queue 3 ,
498fad4b12bSEdward Tomasz Napierala.Xr tree 3
499fad4b12bSEdward Tomasz Napierala.Sh HISTORY
500fad4b12bSEdward Tomasz NapieralaThe
501fad4b12bSEdward Tomasz Napierala.Nm ARB
502fad4b12bSEdward Tomasz Napieralamacros first appeared in
503fad4b12bSEdward Tomasz Napierala.Fx 13.0 .
504fad4b12bSEdward Tomasz Napierala.Sh AUTHORS
505fad4b12bSEdward Tomasz NapieralaThe
506fad4b12bSEdward Tomasz Napierala.Nm ARB
507fad4b12bSEdward Tomasz Napieralamacros were implemented by
508fad4b12bSEdward Tomasz Napierala.An Lawrence Stewart Aq Mt lstewart@FreeBSD.org ,
509fad4b12bSEdward Tomasz Napieralabased on
510fad4b12bSEdward Tomasz Napierala.Xr tree 3
511fad4b12bSEdward Tomasz Napieralamacros written by
512fad4b12bSEdward Tomasz Napierala.An Niels Provos .
513