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.\" 14fa9922c2SRobert Mustacchi.Dd Apr 13, 2015 15fa9922c2SRobert Mustacchi.Dt AVL_ADD 3AVL 16fa9922c2SRobert Mustacchi.Os 17fa9922c2SRobert Mustacchi.Sh NAME 18fa9922c2SRobert Mustacchi.Nm avl_add , 19fa9922c2SRobert Mustacchi.Nm avl_remove 20fa9922c2SRobert Mustacchi.Nd add and remove nodes from an AVL tree 21fa9922c2SRobert Mustacchi.Sh SYNOPSIS 22fa9922c2SRobert Mustacchi.Lb libavl 23fa9922c2SRobert Mustacchi.In sys/avl.h 24fa9922c2SRobert Mustacchi.Ft void 25fa9922c2SRobert Mustacchi.Fo avl_add 26fa9922c2SRobert Mustacchi.Fa "avl_tree_t *tree" 27fa9922c2SRobert Mustacchi.Fa "void *node" 28fa9922c2SRobert Mustacchi.Fc 29fa9922c2SRobert Mustacchi.Ft void 30fa9922c2SRobert Mustacchi.Fo avl_remove 31fa9922c2SRobert Mustacchi.Fa "avl_tree_t *tree" 32fa9922c2SRobert Mustacchi.Fa "void *node" 33fa9922c2SRobert Mustacchi.Fc 34fa9922c2SRobert Mustacchi.Sh DESCRIPTION 35fa9922c2SRobert MustacchiThe 36fa9922c2SRobert Mustacchi.Fn avl_add 37fa9922c2SRobert Mustacchiand 38fa9922c2SRobert Mustacchi.Fn avl_remove 39fa9922c2SRobert Mustacchifunctions add and remove objects from the AVL tree rooted at 40fa9922c2SRobert Mustacchi.Fa tree . 41fa9922c2SRobert Mustacchi.Pp 42fa9922c2SRobert MustacchiThe 43fa9922c2SRobert Mustacchi.Fn avl_add 44fa9922c2SRobert Mustacchifunction inserts 45fa9922c2SRobert Mustacchi.Fa node 46fa9922c2SRobert Mustacchiinto the tree. 47fa9922c2SRobert Mustacchi.Fa node 48fa9922c2SRobert Mustacchimust not already be in the tree, thus implying it must not compare equal 49fa9922c2SRobert Mustacchito any other node in the tree. Adding 50fa9922c2SRobert Mustacchi.Fa node 51fa9922c2SRobert Mustacchito 52fa9922c2SRobert Mustacchi.Fa tree 53fa9922c2SRobert Mustacchiwill take 54fa9922c2SRobert Mustacchi.Sy O(log(n)) 55fa9922c2SRobert Mustacchitime, as it implicitly determines where to place it in the tree. 56fa9922c2SRobert MustacchiIf 57fa9922c2SRobert Mustacchi.Fa node Ns 's 58fa9922c2SRobert Mustacchilocation has already been determined by 59fa9922c2SRobert Mustacchi.Xr avl_find 3AVL , 60fa9922c2SRobert Mustacchithen instead use 61fa9922c2SRobert Mustacchi.Xr avl_insert 3AVL . 62fa9922c2SRobert Mustacchi.Pp 63fa9922c2SRobert MustacchiThe 64fa9922c2SRobert Mustacchi.Fn avl_remove 65fa9922c2SRobert Mustacchifunction removes 66fa9922c2SRobert Mustacchi.Fa node 67fa9922c2SRobert Mustacchifrom the tree rooted at 68fa9922c2SRobert Mustacchi.Fa tree . 69fa9922c2SRobert Mustacchi.Fa node 70fa9922c2SRobert Mustacchimust be present in the tree, otherwise, the behavior is undefined. 71fa9922c2SRobert MustacchiDeleting 72fa9922c2SRobert Mustacchi.Fa node 73fa9922c2SRobert Mustacchifrom 74fa9922c2SRobert Mustacchi.Fa tree 75fa9922c2SRobert Mustacchioccurs in 76fa9922c2SRobert Mustacchi.Sy O(log(n)) 77fa9922c2SRobert Mustacchitime. 78fa9922c2SRobert Mustacchi.Sh EXAMPLES 79fa9922c2SRobert MustacchiSee the 80fa9922c2SRobert Mustacchi.Sy EXAMPLES 81fa9922c2SRobert Mustacchisection in 82fa9922c2SRobert Mustacchi.Xr libavl 3LIB . 83fa9922c2SRobert Mustacchi.Sh INTERFACE STABILITY 84fa9922c2SRobert Mustacchi.Sy Committed 85fa9922c2SRobert Mustacchi.Sh MT-Level 86fa9922c2SRobert MustacchiSee 87fa9922c2SRobert Mustacchi.Sx Locking 88fa9922c2SRobert Mustacchiin 89fa9922c2SRobert Mustacchi.Xr libavl 3LIB . 90fa9922c2SRobert Mustacchi.Sh SEE ALSO 91fa9922c2SRobert Mustacchi.Xr avl_create 3AVL , 92*3a005aadSYuri Pankov.Xr avl_destroy 3AVL , 93fa9922c2SRobert Mustacchi.Xr avl_insert 3AVL , 94fa9922c2SRobert Mustacchi.Xr avl_insert_here 3AVL , 95*3a005aadSYuri Pankov.Xr libavl 3LIB 96