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 ,
93 .Nm RB_FOREACH_REVERSE ,
94 .Nm RB_FOREACH_REVERSE_FROM ,
95 .Nm RB_FOREACH_REVERSE_SAFE ,
99 .Nd "implementations of splay and red-black trees"
102 .Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP
103 .Fn SPLAY_GENERATE NAME TYPE FIELD CMP
105 .Fn SPLAY_HEAD HEADNAME TYPE
107 .Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
108 .Fn SPLAY_ROOT "SPLAY_HEAD *head"
110 .Fn SPLAY_EMPTY "SPLAY_HEAD *head"
112 .Fn SPLAY_NEXT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
114 .Fn SPLAY_MIN NAME "SPLAY_HEAD *head"
116 .Fn SPLAY_MAX NAME "SPLAY_HEAD *head"
118 .Fn SPLAY_FIND NAME "SPLAY_HEAD *head" "struct TYPE *elm"
120 .Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME"
122 .Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME"
123 .Fn SPLAY_FOREACH VARNAME NAME "SPLAY_HEAD *head"
125 .Fn SPLAY_INIT "SPLAY_HEAD *head"
127 .Fn SPLAY_INSERT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
129 .Fn SPLAY_REMOVE NAME "SPLAY_HEAD *head" "struct TYPE *elm"
130 .Fn RB_PROTOTYPE NAME TYPE FIELD CMP
131 .Fn RB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
132 .Fn RB_PROTOTYPE_INSERT NAME TYPE ATTR
133 .Fn RB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR
134 .Fn RB_PROTOTYPE_REMOVE NAME TYPE ATTR
135 .Fn RB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR
136 .Fn RB_PROTOTYPE_FIND NAME TYPE ATTR
137 .Fn RB_PROTOTYPE_NFIND NAME TYPE ATTR
138 .Fn RB_PROTOTYPE_NEXT NAME TYPE ATTR
139 .Fn RB_PROTOTYPE_PREV NAME TYPE ATTR
140 .Fn RB_PROTOTYPE_MINMAX NAME TYPE ATTR
141 .Fn RB_GENERATE NAME TYPE FIELD CMP
142 .Fn RB_GENERATE_STATIC NAME TYPE FIELD CMP
143 .Fn RB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR
144 .Fn RB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR
145 .Fn RB_GENERATE_REMOVE NAME TYPE FIELD ATTR
146 .Fn RB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR
147 .Fn RB_GENERATE_FIND NAME TYPE FIELD CMP ATTR
148 .Fn RB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR
149 .Fn RB_GENERATE_NEXT NAME TYPE FIELD ATTR
150 .Fn RB_GENERATE_PREV NAME TYPE FIELD ATTR
151 .Fn RB_GENERATE_MINMAX NAME TYPE FIELD ATTR
153 .Fn RB_HEAD HEADNAME TYPE
154 .Fn RB_INITIALIZER "RB_HEAD *head"
156 .Fn RB_ROOT "RB_HEAD *head"
158 .Fn RB_EMPTY "RB_HEAD *head"
160 .Fn RB_NEXT NAME "RB_HEAD *head" "struct TYPE *elm"
162 .Fn RB_PREV NAME "RB_HEAD *head" "struct TYPE *elm"
164 .Fn RB_MIN NAME "RB_HEAD *head"
166 .Fn RB_MAX NAME "RB_HEAD *head"
168 .Fn RB_FIND NAME "RB_HEAD *head" "struct TYPE *elm"
170 .Fn RB_NFIND NAME "RB_HEAD *head" "struct TYPE *elm"
172 .Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
174 .Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME"
176 .Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME"
177 .Fn RB_FOREACH VARNAME NAME "RB_HEAD *head"
178 .Fn RB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME"
179 .Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
180 .Fn RB_FOREACH_REVERSE VARNAME NAME "RB_HEAD *head"
181 .Fn RB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME"
182 .Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
184 .Fn RB_INIT "RB_HEAD *head"
186 .Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm"
188 .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm"
190 These macros define data structures for different types of trees:
191 splay trees and red-black trees.
193 In the macro definitions,
195 is the name tag of a user defined structure that must contain a field of type
203 is the name tag of a user defined structure that must be declared
210 has to be a unique name prefix for every tree that is defined.
212 The function prototypes are declared with
213 .Fn SPLAY_PROTOTYPE ,
216 .Fn RB_PROTOTYPE_STATIC .
217 The function bodies are generated with
221 .Fn RB_GENERATE_STATIC .
222 See the examples below for further explanation of how these macros are used.
224 A splay tree is a self-organizing data structure.
225 Every operation on the tree causes a splay to happen.
226 The splay moves the requested
227 node to the root of the tree and partly rebalances it.
229 This has the benefit that request locality causes faster lookups as
230 the requested nodes move to the top of the tree.
231 On the other hand, every lookup causes memory writes.
233 The Balance Theorem bounds the total access time for
237 inserts on an initially empty tree as
238 .Fn O "\*[lp]m + n\*[rp]lg n" .
240 amortized cost for a sequence of
242 accesses to a splay tree is
245 A splay tree is headed by a structure defined by the
249 structure is declared as follows:
250 .Bd -ragged -offset indent
251 .Fn SPLAY_HEAD HEADNAME TYPE
257 is the name of the structure to be defined, and struct
259 is the type of the elements to be inserted into the tree.
263 macro declares a structure that allows elements to be connected in the tree.
265 In order to use the functions that manipulate the tree structure,
266 their prototypes need to be declared with the
271 is a unique identifier for this particular tree.
274 argument is the type of the structure that is being managed
278 argument is the name of the element defined by
281 The function bodies are generated with the
284 It takes the same arguments as the
286 macro, but should be used only once.
291 argument is the name of a function used to compare tree nodes
293 The function takes two arguments of type
294 .Vt "struct TYPE *" .
295 If the first argument is smaller than the second, the function returns a
296 value smaller than zero.
297 If they are equal, the function returns zero.
298 Otherwise, it should return a value greater than zero.
300 function defines the order of the tree elements.
304 macro initializes the tree referenced by
307 The splay tree can also be initialized statically by using the
308 .Fn SPLAY_INITIALIZER
310 .Bd -ragged -offset indent
311 .Fn SPLAY_HEAD HEADNAME TYPE
314 .Fn SPLAY_INITIALIZER &head ;
319 macro inserts the new element
325 macro removes the element
327 from the tree pointed by
332 macro can be used to find a particular element in the tree.
333 .Bd -literal -offset indent
334 struct TYPE find, *res;
336 res = SPLAY_FIND(NAME, head, &find);
345 macros can be used to traverse the tree:
346 .Bd -literal -offset indent
347 for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np))
350 Or, for simplicity, one can use the
353 .Bd -ragged -offset indent
354 .Fn SPLAY_FOREACH np NAME head
359 macro should be used to check whether a splay tree is empty.
361 A red-black tree is a binary search tree with the node color as an
363 It fulfills a set of conditions:
364 .Bl -enum -offset indent
366 Every search path from the root to a leaf consists of the same number of
369 Each red node (except for the root) has a black parent.
371 Each leaf node is black.
374 Every operation on a red-black tree is bounded as
376 The maximum height of a red-black tree is
379 A red-black tree is headed by a structure defined by the
383 structure is declared as follows:
384 .Bd -ragged -offset indent
385 .Fn RB_HEAD HEADNAME TYPE
391 is the name of the structure to be defined, and struct
393 is the type of the elements to be inserted into the tree.
397 macro declares a structure that allows elements to be connected in the tree.
399 In order to use the functions that manipulate the tree structure,
400 their prototypes need to be declared with the
403 .Fn RB_PROTOTYPE_STATIC
407 is a unique identifier for this particular tree.
410 argument is the type of the structure that is being managed
414 argument is the name of the element defined by
416 Individual prototypes can be declared with
417 .Fn RB_PROTOTYPE_INSERT ,
418 .Fn RB_PROTOTYPE_INSERT_COLOR ,
419 .Fn RB_PROTOTYPE_REMOVE ,
420 .Fn RB_PROTOTYPE_REMOVE_COLOR ,
421 .Fn RB_PROTOTYPE_FIND ,
422 .Fn RB_PROTOTYPE_NFIND ,
423 .Fn RB_PROTOTYPE_NEXT ,
424 .Fn RB_PROTOTYPE_PREV ,
426 .Fn RB_PROTOTYPE_MINMAX
427 in case not all functions are required.
428 The individual prototype macros expect
436 argument must be empty for global functions or
438 for static functions.
440 The function bodies are generated with the
443 .Fn RB_GENERATE_STATIC
445 These macros take the same arguments as the
448 .Fn RB_PROTOTYPE_STATIC
449 macros, but should be used only once.
450 As an alternative individual function bodies are generated with the
451 .Fn RB_GENERATE_INSERT ,
452 .Fn RB_GENERATE_INSERT_COLOR ,
453 .Fn RB_GENERATE_REMOVE ,
454 .Fn RB_GENERATE_REMOVE_COLOR ,
455 .Fn RB_GENERATE_FIND ,
456 .Fn RB_GENERATE_NFIND ,
457 .Fn RB_GENERATE_NEXT ,
458 .Fn RB_GENERATE_PREV ,
460 .Fn RB_GENERATE_MINMAX
466 argument is the name of a function used to compare tree nodes
468 The function takes two arguments of type
469 .Vt "struct TYPE *" .
470 If the first argument is smaller than the second, the function returns a
471 value smaller than zero.
472 If they are equal, the function returns zero.
473 Otherwise, it should return a value greater than zero.
475 function defines the order of the tree elements.
479 macro initializes the tree referenced by
482 The red-black tree can also be initialized statically by using the
485 .Bd -ragged -offset indent
486 .Fn RB_HEAD HEADNAME TYPE
489 .Fn RB_INITIALIZER &head ;
494 macro inserts the new element
500 macro removes the element
502 from the tree pointed by
509 macros can be used to find a particular element in the tree.
510 .Bd -literal -offset indent
511 struct TYPE find, *res;
513 res = RB_FIND(NAME, head, &find);
523 macros can be used to traverse the tree:
525 .Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))"
527 Or, for simplicity, one can use the
530 .Fn RB_FOREACH_REVERSE
532 .Bd -ragged -offset indent
533 .Fn RB_FOREACH np NAME head
539 .Fn RB_FOREACH_REVERSE_SAFE
540 traverse the tree referenced by head
541 in a forward or reverse direction respectively,
542 assigning each element in turn to np.
543 However, unlike their unsafe counterparts,
544 they permit both the removal of np
545 as well as freeing it from within the loop safely
546 without interfering with the traversal.
551 .Fn RB_FOREACH_REVERSE_FROM
552 may be used to continue an interrupted traversal
553 in a forward or reverse direction respectively.
554 The head pointer is not required.
555 The pointer to the node from where to resume the traversal
556 should be passed as their last argument,
557 and will be overwritten to provide safe traversal.
561 macro should be used to check whether a red-black tree is empty.
563 Trying to free a tree in the following way is a common error:
564 .Bd -literal -offset indent
565 SPLAY_FOREACH(var, NAME, head) {
566 SPLAY_REMOVE(NAME, head, var);
576 macro refers to a pointer that may have been reallocated already.
577 Proper code needs a second variable.
578 .Bd -literal -offset indent
579 for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
580 nxt = SPLAY_NEXT(NAME, head, var);
581 SPLAY_REMOVE(NAME, head, var);
592 if the element was inserted in the tree successfully, otherwise they
593 return a pointer to the element with the colliding key.
599 return the pointer to the removed element otherwise they return
601 to indicate an error.
605 The author of the tree macros is