xref: /freebsd/share/man/man3/tree.3 (revision 3a3af6b2a160bea72509a9d5ef84e25906b0478a)
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 July 27, 2020
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.Nm RB_AUGMENT
103.Nm RB_UPDATE_AUGMENT
104.Nd "implementations of splay and rank-balanced (wavl) trees"
105.Sh SYNOPSIS
106.In sys/tree.h
107.Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP
108.Fn SPLAY_GENERATE NAME TYPE FIELD CMP
109.Fn SPLAY_ENTRY TYPE
110.Fn SPLAY_HEAD HEADNAME TYPE
111.Ft "struct TYPE *"
112.Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
113.Fn SPLAY_ROOT "SPLAY_HEAD *head"
114.Ft bool
115.Fn SPLAY_EMPTY "SPLAY_HEAD *head"
116.Ft "struct TYPE *"
117.Fn SPLAY_NEXT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
118.Ft "struct TYPE *"
119.Fn SPLAY_MIN NAME "SPLAY_HEAD *head"
120.Ft "struct TYPE *"
121.Fn SPLAY_MAX NAME "SPLAY_HEAD *head"
122.Ft "struct TYPE *"
123.Fn SPLAY_FIND NAME "SPLAY_HEAD *head" "struct TYPE *elm"
124.Ft "struct TYPE *"
125.Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME"
126.Ft "struct TYPE *"
127.Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME"
128.Fn SPLAY_FOREACH VARNAME NAME "SPLAY_HEAD *head"
129.Ft void
130.Fn SPLAY_INIT "SPLAY_HEAD *head"
131.Ft "struct TYPE *"
132.Fn SPLAY_INSERT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
133.Ft "struct TYPE *"
134.Fn SPLAY_REMOVE NAME "SPLAY_HEAD *head" "struct TYPE *elm"
135.Fn RB_PROTOTYPE NAME TYPE FIELD CMP
136.Fn RB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
137.Fn RB_PROTOTYPE_INSERT NAME TYPE ATTR
138.Fn RB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR
139.Fn RB_PROTOTYPE_REMOVE NAME TYPE ATTR
140.Fn RB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR
141.Fn RB_PROTOTYPE_FIND NAME TYPE ATTR
142.Fn RB_PROTOTYPE_NFIND NAME TYPE ATTR
143.Fn RB_PROTOTYPE_NEXT NAME TYPE ATTR
144.Fn RB_PROTOTYPE_PREV NAME TYPE ATTR
145.Fn RB_PROTOTYPE_MINMAX NAME TYPE ATTR
146.Fn RB_PROTOTYPE_REINSERT NAME TYPE ATTR
147.Fn RB_GENERATE NAME TYPE FIELD CMP
148.Fn RB_GENERATE_STATIC NAME TYPE FIELD CMP
149.Fn RB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR
150.Fn RB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR
151.Fn RB_GENERATE_REMOVE NAME TYPE FIELD ATTR
152.Fn RB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR
153.Fn RB_GENERATE_FIND NAME TYPE FIELD CMP ATTR
154.Fn RB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR
155.Fn RB_GENERATE_NEXT NAME TYPE FIELD ATTR
156.Fn RB_GENERATE_PREV NAME TYPE FIELD ATTR
157.Fn RB_GENERATE_MINMAX NAME TYPE FIELD ATTR
158.Fn RB_GENERATE_REINSERT NAME TYPE FIELD CMP ATTR
159.Fn RB_ENTRY TYPE
160.Fn RB_HEAD HEADNAME TYPE
161.Fn RB_INITIALIZER "RB_HEAD *head"
162.Ft "struct TYPE *"
163.Fn RB_ROOT "RB_HEAD *head"
164.Ft "bool"
165.Fn RB_EMPTY "RB_HEAD *head"
166.Ft "struct TYPE *"
167.Fn RB_NEXT NAME "RB_HEAD *head" "struct TYPE *elm"
168.Ft "struct TYPE *"
169.Fn RB_PREV NAME "RB_HEAD *head" "struct TYPE *elm"
170.Ft "struct TYPE *"
171.Fn RB_MIN NAME "RB_HEAD *head"
172.Ft "struct TYPE *"
173.Fn RB_MAX NAME "RB_HEAD *head"
174.Ft "struct TYPE *"
175.Fn RB_FIND NAME "RB_HEAD *head" "struct TYPE *elm"
176.Ft "struct TYPE *"
177.Fn RB_NFIND NAME "RB_HEAD *head" "struct TYPE *elm"
178.Ft "struct TYPE *"
179.Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
180.Ft "struct TYPE *"
181.Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME"
182.Ft "struct TYPE *"
183.Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME"
184.Fn RB_FOREACH VARNAME NAME "RB_HEAD *head"
185.Fn RB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME"
186.Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
187.Fn RB_FOREACH_REVERSE VARNAME NAME "RB_HEAD *head"
188.Fn RB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME"
189.Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
190.Ft void
191.Fn RB_INIT "RB_HEAD *head"
192.Ft "struct TYPE *"
193.Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm"
194.Ft "struct TYPE *"
195.Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm"
196.Ft "struct TYPE *"
197.Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm"
198.Ft "void"
199.Fn RB_AUGMENT NAME "struct TYPE *elm"
200.Ft "void"
201.Fn RB_UPDATE_AUGMENT NAME "struct TYPE *elm"
202.Sh DESCRIPTION
203These macros define data structures for different types of trees:
204splay trees and rank-balanced (wavl) trees.
205.Pp
206In the macro definitions,
207.Fa TYPE
208is the name tag of a user defined structure that must contain a field of type
209.Vt SPLAY_ENTRY ,
210or
211.Vt RB_ENTRY ,
212named
213.Fa ENTRYNAME .
214The argument
215.Fa HEADNAME
216is the name tag of a user defined structure that must be declared
217using the macros
218.Fn SPLAY_HEAD ,
219or
220.Fn RB_HEAD .
221The argument
222.Fa NAME
223has to be a unique name prefix for every tree that is defined.
224.Pp
225The function prototypes are declared with
226.Fn SPLAY_PROTOTYPE ,
227.Fn RB_PROTOTYPE ,
228or
229.Fn RB_PROTOTYPE_STATIC .
230The function bodies are generated with
231.Fn SPLAY_GENERATE ,
232.Fn RB_GENERATE ,
233or
234.Fn RB_GENERATE_STATIC .
235See the examples below for further explanation of how these macros are used.
236.Sh SPLAY TREES
237A splay tree is a self-organizing data structure.
238Every operation on the tree causes a splay to happen.
239The splay moves the requested
240node to the root of the tree and partly rebalances it.
241.Pp
242This has the benefit that request locality causes faster lookups as
243the requested nodes move to the top of the tree.
244On the other hand, every lookup causes memory writes.
245.Pp
246The Balance Theorem bounds the total access time for
247.Ar m
248operations and
249.Ar n
250inserts on an initially empty tree as
251.Fn O "\*[lp]m + n\*[rp]lg n" .
252The
253amortized cost for a sequence of
254.Ar m
255accesses to a splay tree is
256.Fn O "lg n" .
257.Pp
258A splay tree is headed by a structure defined by the
259.Fn SPLAY_HEAD
260macro.
261A
262structure is declared as follows:
263.Bd -ragged -offset indent
264.Fn SPLAY_HEAD HEADNAME TYPE
265.Va head ;
266.Ed
267.Pp
268where
269.Fa HEADNAME
270is the name of the structure to be defined, and struct
271.Fa TYPE
272is the type of the elements to be inserted into the tree.
273.Pp
274The
275.Fn SPLAY_ENTRY
276macro declares a structure that allows elements to be connected in the tree.
277.Pp
278In order to use the functions that manipulate the tree structure,
279their prototypes need to be declared with the
280.Fn SPLAY_PROTOTYPE
281macro,
282where
283.Fa NAME
284is a unique identifier for this particular tree.
285The
286.Fa TYPE
287argument is the type of the structure that is being managed
288by the tree.
289The
290.Fa FIELD
291argument is the name of the element defined by
292.Fn SPLAY_ENTRY .
293.Pp
294The function bodies are generated with the
295.Fn SPLAY_GENERATE
296macro.
297It takes the same arguments as the
298.Fn SPLAY_PROTOTYPE
299macro, but should be used only once.
300.Pp
301Finally,
302the
303.Fa CMP
304argument is the name of a function used to compare tree nodes
305with each other.
306The function takes two arguments of type
307.Vt "struct TYPE *" .
308If the first argument is smaller than the second, the function returns a
309value smaller than zero.
310If they are equal, the function returns zero.
311Otherwise, it should return a value greater than zero.
312The compare
313function defines the order of the tree elements.
314.Pp
315The
316.Fn SPLAY_INIT
317macro initializes the tree referenced by
318.Fa head .
319.Pp
320The splay tree can also be initialized statically by using the
321.Fn SPLAY_INITIALIZER
322macro like this:
323.Bd -ragged -offset indent
324.Fn SPLAY_HEAD HEADNAME TYPE
325.Va head
326=
327.Fn SPLAY_INITIALIZER &head ;
328.Ed
329.Pp
330The
331.Fn SPLAY_INSERT
332macro inserts the new element
333.Fa elm
334into the tree.
335.Pp
336The
337.Fn SPLAY_REMOVE
338macro removes the element
339.Fa elm
340from the tree pointed by
341.Fa head .
342.Pp
343The
344.Fn SPLAY_FIND
345macro can be used to find a particular element in the tree.
346.Bd -literal -offset indent
347struct TYPE find, *res;
348find.key = 30;
349res = SPLAY_FIND(NAME, head, &find);
350.Ed
351.Pp
352The
353.Fn SPLAY_ROOT ,
354.Fn SPLAY_MIN ,
355.Fn SPLAY_MAX ,
356and
357.Fn SPLAY_NEXT
358macros can be used to traverse the tree:
359.Bd -literal -offset indent
360for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np))
361.Ed
362.Pp
363Or, for simplicity, one can use the
364.Fn SPLAY_FOREACH
365macro:
366.Bd -ragged -offset indent
367.Fn SPLAY_FOREACH np NAME head
368.Ed
369.Pp
370The
371.Fn SPLAY_EMPTY
372macro should be used to check whether a splay tree is empty.
373.Sh RANK-BALANCED TREES
374Rank-balanced (RB) trees are a framework for defining height-balanced
375binary search trees, including AVL and red-black trees.
376Each tree node has an associated rank.
377Balance conditions are expressed by conditions on the differences in
378rank between any node and its children.
379Rank differences are stored in each tree node.
380.Pp
381The balance conditions implemented by the RB macros lead to weak AVL
382(wavl) trees, which combine the best aspects of AVL and red-black
383trees.
384Wavl trees rebalance after an insertion in the same way AVL trees do,
385with the same worst-case time as red-black trees offer, and with
386better balance in the resulting tree.
387Wavl trees rebalance after a removal in a way that requires less
388restructuring, in the worst case, than either AVL or red-black trees
389do.
390Removals can lead to a tree almost as unbalanced as a red-black
391tree; insertions lead to a tree becoming as balanced as an AVL tree.
392.Pp
393A rank-balanced tree is headed by a structure defined by the
394.Fn RB_HEAD
395macro.
396A
397structure is declared as follows:
398.Bd -ragged -offset indent
399.Fn RB_HEAD HEADNAME TYPE
400.Va head ;
401.Ed
402.Pp
403where
404.Fa HEADNAME
405is the name of the structure to be defined, and struct
406.Fa TYPE
407is the type of the elements to be inserted into the tree.
408.Pp
409The
410.Fn RB_ENTRY
411macro declares a structure that allows elements to be connected in the tree.
412.Pp
413In order to use the functions that manipulate the tree structure,
414their prototypes need to be declared with the
415.Fn RB_PROTOTYPE
416or
417.Fn RB_PROTOTYPE_STATIC
418macro,
419where
420.Fa NAME
421is a unique identifier for this particular tree.
422The
423.Fa TYPE
424argument is the type of the structure that is being managed
425by the tree.
426The
427.Fa FIELD
428argument is the name of the element defined by
429.Fn RB_ENTRY .
430Individual prototypes can be declared with
431.Fn RB_PROTOTYPE_INSERT ,
432.Fn RB_PROTOTYPE_INSERT_COLOR ,
433.Fn RB_PROTOTYPE_REMOVE ,
434.Fn RB_PROTOTYPE_REMOVE_COLOR ,
435.Fn RB_PROTOTYPE_FIND ,
436.Fn RB_PROTOTYPE_NFIND ,
437.Fn RB_PROTOTYPE_NEXT ,
438.Fn RB_PROTOTYPE_PREV ,
439.Fn RB_PROTOTYPE_MINMAX ,
440and
441.Fn RB_PROTOTYPE_REINSERT
442in case not all functions are required.
443The individual prototype macros expect
444.Fa NAME ,
445.Fa TYPE ,
446and
447.Fa ATTR
448arguments.
449The
450.Fa ATTR
451argument must be empty for global functions or
452.Fa static
453for static functions.
454.Pp
455The function bodies are generated with the
456.Fn RB_GENERATE
457or
458.Fn RB_GENERATE_STATIC
459macro.
460These macros take the same arguments as the
461.Fn RB_PROTOTYPE
462and
463.Fn RB_PROTOTYPE_STATIC
464macros, but should be used only once.
465As an alternative individual function bodies are generated with the
466.Fn RB_GENERATE_INSERT ,
467.Fn RB_GENERATE_INSERT_COLOR ,
468.Fn RB_GENERATE_REMOVE ,
469.Fn RB_GENERATE_REMOVE_COLOR ,
470.Fn RB_GENERATE_FIND ,
471.Fn RB_GENERATE_NFIND ,
472.Fn RB_GENERATE_NEXT ,
473.Fn RB_GENERATE_PREV ,
474.Fn RB_GENERATE_MINMAX ,
475and
476.Fn RB_GENERATE_REINSERT
477macros.
478.Pp
479Finally,
480the
481.Fa CMP
482argument is the name of a function used to compare tree nodes
483with each other.
484The function takes two arguments of type
485.Vt "struct TYPE *" .
486If the first argument is smaller than the second, the function returns a
487value smaller than zero.
488If they are equal, the function returns zero.
489Otherwise, it should return a value greater than zero.
490The compare
491function defines the order of the tree elements.
492.Pp
493The
494.Fn RB_INIT
495macro initializes the tree referenced by
496.Fa head .
497.Pp
498The rank-balanced tree can also be initialized statically by using the
499.Fn RB_INITIALIZER
500macro like this:
501.Bd -ragged -offset indent
502.Fn RB_HEAD HEADNAME TYPE
503.Va head
504=
505.Fn RB_INITIALIZER &head ;
506.Ed
507.Pp
508The
509.Fn RB_INSERT
510macro inserts the new element
511.Fa elm
512into the tree.
513.Pp
514The
515.Fn RB_REMOVE
516macro removes the element
517.Fa elm
518from the tree pointed by
519.Fa head .
520.Pp
521The
522.Fn RB_FIND
523and
524.Fn RB_NFIND
525macros can be used to find a particular element in the tree.
526.Pp
527The
528.Fn RB_FIND
529macro returns the element in the tree equal to the provided
530key, or
531.Dv NULL
532if there is no such element.
533.Pp
534The
535.Fn RB_NFIND
536macro returns the least element greater than or equal to the provided
537key, or
538.Dv NULL
539if there is no such element.
540.Bd -literal -offset indent
541struct TYPE find, *res, *resn;
542find.key = 30;
543res = RB_FIND(NAME, head, &find);
544resn = RB_NFIND(NAME, head, &find);
545.Ed
546.Pp
547The
548.Fn RB_ROOT ,
549.Fn RB_MIN ,
550.Fn RB_MAX ,
551.Fn RB_NEXT ,
552and
553.Fn RB_PREV
554macros can be used to traverse the tree:
555.Pp
556.Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))"
557.Pp
558Or, for simplicity, one can use the
559.Fn RB_FOREACH
560or
561.Fn RB_FOREACH_REVERSE
562macro:
563.Bd -ragged -offset indent
564.Fn RB_FOREACH np NAME head
565.Ed
566.Pp
567The macros
568.Fn RB_FOREACH_SAFE
569and
570.Fn RB_FOREACH_REVERSE_SAFE
571traverse the tree referenced by head
572in a forward or reverse direction respectively,
573assigning each element in turn to np.
574However, unlike their unsafe counterparts,
575they permit both the removal of np
576as well as freeing it from within the loop safely
577without interfering with the traversal.
578.Pp
579Both
580.Fn RB_FOREACH_FROM
581and
582.Fn RB_FOREACH_REVERSE_FROM
583may be used to continue an interrupted traversal
584in a forward or reverse direction respectively.
585The head pointer is not required.
586The pointer to the node from where to resume the traversal
587should be passed as their last argument,
588and will be overwritten to provide safe traversal.
589.Pp
590The
591.Fn RB_EMPTY
592macro should be used to check whether a rank-balanced tree is empty.
593.Pp
594The
595.Fn RB_REINSERT
596macro updates the position of the element
597.Fa elm
598in the tree.
599This must be called if a member of a
600.Nm tree
601is modified in a way that affects comparison, such as by modifying
602a node's key.
603This is a lower overhead alternative to removing the element
604and reinserting it again.
605.Pp
606The
607.Fn RB_AUGMENT
608macro updates augmentation data of the element
609.Fa elm
610in the tree.
611By default, it has no effect.
612It is not meant to be invoked by the RB user.
613If
614.Fn RB_AUGMENT
615is defined by the RB user, then when an element is inserted or removed
616from the tree, it is invoked for every element in the tree that is the
617root of an altered subtree, working from the bottom of the tree up to
618the top.
619It is typically used to maintain some associative accumulation of tree
620elements, such as sums, minima, maxima, and the like.
621.Pp
622The
623.Fn RB_UPDATE_AUGMENT
624macro updates augmentation data of the element
625.Fa elm
626and its ancestors in the tree.
627If
628.Fn RB_AUGMENT
629is defined by the RB user, then when an element in the
630tree is changed, without changing the order of items in the tree,
631invoking this function on that element restores consistency of the
632augmentation state of the tree as if the element had been removed and
633inserted again.
634.Sh EXAMPLES
635The following example demonstrates how to declare a rank-balanced tree
636holding integers.
637Values are inserted into it and the contents of the tree are printed
638in order.
639To maintain the sum of the values in the tree, each element maintains
640the sum of its value and the sums from its left and right subtrees.
641Lastly, the internal structure of the tree is printed.
642.Bd -literal -offset 3n
643#include <sys/tree.h>
644#include <err.h>
645#include <stdio.h>
646#include <stdlib.h>
647
648struct node {
649	RB_ENTRY(node) entry;
650	int i, sum;
651};
652
653int
654intcmp(struct node *e1, struct node *e2)
655{
656	return (e1->i < e2->i ? -1 : e1->i > e2->i);
657}
658
659int
660sumaug(struct node *e)
661{
662	e->sum = e->i;
663	if (RB_LEFT(e, entry) != NULL)
664		e->sum += RB_LEFT(e, entry)->sum;
665	if (RB_RIGHT(e, entry) != NULL)
666		e->sum += RB_RIGHT(e, entry)->sum;
667}
668#define RB_AUGMENT(entry) sumaug(entry)
669
670RB_HEAD(inttree, node) head = RB_INITIALIZER(&head);
671RB_GENERATE(inttree, node, entry, intcmp)
672
673int testdata[] = {
674	20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 10, 19, 5, 9, 12, 15, 18,
675	7, 11, 14
676};
677
678void
679print_tree(struct node *n)
680{
681	struct node *left, *right;
682
683	if (n == NULL) {
684		printf("nil");
685		return;
686	}
687	left = RB_LEFT(n, entry);
688	right = RB_RIGHT(n, entry);
689	if (left == NULL && right == NULL)
690		printf("%d", n->i);
691	else {
692		printf("%d(", n->i);
693		print_tree(left);
694		printf(",");
695		print_tree(right);
696		printf(")");
697	}
698}
699
700int
701main(void)
702{
703	int i;
704	struct node *n;
705
706	for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) {
707		if ((n = malloc(sizeof(struct node))) == NULL)
708			err(1, NULL);
709		n->i = testdata[i];
710		RB_INSERT(inttree, &head, n);
711	}
712
713	RB_FOREACH(n, inttree, &head) {
714		printf("%d\en", n->i);
715	}
716	print_tree(RB_ROOT(&head));
717	printf("Sum of values = %d\n", RB_ROOT(&head)->sum);
718	printf("\en");
719	return (0);
720}
721.Ed
722.Sh NOTES
723Trying to free a tree in the following way is a common error:
724.Bd -literal -offset indent
725SPLAY_FOREACH(var, NAME, head) {
726	SPLAY_REMOVE(NAME, head, var);
727	free(var);
728}
729free(head);
730.Ed
731.Pp
732Since
733.Va var
734is freed, the
735.Fn FOREACH
736macro refers to a pointer that may have been reallocated already.
737Proper code needs a second variable.
738.Bd -literal -offset indent
739for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
740	nxt = SPLAY_NEXT(NAME, head, var);
741	SPLAY_REMOVE(NAME, head, var);
742	free(var);
743}
744.Ed
745.Pp
746Both
747.Fn RB_INSERT
748and
749.Fn SPLAY_INSERT
750return
751.Dv NULL
752if the element was inserted in the tree successfully, otherwise they
753return a pointer to the element with the colliding key.
754.Pp
755Accordingly,
756.Fn RB_REMOVE
757and
758.Fn SPLAY_REMOVE
759return the pointer to the removed element otherwise they return
760.Dv NULL
761to indicate an error.
762.Sh SEE ALSO
763.Xr arb 3 ,
764.Xr queue 3
765.Rs
766.%A "Bernhard Haeupler"
767.%A "Siddhartha Sen"
768.%A "Robert E. Tarjan"
769.%T "Rank-Balanced Trees"
770.%U "http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf"
771.%J "ACM Transactions on Algorithms"
772.%V "11"
773.%N "4"
774.%D "June 2015"
775.Re
776.Sh HISTORY
777The tree macros first appeared in
778.Fx 4.6 .
779.Sh AUTHORS
780The author of the tree macros is
781.An Niels Provos .
782