xref: /titanic_50/usr/src/man/man3lib/libavl.3lib (revision 5690df7e59608f4ee5c051c27524c9d55186cf58)
1fa9922c2SRobert Mustacchi.\"
2fa9922c2SRobert Mustacchi.\" This file and its contents are supplied under the terms of the
3fa9922c2SRobert Mustacchi.\" Common Development and Distribution License ("CDDL"), version 1.0.
4fa9922c2SRobert Mustacchi.\" You may only use this file in accordance with the terms of version
5fa9922c2SRobert Mustacchi.\" 1.0 of the CDDL.
6fa9922c2SRobert Mustacchi.\"
7fa9922c2SRobert Mustacchi.\" A full copy of the text of the CDDL should have accompanied this
8fa9922c2SRobert Mustacchi.\" source.  A copy of the CDDL is also available via the Internet at
9fa9922c2SRobert Mustacchi.\" http://www.illumos.org/license/CDDL.
10fa9922c2SRobert Mustacchi.\"
11fa9922c2SRobert Mustacchi.\"
12fa9922c2SRobert Mustacchi.\" Copyright 2015 Joyent, Inc.
13fa9922c2SRobert Mustacchi.\"
14*5690df7eSMohamed A. Khalfella.Dd Dec 04, 2015
15fa9922c2SRobert Mustacchi.Dt LIBAVL 3LIB
16fa9922c2SRobert Mustacchi.Os
17fa9922c2SRobert Mustacchi.Sh NAME
18fa9922c2SRobert Mustacchi.Nm libavl
19fa9922c2SRobert Mustacchi.Nd generic self-balancing binary search tree library
20fa9922c2SRobert Mustacchi.Sh SYNOPSIS
21fa9922c2SRobert Mustacchi.Lb libavl
22fa9922c2SRobert Mustacchi.In sys/avl.h
23fa9922c2SRobert Mustacchi.Sh DESCRIPTION
24fa9922c2SRobert MustacchiThe
25fa9922c2SRobert Mustacchi.Nm
26fa9922c2SRobert Mustacchilibrary provides a generic implementation of AVL trees, a form of
27fa9922c2SRobert Mustacchiself-balancing binary tree. The interfaces provided allow for an
28fa9922c2SRobert Mustacchiefficient way of implementing an ordered set of data structures and, due
29fa9922c2SRobert Mustacchito its embeddable nature, allow for a single instance of a data
30fa9922c2SRobert Mustacchistructure to belong to multiple AVL trees.
31fa9922c2SRobert Mustacchi.Lp
32fa9922c2SRobert MustacchiEach AVL tree contains entries of a single type of data structure.
33fa9922c2SRobert MustacchiRather than allocating memory for pointers for those data structures,
34fa9922c2SRobert Mustacchithe storage for the tree is embedded into the data structures by
35fa9922c2SRobert Mustacchideclaring a member of type
36fa9922c2SRobert Mustacchi.Vt avl_node_t .
37fa9922c2SRobert MustacchiWhen an AVL tree is created, through the use of
38fa9922c2SRobert Mustacchi.Fn avl_create ,
39fa9922c2SRobert Mustacchiit encodes the size of the data structure, the offset of the data
40fa9922c2SRobert Mustacchistructure, and a comparator function which is used to compare two
41fa9922c2SRobert Mustacchiinstances of a data structure. A data structure may be a member of
42fa9922c2SRobert Mustacchimultiple AVL trees by creating AVL trees which use different
43fa9922c2SRobert Mustacchioffsets (different members) into the data structure.
44fa9922c2SRobert Mustacchi.Lp
45fa9922c2SRobert MustacchiAVL trees support both look up of an arbitrary item and ordered
46fa9922c2SRobert Mustacchiiteration over the contents of the entire tree. In addition, from any
47fa9922c2SRobert Mustacchinode, you can find the previous and next entries in the tree, if they
48fa9922c2SRobert Mustacchiexist. In addition, AVL trees support arbitrary insertion and deletion.
49fa9922c2SRobert Mustacchi.Ss Performance
50fa9922c2SRobert MustacchiAVL trees are often used in place of linked lists. Compared to the
51fa9922c2SRobert Mustacchistandard, intrusive, doubly linked list, it has the following
52fa9922c2SRobert Mustacchiperformance characteristics:
53fa9922c2SRobert Mustacchi.Bl -hang -width Ds
54fa9922c2SRobert Mustacchi.It Sy Lookup One Node
55fa9922c2SRobert Mustacchi.Bd -filled -compact
56fa9922c2SRobert MustacchiLookup of a single node in a linked list is
57fa9922c2SRobert Mustacchi.Sy O(n) ,
58fa9922c2SRobert Mustacchiwhereas lookup of a single node in an AVL tree is
59fa9922c2SRobert Mustacchi.Sy O(log(n)) .
60fa9922c2SRobert Mustacchi.Ed
61fa9922c2SRobert Mustacchi.It Sy Insert One Node
62fa9922c2SRobert Mustacchi.Bd -filled -compact
63fa9922c2SRobert MustacchiInserting a single node into a linked list is
64fa9922c2SRobert Mustacchi.Sy O(1) .
65fa9922c2SRobert MustacchiInserting a single node into an AVL tree is
66fa9922c2SRobert Mustacchi.Sy O(log(n)) .
67fa9922c2SRobert Mustacchi.Pp
68fa9922c2SRobert MustacchiNote, insertions into an AVL tree always result in an ordered tree.
69fa9922c2SRobert MustacchiInsertions into a linked list do not guarantee order. If order is
70fa9922c2SRobert Mustacchirequired, then the time to do the insertion into a linked list will
71fa9922c2SRobert Mustacchidepend on the time of the search algorithm being employed to find the
72fa9922c2SRobert Mustacchiplace to insert at.
73fa9922c2SRobert Mustacchi.Ed
74fa9922c2SRobert Mustacchi.It Sy Delete One Node
75fa9922c2SRobert Mustacchi.Bd -filled -compact
76fa9922c2SRobert MustacchiDeleting a single node from a linked list is
77fa9922c2SRobert Mustacchi.Sy O(1),
78fa9922c2SRobert Mustacchiwhereas deleting a single node from an AVL tree takes
79fa9922c2SRobert Mustacchi.Sy O(log(n))
80fa9922c2SRobert Mustacchitime.
81fa9922c2SRobert Mustacchi.Ed
82fa9922c2SRobert Mustacchi.It Sy Delete All Nodes
83fa9922c2SRobert Mustacchi.Bd -filled -compact
84fa9922c2SRobert MustacchiDeleting all nodes from a linked list is
85fa9922c2SRobert Mustacchi.Sy O(n) .
86fa9922c2SRobert MustacchiWith an AVL tree, if using the
87*5690df7eSMohamed A. Khalfella.Xr avl_destroy_nodes 3AVL
88fa9922c2SRobert Mustacchifunction then deleting all nodes
89fa9922c2SRobert Mustacchiis
90fa9922c2SRobert Mustacchi.Sy O(n) .
91fa9922c2SRobert MustacchiHowever, if iterating over each entry in the tree and then removing it using
92fa9922c2SRobert Mustacchia while loop,
93fa9922c2SRobert Mustacchi.Xr avl_first 3AVL
94fa9922c2SRobert Mustacchiand
95fa9922c2SRobert Mustacchi.Xr avl_remove 3AVL
96fa9922c2SRobert Mustacchithen the time to remove all nodes is
97fa9922c2SRobert Mustacchi.Sy O(n\ *\ log(n)).
98fa9922c2SRobert Mustacchi.Ed
99fa9922c2SRobert Mustacchi.It Sy Visit the Next or Previous Node
100fa9922c2SRobert Mustacchi.Bd -filled -compact
101fa9922c2SRobert MustacchiVisiting the next or previous node in a linked list is
102fa9922c2SRobert Mustacchi.Sy O(1) ,
103fa9922c2SRobert Mustacchiwhereas going from the next to the previous node in an AVL tree will
104fa9922c2SRobert Mustacchitake between
105fa9922c2SRobert Mustacchi.Sy O(1)
106fa9922c2SRobert Mustacchiand
107fa9922c2SRobert Mustacchi.Sy O(log(n)) .
108fa9922c2SRobert Mustacchi.Ed
109fa9922c2SRobert Mustacchi.El
110fa9922c2SRobert Mustacchi.Pp
111fa9922c2SRobert MustacchiIn general, AVL trees are a good alternative for linked lists when order
112fa9922c2SRobert Mustacchior lookup speed is important and a reasonable number of items will be
113fa9922c2SRobert Mustacchipresent.
114fa9922c2SRobert Mustacchi.Sh INTERFACES
115fa9922c2SRobert MustacchiThe shared object
116fa9922c2SRobert Mustacchi.Sy libavl.so.1
117fa9922c2SRobert Mustacchiprovides the public interfaces defined below. See
118fa9922c2SRobert Mustacchi.Xr Intro(3)
119fa9922c2SRobert Mustacchifor additional information on shared object interfaces. Individual
120fa9922c2SRobert Mustacchifunctions are documented in their own manual pages.
121fa9922c2SRobert Mustacchi.Bl -column -offset indent ".Sy avl_is_empty" ".Sy avl_destroy_nodes"
122fa9922c2SRobert Mustacchi.It Sy avl_add Ta Sy avl_create
123fa9922c2SRobert Mustacchi.It Sy avl_destroy Ta Sy avl_destroy_nodes
124fa9922c2SRobert Mustacchi.It Sy avl_find Ta Sy avl_first
125fa9922c2SRobert Mustacchi.It Sy avl_insert Ta Sy avl_insert_here
126fa9922c2SRobert Mustacchi.It Sy avl_is_empty Ta Sy avl_last
127fa9922c2SRobert Mustacchi.It Sy avl_nearest Ta Sy avl_numnodes
128fa9922c2SRobert Mustacchi.It Sy avl_remove Ta Sy avl_swap
129fa9922c2SRobert Mustacchi.El
130fa9922c2SRobert Mustacchi.Pp
131fa9922c2SRobert MustacchiIn addition, the library defines C pre-processor macros which are
132fa9922c2SRobert Mustacchidefined below and documented in their own manual pages.
133fa9922c2SRobert Mustacchi.\"
134fa9922c2SRobert Mustacchi.\" Use the same column widths in both cases where we describe the list
135fa9922c2SRobert Mustacchi.\" of interfaces, to allow the manual page to better line up when rendered.
136fa9922c2SRobert Mustacchi.\"
137fa9922c2SRobert Mustacchi.Bl -column -offset indent ".Sy avl_is_empty" ".Sy avl_destroy_nodes"
138fa9922c2SRobert Mustacchi.It Sy AVL_NEXT Ta Sy AVL_PREV
139fa9922c2SRobert Mustacchi.El
140fa9922c2SRobert Mustacchi.Sh TYPES
141fa9922c2SRobert MustacchiThe
142fa9922c2SRobert Mustacchi.Nm
143fa9922c2SRobert Mustacchilibrary defines the following types:
144fa9922c2SRobert Mustacchi.Lp
145fa9922c2SRobert Mustacchi.Sy avl_tree_t
146fa9922c2SRobert Mustacchi.Lp
147fa9922c2SRobert MustacchiType used for the root of the AVL tree. Consumers define one of these
148fa9922c2SRobert Mustacchifor each of the different trees that they want to have.
149fa9922c2SRobert Mustacchi.Lp
150fa9922c2SRobert Mustacchi.Sy avl_node_t
151fa9922c2SRobert Mustacchi.Lp
152fa9922c2SRobert MustacchiType used as the data node for an AVL tree. One of these is embedded in
153fa9922c2SRobert Mustacchieach data structure that is the member of an AVL tree.
154fa9922c2SRobert Mustacchi.Lp
155fa9922c2SRobert Mustacchi.Sy avl_index_t
156fa9922c2SRobert Mustacchi.Lp
157fa9922c2SRobert MustacchiType used to locate a position in a tree. This is used with
158fa9922c2SRobert Mustacchi.Xr avl_find 3AVL
159fa9922c2SRobert Mustacchiand
160fa9922c2SRobert Mustacchi.Xr avl_insert 3AVL .
161fa9922c2SRobert Mustacchi.Sh LOCKING
162fa9922c2SRobert MustacchiThe
163fa9922c2SRobert Mustacchi.Nm
164fa9922c2SRobert Mustacchilibrary provides no locking. Callers that are using the same AVL tree
165fa9922c2SRobert Mustacchifrom multiple threads need to provide their own synchronization. If only
166fa9922c2SRobert Mustacchione thread is ever accessing or modifying the AVL tree, then there are
167fa9922c2SRobert Mustacchino synchronization concerns. If multiple AVL trees exist, then they may
168fa9922c2SRobert Mustacchiall be used simultaneously; however, they are subject to the same rules
169fa9922c2SRobert Mustacchiaround simultaneous access from a single thread.
170fa9922c2SRobert Mustacchi.Lp
171fa9922c2SRobert MustacchiAll routines are both
172fa9922c2SRobert Mustacchi.Sy Fork-safe
173fa9922c2SRobert Mustacchiand
174fa9922c2SRobert Mustacchi.Sy Async-Signal-Safe .
175fa9922c2SRobert MustacchiCallers may call functions in
176fa9922c2SRobert Mustacchi.Nm
177fa9922c2SRobert Mustacchifrom a signal handler and
178fa9922c2SRobert Mustacchi.Nm
179fa9922c2SRobert Mustacchicalls are all safe in face of
180fa9922c2SRobert Mustacchi.Xr fork 2 ;
181fa9922c2SRobert Mustacchihowever, if callers have their own locks, then they must make sure that
182fa9922c2SRobert Mustacchithey are accounted for by the use of routines such as
183fa9922c2SRobert Mustacchi.Xr pthread_atfork 3C .
184fa9922c2SRobert Mustacchi.Sh EXAMPLES
185fa9922c2SRobert MustacchiThe following code shows examples of exercising all of the functionality
186fa9922c2SRobert Mustacchithat is present in
187fa9922c2SRobert Mustacchi.Nm .
188fa9922c2SRobert MustacchiIt can be compiled by using a C compiler and linking
189fa9922c2SRobert Mustacchiagainst
190fa9922c2SRobert Mustacchi.Nm .
191fa9922c2SRobert MustacchiFor example, given a file named avl.c, with gcc, one would run:
192fa9922c2SRobert Mustacchi.Bd -literal
193fa9922c2SRobert Mustacchi$ gcc -Wall -o avl avl.c -lavl
194fa9922c2SRobert Mustacchi.Ed
195fa9922c2SRobert Mustacchi.Bd -literal
196fa9922c2SRobert Mustacchi/*
197fa9922c2SRobert Mustacchi * Example of using AVL Trees
198fa9922c2SRobert Mustacchi */
199fa9922c2SRobert Mustacchi
200fa9922c2SRobert Mustacchi#include <sys/avl.h>
201fa9922c2SRobert Mustacchi#include <stddef.h>
202fa9922c2SRobert Mustacchi#include <stdlib.h>
203fa9922c2SRobert Mustacchi#include <stdio.h>
204fa9922c2SRobert Mustacchi
205fa9922c2SRobert Mustacchistatic avl_tree_t inttree;
206fa9922c2SRobert Mustacchi
207fa9922c2SRobert Mustacchi/*
208fa9922c2SRobert Mustacchi * The structure that we're storing in an AVL tree.
209fa9922c2SRobert Mustacchi */
210fa9922c2SRobert Mustacchitypedef struct intnode {
211fa9922c2SRobert Mustacchi	int in_val;
212fa9922c2SRobert Mustacchi	avl_node_t in_avl;
213fa9922c2SRobert Mustacchi} intnode_t;
214fa9922c2SRobert Mustacchi
215fa9922c2SRobert Mustacchistatic int
216fa9922c2SRobert Mustacchiintnode_comparator(const void *l, const void *r)
217fa9922c2SRobert Mustacchi{
218fa9922c2SRobert Mustacchi	const intnode_t *li = l;
219fa9922c2SRobert Mustacchi	const intnode_t *ri = r;
220fa9922c2SRobert Mustacchi
221fa9922c2SRobert Mustacchi	if (li->in_val > ri->in_val)
222fa9922c2SRobert Mustacchi		return (1);
223fa9922c2SRobert Mustacchi	if (li->in_val < ri->in_val)
224fa9922c2SRobert Mustacchi		return (-1);
225fa9922c2SRobert Mustacchi	return (0);
226fa9922c2SRobert Mustacchi}
227fa9922c2SRobert Mustacchi
228fa9922c2SRobert Mustacchi/*
229fa9922c2SRobert Mustacchi * Create an AVL Tree
230fa9922c2SRobert Mustacchi */
231fa9922c2SRobert Mustacchistatic void
232fa9922c2SRobert Mustacchicreate_avl(void)
233fa9922c2SRobert Mustacchi{
234fa9922c2SRobert Mustacchi	avl_create(&inttree, intnode_comparator, sizeof (intnode_t),
235fa9922c2SRobert Mustacchi	    offsetof(intnode_t, in_avl));
236fa9922c2SRobert Mustacchi}
237fa9922c2SRobert Mustacchi
238fa9922c2SRobert Mustacchi/*
239fa9922c2SRobert Mustacchi * Add entries to the tree with the avl_add function.
240fa9922c2SRobert Mustacchi */
241fa9922c2SRobert Mustacchistatic void
242fa9922c2SRobert Mustacchifill_avl(void)
243fa9922c2SRobert Mustacchi{
244fa9922c2SRobert Mustacchi	int i;
245fa9922c2SRobert Mustacchi	intnode_t *inp;
246fa9922c2SRobert Mustacchi
247fa9922c2SRobert Mustacchi	for (i = 0; i < 20; i++) {
248fa9922c2SRobert Mustacchi		inp = malloc(sizeof (intnode_t));
249fa9922c2SRobert Mustacchi		assert(inp != NULL);
250fa9922c2SRobert Mustacchi		inp->in_val = i;
251fa9922c2SRobert Mustacchi		avl_add(&inttree, inp);
252fa9922c2SRobert Mustacchi	}
253fa9922c2SRobert Mustacchi}
254fa9922c2SRobert Mustacchi
255fa9922c2SRobert Mustacchi/*
256fa9922c2SRobert Mustacchi * Find entries in the AVL tree. Note, we create an intnode_t on the
257fa9922c2SRobert Mustacchi * stack that we use to look this up.
258fa9922c2SRobert Mustacchi */
259fa9922c2SRobert Mustacchistatic void
260fa9922c2SRobert Mustacchifind_avl(void)
261fa9922c2SRobert Mustacchi{
262fa9922c2SRobert Mustacchi	int i;
263fa9922c2SRobert Mustacchi	intnode_t lookup, *inp;
264fa9922c2SRobert Mustacchi
265fa9922c2SRobert Mustacchi	for (i = 10; i < 30; i++) {
266fa9922c2SRobert Mustacchi		lookup.in_val = i;
267fa9922c2SRobert Mustacchi		inp = avl_find(&inttree, &lookup, NULL);
268fa9922c2SRobert Mustacchi		if (inp == NULL) {
269fa9922c2SRobert Mustacchi			printf("Entry %d is not in the tree\\n", i);
270fa9922c2SRobert Mustacchi		} else {
271fa9922c2SRobert Mustacchi			printf("Entry %d is in the tree\\n",
272fa9922c2SRobert Mustacchi			    inp->in_val);
273fa9922c2SRobert Mustacchi		}
274fa9922c2SRobert Mustacchi	}
275fa9922c2SRobert Mustacchi}
276fa9922c2SRobert Mustacchi
277fa9922c2SRobert Mustacchi/*
278fa9922c2SRobert Mustacchi * Walk the tree forwards
279fa9922c2SRobert Mustacchi */
280fa9922c2SRobert Mustacchistatic void
281fa9922c2SRobert Mustacchiwalk_forwards(void)
282fa9922c2SRobert Mustacchi{
283fa9922c2SRobert Mustacchi	intnode_t *inp;
284fa9922c2SRobert Mustacchi	for (inp = avl_first(&inttree); inp != NULL;
285fa9922c2SRobert Mustacchi	    inp = AVL_NEXT(&inttree, inp)) {
286fa9922c2SRobert Mustacchi		printf("Found entry %d\\n", inp->in_val);
287fa9922c2SRobert Mustacchi	}
288fa9922c2SRobert Mustacchi}
289fa9922c2SRobert Mustacchi
290fa9922c2SRobert Mustacchi/*
291fa9922c2SRobert Mustacchi * Walk the tree backwards.
292fa9922c2SRobert Mustacchi */
293fa9922c2SRobert Mustacchistatic void
294fa9922c2SRobert Mustacchiwalk_backwards(void)
295fa9922c2SRobert Mustacchi{
296fa9922c2SRobert Mustacchi	intnode_t *inp;
297fa9922c2SRobert Mustacchi	for (inp = avl_last(&inttree); inp != NULL;
298fa9922c2SRobert Mustacchi	    inp = AVL_PREV(&inttree, inp)) {
299fa9922c2SRobert Mustacchi		printf("Found entry %d\\n", inp->in_val);
300fa9922c2SRobert Mustacchi	}
301fa9922c2SRobert Mustacchi}
302fa9922c2SRobert Mustacchi
303fa9922c2SRobert Mustacchi/*
304fa9922c2SRobert Mustacchi * Determine the number of nodes in the tree and if it is empty or
305fa9922c2SRobert Mustacchi * not.
306fa9922c2SRobert Mustacchi */
307fa9922c2SRobert Mustacchistatic void
308fa9922c2SRobert Mustacchiinttree_inspect(void)
309fa9922c2SRobert Mustacchi{
310fa9922c2SRobert Mustacchi	printf("The tree is %s, there are %ld nodes in it\\n",
311fa9922c2SRobert Mustacchi	    avl_is_empty(&inttree) == B_TRUE ? "empty" : "not empty",
312fa9922c2SRobert Mustacchi	    avl_numnodes(&inttree));
313fa9922c2SRobert Mustacchi}
314fa9922c2SRobert Mustacchi
315fa9922c2SRobert Mustacchi/*
316fa9922c2SRobert Mustacchi * Use avl_remove to remove entries from the tree.
317fa9922c2SRobert Mustacchi */
318fa9922c2SRobert Mustacchistatic void
319fa9922c2SRobert Mustacchiremove_nodes(void)
320fa9922c2SRobert Mustacchi{
321fa9922c2SRobert Mustacchi	int i;
322fa9922c2SRobert Mustacchi	intnode_t lookup, *inp;
323fa9922c2SRobert Mustacchi
324fa9922c2SRobert Mustacchi	for (i = 0; i < 20; i+= 4) {
325fa9922c2SRobert Mustacchi		lookup.in_val = i;
326fa9922c2SRobert Mustacchi		inp = avl_find(&inttree, &lookup, NULL);
327fa9922c2SRobert Mustacchi		if (inp != NULL)
328fa9922c2SRobert Mustacchi			avl_remove(&inttree, inp);
329fa9922c2SRobert Mustacchi	}
330fa9922c2SRobert Mustacchi}
331fa9922c2SRobert Mustacchi
332fa9922c2SRobert Mustacchi/*
333fa9922c2SRobert Mustacchi * Find the nearest nodes in the tree.
334fa9922c2SRobert Mustacchi */
335fa9922c2SRobert Mustacchistatic void
336fa9922c2SRobert Mustacchinearest_nodes(void)
337fa9922c2SRobert Mustacchi{
338fa9922c2SRobert Mustacchi	intnode_t lookup, *inp;
339fa9922c2SRobert Mustacchi	avl_index_t where;
340fa9922c2SRobert Mustacchi
341fa9922c2SRobert Mustacchi	lookup.in_val = 12;
342fa9922c2SRobert Mustacchi	if (avl_find(&inttree, &lookup, &where) != NULL)
343fa9922c2SRobert Mustacchi		abort();
344fa9922c2SRobert Mustacchi	inp = avl_nearest(&inttree, where, AVL_BEFORE);
345fa9922c2SRobert Mustacchi	assert(inp != NULL);
346fa9922c2SRobert Mustacchi	printf("closest node before 12 is: %d\\n", inp->in_val);
347fa9922c2SRobert Mustacchi	inp = avl_nearest(&inttree, where, AVL_AFTER);
348fa9922c2SRobert Mustacchi	assert(inp != NULL);
349fa9922c2SRobert Mustacchi	printf("closest node after 12 is: %d\\n", inp->in_val);
350fa9922c2SRobert Mustacchi}
351fa9922c2SRobert Mustacchi
352fa9922c2SRobert Mustacchistatic void
353fa9922c2SRobert Mustacchiinsert_avl(void)
354fa9922c2SRobert Mustacchi{
355fa9922c2SRobert Mustacchi	intnode_t lookup, *inp;
356fa9922c2SRobert Mustacchi	avl_index_t where;
357fa9922c2SRobert Mustacchi
358fa9922c2SRobert Mustacchi	lookup.in_val = 12;
359fa9922c2SRobert Mustacchi	if (avl_find(&inttree, &lookup, &where) != NULL)
360fa9922c2SRobert Mustacchi		abort();
361fa9922c2SRobert Mustacchi	inp = malloc(sizeof (intnode_t));
362fa9922c2SRobert Mustacchi	assert(inp != NULL);
363fa9922c2SRobert Mustacchi	avl_insert(&inttree, inp, where);
364fa9922c2SRobert Mustacchi}
365fa9922c2SRobert Mustacchi
366fa9922c2SRobert Mustacchistatic void
367fa9922c2SRobert Mustacchiswap_avl(void)
368fa9922c2SRobert Mustacchi{
369fa9922c2SRobert Mustacchi	avl_tree_t swap;
370fa9922c2SRobert Mustacchi
371fa9922c2SRobert Mustacchi	avl_create(&swap, intnode_comparator, sizeof (intnode_t),
372fa9922c2SRobert Mustacchi	    offsetof(intnode_t, in_avl));
373fa9922c2SRobert Mustacchi	avl_swap(&inttree, &swap);
374fa9922c2SRobert Mustacchi	inttree_inspect();
375fa9922c2SRobert Mustacchi	avl_swap(&inttree, &swap);
376fa9922c2SRobert Mustacchi	inttree_inspect();
377fa9922c2SRobert Mustacchi}
378fa9922c2SRobert Mustacchi
379fa9922c2SRobert Mustacchi/*
380fa9922c2SRobert Mustacchi * Remove all remaining nodes in the tree. We first use
381fa9922c2SRobert Mustacchi * avl_destroy_nodes to empty the tree, then avl_destroy to finish.
382fa9922c2SRobert Mustacchi */
383fa9922c2SRobert Mustacchistatic void
384fa9922c2SRobert Mustacchicleanup(void)
385fa9922c2SRobert Mustacchi{
386fa9922c2SRobert Mustacchi	intnode_t *inp;
387fa9922c2SRobert Mustacchi	void *c = NULL;
388fa9922c2SRobert Mustacchi
389fa9922c2SRobert Mustacchi	while ((inp = avl_destroy_nodes(&inttree, &c)) != NULL) {
390fa9922c2SRobert Mustacchi		free(inp);
391fa9922c2SRobert Mustacchi	}
392fa9922c2SRobert Mustacchi	avl_destroy(&inttree);
393fa9922c2SRobert Mustacchi}
394fa9922c2SRobert Mustacchi
395fa9922c2SRobert Mustacchiint
396fa9922c2SRobert Mustacchimain(void)
397fa9922c2SRobert Mustacchi{
398fa9922c2SRobert Mustacchi	create_avl();
399fa9922c2SRobert Mustacchi	inttree_inspect();
400fa9922c2SRobert Mustacchi	fill_avl();
401fa9922c2SRobert Mustacchi	find_avl();
402fa9922c2SRobert Mustacchi	walk_forwards();
403fa9922c2SRobert Mustacchi	walk_backwards();
404fa9922c2SRobert Mustacchi	inttree_inspect();
405fa9922c2SRobert Mustacchi	remove_nodes();
406fa9922c2SRobert Mustacchi	inttree_inspect();
407fa9922c2SRobert Mustacchi	nearest_nodes();
408fa9922c2SRobert Mustacchi	insert_avl();
409fa9922c2SRobert Mustacchi	inttree_inspect();
410fa9922c2SRobert Mustacchi	swap_avl();
411fa9922c2SRobert Mustacchi	cleanup();
412fa9922c2SRobert Mustacchi	return (0);
413fa9922c2SRobert Mustacchi}
414fa9922c2SRobert Mustacchi.Ed
415fa9922c2SRobert Mustacchi.Sh INTERFACE STABILITY
416fa9922c2SRobert Mustacchi.Sy Committed
417fa9922c2SRobert Mustacchi.Sh MT-Level
418fa9922c2SRobert MustacchiSee
419fa9922c2SRobert Mustacchi.Sx Locking.
420fa9922c2SRobert Mustacchi.Sh SEE ALSO
421fa9922c2SRobert Mustacchi.Xr Intro 3 ,
422fa9922c2SRobert Mustacchi.Xr pthread_atfork 3C
423fa9922c2SRobert Mustacchi.Lp
424fa9922c2SRobert Mustacchi.Xr avl_add 3AVL ,
425fa9922c2SRobert Mustacchi.Xr avl_create 3AVL ,
426fa9922c2SRobert Mustacchi.Xr avl_destroy 3AVL ,
427fa9922c2SRobert Mustacchi.Xr avl_destroy_nodes 3AVL ,
428fa9922c2SRobert Mustacchi.Xr avl_find 3AVL ,
429fa9922c2SRobert Mustacchi.Xr avl_first 3AVL ,
430fa9922c2SRobert Mustacchi.Xr avl_insert 3AVL ,
431fa9922c2SRobert Mustacchi.Xr avl_insert_here 3AVL ,
432fa9922c2SRobert Mustacchi.Xr avl_is_empty 3AVL ,
433fa9922c2SRobert Mustacchi.Xr avl_last 3AVL ,
434fa9922c2SRobert Mustacchi.Xr avl_nearest 3AVL ,
435fa9922c2SRobert Mustacchi.Xr avl_numnodes 3AVL ,
436fa9922c2SRobert Mustacchi.Xr avl_remove 3AVL ,
437fa9922c2SRobert Mustacchi.Xr avl_swap 3AVL ,
438fa9922c2SRobert Mustacchi.Rs
439fa9922c2SRobert Mustacchi.%A Adel'son-Vel'skiy, G. M.
440fa9922c2SRobert Mustacchi.%A Landis, Ye. M.
441fa9922c2SRobert Mustacchi.%T "An Algorithm for the Organization of Information"
442fa9922c2SRobert Mustacchi.%Q Deklady Akademii Nauk
443fa9922c2SRobert Mustacchi.%C USSR, Moscow
444fa9922c2SRobert Mustacchi.%P 263-266
445fa9922c2SRobert Mustacchi.%V Vol. 16
446fa9922c2SRobert Mustacchi.%N No. 2
447fa9922c2SRobert Mustacchi.%D 1962
448fa9922c2SRobert Mustacchi.Re
449