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