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. The 39.Fa size 40argument represents the total size of the data structure being used in 41the tree. This is a constant that is generally expressed to 42.Fn avl_create 43using the 44.Sy sizeof 45operator. 46.Pp 47The data structure that is being stored in the AVL tree must include an 48.Sy avl_node_t 49as a member of the structure. The structure may have multiple 50.Sy avl_node_t Ns 's, 51one for each AVL tree that it may concurrently be a member of. The 52.Fa offset 53argument indicates what the offset of the 54.Sy avl_node_t 55is for the data structure that this AVL tree contains. 56.Pp 57The 58.Fa compare 59function pointer is used to compare two nodes in the tree. This is used as part 60of all operations on the tree that cause traversal. The function is 61given, as arguments, two pointers to the actual data nodes, which should be 62cast to the corresponding type of actual data. The return value must 63adhere to the following rules: 64.Bl -enum 65.It 66If the first argument, 67.Fa first , 68is less than the second argument, 69.Fa second , 70then the 71.Fa compare 72function must return 73.Sy -1 . 74.It 75If the first argument is greater than the second argument, then the 76.Fa compare 77function must return 78.Sy 1 . 79.It 80Otherwise, if they compare to the same value, then it should return 81.Sy 0 . 82.It 83Only the return values, -1, 0, and 1, are valid. Returning values 84other than those will result in undefined behavior. 85.El 86.Pp 87When two nodes in the tree compare equal, then that means that they 88should represent the same data, though they may not always be equivalent 89pointers, due to lookups. 90.Pp 91The life time and storage of the AVL tree is maintained by the caller. 92The library does not perform any allocations as part of creating an AVL 93tree. 94.Sh EXAMPLES 95See the 96.Sy EXAMPLES 97section in 98.Xr libavl 3LIB . 99.Sh INTERFACE STABILITY 100.Sy Committed 101.Sh MT-Level 102See 103.Sx Locking 104in 105.Xr libavl 3LIB . 106.Sh SEE ALSO 107.Xr libavl 3LIB 108