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