| blob | 9bfe554f8b055cde1268c2414dccc42c9b6973e6 |
1 .\" $NetBSD: tree.3,v 1.4 2008/10/07 13:03:50 apb Exp $
2 .\" $OpenBSD: tree.3,v 1.9 2003/05/20 09:13:38 jmc Exp $
3 .\"/*
4 .\" * Copyright 2002 Niels Provos <provos@citi.umich.edu>
5 .\" * All rights reserved.
6 .\" *
7 .\" * Redistribution and use in source and binary forms, with or without
8 .\" * modification, are permitted provided that the following conditions
9 .\" * are met:
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.
20 .\" *
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.
31 .\" */
32 .Dd February 14, 2009
33 .Dt TREE 3
34 .Os
35 .Sh NAME
36 .Nm SPLAY_PROTOTYPE ,
37 .Nm SPLAY_GENERATE ,
38 .Nm SPLAY_ENTRY ,
39 .Nm SPLAY_HEAD ,
40 .Nm SPLAY_INITIALIZER ,
41 .Nm SPLAY_ROOT ,
42 .Nm SPLAY_EMPTY ,
43 .Nm SPLAY_NEXT ,
44 .Nm SPLAY_MIN ,
45 .Nm SPLAY_MAX ,
46 .Nm SPLAY_FIND ,
47 .Nm SPLAY_LEFT ,
48 .Nm SPLAY_RIGHT ,
49 .Nm SPLAY_FOREACH ,
50 .Nm SPLAY_INIT ,
51 .Nm SPLAY_INSERT ,
52 .Nm SPLAY_REMOVE ,
53 .Nm RB_PROTOTYPE ,
54 .Nm RB_GENERATE ,
55 .Nm RB_ENTRY ,
56 .Nm RB_HEAD ,
57 .Nm RB_INITIALIZER ,
58 .Nm RB_ROOT ,
59 .Nm RB_EMPTY ,
60 .Nm RB_NEXT ,
61 .Nm RB_MIN ,
62 .Nm RB_MAX ,
63 .Nm RB_FIND ,
64 .Nm RB_LEFT ,
65 .Nm RB_RIGHT ,
66 .Nm RB_PARENT ,
67 .Nm RB_FOREACH ,
68 .Nm RB_INIT ,
69 .Nm RB_INSERT ,
70 .Nm RB_REMOVE
71 .Nd implementations of splay and red-black trees
72 .Sh SYNOPSIS
73 .In sys/tree.h
74 .Fn SPLAY_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP"
75 .Fn SPLAY_GENERATE "NAME" "TYPE" "FIELD" "CMP"
76 .Fn SPLAY_ENTRY "TYPE"
77 .Fn SPLAY_HEAD "HEADNAME" "TYPE"
78 .Ft "struct TYPE *"
79 .Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
80 .Fn SPLAY_ROOT "SPLAY_HEAD *head"
81 .Ft "bool"
82 .Fn SPLAY_EMPTY "SPLAY_HEAD *head"
83 .Ft "struct TYPE *"
84 .Fn SPLAY_NEXT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
85 .Ft "struct TYPE *"
86 .Fn SPLAY_MIN "NAME" "SPLAY_HEAD *head"
87 .Ft "struct TYPE *"
88 .Fn SPLAY_MAX "NAME" "SPLAY_HEAD *head"
89 .Ft "struct TYPE *"
90 .Fn SPLAY_FIND "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
91 .Ft "struct TYPE *"
92 .Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME"
93 .Ft "struct TYPE *"
94 .Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME"
95 .Fn SPLAY_FOREACH "VARNAME" "NAME" "SPLAY_HEAD *head"
96 .Ft void
97 .Fn SPLAY_INIT "SPLAY_HEAD *head"
98 .Ft "struct TYPE *"
99 .Fn SPLAY_INSERT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
100 .Ft "struct TYPE *"
101 .Fn SPLAY_REMOVE "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
102 .Pp
103 .Fn RB_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP"
104 .Fn RB_GENERATE "NAME" "TYPE" "FIELD" "CMP"
105 .Fn RB_ENTRY "TYPE"
106 .Fn RB_HEAD "HEADNAME" "TYPE"
107 .Fn RB_INITIALIZER "RB_HEAD *head"
108 .Ft "struct TYPE *"
109 .Fn RB_ROOT "RB_HEAD *head"
110 .Ft "bool"
111 .Fn RB_EMPTY "RB_HEAD *head"
112 .Ft "struct TYPE *"
113 .Fn RB_NEXT "NAME" "RB_HEAD *head" "struct TYPE *elm"
114 .Ft "struct TYPE *"
115 .Fn RB_MIN "NAME" "RB_HEAD *head"
116 .Ft "struct TYPE *"
117 .Fn RB_MAX "NAME" "RB_HEAD *head"
118 .Ft "struct TYPE *"
119 .Fn RB_FIND "NAME" "RB_HEAD *head" "struct TYPE *elm"
120 .Ft "struct TYPE *"
121 .Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
122 .Ft "struct TYPE *"
123 .Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME"
124 .Ft "struct TYPE *"
125 .Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME"
126 .Fn RB_FOREACH "VARNAME" "NAME" "RB_HEAD *head"
127 .Ft void
128 .Fn RB_INIT "RB_HEAD *head"
129 .Ft "struct TYPE *"
130 .Fn RB_INSERT "NAME" "RB_HEAD *head" "struct TYPE *elm"
131 .Ft "struct TYPE *"
132 .Fn RB_REMOVE "NAME" "RB_HEAD *head" "struct TYPE *elm"
133 .Sh DESCRIPTION
134 These macros define data structures for different types of trees:
135 splay trees and red-black trees.
136 .Pp
137 In the macro definitions,
138 .Fa TYPE
139 is the name tag of a user defined structure that must contain a field of type
140 .Li SPLAY_ENTRY ,
141 or
142 .Li RB_ENTRY ,
143 named
144 .Fa ENTRYNAME .
145 The argument
146 .Fa HEADNAME
147 is the name tag of a user defined structure that must be declared
148 using the macros
149 .Fn SPLAY_HEAD
150 or
151 .Fn RB_HEAD .
152 The argument
153 .Fa NAME
154 has to be a unique name prefix for every tree that is defined.
155 .Pp
156 The function prototypes are declared with either
157 .Li SPLAY_PROTOTYPE
158 or
159 .Li RB_PROTOTYPE .
160 The function bodies are generated with either
161 .Li SPLAY_GENERATE
162 or
163 .Li RB_GENERATE .
164 See the examples below for further explanation of how these macros are used.
165 .Sh SPLAY TREES
166 A splay tree is a self-organizing data structure.
167 Every operation on the tree causes a splay to happen.
168 The splay moves the requested node to the root of the tree and partly
169 rebalances it.
170 .Pp
171 This has the benefit that request locality causes faster lookups as
172 the requested nodes move to the top of the tree.
173 On the other hand, every lookup causes memory writes.
174 .Pp
175 The Balance Theorem bounds the total access time for m operations
176 and n inserts on an initially empty tree as O((m + n)lg n).
177 The amortized cost for a sequence of m accesses to a splay tree is O(lg n).
178 .Pp
179 A splay tree is headed by a structure defined by the
180 .Fn SPLAY_HEAD
181 macro.
182 A
183 .Fa SPLAY_HEAD
184 structure is declared as follows:
185 .Bd -literal -offset indent
186 SPLAY_HEAD(HEADNAME, TYPE) head;
187 .Ed
188 .Pp
189 where
190 .Fa HEADNAME
191 is the name of the structure to be defined, and struct
192 .Fa TYPE
193 is the type of the elements to be inserted into the tree.
194 .Pp
195 The
196 .Fn SPLAY_ENTRY
197 macro declares a structure that allows elements to be connected in the tree.
198 .Pp
199 In order to use the functions that manipulate the tree structure,
200 their prototypes need to be declared with the
201 .Fn SPLAY_PROTOTYPE
202 macro,
203 where
204 .Fa NAME
205 is a unique identifier for this particular tree.
206 The
207 .Fa TYPE
208 argument is the type of the structure that is being managed
209 by the tree.
210 The
211 .Fa FIELD
212 argument is the name of the element defined by
213 .Fn SPLAY_ENTRY .
214 .Pp
215 The function bodies are generated with the
216 .Fn SPLAY_GENERATE
217 macro.
218 It takes the same arguments as the
219 .Fn SPLAY_PROTOTYPE
220 macro, but should be used only once.
221 .Pp
222 Finally,
223 the
224 .Fa CMP
225 argument is the name of a function used to compare trees noded
226 with each other.
227 The function takes two arguments of type
228 .Fa "struct TYPE *" .
229 If the first argument is smaller than the second, the function returns a
230 value smaller than zero.
231 If they are equal, the function returns zero.
232 Otherwise, it should return a value greater than zero.
233 The compare function defines the order of the tree elements.
234 .Pp
235 The
236 .Fn SPLAY_INIT
237 macro initializes the tree referenced by
238 .Fa head .
239 .Pp
240 The splay tree can also be initialized statically by using the
241 .Fn SPLAY_INITIALIZER
242 macro like this:
243 .Bd -literal -offset indent
244 SPLAY_HEAD(HEADNAME, TYPE) head = SPLAY_INITIALIZER(\*[Am]head);
245 .Ed
246 .Pp
247 The
248 .Fn SPLAY_INSERT
249 macro inserts the new element
250 .Fa elm
251 into the tree.
252 .Pp
253 The
254 .Fn SPLAY_REMOVE
255 macro removes the element
256 .Fa elm
257 from the tree pointed by
258 .Fa head .
259 .Pp
260 The
261 .Fn SPLAY_FIND
262 macro can be used to find a particular element in the tree.
263 .Bd -literal -offset indent
264 struct TYPE find, *res;
265 find.key = 30;
266 res = SPLAY_FIND(NAME, head, \*[Am]find);
267 .Ed
268 .Pp
269 The
270 .Fn SPLAY_ROOT ,
271 .Fn SPLAY_MIN ,
272 .Fn SPLAY_MAX ,
273 and
274 .Fn SPLAY_NEXT
275 macros can be used to traverse the tree:
276 .Bd -literal -offset indent
277 for (np = SPLAY_MIN(NAME, \*[Am]head); np != NULL; np = SPLAY_NEXT(NAME, \*[Am]head, np))
278 .Ed
279 .Pp
280 Or, for simplicity, one can use the
281 .Fn SPLAY_FOREACH
282 macro:
283 .Bd -literal -offset indent
284 SPLAY_FOREACH(np, NAME, head)
285 .Ed
286 .Pp
287 The
288 .Fn SPLAY_EMPTY
289 macro should be used to check whether a splay tree is empty.
290 .Sh RED-BLACK TREES
291 A red-black tree is a binary search tree with the node color as an
292 extra attribute.
293 It fulfills a set of conditions:
294 .Bl -enum -compact -offset indent
295 .It
296 every search path from the root to a leaf consists of the same number of
297 black nodes,
298 .It
299 each red node (except for the root) has a black parent,
300 .It
301 each leaf node is black.
302 .El
303 .Pp
304 Every operation on a red-black tree is bounded as O(lg n).
305 The maximum height of a red-black tree is 2lg (n+1).
306 .Pp
307 A red-black tree is headed by a structure defined by the
308 .Fn RB_HEAD
309 macro.
310 A
311 .Fa RB_HEAD
312 structure is declared as follows:
313 .Bd -literal -offset indent
314 RB_HEAD(HEADNAME, TYPE) head;
315 .Ed
316 .Pp
317 where
318 .Fa HEADNAME
319 is the name of the structure to be defined, and struct
320 .Fa TYPE
321 is the type of the elements to be inserted into the tree.
322 .Pp
323 The
324 .Fn RB_ENTRY
325 macro declares a structure that allows elements to be connected in the tree.
326 .Pp
327 In order to use the functions that manipulate the tree structure,
328 their prototypes need to be declared with the
329 .Fn RB_PROTOTYPE
330 macro,
331 where
332 .Fa NAME
333 is a unique identifier for this particular tree.
334 The
335 .Fa TYPE
336 argument is the type of the structure that is being managed
337 by the tree.
338 The
339 .Fa FIELD
340 argument is the name of the element defined by
341 .Fn RB_ENTRY .
342 .Pp
343 The function bodies are generated with the
344 .Fn RB_GENERATE
345 macro.
346 It takes the same arguments as the
347 .Fn RB_PROTOTYPE
348 macro, but should be used only once.
349 .Pp
350 Finally,
351 the
352 .Fa CMP
353 argument is the name of a function used to compare trees noded
354 with each other.
355 The function takes two arguments of type
356 .Fa "struct TYPE *" .
357 If the first argument is smaller than the second, the function returns a
358 value smaller than zero.
359 If they are equal, the function returns zero.
360 Otherwise, it should return a value greater than zero.
361 The compare function defines the order of the tree elements.
362 .Pp
363 The
364 .Fn RB_INIT
365 macro initializes the tree referenced by
366 .Fa head .
367 .Pp
368 The redblack tree can also be initialized statically by using the
369 .Fn RB_INITIALIZER
370 macro like this:
371 .Bd -literal -offset indent
372 RB_HEAD(HEADNAME, TYPE) head = RB_INITIALIZER(\*[Am]head);
373 .Ed
374 .Pp
375 The
376 .Fn RB_INSERT
377 macro inserts the new element
378 .Fa elm
379 into the tree.
380 .Pp
381 The
382 .Fn RB_REMOVE
383 macro removes the element
384 .Fa elm
385 from the tree pointed to by
386 .Fa head .
387 The element must be present in that tree.
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 Some of these macros or functions perform no error checking,
421 and invalid usage leads to undefined behaviour.
422 In the case of macros or functions that expect their arguments
423 to be elements that are present in the tree, passing an element
424 that is not present in the tree is invalid.
425 .Pp
426 Trying to free a tree in the following way is a common error:
427 .Bd -literal -offset indent
428 SPLAY_FOREACH(var, NAME, head) {
429 SPLAY_REMOVE(NAME, head, var);
430 free(var);
431 }
432 free(head);
433 .Ed
434 .Pp
435 Since
436 .Va var
437 is free'd, the
438 .Fn FOREACH
439 macro refers to a pointer that may have been reallocated already.
440 Proper code needs a second variable.
441 .Bd -literal -offset indent
442 for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
443 nxt = SPLAY_NEXT(NAME, head, var);
444 SPLAY_REMOVE(NAME, head, var);
445 free(var);
446 }
447 .Ed
448 .Pp
449 Both
450 .Fn RB_INSERT
451 and
452 .Fn SPLAY_INSERT
453 return
454 .Dv NULL
455 if the element was inserted in the tree successfully, otherwise they
456 return a pointer to the element with the colliding key.
457 .Pp
458 Accordingly,
459 .Fn RB_REMOVE
460 and
461 .Fn SPLAY_REMOVE
462 return the pointer to the removed element, otherwise they return
463 .Dv NULL
464 to indicate an error.
465 .Sh AUTHORS
466 The author of the tree macros is
467 .An Niels Provos .