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
24 The
25 .Nm
26 library provides a generic implementation of AVL trees, a form of
27 self-balancing binary tree. The interfaces provided allow for an
28 efficient way of implementing an ordered set of data structures and, due
29 to its embeddable nature, allow for a single instance of a data
30 structure to belong to multiple AVL trees.
31 .Lp
32 Each AVL tree contains entries of a single type of data structure.
33 Rather than allocating memory for pointers for those data structures,
34 the storage for the tree is embedded into the data structures by
35 declaring a member of type
36 .Vt avl_node_t .
37 When an AVL tree is created, through the use of
38 .Fn avl_create ,
39 it encodes the size of the data structure, the offset of the data
40 structure, and a comparator function which is used to compare two
41 instances of a data structure. A data structure may be a member of
42 multiple AVL trees by creating AVL trees which use different
43 offsets (different members) into the data structure.
44 .Lp
45 AVL trees support both look up of an arbitrary item and ordered
46 iteration over the contents of the entire tree. In addition, from any
47 node, you can find the previous and next entries in the tree, if they
48 exist. In addition, AVL trees support arbitrary insertion and deletion.
49 .Ss Performance
50 AVL trees are often used in place of linked lists. Compared to the
51 standard, intrusive, doubly linked list, it has the following
52 performance characteristics:
53 .Bl -hang -width Ds
54 .It Sy Lookup One Node
55 .Bd -filled -compact
56 Lookup of a single node in a linked list is
57 .Sy O(n) ,
58 whereas 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
63 Inserting a single node into a linked list is
64 .Sy O(1) .
65 Inserting a single node into an AVL tree is
66 .Sy O(log(n)) .
67 .Pp
68 Note, insertions into an AVL tree always result in an ordered tree.
69 Insertions into a linked list do not guarantee order. If order is
70 required, then the time to do the insertion into a linked list will
71 depend on the time of the search algorithm being employed to find the
72 place to insert at.
73 .Ed
74 .It Sy Delete One Node
75 .Bd -filled -compact
76 Deleting a single node from a linked list is
77 .Sy O(1),
78 whereas deleting a single node from an AVL tree takes
79 .Sy O(log(n))
80 time.
81 .Ed
82 .It Sy Delete All Nodes
83 .Bd -filled -compact
84 Deleting all nodes from a linked list is
85 .Sy O(n) .
86 With an AVL tree, if using the
87 .Xr avl_destroy_nodes 3AVL
88 function then deleting all nodes
89 is
90 .Sy O(n) .
91 However, if iterating over each entry in the tree and then removing it using
92 a while loop,
93 .Xr avl_first 3AVL
94 and
95 .Xr avl_remove 3AVL
96 then 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
101 Visiting the next or previous node in a linked list is
102 .Sy O(1) ,
103 whereas going from the next to the previous node in an AVL tree will
104 take between
105 .Sy O(1)
106 and
107 .Sy O(log(n)) .
108 .Ed
109 .El
110 .Pp
111 In general, AVL trees are a good alternative for linked lists when order
112 or lookup speed is important and a reasonable number of items will be
113 present.
114 .Sh INTERFACES
115 The shared object
116 .Sy libavl.so.1
117 provides the public interfaces defined below. See
118 .Xr Intro(3)
119 for additional information on shared object interfaces. Individual
120 functions 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
131 In addition, the library defines C pre-processor macros which are
132 defined 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
141 The
142 .Nm
143 library defines the following types:
144 .Lp
145 .Sy avl_tree_t
146 .Lp
147 Type used for the root of the AVL tree. Consumers define one of these
148 for each of the different trees that they want to have.
149 .Lp
150 .Sy avl_node_t
151 .Lp
152 Type used as the data node for an AVL tree. One of these is embedded in
153 each data structure that is the member of an AVL tree.
154 .Lp
155 .Sy avl_index_t
156 .Lp
157 Type used to locate a position in a tree. This is used with
158 .Xr avl_find 3AVL
159 and
160 .Xr avl_insert 3AVL .
161 .Sh LOCKING
162 The
163 .Nm
164 library provides no locking. Callers that are using the same AVL tree
165 from multiple threads need to provide their own synchronization. If only
166 one thread is ever accessing or modifying the AVL tree, then there are
167 no synchronization concerns. If multiple AVL trees exist, then they may
168 all be used simultaneously; however, they are subject to the same rules
169 around simultaneous access from a single thread.
170 .Lp
171 All routines are both
172 .Sy Fork-safe
173 and
174 .Sy Async-Signal-Safe .
175 Callers may call functions in
176 .Nm
177 from a signal handler and
178 .Nm
179 calls are all safe in face of
180 .Xr fork 2 ;
181 however, if callers have their own locks, then they must make sure that
182 they are accounted for by the use of routines such as
183 .Xr pthread_atfork 3C .
184 .Sh EXAMPLES
185 The following code shows examples of exercising all of the functionality
186 that is present in
187 .Nm .
188 It can be compiled by using a C compiler and linking
189 against
190 .Nm .
191 For 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
205 static avl_tree_t inttree;
206
207 /*
208 * The structure that we're storing in an AVL tree.
209 */
210 typedef struct intnode {
211 int in_val;
212 avl_node_t in_avl;
213 } intnode_t;
214
215 static int
216 intnode_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 */
231 static void
232 create_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 */
241 static void
242 fill_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 */
259 static void
260 find_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 */
280 static void
281 walk_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 */
293 static void
294 walk_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 */
307 static void
308 inttree_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 */
318 static void
319 remove_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 */
335 static void
336 nearest_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
352 static void
353 insert_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
366 static void
367 swap_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 */
383 static void
384 cleanup(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
395 int
396 main(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
418 See
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