inpcb: Factor out function to obtain lport hash token.
[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 .\"/*
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 August 9, 2015
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_FOREACH_FROM ,
69 .Nm RB_FOREACH_SAFE ,
70 .Nm RB_FOREACH_REVERSE ,
71 .Nm RB_FOREACH_REVERSE_FROM ,
72 .Nm RB_FOREACH_REVERSE_SAFE ,
73 .Nm RB_INIT ,
74 .Nm RB_INSERT ,
75 .Nm RB_REMOVE
76 .Nd implementations of splay and red-black trees
77 .Sh SYNOPSIS
78 .In sys/tree.h
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"
83 .Ft "struct TYPE *"
84 .Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
85 .Fn SPLAY_ROOT "SPLAY_HEAD *head"
86 .Ft "bool"
87 .Fn SPLAY_EMPTY "SPLAY_HEAD *head"
88 .Ft "struct TYPE *"
89 .Fn SPLAY_NEXT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
90 .Ft "struct TYPE *"
91 .Fn SPLAY_MIN "NAME" "SPLAY_HEAD *head"
92 .Ft "struct TYPE *"
93 .Fn SPLAY_MAX "NAME" "SPLAY_HEAD *head"
94 .Ft "struct TYPE *"
95 .Fn SPLAY_FIND "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
96 .Ft "struct TYPE *"
97 .Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME"
98 .Ft "struct TYPE *"
99 .Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME"
100 .Fn SPLAY_FOREACH "VARNAME" "NAME" "SPLAY_HEAD *head"
101 .Ft void
102 .Fn SPLAY_INIT "SPLAY_HEAD *head"
103 .Ft "struct TYPE *"
104 .Fn SPLAY_INSERT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
105 .Ft "struct TYPE *"
106 .Fn SPLAY_REMOVE "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
107 .Pp
108 .Fn RB_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP"
109 .Fn RB_GENERATE "NAME" "TYPE" "FIELD" "CMP"
110 .Fn RB_ENTRY "TYPE"
111 .Fn RB_HEAD "HEADNAME" "TYPE"
112 .Fn RB_INITIALIZER "RB_HEAD *head"
113 .Ft "struct TYPE *"
114 .Fn RB_ROOT "RB_HEAD *head"
115 .Ft "bool"
116 .Fn RB_EMPTY "RB_HEAD *head"
117 .Ft "struct TYPE *"
118 .Fn RB_NEXT "NAME" "RB_HEAD *head" "struct TYPE *elm"
119 .Ft "struct TYPE *"
120 .Fn RB_MIN "NAME" "RB_HEAD *head"
121 .Ft "struct TYPE *"
122 .Fn RB_MAX "NAME" "RB_HEAD *head"
123 .Ft "struct TYPE *"
124 .Fn RB_FIND "NAME" "RB_HEAD *head" "struct TYPE *elm"
125 .Ft "struct TYPE *"
126 .Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
127 .Ft "struct TYPE *"
128 .Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME"
129 .Ft "struct TYPE *"
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"
137 .Ft void
138 .Fn RB_INIT "RB_HEAD *head"
139 .Ft "struct TYPE *"
140 .Fn RB_INSERT "NAME" "RB_HEAD *head" "struct TYPE *elm"
141 .Ft "struct TYPE *"
142 .Fn RB_REMOVE "NAME" "RB_HEAD *head" "struct TYPE *elm"
143 .Sh DESCRIPTION
144 These macros define data structures for different types of trees:
145 splay trees and red-black trees.
146 .Pp
147 In the macro definitions,
148 .Fa TYPE
149 is the name tag of a user defined structure that must contain a field of type
150 .Li SPLAY_ENTRY ,
151 or
152 .Li RB_ENTRY ,
153 named
154 .Fa ENTRYNAME .
155 The argument
156 .Fa HEADNAME
157 is the name tag of a user defined structure that must be declared
158 using the macros
159 .Fn SPLAY_HEAD
160 or
161 .Fn RB_HEAD .
162 The argument
163 .Fa NAME
164 has to be a unique name prefix for every tree that is defined.
165 .Pp
166 The function prototypes are declared with either
167 .Li SPLAY_PROTOTYPE
168 or
169 .Li RB_PROTOTYPE .
170 The function bodies are generated with either
171 .Li SPLAY_GENERATE
172 or
173 .Li RB_GENERATE .
174 See the examples below for further explanation of how these macros are used.
175 .Sh SPLAY TREES
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
179 rebalances it.
180 .Pp
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.
184 .Pp
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).
188 .Pp
189 A splay tree is headed by a structure defined by the
190 .Fn SPLAY_HEAD
191 macro.
192 A
193 .Fa SPLAY_HEAD
194 structure is declared as follows:
195 .Bd -literal -offset indent
196 SPLAY_HEAD(HEADNAME, TYPE) head;
197 .Ed
198 .Pp
199 where
200 .Fa HEADNAME
201 is the name of the structure to be defined, and struct
202 .Fa TYPE
203 is the type of the elements to be inserted into the tree.
204 .Pp
205 The
206 .Fn SPLAY_ENTRY
207 macro declares a structure that allows elements to be connected in the tree.
208 .Pp
209 In order to use the functions that manipulate the tree structure,
210 their prototypes need to be declared with the
211 .Fn SPLAY_PROTOTYPE
212 macro,
213 where
214 .Fa NAME
215 is a unique identifier for this particular tree.
216 The
217 .Fa TYPE
218 argument is the type of the structure that is being managed
219 by the tree.
220 The
221 .Fa FIELD
222 argument is the name of the element defined by
223 .Fn SPLAY_ENTRY .
224 .Pp
225 The function bodies are generated with the
226 .Fn SPLAY_GENERATE
227 macro.
228 It takes the same arguments as the
229 .Fn SPLAY_PROTOTYPE
230 macro, but should be used only once.
231 .Pp
232 Finally,
233 the
234 .Fa CMP
235 argument is the name of a function used to compare trees noded
236 with each other.
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.
244 .Pp
245 The
246 .Fn SPLAY_INIT
247 macro initializes the tree referenced by
248 .Fa head .
249 .Pp
250 The splay tree can also be initialized statically by using the
251 .Fn SPLAY_INITIALIZER
252 macro like this:
253 .Bd -literal -offset indent
254 SPLAY_HEAD(HEADNAME, TYPE) head = SPLAY_INITIALIZER(\*[Am]head);
255 .Ed
256 .Pp
257 The
258 .Fn SPLAY_INSERT
259 macro inserts the new element
260 .Fa elm
261 into the tree.
262 .Pp
263 The
264 .Fn SPLAY_REMOVE
265 macro removes the element
266 .Fa elm
267 from the tree pointed by
268 .Fa head .
269 .Pp
270 The
271 .Fn SPLAY_FIND
272 macro can be used to find a particular element in the tree.
273 .Bd -literal -offset indent
274 struct TYPE find, *res;
275 find.key = 30;
276 res = SPLAY_FIND(NAME, head, \*[Am]find);
277 .Ed
278 .Pp
279 The
280 .Fn SPLAY_ROOT ,
281 .Fn SPLAY_MIN ,
282 .Fn SPLAY_MAX ,
283 and
284 .Fn SPLAY_NEXT
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))
288 .Ed
289 .Pp
290 Or, for simplicity, one can use the
291 .Fn SPLAY_FOREACH
292 macro:
293 .Bd -literal -offset indent
294 SPLAY_FOREACH(np, NAME, head)
295 .Ed
296 .Pp
297 The
298 .Fn SPLAY_EMPTY
299 macro should be used to check whether a splay tree is empty.
300 .Sh RED-BLACK TREES
301 A red-black tree is a binary search tree with the node color as an
302 extra attribute.
303 It fulfills a set of conditions:
304 .Bl -enum -compact -offset indent
305 .It
306 every search path from the root to a leaf consists of the same number of
307 black nodes,
308 .It
309 each red node (except for the root) has a black parent,
310 .It
311 each leaf node is black.
312 .El
313 .Pp
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).
316 .Pp
317 A red-black tree is headed by a structure defined by the
318 .Fn RB_HEAD
319 macro.
320 A
321 .Fa RB_HEAD
322 structure is declared as follows:
323 .Bd -literal -offset indent
324 RB_HEAD(HEADNAME, TYPE) head;
325 .Ed
326 .Pp
327 where
328 .Fa HEADNAME
329 is the name of the structure to be defined, and struct
330 .Fa TYPE
331 is the type of the elements to be inserted into the tree.
332 .Pp
333 The
334 .Fn RB_ENTRY
335 macro declares a structure that allows elements to be connected in the tree.
336 .Pp
337 In order to use the functions that manipulate the tree structure,
338 their prototypes need to be declared with the
339 .Fn RB_PROTOTYPE
340 macro,
341 where
342 .Fa NAME
343 is a unique identifier for this particular tree.
344 The
345 .Fa TYPE
346 argument is the type of the structure that is being managed
347 by the tree.
348 The
349 .Fa FIELD
350 argument is the name of the element defined by
351 .Fn RB_ENTRY .
352 .Pp
353 The function bodies are generated with the
354 .Fn RB_GENERATE
355 macro.
356 It takes the same arguments as the
357 .Fn RB_PROTOTYPE
358 macro, but should be used only once.
359 .Pp
360 Finally,
361 the
362 .Fa CMP
363 argument is the name of a function used to compare trees noded
364 with each other.
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.
372 .Pp
373 The
374 .Fn RB_INIT
375 macro initializes the tree referenced by
376 .Fa head .
377 .Pp
378 The redblack tree can also be initialized statically by using the
379 .Fn RB_INITIALIZER
380 macro like this:
381 .Bd -literal -offset indent
382 RB_HEAD(HEADNAME, TYPE) head = RB_INITIALIZER(\*[Am]head);
383 .Ed
384 .Pp
385 The
386 .Fn RB_INSERT
387 macro inserts the new element
388 .Fa elm
389 into the tree.
390 .Pp
391 The
392 .Fn RB_REMOVE
393 macro removes the element
394 .Fa elm
395 from the tree pointed by
396 .Fa head .
397 .Pp
398 The
399 .Fn RB_FIND
400 macro can be used to find a particular element in the tree.
401 .Bd -literal -offset indent
402 struct TYPE find, *res;
403 find.key = 30;
404 res = RB_FIND(NAME, head, \*[Am]find);
405 .Ed
406 .Pp
407 The
408 .Fn RB_ROOT ,
409 .Fn RB_MIN ,
410 .Fn RB_MAX ,
411 and
412 .Fn RB_NEXT
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))
416 .Ed
417 .Pp
418 Or, for simplicity, one can use the
419 .Fn RB_FOREACH
420 or
421 .Fn RB_FOREACH_REVERSE
422 macro:
423 .Bd -literal -offset indent
424 RB_FOREACH(np, NAME, head)
425 .Ed
426 .Pp
427 The macros
428 .Fn RB_FOREACH_SAFE
429 and
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.
438 .Pp
439 Both
440 .Fn RB_FOREACH_FROM
441 and
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.
449 .Pp
450 The
451 .Fn RB_EMPTY
452 macro should be used to check whether a red-black tree is empty.
453 .Sh NOTES
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);
458         free(var);
459 }
460 free(head);
461 .Ed
462 .Pp
463 Since
464 .Va var
465 is free'd, the
466 .Fn SPLAY_FOREACH
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);
473         free(var);
474 }
475 .Ed
476 .Pp
477 Both
478 .Fn RB_INSERT
479 and
480 .Fn SPLAY_INSERT
481 return
482 .Dv NULL
483 if the element was inserted in the tree successfully, otherwise they
484 return a pointer to the element with the colliding key.
485 .Pp
486 Accordingly,
487 .Fn RB_REMOVE
488 and
489 .Fn SPLAY_REMOVE
490 return the pointer to the removed element, otherwise they return
491 .Dv NULL
492 to indicate an error.
493 .Sh AUTHORS
494 The author of the tree macros is
495 .An Niels Provos .