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