1fa9922c2SRobert Mustacchi.\" 2fa9922c2SRobert Mustacchi.\" This file and its contents are supplied under the terms of the 3fa9922c2SRobert Mustacchi.\" Common Development and Distribution License ("CDDL"), version 1.0. 4fa9922c2SRobert Mustacchi.\" You may only use this file in accordance with the terms of version 5fa9922c2SRobert Mustacchi.\" 1.0 of the CDDL. 6fa9922c2SRobert Mustacchi.\" 7fa9922c2SRobert Mustacchi.\" A full copy of the text of the CDDL should have accompanied this 8fa9922c2SRobert Mustacchi.\" source. A copy of the CDDL is also available via the Internet at 9fa9922c2SRobert Mustacchi.\" http://www.illumos.org/license/CDDL. 10fa9922c2SRobert Mustacchi.\" 11fa9922c2SRobert Mustacchi.\" 12fa9922c2SRobert Mustacchi.\" Copyright 2015 Joyent, Inc. 13fa9922c2SRobert Mustacchi.\" 14*5690df7eSMohamed A. Khalfella.Dd Dec 04, 2015 15fa9922c2SRobert Mustacchi.Dt LIBAVL 3LIB 16fa9922c2SRobert Mustacchi.Os 17fa9922c2SRobert Mustacchi.Sh NAME 18fa9922c2SRobert Mustacchi.Nm libavl 19fa9922c2SRobert Mustacchi.Nd generic self-balancing binary search tree library 20fa9922c2SRobert Mustacchi.Sh SYNOPSIS 21fa9922c2SRobert Mustacchi.Lb libavl 22fa9922c2SRobert Mustacchi.In sys/avl.h 23fa9922c2SRobert Mustacchi.Sh DESCRIPTION 24fa9922c2SRobert MustacchiThe 25fa9922c2SRobert Mustacchi.Nm 26fa9922c2SRobert Mustacchilibrary provides a generic implementation of AVL trees, a form of 27fa9922c2SRobert Mustacchiself-balancing binary tree. The interfaces provided allow for an 28fa9922c2SRobert Mustacchiefficient way of implementing an ordered set of data structures and, due 29fa9922c2SRobert Mustacchito its embeddable nature, allow for a single instance of a data 30fa9922c2SRobert Mustacchistructure to belong to multiple AVL trees. 31fa9922c2SRobert Mustacchi.Lp 32fa9922c2SRobert MustacchiEach AVL tree contains entries of a single type of data structure. 33fa9922c2SRobert MustacchiRather than allocating memory for pointers for those data structures, 34fa9922c2SRobert Mustacchithe storage for the tree is embedded into the data structures by 35fa9922c2SRobert Mustacchideclaring a member of type 36fa9922c2SRobert Mustacchi.Vt avl_node_t . 37fa9922c2SRobert MustacchiWhen an AVL tree is created, through the use of 38fa9922c2SRobert Mustacchi.Fn avl_create , 39fa9922c2SRobert Mustacchiit encodes the size of the data structure, the offset of the data 40fa9922c2SRobert Mustacchistructure, and a comparator function which is used to compare two 41fa9922c2SRobert Mustacchiinstances of a data structure. A data structure may be a member of 42fa9922c2SRobert Mustacchimultiple AVL trees by creating AVL trees which use different 43fa9922c2SRobert Mustacchioffsets (different members) into the data structure. 44fa9922c2SRobert Mustacchi.Lp 45fa9922c2SRobert MustacchiAVL trees support both look up of an arbitrary item and ordered 46fa9922c2SRobert Mustacchiiteration over the contents of the entire tree. In addition, from any 47fa9922c2SRobert Mustacchinode, you can find the previous and next entries in the tree, if they 48fa9922c2SRobert Mustacchiexist. In addition, AVL trees support arbitrary insertion and deletion. 49fa9922c2SRobert Mustacchi.Ss Performance 50fa9922c2SRobert MustacchiAVL trees are often used in place of linked lists. Compared to the 51fa9922c2SRobert Mustacchistandard, intrusive, doubly linked list, it has the following 52fa9922c2SRobert Mustacchiperformance characteristics: 53fa9922c2SRobert Mustacchi.Bl -hang -width Ds 54fa9922c2SRobert Mustacchi.It Sy Lookup One Node 55fa9922c2SRobert Mustacchi.Bd -filled -compact 56fa9922c2SRobert MustacchiLookup of a single node in a linked list is 57fa9922c2SRobert Mustacchi.Sy O(n) , 58fa9922c2SRobert Mustacchiwhereas lookup of a single node in an AVL tree is 59fa9922c2SRobert Mustacchi.Sy O(log(n)) . 60fa9922c2SRobert Mustacchi.Ed 61fa9922c2SRobert Mustacchi.It Sy Insert One Node 62fa9922c2SRobert Mustacchi.Bd -filled -compact 63fa9922c2SRobert MustacchiInserting a single node into a linked list is 64fa9922c2SRobert Mustacchi.Sy O(1) . 65fa9922c2SRobert MustacchiInserting a single node into an AVL tree is 66fa9922c2SRobert Mustacchi.Sy O(log(n)) . 67fa9922c2SRobert Mustacchi.Pp 68fa9922c2SRobert MustacchiNote, insertions into an AVL tree always result in an ordered tree. 69fa9922c2SRobert MustacchiInsertions into a linked list do not guarantee order. If order is 70fa9922c2SRobert Mustacchirequired, then the time to do the insertion into a linked list will 71fa9922c2SRobert Mustacchidepend on the time of the search algorithm being employed to find the 72fa9922c2SRobert Mustacchiplace to insert at. 73fa9922c2SRobert Mustacchi.Ed 74fa9922c2SRobert Mustacchi.It Sy Delete One Node 75fa9922c2SRobert Mustacchi.Bd -filled -compact 76fa9922c2SRobert MustacchiDeleting a single node from a linked list is 77fa9922c2SRobert Mustacchi.Sy O(1), 78fa9922c2SRobert Mustacchiwhereas deleting a single node from an AVL tree takes 79fa9922c2SRobert Mustacchi.Sy O(log(n)) 80fa9922c2SRobert Mustacchitime. 81fa9922c2SRobert Mustacchi.Ed 82fa9922c2SRobert Mustacchi.It Sy Delete All Nodes 83fa9922c2SRobert Mustacchi.Bd -filled -compact 84fa9922c2SRobert MustacchiDeleting all nodes from a linked list is 85fa9922c2SRobert Mustacchi.Sy O(n) . 86fa9922c2SRobert MustacchiWith an AVL tree, if using the 87*5690df7eSMohamed A. Khalfella.Xr avl_destroy_nodes 3AVL 88fa9922c2SRobert Mustacchifunction then deleting all nodes 89fa9922c2SRobert Mustacchiis 90fa9922c2SRobert Mustacchi.Sy O(n) . 91fa9922c2SRobert MustacchiHowever, if iterating over each entry in the tree and then removing it using 92fa9922c2SRobert Mustacchia while loop, 93fa9922c2SRobert Mustacchi.Xr avl_first 3AVL 94fa9922c2SRobert Mustacchiand 95fa9922c2SRobert Mustacchi.Xr avl_remove 3AVL 96fa9922c2SRobert Mustacchithen the time to remove all nodes is 97fa9922c2SRobert Mustacchi.Sy O(n\ *\ log(n)). 98fa9922c2SRobert Mustacchi.Ed 99fa9922c2SRobert Mustacchi.It Sy Visit the Next or Previous Node 100fa9922c2SRobert Mustacchi.Bd -filled -compact 101fa9922c2SRobert MustacchiVisiting the next or previous node in a linked list is 102fa9922c2SRobert Mustacchi.Sy O(1) , 103fa9922c2SRobert Mustacchiwhereas going from the next to the previous node in an AVL tree will 104fa9922c2SRobert Mustacchitake between 105fa9922c2SRobert Mustacchi.Sy O(1) 106fa9922c2SRobert Mustacchiand 107fa9922c2SRobert Mustacchi.Sy O(log(n)) . 108fa9922c2SRobert Mustacchi.Ed 109fa9922c2SRobert Mustacchi.El 110fa9922c2SRobert Mustacchi.Pp 111fa9922c2SRobert MustacchiIn general, AVL trees are a good alternative for linked lists when order 112fa9922c2SRobert Mustacchior lookup speed is important and a reasonable number of items will be 113fa9922c2SRobert Mustacchipresent. 114fa9922c2SRobert Mustacchi.Sh INTERFACES 115fa9922c2SRobert MustacchiThe shared object 116fa9922c2SRobert Mustacchi.Sy libavl.so.1 117fa9922c2SRobert Mustacchiprovides the public interfaces defined below. See 118fa9922c2SRobert Mustacchi.Xr Intro(3) 119fa9922c2SRobert Mustacchifor additional information on shared object interfaces. Individual 120fa9922c2SRobert Mustacchifunctions are documented in their own manual pages. 121fa9922c2SRobert Mustacchi.Bl -column -offset indent ".Sy avl_is_empty" ".Sy avl_destroy_nodes" 122fa9922c2SRobert Mustacchi.It Sy avl_add Ta Sy avl_create 123fa9922c2SRobert Mustacchi.It Sy avl_destroy Ta Sy avl_destroy_nodes 124fa9922c2SRobert Mustacchi.It Sy avl_find Ta Sy avl_first 125fa9922c2SRobert Mustacchi.It Sy avl_insert Ta Sy avl_insert_here 126fa9922c2SRobert Mustacchi.It Sy avl_is_empty Ta Sy avl_last 127fa9922c2SRobert Mustacchi.It Sy avl_nearest Ta Sy avl_numnodes 128fa9922c2SRobert Mustacchi.It Sy avl_remove Ta Sy avl_swap 129fa9922c2SRobert Mustacchi.El 130fa9922c2SRobert Mustacchi.Pp 131fa9922c2SRobert MustacchiIn addition, the library defines C pre-processor macros which are 132fa9922c2SRobert Mustacchidefined below and documented in their own manual pages. 133fa9922c2SRobert Mustacchi.\" 134fa9922c2SRobert Mustacchi.\" Use the same column widths in both cases where we describe the list 135fa9922c2SRobert Mustacchi.\" of interfaces, to allow the manual page to better line up when rendered. 136fa9922c2SRobert Mustacchi.\" 137fa9922c2SRobert Mustacchi.Bl -column -offset indent ".Sy avl_is_empty" ".Sy avl_destroy_nodes" 138fa9922c2SRobert Mustacchi.It Sy AVL_NEXT Ta Sy AVL_PREV 139fa9922c2SRobert Mustacchi.El 140fa9922c2SRobert Mustacchi.Sh TYPES 141fa9922c2SRobert MustacchiThe 142fa9922c2SRobert Mustacchi.Nm 143fa9922c2SRobert Mustacchilibrary defines the following types: 144fa9922c2SRobert Mustacchi.Lp 145fa9922c2SRobert Mustacchi.Sy avl_tree_t 146fa9922c2SRobert Mustacchi.Lp 147fa9922c2SRobert MustacchiType used for the root of the AVL tree. Consumers define one of these 148fa9922c2SRobert Mustacchifor each of the different trees that they want to have. 149fa9922c2SRobert Mustacchi.Lp 150fa9922c2SRobert Mustacchi.Sy avl_node_t 151fa9922c2SRobert Mustacchi.Lp 152fa9922c2SRobert MustacchiType used as the data node for an AVL tree. One of these is embedded in 153fa9922c2SRobert Mustacchieach data structure that is the member of an AVL tree. 154fa9922c2SRobert Mustacchi.Lp 155fa9922c2SRobert Mustacchi.Sy avl_index_t 156fa9922c2SRobert Mustacchi.Lp 157fa9922c2SRobert MustacchiType used to locate a position in a tree. This is used with 158fa9922c2SRobert Mustacchi.Xr avl_find 3AVL 159fa9922c2SRobert Mustacchiand 160fa9922c2SRobert Mustacchi.Xr avl_insert 3AVL . 161fa9922c2SRobert Mustacchi.Sh LOCKING 162fa9922c2SRobert MustacchiThe 163fa9922c2SRobert Mustacchi.Nm 164fa9922c2SRobert Mustacchilibrary provides no locking. Callers that are using the same AVL tree 165fa9922c2SRobert Mustacchifrom multiple threads need to provide their own synchronization. If only 166fa9922c2SRobert Mustacchione thread is ever accessing or modifying the AVL tree, then there are 167fa9922c2SRobert Mustacchino synchronization concerns. If multiple AVL trees exist, then they may 168fa9922c2SRobert Mustacchiall be used simultaneously; however, they are subject to the same rules 169fa9922c2SRobert Mustacchiaround simultaneous access from a single thread. 170fa9922c2SRobert Mustacchi.Lp 171fa9922c2SRobert MustacchiAll routines are both 172fa9922c2SRobert Mustacchi.Sy Fork-safe 173fa9922c2SRobert Mustacchiand 174fa9922c2SRobert Mustacchi.Sy Async-Signal-Safe . 175fa9922c2SRobert MustacchiCallers may call functions in 176fa9922c2SRobert Mustacchi.Nm 177fa9922c2SRobert Mustacchifrom a signal handler and 178fa9922c2SRobert Mustacchi.Nm 179fa9922c2SRobert Mustacchicalls are all safe in face of 180fa9922c2SRobert Mustacchi.Xr fork 2 ; 181fa9922c2SRobert Mustacchihowever, if callers have their own locks, then they must make sure that 182fa9922c2SRobert Mustacchithey are accounted for by the use of routines such as 183fa9922c2SRobert Mustacchi.Xr pthread_atfork 3C . 184fa9922c2SRobert Mustacchi.Sh EXAMPLES 185fa9922c2SRobert MustacchiThe following code shows examples of exercising all of the functionality 186fa9922c2SRobert Mustacchithat is present in 187fa9922c2SRobert Mustacchi.Nm . 188fa9922c2SRobert MustacchiIt can be compiled by using a C compiler and linking 189fa9922c2SRobert Mustacchiagainst 190fa9922c2SRobert Mustacchi.Nm . 191fa9922c2SRobert MustacchiFor example, given a file named avl.c, with gcc, one would run: 192fa9922c2SRobert Mustacchi.Bd -literal 193fa9922c2SRobert Mustacchi$ gcc -Wall -o avl avl.c -lavl 194fa9922c2SRobert Mustacchi.Ed 195fa9922c2SRobert Mustacchi.Bd -literal 196fa9922c2SRobert Mustacchi/* 197fa9922c2SRobert Mustacchi * Example of using AVL Trees 198fa9922c2SRobert Mustacchi */ 199fa9922c2SRobert Mustacchi 200fa9922c2SRobert Mustacchi#include <sys/avl.h> 201fa9922c2SRobert Mustacchi#include <stddef.h> 202fa9922c2SRobert Mustacchi#include <stdlib.h> 203fa9922c2SRobert Mustacchi#include <stdio.h> 204fa9922c2SRobert Mustacchi 205fa9922c2SRobert Mustacchistatic avl_tree_t inttree; 206fa9922c2SRobert Mustacchi 207fa9922c2SRobert Mustacchi/* 208fa9922c2SRobert Mustacchi * The structure that we're storing in an AVL tree. 209fa9922c2SRobert Mustacchi */ 210fa9922c2SRobert Mustacchitypedef struct intnode { 211fa9922c2SRobert Mustacchi int in_val; 212fa9922c2SRobert Mustacchi avl_node_t in_avl; 213fa9922c2SRobert Mustacchi} intnode_t; 214fa9922c2SRobert Mustacchi 215fa9922c2SRobert Mustacchistatic int 216fa9922c2SRobert Mustacchiintnode_comparator(const void *l, const void *r) 217fa9922c2SRobert Mustacchi{ 218fa9922c2SRobert Mustacchi const intnode_t *li = l; 219fa9922c2SRobert Mustacchi const intnode_t *ri = r; 220fa9922c2SRobert Mustacchi 221fa9922c2SRobert Mustacchi if (li->in_val > ri->in_val) 222fa9922c2SRobert Mustacchi return (1); 223fa9922c2SRobert Mustacchi if (li->in_val < ri->in_val) 224fa9922c2SRobert Mustacchi return (-1); 225fa9922c2SRobert Mustacchi return (0); 226fa9922c2SRobert Mustacchi} 227fa9922c2SRobert Mustacchi 228fa9922c2SRobert Mustacchi/* 229fa9922c2SRobert Mustacchi * Create an AVL Tree 230fa9922c2SRobert Mustacchi */ 231fa9922c2SRobert Mustacchistatic void 232fa9922c2SRobert Mustacchicreate_avl(void) 233fa9922c2SRobert Mustacchi{ 234fa9922c2SRobert Mustacchi avl_create(&inttree, intnode_comparator, sizeof (intnode_t), 235fa9922c2SRobert Mustacchi offsetof(intnode_t, in_avl)); 236fa9922c2SRobert Mustacchi} 237fa9922c2SRobert Mustacchi 238fa9922c2SRobert Mustacchi/* 239fa9922c2SRobert Mustacchi * Add entries to the tree with the avl_add function. 240fa9922c2SRobert Mustacchi */ 241fa9922c2SRobert Mustacchistatic void 242fa9922c2SRobert Mustacchifill_avl(void) 243fa9922c2SRobert Mustacchi{ 244fa9922c2SRobert Mustacchi int i; 245fa9922c2SRobert Mustacchi intnode_t *inp; 246fa9922c2SRobert Mustacchi 247fa9922c2SRobert Mustacchi for (i = 0; i < 20; i++) { 248fa9922c2SRobert Mustacchi inp = malloc(sizeof (intnode_t)); 249fa9922c2SRobert Mustacchi assert(inp != NULL); 250fa9922c2SRobert Mustacchi inp->in_val = i; 251fa9922c2SRobert Mustacchi avl_add(&inttree, inp); 252fa9922c2SRobert Mustacchi } 253fa9922c2SRobert Mustacchi} 254fa9922c2SRobert Mustacchi 255fa9922c2SRobert Mustacchi/* 256fa9922c2SRobert Mustacchi * Find entries in the AVL tree. Note, we create an intnode_t on the 257fa9922c2SRobert Mustacchi * stack that we use to look this up. 258fa9922c2SRobert Mustacchi */ 259fa9922c2SRobert Mustacchistatic void 260fa9922c2SRobert Mustacchifind_avl(void) 261fa9922c2SRobert Mustacchi{ 262fa9922c2SRobert Mustacchi int i; 263fa9922c2SRobert Mustacchi intnode_t lookup, *inp; 264fa9922c2SRobert Mustacchi 265fa9922c2SRobert Mustacchi for (i = 10; i < 30; i++) { 266fa9922c2SRobert Mustacchi lookup.in_val = i; 267fa9922c2SRobert Mustacchi inp = avl_find(&inttree, &lookup, NULL); 268fa9922c2SRobert Mustacchi if (inp == NULL) { 269fa9922c2SRobert Mustacchi printf("Entry %d is not in the tree\\n", i); 270fa9922c2SRobert Mustacchi } else { 271fa9922c2SRobert Mustacchi printf("Entry %d is in the tree\\n", 272fa9922c2SRobert Mustacchi inp->in_val); 273fa9922c2SRobert Mustacchi } 274fa9922c2SRobert Mustacchi } 275fa9922c2SRobert Mustacchi} 276fa9922c2SRobert Mustacchi 277fa9922c2SRobert Mustacchi/* 278fa9922c2SRobert Mustacchi * Walk the tree forwards 279fa9922c2SRobert Mustacchi */ 280fa9922c2SRobert Mustacchistatic void 281fa9922c2SRobert Mustacchiwalk_forwards(void) 282fa9922c2SRobert Mustacchi{ 283fa9922c2SRobert Mustacchi intnode_t *inp; 284fa9922c2SRobert Mustacchi for (inp = avl_first(&inttree); inp != NULL; 285fa9922c2SRobert Mustacchi inp = AVL_NEXT(&inttree, inp)) { 286fa9922c2SRobert Mustacchi printf("Found entry %d\\n", inp->in_val); 287fa9922c2SRobert Mustacchi } 288fa9922c2SRobert Mustacchi} 289fa9922c2SRobert Mustacchi 290fa9922c2SRobert Mustacchi/* 291fa9922c2SRobert Mustacchi * Walk the tree backwards. 292fa9922c2SRobert Mustacchi */ 293fa9922c2SRobert Mustacchistatic void 294fa9922c2SRobert Mustacchiwalk_backwards(void) 295fa9922c2SRobert Mustacchi{ 296fa9922c2SRobert Mustacchi intnode_t *inp; 297fa9922c2SRobert Mustacchi for (inp = avl_last(&inttree); inp != NULL; 298fa9922c2SRobert Mustacchi inp = AVL_PREV(&inttree, inp)) { 299fa9922c2SRobert Mustacchi printf("Found entry %d\\n", inp->in_val); 300fa9922c2SRobert Mustacchi } 301fa9922c2SRobert Mustacchi} 302fa9922c2SRobert Mustacchi 303fa9922c2SRobert Mustacchi/* 304fa9922c2SRobert Mustacchi * Determine the number of nodes in the tree and if it is empty or 305fa9922c2SRobert Mustacchi * not. 306fa9922c2SRobert Mustacchi */ 307fa9922c2SRobert Mustacchistatic void 308fa9922c2SRobert Mustacchiinttree_inspect(void) 309fa9922c2SRobert Mustacchi{ 310fa9922c2SRobert Mustacchi printf("The tree is %s, there are %ld nodes in it\\n", 311fa9922c2SRobert Mustacchi avl_is_empty(&inttree) == B_TRUE ? "empty" : "not empty", 312fa9922c2SRobert Mustacchi avl_numnodes(&inttree)); 313fa9922c2SRobert Mustacchi} 314fa9922c2SRobert Mustacchi 315fa9922c2SRobert Mustacchi/* 316fa9922c2SRobert Mustacchi * Use avl_remove to remove entries from the tree. 317fa9922c2SRobert Mustacchi */ 318fa9922c2SRobert Mustacchistatic void 319fa9922c2SRobert Mustacchiremove_nodes(void) 320fa9922c2SRobert Mustacchi{ 321fa9922c2SRobert Mustacchi int i; 322fa9922c2SRobert Mustacchi intnode_t lookup, *inp; 323fa9922c2SRobert Mustacchi 324fa9922c2SRobert Mustacchi for (i = 0; i < 20; i+= 4) { 325fa9922c2SRobert Mustacchi lookup.in_val = i; 326fa9922c2SRobert Mustacchi inp = avl_find(&inttree, &lookup, NULL); 327fa9922c2SRobert Mustacchi if (inp != NULL) 328fa9922c2SRobert Mustacchi avl_remove(&inttree, inp); 329fa9922c2SRobert Mustacchi } 330fa9922c2SRobert Mustacchi} 331fa9922c2SRobert Mustacchi 332fa9922c2SRobert Mustacchi/* 333fa9922c2SRobert Mustacchi * Find the nearest nodes in the tree. 334fa9922c2SRobert Mustacchi */ 335fa9922c2SRobert Mustacchistatic void 336fa9922c2SRobert Mustacchinearest_nodes(void) 337fa9922c2SRobert Mustacchi{ 338fa9922c2SRobert Mustacchi intnode_t lookup, *inp; 339fa9922c2SRobert Mustacchi avl_index_t where; 340fa9922c2SRobert Mustacchi 341fa9922c2SRobert Mustacchi lookup.in_val = 12; 342fa9922c2SRobert Mustacchi if (avl_find(&inttree, &lookup, &where) != NULL) 343fa9922c2SRobert Mustacchi abort(); 344fa9922c2SRobert Mustacchi inp = avl_nearest(&inttree, where, AVL_BEFORE); 345fa9922c2SRobert Mustacchi assert(inp != NULL); 346fa9922c2SRobert Mustacchi printf("closest node before 12 is: %d\\n", inp->in_val); 347fa9922c2SRobert Mustacchi inp = avl_nearest(&inttree, where, AVL_AFTER); 348fa9922c2SRobert Mustacchi assert(inp != NULL); 349fa9922c2SRobert Mustacchi printf("closest node after 12 is: %d\\n", inp->in_val); 350fa9922c2SRobert Mustacchi} 351fa9922c2SRobert Mustacchi 352fa9922c2SRobert Mustacchistatic void 353fa9922c2SRobert Mustacchiinsert_avl(void) 354fa9922c2SRobert Mustacchi{ 355fa9922c2SRobert Mustacchi intnode_t lookup, *inp; 356fa9922c2SRobert Mustacchi avl_index_t where; 357fa9922c2SRobert Mustacchi 358fa9922c2SRobert Mustacchi lookup.in_val = 12; 359fa9922c2SRobert Mustacchi if (avl_find(&inttree, &lookup, &where) != NULL) 360fa9922c2SRobert Mustacchi abort(); 361fa9922c2SRobert Mustacchi inp = malloc(sizeof (intnode_t)); 362fa9922c2SRobert Mustacchi assert(inp != NULL); 363fa9922c2SRobert Mustacchi avl_insert(&inttree, inp, where); 364fa9922c2SRobert Mustacchi} 365fa9922c2SRobert Mustacchi 366fa9922c2SRobert Mustacchistatic void 367fa9922c2SRobert Mustacchiswap_avl(void) 368fa9922c2SRobert Mustacchi{ 369fa9922c2SRobert Mustacchi avl_tree_t swap; 370fa9922c2SRobert Mustacchi 371fa9922c2SRobert Mustacchi avl_create(&swap, intnode_comparator, sizeof (intnode_t), 372fa9922c2SRobert Mustacchi offsetof(intnode_t, in_avl)); 373fa9922c2SRobert Mustacchi avl_swap(&inttree, &swap); 374fa9922c2SRobert Mustacchi inttree_inspect(); 375fa9922c2SRobert Mustacchi avl_swap(&inttree, &swap); 376fa9922c2SRobert Mustacchi inttree_inspect(); 377fa9922c2SRobert Mustacchi} 378fa9922c2SRobert Mustacchi 379fa9922c2SRobert Mustacchi/* 380fa9922c2SRobert Mustacchi * Remove all remaining nodes in the tree. We first use 381fa9922c2SRobert Mustacchi * avl_destroy_nodes to empty the tree, then avl_destroy to finish. 382fa9922c2SRobert Mustacchi */ 383fa9922c2SRobert Mustacchistatic void 384fa9922c2SRobert Mustacchicleanup(void) 385fa9922c2SRobert Mustacchi{ 386fa9922c2SRobert Mustacchi intnode_t *inp; 387fa9922c2SRobert Mustacchi void *c = NULL; 388fa9922c2SRobert Mustacchi 389fa9922c2SRobert Mustacchi while ((inp = avl_destroy_nodes(&inttree, &c)) != NULL) { 390fa9922c2SRobert Mustacchi free(inp); 391fa9922c2SRobert Mustacchi } 392fa9922c2SRobert Mustacchi avl_destroy(&inttree); 393fa9922c2SRobert Mustacchi} 394fa9922c2SRobert Mustacchi 395fa9922c2SRobert Mustacchiint 396fa9922c2SRobert Mustacchimain(void) 397fa9922c2SRobert Mustacchi{ 398fa9922c2SRobert Mustacchi create_avl(); 399fa9922c2SRobert Mustacchi inttree_inspect(); 400fa9922c2SRobert Mustacchi fill_avl(); 401fa9922c2SRobert Mustacchi find_avl(); 402fa9922c2SRobert Mustacchi walk_forwards(); 403fa9922c2SRobert Mustacchi walk_backwards(); 404fa9922c2SRobert Mustacchi inttree_inspect(); 405fa9922c2SRobert Mustacchi remove_nodes(); 406fa9922c2SRobert Mustacchi inttree_inspect(); 407fa9922c2SRobert Mustacchi nearest_nodes(); 408fa9922c2SRobert Mustacchi insert_avl(); 409fa9922c2SRobert Mustacchi inttree_inspect(); 410fa9922c2SRobert Mustacchi swap_avl(); 411fa9922c2SRobert Mustacchi cleanup(); 412fa9922c2SRobert Mustacchi return (0); 413fa9922c2SRobert Mustacchi} 414fa9922c2SRobert Mustacchi.Ed 415fa9922c2SRobert Mustacchi.Sh INTERFACE STABILITY 416fa9922c2SRobert Mustacchi.Sy Committed 417fa9922c2SRobert Mustacchi.Sh MT-Level 418fa9922c2SRobert MustacchiSee 419fa9922c2SRobert Mustacchi.Sx Locking. 420fa9922c2SRobert Mustacchi.Sh SEE ALSO 421fa9922c2SRobert Mustacchi.Xr Intro 3 , 422fa9922c2SRobert Mustacchi.Xr pthread_atfork 3C 423fa9922c2SRobert Mustacchi.Lp 424fa9922c2SRobert Mustacchi.Xr avl_add 3AVL , 425fa9922c2SRobert Mustacchi.Xr avl_create 3AVL , 426fa9922c2SRobert Mustacchi.Xr avl_destroy 3AVL , 427fa9922c2SRobert Mustacchi.Xr avl_destroy_nodes 3AVL , 428fa9922c2SRobert Mustacchi.Xr avl_find 3AVL , 429fa9922c2SRobert Mustacchi.Xr avl_first 3AVL , 430fa9922c2SRobert Mustacchi.Xr avl_insert 3AVL , 431fa9922c2SRobert Mustacchi.Xr avl_insert_here 3AVL , 432fa9922c2SRobert Mustacchi.Xr avl_is_empty 3AVL , 433fa9922c2SRobert Mustacchi.Xr avl_last 3AVL , 434fa9922c2SRobert Mustacchi.Xr avl_nearest 3AVL , 435fa9922c2SRobert Mustacchi.Xr avl_numnodes 3AVL , 436fa9922c2SRobert Mustacchi.Xr avl_remove 3AVL , 437fa9922c2SRobert Mustacchi.Xr avl_swap 3AVL , 438fa9922c2SRobert Mustacchi.Rs 439fa9922c2SRobert Mustacchi.%A Adel'son-Vel'skiy, G. M. 440fa9922c2SRobert Mustacchi.%A Landis, Ye. M. 441fa9922c2SRobert Mustacchi.%T "An Algorithm for the Organization of Information" 442fa9922c2SRobert Mustacchi.%Q Deklady Akademii Nauk 443fa9922c2SRobert Mustacchi.%C USSR, Moscow 444fa9922c2SRobert Mustacchi.%P 263-266 445fa9922c2SRobert Mustacchi.%V Vol. 16 446fa9922c2SRobert Mustacchi.%N No. 2 447fa9922c2SRobert Mustacchi.%D 1962 448fa9922c2SRobert Mustacchi.Re 449