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