xref: /freebsd/share/man/man3/tree.3 (revision 7029da5c36f2d3cf6bb6c81bf551229f416399e8)
1.\"	$OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $
2.\"
3.\" Copyright 2002 Niels Provos <provos@citi.umich.edu>
4.\" All rights reserved.
5.\"
6.\" Redistribution and use in source and binary forms, with or without
7.\" modification, are permitted provided that the following conditions
8.\" are met:
9.\" 1. Redistributions of source code must retain the above copyright
10.\"    notice, this list of conditions and the following disclaimer.
11.\" 2. Redistributions in binary form must reproduce the above copyright
12.\"    notice, this list of conditions and the following disclaimer in the
13.\"    documentation and/or other materials provided with the distribution.
14.\" 3. All advertising materials mentioning features or use of this software
15.\"    must display the following acknowledgement:
16.\"      This product includes software developed by Niels Provos.
17.\" 4. The name of the author may not be used to endorse or promote products
18.\"    derived from this software without specific prior written permission.
19.\"
20.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
21.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
22.\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
23.\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
24.\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
25.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
29.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30.\"
31.\" $FreeBSD$
32.\"
33.Dd September 28, 2019
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_PROTOTYPE_STATIC ,
56.Nm RB_PROTOTYPE_INSERT ,
57.Nm RB_PROTOTYPE_INSERT_COLOR ,
58.Nm RB_PROTOTYPE_REMOVE ,
59.Nm RB_PROTOTYPE_REMOVE_COLOR ,
60.Nm RB_PROTOTYPE_FIND ,
61.Nm RB_PROTOTYPE_NFIND ,
62.Nm RB_PROTOTYPE_NEXT ,
63.Nm RB_PROTOTYPE_PREV ,
64.Nm RB_PROTOTYPE_MINMAX ,
65.Nm RB_PROTOTYPE_REINSERT ,
66.Nm RB_GENERATE ,
67.Nm RB_GENERATE_STATIC ,
68.Nm RB_GENERATE_INSERT ,
69.Nm RB_GENERATE_INSERT_COLOR ,
70.Nm RB_GENERATE_REMOVE ,
71.Nm RB_GENERATE_REMOVE_COLOR ,
72.Nm RB_GENERATE_FIND ,
73.Nm RB_GENERATE_NFIND ,
74.Nm RB_GENERATE_NEXT ,
75.Nm RB_GENERATE_PREV ,
76.Nm RB_GENERATE_MINMAX ,
77.Nm RB_GENERATE_REINSERT ,
78.Nm RB_ENTRY ,
79.Nm RB_HEAD ,
80.Nm RB_INITIALIZER ,
81.Nm RB_ROOT ,
82.Nm RB_EMPTY ,
83.Nm RB_NEXT ,
84.Nm RB_PREV ,
85.Nm RB_MIN ,
86.Nm RB_MAX ,
87.Nm RB_FIND ,
88.Nm RB_NFIND ,
89.Nm RB_LEFT ,
90.Nm RB_RIGHT ,
91.Nm RB_PARENT ,
92.Nm RB_FOREACH ,
93.Nm RB_FOREACH_FROM ,
94.Nm RB_FOREACH_SAFE ,
95.Nm RB_FOREACH_REVERSE ,
96.Nm RB_FOREACH_REVERSE_FROM ,
97.Nm RB_FOREACH_REVERSE_SAFE ,
98.Nm RB_INIT ,
99.Nm RB_INSERT ,
100.Nm RB_REMOVE ,
101.Nm RB_REINSERT
102.Nd "implementations of splay and red-black trees"
103.Sh SYNOPSIS
104.In sys/tree.h
105.Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP
106.Fn SPLAY_GENERATE NAME TYPE FIELD CMP
107.Fn SPLAY_ENTRY TYPE
108.Fn SPLAY_HEAD HEADNAME TYPE
109.Ft "struct TYPE *"
110.Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
111.Fn SPLAY_ROOT "SPLAY_HEAD *head"
112.Ft bool
113.Fn SPLAY_EMPTY "SPLAY_HEAD *head"
114.Ft "struct TYPE *"
115.Fn SPLAY_NEXT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
116.Ft "struct TYPE *"
117.Fn SPLAY_MIN NAME "SPLAY_HEAD *head"
118.Ft "struct TYPE *"
119.Fn SPLAY_MAX NAME "SPLAY_HEAD *head"
120.Ft "struct TYPE *"
121.Fn SPLAY_FIND NAME "SPLAY_HEAD *head" "struct TYPE *elm"
122.Ft "struct TYPE *"
123.Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME"
124.Ft "struct TYPE *"
125.Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME"
126.Fn SPLAY_FOREACH VARNAME NAME "SPLAY_HEAD *head"
127.Ft void
128.Fn SPLAY_INIT "SPLAY_HEAD *head"
129.Ft "struct TYPE *"
130.Fn SPLAY_INSERT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
131.Ft "struct TYPE *"
132.Fn SPLAY_REMOVE NAME "SPLAY_HEAD *head" "struct TYPE *elm"
133.Fn RB_PROTOTYPE NAME TYPE FIELD CMP
134.Fn RB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
135.Fn RB_PROTOTYPE_INSERT NAME TYPE ATTR
136.Fn RB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR
137.Fn RB_PROTOTYPE_REMOVE NAME TYPE ATTR
138.Fn RB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR
139.Fn RB_PROTOTYPE_FIND NAME TYPE ATTR
140.Fn RB_PROTOTYPE_NFIND NAME TYPE ATTR
141.Fn RB_PROTOTYPE_NEXT NAME TYPE ATTR
142.Fn RB_PROTOTYPE_PREV NAME TYPE ATTR
143.Fn RB_PROTOTYPE_MINMAX NAME TYPE ATTR
144.Fn RB_PROTOTYPE_REINSERT NAME TYPE ATTR
145.Fn RB_GENERATE NAME TYPE FIELD CMP
146.Fn RB_GENERATE_STATIC NAME TYPE FIELD CMP
147.Fn RB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR
148.Fn RB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR
149.Fn RB_GENERATE_REMOVE NAME TYPE FIELD ATTR
150.Fn RB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR
151.Fn RB_GENERATE_FIND NAME TYPE FIELD CMP ATTR
152.Fn RB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR
153.Fn RB_GENERATE_NEXT NAME TYPE FIELD ATTR
154.Fn RB_GENERATE_PREV NAME TYPE FIELD ATTR
155.Fn RB_GENERATE_MINMAX NAME TYPE FIELD ATTR
156.Fn RB_GENERATE_REINSERT NAME TYPE FIELD CMP ATTR
157.Fn RB_ENTRY TYPE
158.Fn RB_HEAD HEADNAME TYPE
159.Fn RB_INITIALIZER "RB_HEAD *head"
160.Ft "struct TYPE *"
161.Fn RB_ROOT "RB_HEAD *head"
162.Ft "bool"
163.Fn RB_EMPTY "RB_HEAD *head"
164.Ft "struct TYPE *"
165.Fn RB_NEXT NAME "RB_HEAD *head" "struct TYPE *elm"
166.Ft "struct TYPE *"
167.Fn RB_PREV NAME "RB_HEAD *head" "struct TYPE *elm"
168.Ft "struct TYPE *"
169.Fn RB_MIN NAME "RB_HEAD *head"
170.Ft "struct TYPE *"
171.Fn RB_MAX NAME "RB_HEAD *head"
172.Ft "struct TYPE *"
173.Fn RB_FIND NAME "RB_HEAD *head" "struct TYPE *elm"
174.Ft "struct TYPE *"
175.Fn RB_NFIND NAME "RB_HEAD *head" "struct TYPE *elm"
176.Ft "struct TYPE *"
177.Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
178.Ft "struct TYPE *"
179.Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME"
180.Ft "struct TYPE *"
181.Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME"
182.Fn RB_FOREACH VARNAME NAME "RB_HEAD *head"
183.Fn RB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME"
184.Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
185.Fn RB_FOREACH_REVERSE VARNAME NAME "RB_HEAD *head"
186.Fn RB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME"
187.Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
188.Ft void
189.Fn RB_INIT "RB_HEAD *head"
190.Ft "struct TYPE *"
191.Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm"
192.Ft "struct TYPE *"
193.Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm"
194.Ft "struct TYPE *"
195.Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm"
196.Sh DESCRIPTION
197These macros define data structures for different types of trees:
198splay trees and red-black trees.
199.Pp
200In the macro definitions,
201.Fa TYPE
202is the name tag of a user defined structure that must contain a field of type
203.Vt SPLAY_ENTRY ,
204or
205.Vt RB_ENTRY ,
206named
207.Fa ENTRYNAME .
208The argument
209.Fa HEADNAME
210is the name tag of a user defined structure that must be declared
211using the macros
212.Fn SPLAY_HEAD ,
213or
214.Fn RB_HEAD .
215The argument
216.Fa NAME
217has to be a unique name prefix for every tree that is defined.
218.Pp
219The function prototypes are declared with
220.Fn SPLAY_PROTOTYPE ,
221.Fn RB_PROTOTYPE ,
222or
223.Fn RB_PROTOTYPE_STATIC .
224The function bodies are generated with
225.Fn SPLAY_GENERATE ,
226.Fn RB_GENERATE ,
227or
228.Fn RB_GENERATE_STATIC .
229See the examples below for further explanation of how these macros are used.
230.Sh SPLAY TREES
231A splay tree is a self-organizing data structure.
232Every operation on the tree causes a splay to happen.
233The splay moves the requested
234node to the root of the tree and partly rebalances it.
235.Pp
236This has the benefit that request locality causes faster lookups as
237the requested nodes move to the top of the tree.
238On the other hand, every lookup causes memory writes.
239.Pp
240The Balance Theorem bounds the total access time for
241.Ar m
242operations and
243.Ar n
244inserts on an initially empty tree as
245.Fn O "\*[lp]m + n\*[rp]lg n" .
246The
247amortized cost for a sequence of
248.Ar m
249accesses to a splay tree is
250.Fn O "lg n" .
251.Pp
252A splay tree is headed by a structure defined by the
253.Fn SPLAY_HEAD
254macro.
255A
256structure is declared as follows:
257.Bd -ragged -offset indent
258.Fn SPLAY_HEAD HEADNAME TYPE
259.Va head ;
260.Ed
261.Pp
262where
263.Fa HEADNAME
264is the name of the structure to be defined, and struct
265.Fa TYPE
266is the type of the elements to be inserted into the tree.
267.Pp
268The
269.Fn SPLAY_ENTRY
270macro declares a structure that allows elements to be connected in the tree.
271.Pp
272In order to use the functions that manipulate the tree structure,
273their prototypes need to be declared with the
274.Fn SPLAY_PROTOTYPE
275macro,
276where
277.Fa NAME
278is a unique identifier for this particular tree.
279The
280.Fa TYPE
281argument is the type of the structure that is being managed
282by the tree.
283The
284.Fa FIELD
285argument is the name of the element defined by
286.Fn SPLAY_ENTRY .
287.Pp
288The function bodies are generated with the
289.Fn SPLAY_GENERATE
290macro.
291It takes the same arguments as the
292.Fn SPLAY_PROTOTYPE
293macro, but should be used only once.
294.Pp
295Finally,
296the
297.Fa CMP
298argument is the name of a function used to compare tree nodes
299with each other.
300The function takes two arguments of type
301.Vt "struct TYPE *" .
302If the first argument is smaller than the second, the function returns a
303value smaller than zero.
304If they are equal, the function returns zero.
305Otherwise, it should return a value greater than zero.
306The compare
307function defines the order of the tree elements.
308.Pp
309The
310.Fn SPLAY_INIT
311macro initializes the tree referenced by
312.Fa head .
313.Pp
314The splay tree can also be initialized statically by using the
315.Fn SPLAY_INITIALIZER
316macro like this:
317.Bd -ragged -offset indent
318.Fn SPLAY_HEAD HEADNAME TYPE
319.Va head
320=
321.Fn SPLAY_INITIALIZER &head ;
322.Ed
323.Pp
324The
325.Fn SPLAY_INSERT
326macro inserts the new element
327.Fa elm
328into the tree.
329.Pp
330The
331.Fn SPLAY_REMOVE
332macro removes the element
333.Fa elm
334from the tree pointed by
335.Fa head .
336.Pp
337The
338.Fn SPLAY_FIND
339macro can be used to find a particular element in the tree.
340.Bd -literal -offset indent
341struct TYPE find, *res;
342find.key = 30;
343res = SPLAY_FIND(NAME, head, &find);
344.Ed
345.Pp
346The
347.Fn SPLAY_ROOT ,
348.Fn SPLAY_MIN ,
349.Fn SPLAY_MAX ,
350and
351.Fn SPLAY_NEXT
352macros can be used to traverse the tree:
353.Bd -literal -offset indent
354for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np))
355.Ed
356.Pp
357Or, for simplicity, one can use the
358.Fn SPLAY_FOREACH
359macro:
360.Bd -ragged -offset indent
361.Fn SPLAY_FOREACH np NAME head
362.Ed
363.Pp
364The
365.Fn SPLAY_EMPTY
366macro should be used to check whether a splay tree is empty.
367.Sh RED-BLACK TREES
368A red-black tree is a binary search tree with the node color as an
369extra attribute.
370It fulfills a set of conditions:
371.Bl -enum -offset indent
372.It
373Every search path from the root to a leaf consists of the same number of
374black nodes.
375.It
376Each red node (except for the root) has a black parent.
377.It
378Each leaf node is black.
379.El
380.Pp
381Every operation on a red-black tree is bounded as
382.Fn O "lg n" .
383The maximum height of a red-black tree is
384.Fn 2lg "n + 1" .
385.Pp
386A red-black tree is headed by a structure defined by the
387.Fn RB_HEAD
388macro.
389A
390structure is declared as follows:
391.Bd -ragged -offset indent
392.Fn RB_HEAD HEADNAME TYPE
393.Va head ;
394.Ed
395.Pp
396where
397.Fa HEADNAME
398is the name of the structure to be defined, and struct
399.Fa TYPE
400is the type of the elements to be inserted into the tree.
401.Pp
402The
403.Fn RB_ENTRY
404macro declares a structure that allows elements to be connected in the tree.
405.Pp
406In order to use the functions that manipulate the tree structure,
407their prototypes need to be declared with the
408.Fn RB_PROTOTYPE
409or
410.Fn RB_PROTOTYPE_STATIC
411macro,
412where
413.Fa NAME
414is a unique identifier for this particular tree.
415The
416.Fa TYPE
417argument is the type of the structure that is being managed
418by the tree.
419The
420.Fa FIELD
421argument is the name of the element defined by
422.Fn RB_ENTRY .
423Individual prototypes can be declared with
424.Fn RB_PROTOTYPE_INSERT ,
425.Fn RB_PROTOTYPE_INSERT_COLOR ,
426.Fn RB_PROTOTYPE_REMOVE ,
427.Fn RB_PROTOTYPE_REMOVE_COLOR ,
428.Fn RB_PROTOTYPE_FIND ,
429.Fn RB_PROTOTYPE_NFIND ,
430.Fn RB_PROTOTYPE_NEXT ,
431.Fn RB_PROTOTYPE_PREV ,
432.Fn RB_PROTOTYPE_MINMAX ,
433and
434.Fn RB_PROTOTYPE_REINSERT
435in case not all functions are required.
436The individual prototype macros expect
437.Fa NAME ,
438.Fa TYPE ,
439and
440.Fa ATTR
441arguments.
442The
443.Fa ATTR
444argument must be empty for global functions or
445.Fa static
446for static functions.
447.Pp
448The function bodies are generated with the
449.Fn RB_GENERATE
450or
451.Fn RB_GENERATE_STATIC
452macro.
453These macros take the same arguments as the
454.Fn RB_PROTOTYPE
455and
456.Fn RB_PROTOTYPE_STATIC
457macros, but should be used only once.
458As an alternative individual function bodies are generated with the
459.Fn RB_GENERATE_INSERT ,
460.Fn RB_GENERATE_INSERT_COLOR ,
461.Fn RB_GENERATE_REMOVE ,
462.Fn RB_GENERATE_REMOVE_COLOR ,
463.Fn RB_GENERATE_FIND ,
464.Fn RB_GENERATE_NFIND ,
465.Fn RB_GENERATE_NEXT ,
466.Fn RB_GENERATE_PREV ,
467.Fn RB_GENERATE_MINMAX ,
468and
469.Fn RB_GENERATE_REINSERT
470macros.
471.Pp
472Finally,
473the
474.Fa CMP
475argument is the name of a function used to compare tree nodes
476with each other.
477The function takes two arguments of type
478.Vt "struct TYPE *" .
479If the first argument is smaller than the second, the function returns a
480value smaller than zero.
481If they are equal, the function returns zero.
482Otherwise, it should return a value greater than zero.
483The compare
484function defines the order of the tree elements.
485.Pp
486The
487.Fn RB_INIT
488macro initializes the tree referenced by
489.Fa head .
490.Pp
491The red-black tree can also be initialized statically by using the
492.Fn RB_INITIALIZER
493macro like this:
494.Bd -ragged -offset indent
495.Fn RB_HEAD HEADNAME TYPE
496.Va head
497=
498.Fn RB_INITIALIZER &head ;
499.Ed
500.Pp
501The
502.Fn RB_INSERT
503macro inserts the new element
504.Fa elm
505into the tree.
506.Pp
507The
508.Fn RB_REMOVE
509macro removes the element
510.Fa elm
511from the tree pointed by
512.Fa head .
513.Pp
514The
515.Fn RB_FIND
516and
517.Fn RB_NFIND
518macros can be used to find a particular element in the tree.
519.Bd -literal -offset indent
520struct TYPE find, *res;
521find.key = 30;
522res = RB_FIND(NAME, head, &find);
523.Ed
524.Pp
525The
526.Fn RB_ROOT ,
527.Fn RB_MIN ,
528.Fn RB_MAX ,
529.Fn RB_NEXT ,
530and
531.Fn RB_PREV
532macros can be used to traverse the tree:
533.Pp
534.Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))"
535.Pp
536Or, for simplicity, one can use the
537.Fn RB_FOREACH
538or
539.Fn RB_FOREACH_REVERSE
540macro:
541.Bd -ragged -offset indent
542.Fn RB_FOREACH np NAME head
543.Ed
544.Pp
545The macros
546.Fn RB_FOREACH_SAFE
547and
548.Fn RB_FOREACH_REVERSE_SAFE
549traverse the tree referenced by head
550in a forward or reverse direction respectively,
551assigning each element in turn to np.
552However, unlike their unsafe counterparts,
553they permit both the removal of np
554as well as freeing it from within the loop safely
555without interfering with the traversal.
556.Pp
557Both
558.Fn RB_FOREACH_FROM
559and
560.Fn RB_FOREACH_REVERSE_FROM
561may be used to continue an interrupted traversal
562in a forward or reverse direction respectively.
563The head pointer is not required.
564The pointer to the node from where to resume the traversal
565should be passed as their last argument,
566and will be overwritten to provide safe traversal.
567.Pp
568The
569.Fn RB_EMPTY
570macro should be used to check whether a red-black tree is empty.
571.Pp
572The
573.Fn RB_REINSERT
574macro updates the position of the element
575.Fa elm
576in the tree.
577This must be called if a member of a
578.Nm tree
579is modified in a way that affects comparison, such as by modifying
580a node's key.
581This is a lower overhead alternative to removing the element
582and reinserting it again.
583.Sh EXAMPLES
584The following example demonstrates how to declare a red-black tree
585holding integers.
586Values are inserted into it and the contents of the tree are printed
587in order.
588Lastly, the internal structure of the tree is printed.
589.Bd -literal -offset 3n
590#include <sys/tree.h>
591#include <err.h>
592#include <stdio.h>
593#include <stdlib.h>
594
595struct node {
596	RB_ENTRY(node) entry;
597	int i;
598};
599
600int
601intcmp(struct node *e1, struct node *e2)
602{
603	return (e1->i < e2->i ? -1 : e1->i > e2->i);
604}
605
606RB_HEAD(inttree, node) head = RB_INITIALIZER(&head);
607RB_GENERATE(inttree, node, entry, intcmp)
608
609int testdata[] = {
610	20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 10, 19, 5, 9, 12, 15, 18,
611	7, 11, 14
612};
613
614void
615print_tree(struct node *n)
616{
617	struct node *left, *right;
618
619	if (n == NULL) {
620		printf("nil");
621		return;
622	}
623	left = RB_LEFT(n, entry);
624	right = RB_RIGHT(n, entry);
625	if (left == NULL && right == NULL)
626		printf("%d", n->i);
627	else {
628		printf("%d(", n->i);
629		print_tree(left);
630		printf(",");
631		print_tree(right);
632		printf(")");
633	}
634}
635
636int
637main(void)
638{
639	int i;
640	struct node *n;
641
642	for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) {
643		if ((n = malloc(sizeof(struct node))) == NULL)
644			err(1, NULL);
645		n->i = testdata[i];
646		RB_INSERT(inttree, &head, n);
647	}
648
649	RB_FOREACH(n, inttree, &head) {
650		printf("%d\en", n->i);
651	}
652	print_tree(RB_ROOT(&head));
653	printf("\en");
654	return (0);
655}
656.Ed
657.Sh NOTES
658Trying to free a tree in the following way is a common error:
659.Bd -literal -offset indent
660SPLAY_FOREACH(var, NAME, head) {
661	SPLAY_REMOVE(NAME, head, var);
662	free(var);
663}
664free(head);
665.Ed
666.Pp
667Since
668.Va var
669is freed, the
670.Fn FOREACH
671macro refers to a pointer that may have been reallocated already.
672Proper code needs a second variable.
673.Bd -literal -offset indent
674for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
675	nxt = SPLAY_NEXT(NAME, head, var);
676	SPLAY_REMOVE(NAME, head, var);
677	free(var);
678}
679.Ed
680.Pp
681Both
682.Fn RB_INSERT
683and
684.Fn SPLAY_INSERT
685return
686.Dv NULL
687if the element was inserted in the tree successfully, otherwise they
688return a pointer to the element with the colliding key.
689.Pp
690Accordingly,
691.Fn RB_REMOVE
692and
693.Fn SPLAY_REMOVE
694return the pointer to the removed element otherwise they return
695.Dv NULL
696to indicate an error.
697.Sh SEE ALSO
698.Xr arb 3 ,
699.Xr queue 3
700.Sh AUTHORS
701The author of the tree macros is
702.An Niels Provos .
703