1 .\" $OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $
3 .\" Copyright 2002 Niels Provos <provos@citi.umich.edu>
4 .\" Copyright 2018-2019 Netflix, Inc.
5 .\" All rights reserved.
7 .\" Redistribution and use in source and binary forms, with or without
8 .\" modification, are permitted provided that the following conditions
10 .\" 1. Redistributions of source code must retain the above copyright
11 .\" notice, this list of conditions and the following disclaimer.
12 .\" 2. Redistributions in binary form must reproduce the above copyright
13 .\" notice, this list of conditions and the following disclaimer in the
14 .\" documentation and/or other materials provided with the distribution.
15 .\" 3. All advertising materials mentioning features or use of this software
16 .\" must display the following acknowledgement:
17 .\" This product includes software developed by Niels Provos.
18 .\" 4. The name of the author may not be used to endorse or promote products
19 .\" derived from this software without specific prior written permission.
21 .\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22 .\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
23 .\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
24 .\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
25 .\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
26 .\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 .\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 .\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
30 .\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 .Nm ARB_PROTOTYPE_STATIC ,
38 .Nm ARB_PROTOTYPE_INSERT ,
39 .Nm ARB_PROTOTYPE_INSERT_COLOR ,
40 .Nm ARB_PROTOTYPE_REMOVE ,
41 .Nm ARB_PROTOTYPE_REMOVE_COLOR ,
42 .Nm ARB_PROTOTYPE_FIND ,
43 .Nm ARB_PROTOTYPE_NFIND ,
44 .Nm ARB_PROTOTYPE_NEXT ,
45 .Nm ARB_PROTOTYPE_PREV ,
46 .Nm ARB_PROTOTYPE_MINMAX ,
47 .Nm ARB_PROTOTYPE_REINSERT ,
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 ARB_GENERATE_REINSERT ,
88 .Nm ARB_FOREACH_FROM ,
89 .Nm ARB_FOREACH_SAFE ,
90 .Nm ARB_FOREACH_REVERSE ,
91 .Nm ARB_FOREACH_REVERSE_FROM ,
92 .Nm ARB_FOREACH_REVERSE_SAFE ,
98 .Nd "array-based red-black trees"
101 .Fn ARB_PROTOTYPE NAME TYPE FIELD CMP
102 .Fn ARB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
103 .Fn ARB_PROTOTYPE_INSERT NAME TYPE ATTR
104 .Fn ARB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR
105 .Fn ARB_PROTOTYPE_REMOVE NAME TYPE ATTR
106 .Fn ARB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR
107 .Fn ARB_PROTOTYPE_FIND NAME TYPE ATTR
108 .Fn ARB_PROTOTYPE_NFIND NAME TYPE ATTR
109 .Fn ARB_PROTOTYPE_NEXT NAME TYPE ATTR
110 .Fn ARB_PROTOTYPE_PREV NAME TYPE ATTR
111 .Fn ARB_PROTOTYPE_MINMAX NAME TYPE ATTR
112 .Fn ARB_PROTOTYPE_REINSERT NAME TYPE ATTR
113 .Fn ARB_GENERATE NAME TYPE FIELD CMP
114 .Fn ARB_GENERATE_STATIC NAME TYPE FIELD CMP
115 .Fn ARB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR
116 .Fn ARB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR
117 .Fn ARB_GENERATE_REMOVE NAME TYPE FIELD ATTR
118 .Fn ARB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR
119 .Fn ARB_GENERATE_FIND NAME TYPE FIELD CMP ATTR
120 .Fn ARB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR
121 .Fn ARB_GENERATE_NEXT NAME TYPE FIELD ATTR
122 .Fn ARB_GENERATE_PREV NAME TYPE FIELD ATTR
123 .Fn ARB_GENERATE_MINMAX NAME TYPE FIELD ATTR
124 .Fn ARB_GENERATE_REINSERT NAME TYPE FIELD CMP ATTR
125 .Fn ARB<8|16|32>_ENTRY
126 .Fn ARB<8|16|32>_HEAD HEADNAME TYPE
128 .Fn ARB_ALLOCSIZE "ARB_HEAD *head" "int<8|16|32>_t maxnodes" "struct TYPE *elm"
129 .Fn ARB_INITIALIZER "ARB_HEAD *head" "int<8|16|32>_t maxnodes"
131 .Fn ARB_ROOT "ARB_HEAD *head"
133 .Fn ARB_EMPTY "ARB_HEAD *head"
135 .Fn ARB_FULL "ARB_HEAD *head"
137 .Fn ARB_CURNODES "ARB_HEAD *head"
139 .Fn ARB_MAXNODES "ARB_HEAD *head"
141 .Fn ARB_NEXT NAME "ARB_HEAD *head" "struct TYPE *elm"
143 .Fn ARB_PREV NAME "ARB_HEAD *head" "struct TYPE *elm"
145 .Fn ARB_MIN NAME "ARB_HEAD *head"
147 .Fn ARB_MAX NAME "ARB_HEAD *head"
149 .Fn ARB_FIND NAME "ARB_HEAD *head" "struct TYPE *elm"
151 .Fn ARB_NFIND NAME "ARB_HEAD *head" "struct TYPE *elm"
153 .Fn ARB_LEFT "struct TYPE *elm" "ARB_ENTRY NAME"
155 .Fn ARB_LEFTIDX "struct TYPE *elm" "ARB_ENTRY NAME"
157 .Fn ARB_RIGHT "struct TYPE *elm" "ARB_ENTRY NAME"
159 .Fn ARB_RIGHTIDX "struct TYPE *elm" "ARB_ENTRY NAME"
161 .Fn ARB_PARENT "struct TYPE *elm" "ARB_ENTRY NAME"
163 .Fn ARB_PARENTIDX "struct TYPE *elm" "ARB_ENTRY NAME"
165 .Fn ARB_GETFREE "ARB_HEAD *head" "FIELD"
167 .Fn ARB_FREEIDX "ARB_HEAD *head"
168 .Fn ARB_FOREACH VARNAME NAME "ARB_HEAD *head"
169 .Fn ARB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME"
170 .Fn ARB_FOREACH_SAFE "VARNAME" "NAME" "ARB_HEAD *head" "TEMP_VARNAME"
171 .Fn ARB_FOREACH_REVERSE VARNAME NAME "ARB_HEAD *head"
172 .Fn ARB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME"
173 .Fn ARB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "ARB_HEAD *head" "TEMP_VARNAME"
175 .Fn ARB_INIT "struct TYPE *elm" "FIELD" "ARB_HEAD *head" "int<8|16|32>_t maxnodes"
177 .Fn ARB_INSERT NAME "ARB_HEAD *head" "struct TYPE *elm"
179 .Fn ARB_REMOVE NAME "ARB_HEAD *head" "struct TYPE *elm"
181 .Fn ARB_REINSERT NAME "ARB_HEAD *head" "struct TYPE *elm"
183 .Fn ARB_RESET_TREE "ARB_HEAD *head" NAME "int<8|16|32>_t maxnodes"
185 These macros define data structures for and array-based red-black trees.
186 They use a single, continuous chunk of memory, and are useful
187 e.g., when the tree needs to be transferred between userspace and kernel.
189 In the macro definitions,
191 is the name tag of a user defined structure that must contain a field of type
197 is the name tag of a user defined structure that must be declared
203 has to be a unique name prefix for every tree that is defined.
205 The function prototypes are declared with
208 .Fn ARB_PROTOTYPE_STATIC .
209 The function bodies are generated with
212 .Fn ARB_GENERATE_STATIC .
213 See the examples below for further explanation of how these macros are used.
215 A red-black tree is a binary search tree with the node color as an
217 It fulfills a set of conditions:
218 .Bl -enum -offset indent
220 Every search path from the root to a leaf consists of the same number of
223 Each red node (except for the root) has a black parent.
225 Each leaf node is black.
228 Every operation on a red-black tree is bounded as
230 The maximum height of a red-black tree is
234 trees require entries to be allocated as an array, and uses array
235 indices to link entries together.
236 The maximum number of
238 tree entries is therefore constrained by the minimum of array size and choice of
239 signed integer data type used to store array indices.
242 to compute the size of memory chunk to allocate.
244 A red-black tree is headed by a structure defined by the
248 structure is declared with either of the following:
249 .Bd -ragged -offset indent
250 .Fn ARB<8|16|32>_HEAD HEADNAME TYPE
256 is the name of the structure to be defined, and struct
258 is the type of the elements to be inserted into the tree.
262 variant includes a suffix denoting the signed integer data type size
264 used to store array indices.
267 creates a red-black tree head strucutre with 8-bit signed array indices capable
268 of indexing up to 128 entries.
272 macro declares a structure that allows elements to be connected in the tree.
274 .Fn ARB<8|16|32>_HEAD
277 variant includes a suffix denoting the signed integer data type size
279 used to store array indices.
280 Entries should use the same number of bits as the tree head structure they will
283 In order to use the functions that manipulate the tree structure,
284 their prototypes need to be declared with the
287 .Fn ARB_PROTOTYPE_STATIC
291 is a unique identifier for this particular tree.
294 argument is the type of the structure that is being managed
298 argument is the name of the element defined by
300 Individual prototypes can be declared with
301 .Fn ARB_PROTOTYPE_INSERT ,
302 .Fn ARB_PROTOTYPE_INSERT_COLOR ,
303 .Fn ARB_PROTOTYPE_REMOVE ,
304 .Fn ARB_PROTOTYPE_REMOVE_COLOR ,
305 .Fn ARB_PROTOTYPE_FIND ,
306 .Fn ARB_PROTOTYPE_NFIND ,
307 .Fn ARB_PROTOTYPE_NEXT ,
308 .Fn ARB_PROTOTYPE_PREV ,
309 .Fn ARB_PROTOTYPE_MINMAX ,
311 .Fn ARB_PROTOTYPE_REINSERT
312 in case not all functions are required.
313 The individual prototype macros expect
321 argument must be empty for global functions or
323 for static functions.
325 The function bodies are generated with the
328 .Fn ARB_GENERATE_STATIC
330 These macros take the same arguments as the
333 .Fn ARB_PROTOTYPE_STATIC
334 macros, but should be used only once.
335 As an alternative individual function bodies are generated with the
336 .Fn ARB_GENERATE_INSERT ,
337 .Fn ARB_GENERATE_INSERT_COLOR ,
338 .Fn ARB_GENERATE_REMOVE ,
339 .Fn ARB_GENERATE_REMOVE_COLOR ,
340 .Fn ARB_GENERATE_FIND ,
341 .Fn ARB_GENERATE_NFIND ,
342 .Fn ARB_GENERATE_NEXT ,
343 .Fn ARB_GENERATE_PREV ,
344 .Fn ARB_GENERATE_MINMAX ,
346 .Fn ARB_GENERATE_REINSERT
352 argument is the name of a function used to compare tree nodes
354 The function takes two arguments of type
355 .Vt "struct TYPE *" .
356 If the first argument is smaller than the second, the function returns a
357 value smaller than zero.
358 If they are equal, the function returns zero.
359 Otherwise, it should return a value greater than zero.
361 function defines the order of the tree elements.
365 macro initializes the tree referenced by
367 with the array length of
370 The red-black tree can also be initialized statically by using the
373 .Bd -ragged -offset indent
374 .Fn ARB<8|16|32>_HEAD HEADNAME TYPE
377 .Fn ARB_INITIALIZER &head maxnodes ;
382 macro inserts the new element
388 macro removes the element
390 from the tree pointed by
397 macros can be used to find a particular element in the tree.
398 .Bd -literal -offset indent
399 struct TYPE find, *res;
401 res = ARB_FIND(NAME, head, &find);
411 macros can be used to traverse the tree:
413 .Dl "for (np = ARB_MIN(NAME, &head); np != NULL; np = ARB_NEXT(NAME, &head, np))"
415 Or, for simplicity, one can use the
418 .Fn ARB_FOREACH_REVERSE
420 .Bd -ragged -offset indent
421 .Fn ARB_FOREACH np NAME head
427 .Fn ARB_FOREACH_REVERSE_SAFE
428 traverse the tree referenced by head
429 in a forward or reverse direction respectively,
430 assigning each element in turn to np.
431 However, unlike their unsafe counterparts,
432 they permit both the removal of np
433 as well as freeing it from within the loop safely
434 without interfering with the traversal.
439 .Fn ARB_FOREACH_REVERSE_FROM
440 may be used to continue an interrupted traversal
441 in a forward or reverse direction respectively.
442 The head pointer is not required.
443 The pointer to the node from where to resume the traversal
444 should be passed as their last argument,
445 and will be overwritten to provide safe traversal.
449 macro should be used to check whether a red-black tree is empty.
451 Given that ARB trees have an intrinsic upper bound on the number of entries,
452 some ARB-specific additional macros are defined.
455 macro returns a boolean indicating whether the current number of tree entries
456 equals the tree's maximum.
461 macros return the current and maximum number of entries respectively.
464 macro returns a pointer to the next free entry in the array of entries, ready to
465 be linked into the tree.
470 if the element was inserted in the tree successfully, otherwise they
471 return a pointer to the element with the colliding key.
475 returns the pointer to the removed element otherwise they return
477 to indicate an error.
481 macro updates the position of the element
484 This must be called if a member of a
486 is modified in a way that affects comparison, such as by modifying
488 This is a lower overhead alternative to removing the element
489 and reinserting it again.
493 macro discards the tree topology.
494 It does not modify embedded object values or the free list.
501 macros first appeared in
506 macros were implemented by
507 .An Lawrence Stewart Aq Mt lstewart@FreeBSD.org ,