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 .\" All rights reserved.
6 .\" Redistribution and use in source and binary forms, with or without
7 .\" modification, are permitted provided that the following conditions
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.
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.
41 .Nm SPLAY_INITIALIZER ,
55 .Nm RB_PROTOTYPE_STATIC ,
56 .Nm RB_PROTOTYPE_INSERT ,
57 .Nm RB_PROTOTYPE_INSERT_COLOR ,
58 .Nm RB_PROTOTYPE_REMOVE ,
59 .Nm RB_PROTOTYPE_REMOVE_COLOR ,
60 .Nm RB_PROTOTYPE_FIND ,
61 .Nm RB_PROTOTYPE_NFIND ,
62 .Nm RB_PROTOTYPE_NEXT ,
63 .Nm RB_PROTOTYPE_PREV ,
64 .Nm RB_PROTOTYPE_MINMAX ,
66 .Nm RB_GENERATE_STATIC ,
67 .Nm RB_GENERATE_INSERT ,
68 .Nm RB_GENERATE_INSERT_COLOR ,
69 .Nm RB_GENERATE_REMOVE ,
70 .Nm RB_GENERATE_REMOVE_COLOR ,
71 .Nm RB_GENERATE_FIND ,
72 .Nm RB_GENERATE_NFIND ,
73 .Nm RB_GENERATE_NEXT ,
74 .Nm RB_GENERATE_PREV ,
75 .Nm RB_GENERATE_MINMAX ,
92 .Nm RB_FOREACH_REVERSE ,
93 .Nm RB_FOREACH_REVERSE_SAFE ,
97 .Nd "implementations of splay and red-black trees"
100 .Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP
101 .Fn SPLAY_GENERATE NAME TYPE FIELD CMP
103 .Fn SPLAY_HEAD HEADNAME TYPE
105 .Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
106 .Fn SPLAY_ROOT "SPLAY_HEAD *head"
108 .Fn SPLAY_EMPTY "SPLAY_HEAD *head"
110 .Fn SPLAY_NEXT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
112 .Fn SPLAY_MIN NAME "SPLAY_HEAD *head"
114 .Fn SPLAY_MAX NAME "SPLAY_HEAD *head"
116 .Fn SPLAY_FIND NAME "SPLAY_HEAD *head" "struct TYPE *elm"
118 .Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME"
120 .Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME"
121 .Fn SPLAY_FOREACH VARNAME NAME "SPLAY_HEAD *head"
123 .Fn SPLAY_INIT "SPLAY_HEAD *head"
125 .Fn SPLAY_INSERT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
127 .Fn SPLAY_REMOVE NAME "SPLAY_HEAD *head" "struct TYPE *elm"
128 .Fn RB_PROTOTYPE NAME TYPE FIELD CMP
129 .Fn RB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
130 .Fn RB_PROTOTYPE_INSERT NAME TYPE ATTR
131 .Fn RB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR
132 .Fn RB_PROTOTYPE_REMOVE NAME TYPE ATTR
133 .Fn RB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR
134 .Fn RB_PROTOTYPE_FIND NAME TYPE ATTR
135 .Fn RB_PROTOTYPE_NFIND NAME TYPE ATTR
136 .Fn RB_PROTOTYPE_NEXT NAME TYPE ATTR
137 .Fn RB_PROTOTYPE_PREV NAME TYPE ATTR
138 .Fn RB_PROTOTYPE_MINMAX NAME TYPE ATTR
139 .Fn RB_GENERATE NAME TYPE FIELD CMP
140 .Fn RB_GENERATE_STATIC NAME TYPE FIELD CMP
141 .Fn RB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR
142 .Fn RB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR
143 .Fn RB_GENERATE_REMOVE NAME TYPE FIELD ATTR
144 .Fn RB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR
145 .Fn RB_GENERATE_FIND NAME TYPE FIELD CMP ATTR
146 .Fn RB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR
147 .Fn RB_GENERATE_NEXT NAME TYPE FIELD ATTR
148 .Fn RB_GENERATE_PREV NAME TYPE FIELD ATTR
149 .Fn RB_GENERATE_MINMAX NAME TYPE FIELD ATTR
151 .Fn RB_HEAD HEADNAME TYPE
152 .Fn RB_INITIALIZER "RB_HEAD *head"
154 .Fn RB_ROOT "RB_HEAD *head"
156 .Fn RB_EMPTY "RB_HEAD *head"
158 .Fn RB_NEXT NAME "RB_HEAD *head" "struct TYPE *elm"
160 .Fn RB_PREV NAME "RB_HEAD *head" "struct TYPE *elm"
162 .Fn RB_MIN NAME "RB_HEAD *head"
164 .Fn RB_MAX NAME "RB_HEAD *head"
166 .Fn RB_FIND NAME "RB_HEAD *head" "struct TYPE *elm"
168 .Fn RB_NFIND NAME "RB_HEAD *head" "struct TYPE *elm"
170 .Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
172 .Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME"
174 .Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME"
175 .Fn RB_FOREACH VARNAME NAME "RB_HEAD *head"
176 .Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
177 .Fn RB_FOREACH_REVERSE VARNAME NAME "RB_HEAD *head"
178 .Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
180 .Fn RB_INIT "RB_HEAD *head"
182 .Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm"
184 .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm"
186 These macros define data structures for different types of trees:
187 splay trees and red-black trees.
189 In the macro definitions,
191 is the name tag of a user defined structure that must contain a field of type
199 is the name tag of a user defined structure that must be declared
206 has to be a unique name prefix for every tree that is defined.
208 The function prototypes are declared with
209 .Fn SPLAY_PROTOTYPE ,
212 .Fn RB_PROTOTYPE_STATIC .
213 The function bodies are generated with
217 .Fn RB_GENERATE_STATIC .
218 See the examples below for further explanation of how these macros are used.
220 A splay tree is a self-organizing data structure.
221 Every operation on the tree causes a splay to happen.
222 The splay moves the requested
223 node to the root of the tree and partly rebalances it.
225 This has the benefit that request locality causes faster lookups as
226 the requested nodes move to the top of the tree.
227 On the other hand, every lookup causes memory writes.
229 The Balance Theorem bounds the total access time for
233 inserts on an initially empty tree as
234 .Fn O "\*[lp]m + n\*[rp]lg n" .
236 amortized cost for a sequence of
238 accesses to a splay tree is
241 A splay tree is headed by a structure defined by the
245 structure is declared as follows:
246 .Bd -ragged -offset indent
247 .Fn SPLAY_HEAD HEADNAME TYPE
253 is the name of the structure to be defined, and struct
255 is the type of the elements to be inserted into the tree.
259 macro declares a structure that allows elements to be connected in the tree.
261 In order to use the functions that manipulate the tree structure,
262 their prototypes need to be declared with the
267 is a unique identifier for this particular tree.
270 argument is the type of the structure that is being managed
274 argument is the name of the element defined by
277 The function bodies are generated with the
280 It takes the same arguments as the
282 macro, but should be used only once.
287 argument is the name of a function used to compare tree nodes
289 The function takes two arguments of type
290 .Vt "struct TYPE *" .
291 If the first argument is smaller than the second, the function returns a
292 value smaller than zero.
293 If they are equal, the function returns zero.
294 Otherwise, it should return a value greater than zero.
296 function defines the order of the tree elements.
300 macro initializes the tree referenced by
303 The splay tree can also be initialized statically by using the
304 .Fn SPLAY_INITIALIZER
306 .Bd -ragged -offset indent
307 .Fn SPLAY_HEAD HEADNAME TYPE
310 .Fn SPLAY_INITIALIZER &head ;
315 macro inserts the new element
321 macro removes the element
323 from the tree pointed by
328 macro can be used to find a particular element in the tree.
329 .Bd -literal -offset indent
330 struct TYPE find, *res;
332 res = SPLAY_FIND(NAME, head, &find);
341 macros can be used to traverse the tree:
342 .Bd -literal -offset indent
343 for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np))
346 Or, for simplicity, one can use the
349 .Bd -ragged -offset indent
350 .Fn SPLAY_FOREACH np NAME head
355 macro should be used to check whether a splay tree is empty.
357 A red-black tree is a binary search tree with the node color as an
359 It fulfills a set of conditions:
360 .Bl -enum -offset indent
362 Every search path from the root to a leaf consists of the same number of
365 Each red node (except for the root) has a black parent.
367 Each leaf node is black.
370 Every operation on a red-black tree is bounded as
372 The maximum height of a red-black tree is
375 A red-black tree is headed by a structure defined by the
379 structure is declared as follows:
380 .Bd -ragged -offset indent
381 .Fn RB_HEAD HEADNAME TYPE
387 is the name of the structure to be defined, and struct
389 is the type of the elements to be inserted into the tree.
393 macro declares a structure that allows elements to be connected in the tree.
395 In order to use the functions that manipulate the tree structure,
396 their prototypes need to be declared with the
399 .Fn RB_PROTOTYPE_STATIC
403 is a unique identifier for this particular tree.
406 argument is the type of the structure that is being managed
410 argument is the name of the element defined by
412 Individual prototypes can be declared with
413 .Fn RB_PROTOTYPE_INSERT ,
414 .Fn RB_PROTOTYPE_INSERT_COLOR ,
415 .Fn RB_PROTOTYPE_REMOVE ,
416 .Fn RB_PROTOTYPE_REMOVE_COLOR ,
417 .Fn RB_PROTOTYPE_FIND ,
418 .Fn RB_PROTOTYPE_NFIND ,
419 .Fn RB_PROTOTYPE_NEXT ,
420 .Fn RB_PROTOTYPE_PREV ,
422 .Fn RB_PROTOTYPE_MINMAX
423 in case not all functions are required. The individual prototype macros expect
430 argument must be empty for global functions or
432 for static functions.
434 The function bodies are generated with the
437 .Fn RB_GENERATE_STATIC
439 These macros take the same arguments as the
442 .Fn RB_PROTOTYPE_STATIC
443 macros, but should be used only once.
444 As an alternative individual function bodies are generated with the
445 .Fn RB_GENERATE_INSERT ,
446 .Fn RB_GENERATE_INSERT_COLOR ,
447 .Fn RB_GENERATE_REMOVE ,
448 .Fn RB_GENERATE_REMOVE_COLOR ,
449 .Fn RB_GENERATE_FIND ,
450 .Fn RB_GENERATE_NFIND ,
451 .Fn RB_GENERATE_NEXT ,
452 .Fn RB_GENERATE_PREV ,
454 .Fn RB_GENERATE_MINMAX
460 argument is the name of a function used to compare tree nodes
462 The function takes two arguments of type
463 .Vt "struct TYPE *" .
464 If the first argument is smaller than the second, the function returns a
465 value smaller than zero.
466 If they are equal, the function returns zero.
467 Otherwise, it should return a value greater than zero.
469 function defines the order of the tree elements.
473 macro initializes the tree referenced by
476 The red-black tree can also be initialized statically by using the
479 .Bd -ragged -offset indent
480 .Fn RB_HEAD HEADNAME TYPE
483 .Fn RB_INITIALIZER &head ;
488 macro inserts the new element
494 macro removes the element
496 from the tree pointed by
503 macros can be used to find a particular element in the tree.
504 .Bd -literal -offset indent
505 struct TYPE find, *res;
507 res = RB_FIND(NAME, head, &find);
517 macros can be used to traverse the tree:
519 .Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))"
521 Or, for simplicity, one can use the
524 .Fn RB_FOREACH_REVERSE
526 .Bd -ragged -offset indent
527 .Fn RB_FOREACH np NAME head
533 .Fn RB_FOREACH_REVERSE_SAFE
534 traverse the tree referenced by head
535 in a forward or reverse direction respectively,
536 assigning each element in turn to np.
537 However, unlike their unsafe counterparts,
538 they permit both the removal of np
539 as well as freeing it from within the loop safely
540 without interfering with the traversal.
544 macro should be used to check whether a red-black tree is empty.
546 Trying to free a tree in the following way is a common error:
547 .Bd -literal -offset indent
548 SPLAY_FOREACH(var, NAME, head) {
549 SPLAY_REMOVE(NAME, head, var);
559 macro refers to a pointer that may have been reallocated already.
560 Proper code needs a second variable.
561 .Bd -literal -offset indent
562 for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
563 nxt = SPLAY_NEXT(NAME, head, var);
564 SPLAY_REMOVE(NAME, head, var);
575 if the element was inserted in the tree successfully, otherwise they
576 return a pointer to the element with the colliding key.
582 return the pointer to the removed element otherwise they return
584 to indicate an error.
588 The author of the tree macros is