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. 28The interfaces provided allow for an efficient way of implementing an ordered 29set of data structures and, due to its embeddable nature, allow for a single 30instance of a data structure 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. 42A data structure may be a member of multiple AVL trees by creating AVL trees 43which use different offsets (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. 47In addition, from any node, you can find the previous and next entries in the 48tree, if they exist. 49In addition, AVL trees support arbitrary insertion and deletion. 50.Ss Performance 51AVL trees are often used in place of linked lists. 52Compared to the standard, intrusive, doubly linked list, it has the following 53performance characteristics: 54.Bl -hang -width Ds 55.It Sy Lookup One Node 56.Bd -filled -compact 57Lookup of a single node in a linked list is 58.Sy O(n) , 59whereas 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 64Inserting a single node into a linked list is 65.Sy O(1) . 66Inserting a single node into an AVL tree is 67.Sy O(log(n)) . 68.Pp 69Note, insertions into an AVL tree always result in an ordered tree. 70Insertions into a linked list do not guarantee order. 71If order is required, then the time to do the insertion into a linked list will 72depend on the time of the search algorithm being employed to find the place to 73insert at. 74.Ed 75.It Sy Delete One Node 76.Bd -filled -compact 77Deleting a single node from a linked list is 78.Sy O(1), 79whereas deleting a single node from an AVL tree takes 80.Sy O(log(n)) 81time. 82.Ed 83.It Sy Delete All Nodes 84.Bd -filled -compact 85Deleting all nodes from a linked list is 86.Sy O(n) . 87With an AVL tree, if using the 88.Xr avl_destroy_nodes 3AVL 89function then deleting all nodes 90is 91.Sy O(n) . 92However, if iterating over each entry in the tree and then removing it using 93a while loop, 94.Xr avl_first 3AVL 95and 96.Xr avl_remove 3AVL 97then 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 102Visiting the next or previous node in a linked list is 103.Sy O(1) , 104whereas going from the next to the previous node in an AVL tree will 105take between 106.Sy O(1) 107and 108.Sy O(log(n)) . 109.Ed 110.El 111.Pp 112In general, AVL trees are a good alternative for linked lists when order 113or lookup speed is important and a reasonable number of items will be 114present. 115.Sh INTERFACES 116The shared object 117.Sy libavl.so.1 118provides the public interfaces defined below. 119See 120.Xr Intro 3 121for additional information on shared object interfaces. 122Individual 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 133In addition, the library defines C pre-processor macros which are 134defined 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 143The 144.Nm 145library defines the following types: 146.Lp 147.Sy avl_tree_t 148.Lp 149Type used for the root of the AVL tree. 150Consumers define one of these for each of the different trees that they want to 151have. 152.Lp 153.Sy avl_node_t 154.Lp 155Type used as the data node for an AVL tree. 156One of these is embedded in each data structure that is the member of an AVL 157tree. 158.Lp 159.Sy avl_index_t 160.Lp 161Type used to locate a position in a tree. 162This is used with 163.Xr avl_find 3AVL 164and 165.Xr avl_insert 3AVL . 166.Sh LOCKING 167The 168.Nm 169library provides no locking. 170Callers that are using the same AVL tree from multiple threads need to provide 171their own synchronization. 172If only one thread is ever accessing or modifying the AVL tree, then there are 173no synchronization concerns. 174If multiple AVL trees exist, then they may all be used simultaneously; however, 175they are subject to the same rules around simultaneous access from a single 176thread. 177.Lp 178All routines are both 179.Sy Fork-safe 180and 181.Sy Async-Signal-Safe . 182Callers may call functions in 183.Nm 184from a signal handler and 185.Nm 186calls are all safe in face of 187.Xr fork 2 ; 188however, if callers have their own locks, then they must make sure that 189they are accounted for by the use of routines such as 190.Xr pthread_atfork 3C . 191.Sh EXAMPLES 192The following code shows examples of exercising all of the functionality 193that is present in 194.Nm . 195It can be compiled by using a C compiler and linking 196against 197.Nm . 198For 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 */ 206 207#include <sys/avl.h> 208#include <stddef.h> 209#include <stdlib.h> 210#include <stdio.h> 211 212static avl_tree_t inttree; 213 214/* 215 * The structure that we're storing in an AVL tree. 216 */ 217typedef struct intnode { 218 int in_val; 219 avl_node_t in_avl; 220} intnode_t; 221 222static int 223intnode_comparator(const void *l, const void *r) 224{ 225 const intnode_t *li = l; 226 const intnode_t *ri = r; 227 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} 234 235/* 236 * Create an AVL Tree 237 */ 238static void 239create_avl(void) 240{ 241 avl_create(&inttree, intnode_comparator, sizeof (intnode_t), 242 offsetof(intnode_t, in_avl)); 243} 244 245/* 246 * Add entries to the tree with the avl_add function. 247 */ 248static void 249fill_avl(void) 250{ 251 int i; 252 intnode_t *inp; 253 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} 261 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 */ 266static void 267find_avl(void) 268{ 269 int i; 270 intnode_t lookup, *inp; 271 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} 283 284/* 285 * Walk the tree forwards 286 */ 287static void 288walk_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} 296 297/* 298 * Walk the tree backwards. 299 */ 300static void 301walk_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} 309 310/* 311 * Determine the number of nodes in the tree and if it is empty or 312 * not. 313 */ 314static void 315inttree_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} 321 322/* 323 * Use avl_remove to remove entries from the tree. 324 */ 325static void 326remove_nodes(void) 327{ 328 int i; 329 intnode_t lookup, *inp; 330 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} 338 339/* 340 * Find the nearest nodes in the tree. 341 */ 342static void 343nearest_nodes(void) 344{ 345 intnode_t lookup, *inp; 346 avl_index_t where; 347 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} 358 359static void 360insert_avl(void) 361{ 362 intnode_t lookup, *inp; 363 avl_index_t where; 364 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} 372 373static void 374swap_avl(void) 375{ 376 avl_tree_t swap; 377 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} 385 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 */ 390static void 391cleanup(void) 392{ 393 intnode_t *inp; 394 void *c = NULL; 395 396 while ((inp = avl_destroy_nodes(&inttree, &c)) != NULL) { 397 free(inp); 398 } 399 avl_destroy(&inttree); 400} 401 402int 403main(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 425See 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 456