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 $
3 .\" $DragonFly: src/share/man/man3/tree.3,v 1.2 2008/05/10 17:52:10 swildner Exp $
5 .\" * Copyright 2002 Niels Provos <provos@citi.umich.edu>
6 .\" * All rights reserved.
8 .\" * Redistribution and use in source and binary forms, with or without
9 .\" * modification, are permitted provided that the following conditions
11 .\" * 1. Redistributions of source code must retain the above copyright
12 .\" * notice, this list of conditions and the following disclaimer.
13 .\" * 2. Redistributions in binary form must reproduce the above copyright
14 .\" * notice, this list of conditions and the following disclaimer in the
15 .\" * documentation and/or other materials provided with the distribution.
16 .\" * 3. All advertising materials mentioning features or use of this software
17 .\" * must display the following acknowledgement:
18 .\" * This product includes software developed by Niels Provos.
19 .\" * 4. The name of the author may not be used to endorse or promote products
20 .\" * derived from this software without specific prior written permission.
22 .\" * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
23 .\" * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
24 .\" * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
25 .\" * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
26 .\" * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
27 .\" * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 .\" * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 .\" * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 .\" * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
31 .\" * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
41 .Nm SPLAY_INITIALIZER ,
72 .Nd implementations of splay and red-black trees
75 .Fn SPLAY_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP"
76 .Fn SPLAY_GENERATE "NAME" "TYPE" "FIELD" "CMP"
77 .Fn SPLAY_ENTRY "TYPE"
78 .Fn SPLAY_HEAD "HEADNAME" "TYPE"
80 .Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
81 .Fn SPLAY_ROOT "SPLAY_HEAD *head"
83 .Fn SPLAY_EMPTY "SPLAY_HEAD *head"
85 .Fn SPLAY_NEXT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
87 .Fn SPLAY_MIN "NAME" "SPLAY_HEAD *head"
89 .Fn SPLAY_MAX "NAME" "SPLAY_HEAD *head"
91 .Fn SPLAY_FIND "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
93 .Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME"
95 .Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME"
96 .Fn SPLAY_FOREACH "VARNAME" "NAME" "SPLAY_HEAD *head"
98 .Fn SPLAY_INIT "SPLAY_HEAD *head"
100 .Fn SPLAY_INSERT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
102 .Fn SPLAY_REMOVE "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
104 .Fn RB_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP"
105 .Fn RB_GENERATE "NAME" "TYPE" "FIELD" "CMP"
107 .Fn RB_HEAD "HEADNAME" "TYPE"
108 .Fn RB_INITIALIZER "RB_HEAD *head"
110 .Fn RB_ROOT "RB_HEAD *head"
112 .Fn RB_EMPTY "RB_HEAD *head"
114 .Fn RB_NEXT "NAME" "RB_HEAD *head" "struct TYPE *elm"
116 .Fn RB_MIN "NAME" "RB_HEAD *head"
118 .Fn RB_MAX "NAME" "RB_HEAD *head"
120 .Fn RB_FIND "NAME" "RB_HEAD *head" "struct TYPE *elm"
122 .Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
124 .Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME"
126 .Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME"
127 .Fn RB_FOREACH "VARNAME" "NAME" "RB_HEAD *head"
129 .Fn RB_INIT "RB_HEAD *head"
131 .Fn RB_INSERT "NAME" "RB_HEAD *head" "struct TYPE *elm"
133 .Fn RB_REMOVE "NAME" "RB_HEAD *head" "struct TYPE *elm"
135 These macros define data structures for different types of trees:
136 splay trees and red-black trees.
138 In the macro definitions,
140 is the name tag of a user defined structure that must contain a field of type
148 is the name tag of a user defined structure that must be declared
155 has to be a unique name prefix for every tree that is defined.
157 The function prototypes are declared with either
161 The function bodies are generated with either
165 See the examples below for further explanation of how these macros are used.
167 A splay tree is a self-organizing data structure.
168 Every operation on the tree causes a splay to happen.
169 The splay moves the requested node to the root of the tree and partly
172 This has the benefit that request locality causes faster lookups as
173 the requested nodes move to the top of the tree.
174 On the other hand, every lookup causes memory writes.
176 The Balance Theorem bounds the total access time for m operations
177 and n inserts on an initially empty tree as O((m + n)lg n).
178 The amortized cost for a sequence of m accesses to a splay tree is O(lg n).
180 A splay tree is headed by a structure defined by the
185 structure is declared as follows:
186 .Bd -literal -offset indent
187 SPLAY_HEAD(HEADNAME, TYPE) head;
192 is the name of the structure to be defined, and struct
194 is the type of the elements to be inserted into the tree.
198 macro declares a structure that allows elements to be connected in the tree.
200 In order to use the functions that manipulate the tree structure,
201 their prototypes need to be declared with the
206 is a unique identifier for this particular tree.
209 argument is the type of the structure that is being managed
213 argument is the name of the element defined by
216 The function bodies are generated with the
219 It takes the same arguments as the
221 macro, but should be used only once.
226 argument is the name of a function used to compare trees noded
228 The function takes two arguments of type
229 .Fa "struct TYPE *" .
230 If the first argument is smaller than the second, the function returns a
231 value smaller than zero.
232 If they are equal, the function returns zero.
233 Otherwise, it should return a value greater than zero.
234 The compare function defines the order of the tree elements.
238 macro initializes the tree referenced by
241 The splay tree can also be initialized statically by using the
242 .Fn SPLAY_INITIALIZER
244 .Bd -literal -offset indent
245 SPLAY_HEAD(HEADNAME, TYPE) head = SPLAY_INITIALIZER(\*[Am]head);
250 macro inserts the new element
256 macro removes the element
258 from the tree pointed by
263 macro can be used to find a particular element in the tree.
264 .Bd -literal -offset indent
265 struct TYPE find, *res;
267 res = SPLAY_FIND(NAME, head, \*[Am]find);
276 macros can be used to traverse the tree:
277 .Bd -literal -offset indent
278 for (np = SPLAY_MIN(NAME, \*[Am]head); np != NULL; np = SPLAY_NEXT(NAME, \*[Am]head, np))
281 Or, for simplicity, one can use the
284 .Bd -literal -offset indent
285 SPLAY_FOREACH(np, NAME, head)
290 macro should be used to check whether a splay tree is empty.
292 A red-black tree is a binary search tree with the node color as an
294 It fulfills a set of conditions:
295 .Bl -enum -compact -offset indent
297 every search path from the root to a leaf consists of the same number of
300 each red node (except for the root) has a black parent,
302 each leaf node is black.
305 Every operation on a red-black tree is bounded as O(lg n).
306 The maximum height of a red-black tree is 2lg (n+1).
308 A red-black tree is headed by a structure defined by the
313 structure is declared as follows:
314 .Bd -literal -offset indent
315 RB_HEAD(HEADNAME, TYPE) head;
320 is the name of the structure to be defined, and struct
322 is the type of the elements to be inserted into the tree.
326 macro declares a structure that allows elements to be connected in the tree.
328 In order to use the functions that manipulate the tree structure,
329 their prototypes need to be declared with the
334 is a unique identifier for this particular tree.
337 argument is the type of the structure that is being managed
341 argument is the name of the element defined by
344 The function bodies are generated with the
347 It takes the same arguments as the
349 macro, but should be used only once.
354 argument is the name of a function used to compare trees noded
356 The function takes two arguments of type
357 .Fa "struct TYPE *" .
358 If the first argument is smaller than the second, the function returns a
359 value smaller than zero.
360 If they are equal, the function returns zero.
361 Otherwise, it should return a value greater than zero.
362 The compare function defines the order of the tree elements.
366 macro initializes the tree referenced by
369 The redblack tree can also be initialized statically by using the
372 .Bd -literal -offset indent
373 RB_HEAD(HEADNAME, TYPE) head = RB_INITIALIZER(\*[Am]head);
378 macro inserts the new element
384 macro removes the element
386 from the tree pointed by
391 macro can be used to find a particular element in the tree.
392 .Bd -literal -offset indent
393 struct TYPE find, *res;
395 res = RB_FIND(NAME, head, \*[Am]find);
404 macros can be used to traverse the tree:
405 .Bd -literal -offset indent
406 for (np = RB_MIN(NAME, \*[Am]head); np != NULL; np = RB_NEXT(NAME, \*[Am]head, np))
409 Or, for simplicity, one can use the
412 .Bd -literal -offset indent
413 RB_FOREACH(np, NAME, head)
418 macro should be used to check whether a red-black tree is empty.
420 Trying to free a tree in the following way is a common error:
421 .Bd -literal -offset indent
422 SPLAY_FOREACH(var, NAME, head) {
423 SPLAY_REMOVE(NAME, head, var);
433 macro refers to a pointer that may have been reallocated already.
434 Proper code needs a second variable.
435 .Bd -literal -offset indent
436 for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
437 nxt = SPLAY_NEXT(NAME, head, var);
438 SPLAY_REMOVE(NAME, head, var);
449 if the element was inserted in the tree successfully, otherwise they
450 return a pointer to the element with the colliding key.
456 return the pointer to the removed element, otherwise they return
458 to indicate an error.
460 The author of the tree macros is