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