Add implemenation of splay tree and red-black tree.
[dragonfly.git] / share / man / man3 / tree.3
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.1 2004/08/19 20:38:33 joerg Exp $
4 .\"/*
5 .\" * Copyright 2002 Niels Provos <provos@citi.umich.edu>
6 .\" * All rights reserved.
7 .\" *
8 .\" * Redistribution and use in source and binary forms, with or without
9 .\" * modification, are permitted provided that the following conditions
10 .\" * are met:
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.
21 .\" *
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.
32 .\" */
33 .Dd February 24, 2002
34 .Dt TREE 3
35 .Os
36 .Sh NAME
37 .Nm SPLAY_PROTOTYPE ,
38 .Nm SPLAY_GENERATE ,
39 .Nm SPLAY_ENTRY ,
40 .Nm SPLAY_HEAD ,
41 .Nm SPLAY_INITIALIZER ,
42 .Nm SPLAY_ROOT ,
43 .Nm SPLAY_EMPTY ,
44 .Nm SPLAY_NEXT ,
45 .Nm SPLAY_MIN ,
46 .Nm SPLAY_MAX ,
47 .Nm SPLAY_FIND ,
48 .Nm SPLAY_LEFT ,
49 .Nm SPLAY_RIGHT ,
50 .Nm SPLAY_FOREACH ,
51 .Nm SPLAY_INIT ,
52 .Nm SPLAY_INSERT ,
53 .Nm SPLAY_REMOVE ,
54 .Nm RB_PROTOTYPE ,
55 .Nm RB_GENERATE ,
56 .Nm RB_ENTRY ,
57 .Nm RB_HEAD ,
58 .Nm RB_INITIALIZER ,
59 .Nm RB_ROOT ,
60 .Nm RB_EMPTY ,
61 .Nm RB_NEXT ,
62 .Nm RB_MIN ,
63 .Nm RB_MAX ,
64 .Nm RB_FIND ,
65 .Nm RB_LEFT ,
66 .Nm RB_RIGHT ,
67 .Nm RB_PARENT ,
68 .Nm RB_FOREACH ,
69 .Nm RB_INIT ,
70 .Nm RB_INSERT ,
71 .Nm RB_REMOVE
72 .Nd implementations of splay and red-black trees
73 .Sh SYNOPSIS
74 .In sys/tree.h
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"
79 .Ft "struct TYPE *"
80 .Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
81 .Fn SPLAY_ROOT "SPLAY_HEAD *head"
82 .Ft "bool"
83 .Fn SPLAY_EMPTY "SPLAY_HEAD *head"
84 .Ft "struct TYPE *"
85 .Fn SPLAY_NEXT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
86 .Ft "struct TYPE *"
87 .Fn SPLAY_MIN "NAME" "SPLAY_HEAD *head"
88 .Ft "struct TYPE *"
89 .Fn SPLAY_MAX "NAME" "SPLAY_HEAD *head"
90 .Ft "struct TYPE *"
91 .Fn SPLAY_FIND "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
92 .Ft "struct TYPE *"
93 .Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME"
94 .Ft "struct TYPE *"
95 .Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME"
96 .Fn SPLAY_FOREACH "VARNAME" "NAME" "SPLAY_HEAD *head"
97 .Ft void
98 .Fn SPLAY_INIT "SPLAY_HEAD *head"
99 .Ft "struct TYPE *"
100 .Fn SPLAY_INSERT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
101 .Ft "struct TYPE *"
102 .Fn SPLAY_REMOVE "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
103 .Pp
104 .Fn RB_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP"
105 .Fn RB_GENERATE "NAME" "TYPE" "FIELD" "CMP"
106 .Fn RB_ENTRY "TYPE"
107 .Fn RB_HEAD "HEADNAME" "TYPE"
108 .Fn RB_INITIALIZER "RB_HEAD *head"
109 .Ft "struct TYPE *"
110 .Fn RB_ROOT "RB_HEAD *head"
111 .Ft "bool"
112 .Fn RB_EMPTY "RB_HEAD *head"
113 .Ft "struct TYPE *"
114 .Fn RB_NEXT "NAME" "RB_HEAD *head" "struct TYPE *elm"
115 .Ft "struct TYPE *"
116 .Fn RB_MIN "NAME" "RB_HEAD *head"
117 .Ft "struct TYPE *"
118 .Fn RB_MAX "NAME" "RB_HEAD *head"
119 .Ft "struct TYPE *"
120 .Fn RB_FIND "NAME" "RB_HEAD *head" "struct TYPE *elm"
121 .Ft "struct TYPE *"
122 .Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
123 .Ft "struct TYPE *"
124 .Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME"
125 .Ft "struct TYPE *"
126 .Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME"
127 .Fn RB_FOREACH "VARNAME" "NAME" "RB_HEAD *head"
128 .Ft void
129 .Fn RB_INIT "RB_HEAD *head"
130 .Ft "struct TYPE *"
131 .Fn RB_INSERT "NAME" "RB_HEAD *head" "struct TYPE *elm"
132 .Ft "struct TYPE *"
133 .Fn RB_REMOVE "NAME" "RB_HEAD *head" "struct TYPE *elm"
134 .Sh DESCRIPTION
135 These macros define data structures for different types of trees:
136 splay trees and red-black trees.
137 .Pp
138 In the macro definitions,
139 .Fa TYPE
140 is the name tag of a user defined structure that must contain a field of type
141 .Li SPLAY_ENTRY ,
142 or
143 .Li RB_ENTRY ,
144 named
145 .Fa ENTRYNAME .
146 The argument
147 .Fa HEADNAME
148 is the name tag of a user defined structure that must be declared
149 using the macros
150 .Fn SPLAY_HEAD
151 or
152 .Fn RB_HEAD .
153 The argument
154 .Fa NAME
155 has to be a unique name prefix for every tree that is defined.
156 .Pp
157 The function prototypes are declared with either
158 .Li SPLAY_PROTOTYPE
159 or
160 .Li RB_PROTOTYPE .
161 The function bodies are generated with either
162 .Li SPLAY_GENERATE
163 or
164 .Li RB_GENERATE .
165 See the examples below for further explanation of how these macros are used.
166 .Sh SPLAY TREES
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
170 rebalances it.
171 .Pp
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.
175 .Pp
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).
179 .Pp
180 A splay tree is headed by a structure defined by the
181 .Fn SPLAY_HEAD
182 macro.
183 A
184 .Fa SPLAY_HEAD
185 structure is declared as follows:
186 .Bd -literal -offset indent
187 SPLAY_HEAD(HEADNAME, TYPE) head;
188 .Ed
189 .Pp
190 where
191 .Fa HEADNAME
192 is the name of the structure to be defined, and struct
193 .Fa TYPE
194 is the type of the elements to be inserted into the tree.
195 .Pp
196 The
197 .Fn SPLAY_ENTRY
198 macro declares a structure that allows elements to be connected in the tree.
199 .Pp
200 In order to use the functions that manipulate the tree structure,
201 their prototypes need to be declared with the
202 .Fn SPLAY_PROTOTYPE
203 macro,
204 where
205 .Fa NAME
206 is a unique identifier for this particular tree.
207 The
208 .Fa TYPE
209 argument is the type of the structure that is being managed
210 by the tree.
211 The
212 .Fa FIELD
213 argument is the name of the element defined by
214 .Fn SPLAY_ENTRY .
215 .Pp
216 The function bodies are generated with the
217 .Fn SPLAY_GENERATE
218 macro.
219 It takes the same arguments as the
220 .Fn SPLAY_PROTOTYPE
221 macro, but should be used only once.
222 .Pp
223 Finally,
224 the
225 .Fa CMP
226 argument is the name of a function used to compare trees noded
227 with each other.
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.
235 .Pp
236 The
237 .Fn SPLAY_INIT
238 macro initializes the tree referenced by
239 .Fa head .
240 .Pp
241 The splay tree can also be initialized statically by using the
242 .Fn SPLAY_INITIALIZER
243 macro like this:
244 .Bd -literal -offset indent
245 SPLAY_HEAD(HEADNAME, TYPE) head = SPLAY_INITIALIZER(\*[Am]head);
246 .Ed
247 .Pp
248 The
249 .Fn SPLAY_INSERT
250 macro inserts the new element
251 .Fa elm
252 into the tree.
253 .Pp
254 The
255 .Fn SPLAY_REMOVE
256 macro removes the element
257 .Fa elm
258 from the tree pointed by
259 .Fa head .
260 .Pp
261 The
262 .Fn SPLAY_FIND
263 macro can be used to find a particular element in the tree.
264 .Bd -literal -offset indent
265 struct TYPE find, *res;
266 find.key = 30;
267 res = SPLAY_FIND(NAME, head, \*[Am]find);
268 .Ed
269 .Pp
270 The
271 .Fn SPLAY_ROOT ,
272 .Fn SPLAY_MIN ,
273 .Fn SPLAY_MAX ,
274 and
275 .Fn SPLAY_NEXT
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))
279 .Ed
280 .Pp
281 Or, for simplicity, one can use the
282 .Fn SPLAY_FOREACH
283 macro:
284 .Bd -literal -offset indent
285 SPLAY_FOREACH(np, NAME, head)
286 .Ed
287 .Pp
288 The
289 .Fn SPLAY_EMPTY
290 macro should be used to check whether a splay tree is empty.
291 .Sh RED-BLACK TREES
292 A red-black tree is a binary search tree with the node color as an
293 extra attribute.
294 It fulfills a set of conditions:
295 .Bl -enum -compact -offset indent
296 .It
297 every search path from the root to a leaf consists of the same number of
298 black nodes,
299 .It
300 each red node (except for the root) has a black parent,
301 .It
302 each leaf node is black.
303 .El
304 .Pp
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).
307 .Pp
308 A red-black tree is headed by a structure defined by the
309 .Fn RB_HEAD
310 macro.
311 A
312 .Fa RB_HEAD
313 structure is declared as follows:
314 .Bd -literal -offset indent
315 RB_HEAD(HEADNAME, TYPE) head;
316 .Ed
317 .Pp
318 where
319 .Fa HEADNAME
320 is the name of the structure to be defined, and struct
321 .Fa TYPE
322 is the type of the elements to be inserted into the tree.
323 .Pp
324 The
325 .Fn RB_ENTRY
326 macro declares a structure that allows elements to be connected in the tree.
327 .Pp
328 In order to use the functions that manipulate the tree structure,
329 their prototypes need to be declared with the
330 .Fn RB_PROTOTYPE
331 macro,
332 where
333 .Fa NAME
334 is a unique identifier for this particular tree.
335 The
336 .Fa TYPE
337 argument is the type of the structure that is being managed
338 by the tree.
339 The
340 .Fa FIELD
341 argument is the name of the element defined by
342 .Fn RB_ENTRY .
343 .Pp
344 The function bodies are generated with the
345 .Fn RB_GENERATE
346 macro.
347 It takes the same arguments as the
348 .Fn RB_PROTOTYPE
349 macro, but should be used only once.
350 .Pp
351 Finally,
352 the
353 .Fa CMP
354 argument is the name of a function used to compare trees noded
355 with each other.
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.
363 .Pp
364 The
365 .Fn RB_INIT
366 macro initializes the tree referenced by
367 .Fa head .
368 .Pp
369 The redblack tree can also be initialized statically by using the
370 .Fn RB_INITIALIZER
371 macro like this:
372 .Bd -literal -offset indent
373 RB_HEAD(HEADNAME, TYPE) head = RB_INITIALIZER(\*[Am]head);
374 .Ed
375 .Pp
376 The
377 .Fn RB_INSERT
378 macro inserts the new element
379 .Fa elm
380 into the tree.
381 .Pp
382 The
383 .Fn RB_REMOVE
384 macro removes the element
385 .Fa elm
386 from the tree pointed by
387 .Fa head .
388 .Pp
389 The
390 .Fn RB_FIND
391 macro can be used to find a particular element in the tree.
392 .Bd -literal -offset indent
393 struct TYPE find, *res;
394 find.key = 30;
395 res = RB_FIND(NAME, head, \*[Am]find);
396 .Ed
397 .Pp
398 The
399 .Fn RB_ROOT ,
400 .Fn RB_MIN ,
401 .Fn RB_MAX ,
402 and
403 .Fn RB_NEXT
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))
407 .Ed
408 .Pp
409 Or, for simplicity, one can use the
410 .Fn RB_FOREACH
411 macro:
412 .Bd -literal -offset indent
413 RB_FOREACH(np, NAME, head)
414 .Ed
415 .Pp
416 The
417 .Fn RB_EMPTY
418 macro should be used to check whether a red-black tree is empty.
419 .Sh NOTES
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);
424         free(var);
425 }
426 free(head);
427 .Ed
428 .Pp
429 Since
430 .Va var
431 is free'd, the
432 .Fn FOREACH
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);
439         free(var);
440 }
441 .Ed
442 .Pp
443 Both
444 .Fn RB_INSERT
445 and
446 .Fn SPLAY_INSERT
447 return
448 .Dv NULL
449 if the element was inserted in the tree successfully, otherwise they
450 return a pointer to the element with the colliding key.
451 .Pp
452 Accordingly,
453 .Fn RB_REMOVE
454 and
455 .Fn SPLAY_REMOVE
456 return the pointer to the removed element, otherwise they return
457 .Dv NULL
458 to indicate an error.
459 .Sh AUTHORS
460 The author of the tree macros is
461 .An Niels Provos .