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