1*fa9922c2SRobert Mustacchi.\" 2*fa9922c2SRobert Mustacchi.\" This file and its contents are supplied under the terms of the 3*fa9922c2SRobert Mustacchi.\" Common Development and Distribution License ("CDDL"), version 1.0. 4*fa9922c2SRobert Mustacchi.\" You may only use this file in accordance with the terms of version 5*fa9922c2SRobert Mustacchi.\" 1.0 of the CDDL. 6*fa9922c2SRobert Mustacchi.\" 7*fa9922c2SRobert Mustacchi.\" A full copy of the text of the CDDL should have accompanied this 8*fa9922c2SRobert Mustacchi.\" source. A copy of the CDDL is also available via the Internet at 9*fa9922c2SRobert Mustacchi.\" http://www.illumos.org/license/CDDL. 10*fa9922c2SRobert Mustacchi.\" 11*fa9922c2SRobert Mustacchi.\" 12*fa9922c2SRobert Mustacchi.\" Copyright 2015 Joyent, Inc. 13*fa9922c2SRobert Mustacchi.\" 14*fa9922c2SRobert Mustacchi.Dd May 07, 2015 15*fa9922c2SRobert Mustacchi.Dt AVL_CREATE 3AVL 16*fa9922c2SRobert Mustacchi.Os 17*fa9922c2SRobert Mustacchi.Sh NAME 18*fa9922c2SRobert Mustacchi.Nm avl_create 19*fa9922c2SRobert Mustacchi.Nd create an AVL tree 20*fa9922c2SRobert Mustacchi.Sh SYNOPSIS 21*fa9922c2SRobert Mustacchi.Lb libavl 22*fa9922c2SRobert Mustacchi.In sys/avl.h 23*fa9922c2SRobert Mustacchi.Ft void 24*fa9922c2SRobert Mustacchi.Fo avl_create 25*fa9922c2SRobert Mustacchi.Fa "avl_tree_t *tree" 26*fa9922c2SRobert Mustacchi.Fa "int (*compare)(const void *first, const void *second)" 27*fa9922c2SRobert Mustacchi.Fa "size_t size" 28*fa9922c2SRobert Mustacchi.Fa "size_t offset" 29*fa9922c2SRobert Mustacchi.Fc 30*fa9922c2SRobert Mustacchi.Sh DESCRIPTION 31*fa9922c2SRobert MustacchiThe 32*fa9922c2SRobert Mustacchi.Fn avl_create 33*fa9922c2SRobert Mustacchifunction initializes an AVL tree rooted at 34*fa9922c2SRobert Mustacchi.Fa tree . 35*fa9922c2SRobert Mustacchi.Pp 36*fa9922c2SRobert MustacchiAn AVL tree needs to encode information about the type of data 37*fa9922c2SRobert Mustacchistructures being stored inside of it and needs to be told how to compare 38*fa9922c2SRobert Mustacchitwo different entries in the same tree. The 39*fa9922c2SRobert Mustacchi.Fa size 40*fa9922c2SRobert Mustacchiargument represents the total size of the data structure being used in 41*fa9922c2SRobert Mustacchithe tree. This is a constant that is generally expressed to 42*fa9922c2SRobert Mustacchi.Fn avl_create 43*fa9922c2SRobert Mustacchiusing the 44*fa9922c2SRobert Mustacchi.Sy sizeof 45*fa9922c2SRobert Mustacchioperator. 46*fa9922c2SRobert Mustacchi.Pp 47*fa9922c2SRobert MustacchiThe data structure that is being stored in the AVL tree must include an 48*fa9922c2SRobert Mustacchi.Sy avl_node_t 49*fa9922c2SRobert Mustacchias a member of the structure. The structure may have multiple 50*fa9922c2SRobert Mustacchi.Sy avl_node_t Ns 's, 51*fa9922c2SRobert Mustacchione for each AVL tree that it may concurrently be a member of. The 52*fa9922c2SRobert Mustacchi.Fa offset 53*fa9922c2SRobert Mustacchiargument indicates what the offset of the 54*fa9922c2SRobert Mustacchi.Sy avl_node_t 55*fa9922c2SRobert Mustacchiis for the data structure that this AVL tree contains. 56*fa9922c2SRobert Mustacchi.Pp 57*fa9922c2SRobert MustacchiThe 58*fa9922c2SRobert Mustacchi.Fa compare 59*fa9922c2SRobert Mustacchifunction pointer is used to compare two nodes in the tree. This is used as part 60*fa9922c2SRobert Mustacchiof all operations on the tree that cause traversal. The function is 61*fa9922c2SRobert Mustacchigiven, as arguments, two pointers to the actual data nodes, which should be 62*fa9922c2SRobert Mustacchicast to the corresponding type of actual data. The return value must 63*fa9922c2SRobert Mustacchiadhere to the following rules: 64*fa9922c2SRobert Mustacchi.Bl -enum 65*fa9922c2SRobert Mustacchi.It 66*fa9922c2SRobert MustacchiIf the first argument, 67*fa9922c2SRobert Mustacchi.Fa first , 68*fa9922c2SRobert Mustacchiis less than the second argument, 69*fa9922c2SRobert Mustacchi.Fa second , 70*fa9922c2SRobert Mustacchithen the 71*fa9922c2SRobert Mustacchi.Fa compare 72*fa9922c2SRobert Mustacchifunction must return 73*fa9922c2SRobert Mustacchi.Sy -1 . 74*fa9922c2SRobert Mustacchi.It 75*fa9922c2SRobert MustacchiIf the first argument is greater than the second argument, then the 76*fa9922c2SRobert Mustacchi.Fa compare 77*fa9922c2SRobert Mustacchifunction must return 78*fa9922c2SRobert Mustacchi.Sy 1 . 79*fa9922c2SRobert Mustacchi.It 80*fa9922c2SRobert MustacchiOtherwise, if they compare to the same value, then it should return 81*fa9922c2SRobert Mustacchi.Sy 0 . 82*fa9922c2SRobert Mustacchi.It 83*fa9922c2SRobert MustacchiOnly the return values, -1, 0, and 1, are valid. Returning values 84*fa9922c2SRobert Mustacchiother than those will result in undefined behavior. 85*fa9922c2SRobert Mustacchi.El 86*fa9922c2SRobert Mustacchi.Pp 87*fa9922c2SRobert MustacchiWhen two nodes in the tree compare equal, then that means that they 88*fa9922c2SRobert Mustacchishould represent the same data, though they may not always be equivalent 89*fa9922c2SRobert Mustacchipointers, due to lookups. 90*fa9922c2SRobert Mustacchi.Pp 91*fa9922c2SRobert MustacchiThe life time and storage of the AVL tree is maintained by the caller. 92*fa9922c2SRobert MustacchiThe library does not perform any allocations as part of creating an AVL 93*fa9922c2SRobert Mustacchitree. 94*fa9922c2SRobert Mustacchi.Sh EXAMPLES 95*fa9922c2SRobert MustacchiSee the 96*fa9922c2SRobert Mustacchi.Sy EXAMPLES 97*fa9922c2SRobert Mustacchisection in 98*fa9922c2SRobert Mustacchi.Xr libavl 3LIB . 99*fa9922c2SRobert Mustacchi.Sh INTERFACE STABILITY 100*fa9922c2SRobert Mustacchi.Sy Committed 101*fa9922c2SRobert Mustacchi.Sh MT-Level 102*fa9922c2SRobert MustacchiSee 103*fa9922c2SRobert Mustacchi.Sx Locking 104*fa9922c2SRobert Mustacchiin 105*fa9922c2SRobert Mustacchi.Xr libavl 3LIB . 106*fa9922c2SRobert Mustacchi.Sh SEE ALSO 107*fa9922c2SRobert Mustacchi.Xr libavl 3LIB 108