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 ,
57 .Nm RB_GENERATE_STATIC ,
75 .Nm RB_FOREACH_REVERSE ,
76 .Nm RB_FOREACH_REVERSE_FROM ,
77 .Nm RB_FOREACH_REVERSE_SAFE ,
81 .Nd "implementations of splay and red-black trees"
84 .Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP
85 .Fn SPLAY_GENERATE NAME TYPE FIELD CMP
87 .Fn SPLAY_HEAD HEADNAME TYPE
89 .Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
90 .Fn SPLAY_ROOT "SPLAY_HEAD *head"
92 .Fn SPLAY_EMPTY "SPLAY_HEAD *head"
94 .Fn SPLAY_NEXT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
96 .Fn SPLAY_MIN NAME "SPLAY_HEAD *head"
98 .Fn SPLAY_MAX NAME "SPLAY_HEAD *head"
100 .Fn SPLAY_FIND NAME "SPLAY_HEAD *head" "struct TYPE *elm"
102 .Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME"
104 .Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME"
105 .Fn SPLAY_FOREACH VARNAME NAME "SPLAY_HEAD *head"
107 .Fn SPLAY_INIT "SPLAY_HEAD *head"
109 .Fn SPLAY_INSERT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
111 .Fn SPLAY_REMOVE NAME "SPLAY_HEAD *head" "struct TYPE *elm"
112 .Fn RB_PROTOTYPE NAME TYPE FIELD CMP
113 .Fn RB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
114 .Fn RB_GENERATE NAME TYPE FIELD CMP
115 .Fn RB_GENERATE_STATIC NAME TYPE FIELD CMP
117 .Fn RB_HEAD HEADNAME TYPE
118 .Fn RB_INITIALIZER "RB_HEAD *head"
120 .Fn RB_ROOT "RB_HEAD *head"
122 .Fn RB_EMPTY "RB_HEAD *head"
124 .Fn RB_NEXT NAME "RB_HEAD *head" "struct TYPE *elm"
126 .Fn RB_PREV NAME "RB_HEAD *head" "struct TYPE *elm"
128 .Fn RB_MIN NAME "RB_HEAD *head"
130 .Fn RB_MAX NAME "RB_HEAD *head"
132 .Fn RB_FIND NAME "RB_HEAD *head" "struct TYPE *elm"
134 .Fn RB_NFIND NAME "RB_HEAD *head" "struct TYPE *elm"
136 .Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
138 .Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME"
140 .Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME"
141 .Fn RB_FOREACH VARNAME NAME "RB_HEAD *head"
142 .Fn RB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME"
143 .Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
144 .Fn RB_FOREACH_REVERSE VARNAME NAME "RB_HEAD *head"
145 .Fn RB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME"
146 .Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
148 .Fn RB_INIT "RB_HEAD *head"
150 .Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm"
152 .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm"
154 These macros define data structures for different types of trees:
155 splay trees and red-black trees.
157 In the macro definitions,
159 is the name tag of a user defined structure that must contain a field of type
167 is the name tag of a user defined structure that must be declared
174 has to be a unique name prefix for every tree that is defined.
176 The function prototypes are declared with
177 .Fn SPLAY_PROTOTYPE ,
180 .Fn RB_PROTOTYPE_STATIC .
181 The function bodies are generated with
185 .Fn RB_GENERATE_STATIC .
186 See the examples below for further explanation of how these macros are used.
188 A splay tree is a self-organizing data structure.
189 Every operation on the tree causes a splay to happen.
190 The splay moves the requested
191 node to the root of the tree and partly rebalances it.
193 This has the benefit that request locality causes faster lookups as
194 the requested nodes move to the top of the tree.
195 On the other hand, every lookup causes memory writes.
197 The Balance Theorem bounds the total access time for
201 inserts on an initially empty tree as
202 .Fn O "\*[lp]m + n\*[rp]lg n" .
204 amortized cost for a sequence of
206 accesses to a splay tree is
209 A splay tree is headed by a structure defined by the
213 structure is declared as follows:
214 .Bd -ragged -offset indent
215 .Fn SPLAY_HEAD HEADNAME TYPE
221 is the name of the structure to be defined, and struct
223 is the type of the elements to be inserted into the tree.
227 macro declares a structure that allows elements to be connected in the tree.
229 In order to use the functions that manipulate the tree structure,
230 their prototypes need to be declared with the
235 is a unique identifier for this particular tree.
238 argument is the type of the structure that is being managed
242 argument is the name of the element defined by
245 The function bodies are generated with the
248 It takes the same arguments as the
250 macro, but should be used only once.
255 argument is the name of a function used to compare tree nodes
257 The function takes two arguments of type
258 .Vt "struct TYPE *" .
259 If the first argument is smaller than the second, the function returns a
260 value smaller than zero.
261 If they are equal, the function returns zero.
262 Otherwise, it should return a value greater than zero.
264 function defines the order of the tree elements.
268 macro initializes the tree referenced by
271 The splay tree can also be initialized statically by using the
272 .Fn SPLAY_INITIALIZER
274 .Bd -ragged -offset indent
275 .Fn SPLAY_HEAD HEADNAME TYPE
278 .Fn SPLAY_INITIALIZER &head ;
283 macro inserts the new element
289 macro removes the element
291 from the tree pointed by
296 macro can be used to find a particular element in the tree.
297 .Bd -literal -offset indent
298 struct TYPE find, *res;
300 res = SPLAY_FIND(NAME, head, &find);
309 macros can be used to traverse the tree:
310 .Bd -literal -offset indent
311 for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np))
314 Or, for simplicity, one can use the
317 .Bd -ragged -offset indent
318 .Fn SPLAY_FOREACH np NAME head
323 macro should be used to check whether a splay tree is empty.
325 A red-black tree is a binary search tree with the node color as an
327 It fulfills a set of conditions:
328 .Bl -enum -offset indent
330 Every search path from the root to a leaf consists of the same number of
333 Each red node (except for the root) has a black parent.
335 Each leaf node is black.
338 Every operation on a red-black tree is bounded as
340 The maximum height of a red-black tree is
343 A red-black tree is headed by a structure defined by the
347 structure is declared as follows:
348 .Bd -ragged -offset indent
349 .Fn RB_HEAD HEADNAME TYPE
355 is the name of the structure to be defined, and struct
357 is the type of the elements to be inserted into the tree.
361 macro declares a structure that allows elements to be connected in the tree.
363 In order to use the functions that manipulate the tree structure,
364 their prototypes need to be declared with the
367 .Fn RB_PROTOTYPE_STATIC
371 is a unique identifier for this particular tree.
374 argument is the type of the structure that is being managed
378 argument is the name of the element defined by
381 The function bodies are generated with the
384 .Fn RB_GENERATE_STATIC
386 These macros take the same arguments as the
389 .Fn RB_PROTOTYPE_STATIC
390 macros, but should be used only once.
395 argument is the name of a function used to compare tree nodes
397 The function takes two arguments of type
398 .Vt "struct TYPE *" .
399 If the first argument is smaller than the second, the function returns a
400 value smaller than zero.
401 If they are equal, the function returns zero.
402 Otherwise, it should return a value greater than zero.
404 function defines the order of the tree elements.
408 macro initializes the tree referenced by
411 The red-black tree can also be initialized statically by using the
414 .Bd -ragged -offset indent
415 .Fn RB_HEAD HEADNAME TYPE
418 .Fn RB_INITIALIZER &head ;
423 macro inserts the new element
429 macro removes the element
431 from the tree pointed by
438 macros can be used to find a particular element in the tree.
439 .Bd -literal -offset indent
440 struct TYPE find, *res;
442 res = RB_FIND(NAME, head, &find);
452 macros can be used to traverse the tree:
454 .Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))"
456 Or, for simplicity, one can use the
459 .Fn RB_FOREACH_REVERSE
461 .Bd -ragged -offset indent
462 .Fn RB_FOREACH np NAME head
468 .Fn RB_FOREACH_REVERSE_SAFE
469 traverse the tree referenced by head
470 in a forward or reverse direction respectively,
471 assigning each element in turn to np.
472 However, unlike their unsafe counterparts,
473 they permit both the removal of np
474 as well as freeing it from within the loop safely
475 without interfering with the traversal.
480 .Fn RB_FOREACH_REVERSE_FROM
481 may be used to continue an interrupted traversal
482 in a forward or reverse direction respectively.
483 The head pointer is not required.
484 The pointer to the node from where to resume the traversal
485 should be passed as their last argument,
486 and will be overwritten to provide safe traversal.
490 macro should be used to check whether a red-black tree is empty.
492 Trying to free a tree in the following way is a common error:
493 .Bd -literal -offset indent
494 SPLAY_FOREACH(var, NAME, head) {
495 SPLAY_REMOVE(NAME, head, var);
505 macro refers to a pointer that may have been reallocated already.
506 Proper code needs a second variable.
507 .Bd -literal -offset indent
508 for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
509 nxt = SPLAY_NEXT(NAME, head, var);
510 SPLAY_REMOVE(NAME, head, var);
521 if the element was inserted in the tree successfully, otherwise they
522 return a pointer to the element with the colliding key.
528 return the pointer to the removed element otherwise they return
530 to indicate an error.
534 The author of the tree macros is