1 .\" $NetBSD: tree.3,v 1.3 2004/04/14 11:05:19 pooka Exp $
2 .\" $OpenBSD: tree.3,v 1.9 2003/05/20 09:13:38 jmc Exp $
4 .\" * Copyright 2002 Niels Provos <provos@citi.umich.edu>
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.
40 .Nm SPLAY_INITIALIZER ,
70 .Nm RB_FOREACH_REVERSE ,
71 .Nm RB_FOREACH_REVERSE_FROM ,
72 .Nm RB_FOREACH_REVERSE_SAFE ,
76 .Nd implementations of splay and red-black trees
79 .Fn SPLAY_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP"
80 .Fn SPLAY_GENERATE "NAME" "TYPE" "FIELD" "CMP"
81 .Fn SPLAY_ENTRY "TYPE"
82 .Fn SPLAY_HEAD "HEADNAME" "TYPE"
84 .Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
85 .Fn SPLAY_ROOT "SPLAY_HEAD *head"
87 .Fn SPLAY_EMPTY "SPLAY_HEAD *head"
89 .Fn SPLAY_NEXT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
91 .Fn SPLAY_MIN "NAME" "SPLAY_HEAD *head"
93 .Fn SPLAY_MAX "NAME" "SPLAY_HEAD *head"
95 .Fn SPLAY_FIND "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
97 .Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME"
99 .Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME"
100 .Fn SPLAY_FOREACH "VARNAME" "NAME" "SPLAY_HEAD *head"
102 .Fn SPLAY_INIT "SPLAY_HEAD *head"
104 .Fn SPLAY_INSERT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
106 .Fn SPLAY_REMOVE "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
108 .Fn RB_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP"
109 .Fn RB_GENERATE "NAME" "TYPE" "FIELD" "CMP"
111 .Fn RB_HEAD "HEADNAME" "TYPE"
112 .Fn RB_INITIALIZER "RB_HEAD *head"
114 .Fn RB_ROOT "RB_HEAD *head"
116 .Fn RB_EMPTY "RB_HEAD *head"
118 .Fn RB_NEXT "NAME" "RB_HEAD *head" "struct TYPE *elm"
120 .Fn RB_MIN "NAME" "RB_HEAD *head"
122 .Fn RB_MAX "NAME" "RB_HEAD *head"
124 .Fn RB_FIND "NAME" "RB_HEAD *head" "struct TYPE *elm"
126 .Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
128 .Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME"
130 .Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME"
131 .Fn RB_FOREACH "VARNAME" "NAME" "RB_HEAD *head"
132 .Fn RB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME"
133 .Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
134 .Fn RB_FOREACH_REVERSE VARNAME NAME "RB_HEAD *head"
135 .Fn RB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME"
136 .Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
138 .Fn RB_INIT "RB_HEAD *head"
140 .Fn RB_INSERT "NAME" "RB_HEAD *head" "struct TYPE *elm"
142 .Fn RB_REMOVE "NAME" "RB_HEAD *head" "struct TYPE *elm"
144 These macros define data structures for different types of trees:
145 splay trees and red-black trees.
147 In the macro definitions,
149 is the name tag of a user defined structure that must contain a field of type
157 is the name tag of a user defined structure that must be declared
164 has to be a unique name prefix for every tree that is defined.
166 The function prototypes are declared with either
170 The function bodies are generated with either
174 See the examples below for further explanation of how these macros are used.
176 A splay tree is a self-organizing data structure.
177 Every operation on the tree causes a splay to happen.
178 The splay moves the requested node to the root of the tree and partly
181 This has the benefit that request locality causes faster lookups as
182 the requested nodes move to the top of the tree.
183 On the other hand, every lookup causes memory writes.
185 The Balance Theorem bounds the total access time for m operations
186 and n inserts on an initially empty tree as O((m + n)lg n).
187 The amortized cost for a sequence of m accesses to a splay tree is O(lg n).
189 A splay tree is headed by a structure defined by the
194 structure is declared as follows:
195 .Bd -literal -offset indent
196 SPLAY_HEAD(HEADNAME, TYPE) head;
201 is the name of the structure to be defined, and struct
203 is the type of the elements to be inserted into the tree.
207 macro declares a structure that allows elements to be connected in the tree.
209 In order to use the functions that manipulate the tree structure,
210 their prototypes need to be declared with the
215 is a unique identifier for this particular tree.
218 argument is the type of the structure that is being managed
222 argument is the name of the element defined by
225 The function bodies are generated with the
228 It takes the same arguments as the
230 macro, but should be used only once.
235 argument is the name of a function used to compare trees noded
237 The function takes two arguments of type
238 .Fa "struct TYPE *" .
239 If the first argument is smaller than the second, the function returns a
240 value smaller than zero.
241 If they are equal, the function returns zero.
242 Otherwise, it should return a value greater than zero.
243 The compare function defines the order of the tree elements.
247 macro initializes the tree referenced by
250 The splay tree can also be initialized statically by using the
251 .Fn SPLAY_INITIALIZER
253 .Bd -literal -offset indent
254 SPLAY_HEAD(HEADNAME, TYPE) head = SPLAY_INITIALIZER(\*[Am]head);
259 macro inserts the new element
265 macro removes the element
267 from the tree pointed by
272 macro can be used to find a particular element in the tree.
273 .Bd -literal -offset indent
274 struct TYPE find, *res;
276 res = SPLAY_FIND(NAME, head, \*[Am]find);
285 macros can be used to traverse the tree:
286 .Bd -literal -offset indent
287 for (np = SPLAY_MIN(NAME, \*[Am]head); np != NULL; np = SPLAY_NEXT(NAME, \*[Am]head, np))
290 Or, for simplicity, one can use the
293 .Bd -literal -offset indent
294 SPLAY_FOREACH(np, NAME, head)
299 macro should be used to check whether a splay tree is empty.
301 A red-black tree is a binary search tree with the node color as an
303 It fulfills a set of conditions:
304 .Bl -enum -compact -offset indent
306 every search path from the root to a leaf consists of the same number of
309 each red node (except for the root) has a black parent,
311 each leaf node is black.
314 Every operation on a red-black tree is bounded as O(lg n).
315 The maximum height of a red-black tree is 2lg (n+1).
317 A red-black tree is headed by a structure defined by the
322 structure is declared as follows:
323 .Bd -literal -offset indent
324 RB_HEAD(HEADNAME, TYPE) head;
329 is the name of the structure to be defined, and struct
331 is the type of the elements to be inserted into the tree.
335 macro declares a structure that allows elements to be connected in the tree.
337 In order to use the functions that manipulate the tree structure,
338 their prototypes need to be declared with the
343 is a unique identifier for this particular tree.
346 argument is the type of the structure that is being managed
350 argument is the name of the element defined by
353 The function bodies are generated with the
356 It takes the same arguments as the
358 macro, but should be used only once.
363 argument is the name of a function used to compare trees noded
365 The function takes two arguments of type
366 .Fa "struct TYPE *" .
367 If the first argument is smaller than the second, the function returns a
368 value smaller than zero.
369 If they are equal, the function returns zero.
370 Otherwise, it should return a value greater than zero.
371 The compare function defines the order of the tree elements.
375 macro initializes the tree referenced by
378 The redblack tree can also be initialized statically by using the
381 .Bd -literal -offset indent
382 RB_HEAD(HEADNAME, TYPE) head = RB_INITIALIZER(\*[Am]head);
387 macro inserts the new element
393 macro removes the element
395 from the tree pointed by
400 macro can be used to find a particular element in the tree.
401 .Bd -literal -offset indent
402 struct TYPE find, *res;
404 res = RB_FIND(NAME, head, \*[Am]find);
413 macros can be used to traverse the tree:
414 .Bd -literal -offset indent
415 for (np = RB_MIN(NAME, \*[Am]head); np != NULL; np = RB_NEXT(NAME, \*[Am]head, np))
418 Or, for simplicity, one can use the
421 .Fn RB_FOREACH_REVERSE
423 .Bd -literal -offset indent
424 RB_FOREACH(np, NAME, head)
430 .Fn RB_FOREACH_REVERSE_SAFE
431 traverse the tree referenced by head
432 in a forward or reverse direction respectively,
433 assigning each element in turn to np.
434 However, unlike their unsafe counterparts,
435 they permit both the removal of np
436 as well as freeing it from within the loop safely
437 without interfering with the traversal.
442 .Fn RB_FOREACH_REVERSE_FROM
443 may be used to continue an interrupted traversal
444 in a forward or reverse direction respectively.
445 The head pointer is not required.
446 The pointer to the node from where to resume the traversal
447 should be passed as their last argument,
448 and will be overwritten to provide safe traversal.
452 macro should be used to check whether a red-black tree is empty.
454 Trying to free a tree in the following way is a common error:
455 .Bd -literal -offset indent
456 SPLAY_FOREACH(var, NAME, head) {
457 SPLAY_REMOVE(NAME, head, var);
467 macro refers to a pointer that may have been reallocated already.
468 Proper code needs a second variable.
469 .Bd -literal -offset indent
470 for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
471 nxt = SPLAY_NEXT(NAME, head, var);
472 SPLAY_REMOVE(NAME, head, var);
483 if the element was inserted in the tree successfully, otherwise they
484 return a pointer to the element with the colliding key.
490 return the pointer to the removed element, otherwise they return
492 to indicate an error.
494 The author of the tree macros is