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