usr/src/man/man3avl/avl_create.3avl

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