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 May 07, 2015 15.Dt AVL_CREATE 3AVL 16.Os 17.Sh NAME 18.Nm avl_create 19.Nd create an AVL tree 20.Sh SYNOPSIS 21.Lb libavl 22.In sys/avl.h 23.Ft void 24.Fo avl_create 25.Fa "avl_tree_t *tree" 26.Fa "int (*compare)(const void *first, const void *second)" 27.Fa "size_t size" 28.Fa "size_t offset" 29.Fc 30.Sh DESCRIPTION 31The 32.Fn avl_create 33function initializes an AVL tree rooted at 34.Fa tree . 35.Pp 36An AVL tree needs to encode information about the type of data 37structures being stored inside of it and needs to be told how to compare 38two different entries in the same tree. 39The 40.Fa size 41argument represents the total size of the data structure being used in 42the tree. 43This is a constant that is generally expressed to 44.Fn avl_create 45using the 46.Sy sizeof 47operator. 48.Pp 49The data structure that is being stored in the AVL tree must include an 50.Sy avl_node_t 51as a member of the structure. 52The structure may have multiple 53.Sy avl_node_t Ns 's, 54one for each AVL tree that it may concurrently be a member of. 55The 56.Fa offset 57argument indicates what the offset of the 58.Sy avl_node_t 59is for the data structure that this AVL tree contains. 60.Pp 61The 62.Fa compare 63function pointer is used to compare two nodes in the tree. 64This is used as part of all operations on the tree that cause traversal. 65The function is given, as arguments, two pointers to the actual data nodes, 66which should be cast to the corresponding type of actual data. 67The return value must adhere to the following rules: 68.Bl -enum 69.It 70If the first argument, 71.Fa first , 72is less than the second argument, 73.Fa second , 74then the 75.Fa compare 76function must return 77.Sy -1 . 78.It 79If the first argument is greater than the second argument, then the 80.Fa compare 81function must return 82.Sy 1 . 83.It 84Otherwise, if they compare to the same value, then it should return 85.Sy 0 . 86.It 87Only the return values, -1, 0, and 1, are valid. 88Returning values other than those will result in undefined behavior. 89.El 90.Pp 91When two nodes in the tree compare equal, then that means that they 92should represent the same data, though they may not always be equivalent 93pointers, due to lookups. 94.Pp 95The life time and storage of the AVL tree is maintained by the caller. 96The library does not perform any allocations as part of creating an AVL 97tree. 98.Sh EXAMPLES 99See the 100.Sy EXAMPLES 101section in 102.Xr libavl 3LIB . 103.Sh INTERFACE STABILITY 104.Sy Committed 105.Sh MT-Level 106See 107.Sx Locking 108in 109.Xr libavl 3LIB . 110.Sh SEE ALSO 111.Xr libavl 3LIB 112