share/man/man3avl/avl_insert.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_INSERT 3AVL
  16 .Os
  17 .Sh NAME
  18 .Nm avl_insert ,
  19 .Nm avl_insert_here
  20 .Nd insert items into an AVL tree
  21 .Sh SYNOPSIS
  22 .Lb libavl
  23 .In sys/avl.h
  24 .Ft void
  25 .Fo avl_insert
  26 .Fa "avl_tree_t *tree"
  27 .Fa "void *new"
  28 .Fa "avl_index_t where"
  29 .Fc
  30 .Ft void
  31 .Fo avl_insert_here
  32 .Fa "avl_tree_t *tree"
  33 .Fa "void *new"
  34 .Fa "void *here"
  35 .Fa "int direction"
  36 .Fc
  37 .Sh DESCRIPTION
  38 The
  39 .Fn avl_insert
  40 and
  41 .Fn avl_insert_here
  42 functions are used to add the entry
  43 .Fa new
  44 to the tree rooted at
  45 .Fa tree .
  46 .Pp
  47 The
  48 .Fn avl_insert
  49 function uses the
  50 .Fa where
  51 value, obtained from a call to
  52 .Xr avl_find 3AVL ,
  53 to determine where to insert the new entry into the tree. The tree must
  54 not have been modified in between the call to
  55 .Xr avl_find 3AVL
  56 and the call to
  57 .Fn avl_insert .
  58 If callers are not using
  59 .Xr avl_find 3AVL
  60 to validate the presence of
  61 .Fa new
  62 in the tree and only immediately insert it, then
  63 .Xr avl_add 3AVL
  64 may be used instead.
  65 .Pp
  66 The
  67 .Fn avl_insert_here
  68 function is for consumers who are keeping track of recently accessed
  69 data and wish to avoid an additional call to
  70 .Xr avl_find 3AVL .
  71 The new entry,
  72 .Fa new ,
  73 will be inserted starting at the node
  74 .Fa here ,
  75 which must already exist in the tree. To insert the node in the tree
  76 before
  77 .Fa here ,
  78 then the argument
  79 .Fa direction
  80 should have the value
  81 .Dv AVL_BEFORE .
  82 Otherwise, to indicate that the new entry should be inserted after
  83 .Fa here ,
  84 then
  85 .Fa direction
  86 should be set to
  87 .Dv AVL_AFTER .
  88 It is illegal to set
  89 .Fa direction
  90 to anything other than
  91 .Dv AVL_BEFORE
  92 or
  93 .Dv AVL_AFTER .
  94 If this is done, the behavior is not defined.
  95 .Sh EXAMPLES
  96 See the
  97 .Sy EXAMPLES
  98 section in
  99 .Xr libavl 3LIB .
 100 .Sh INTERFACE STABILITY
 101 .Sy Committed
 102 .Sh MT-Level
 103 See
 104 .Sx Locking
 105 in
 106 .Xr libavl 3LIB .
 107 .Sh SEE ALSO
 108 .Xr avl_add 3AVL ,
 109 .Xr avl_find 3AVL ,
 110 .Xr libavl 3LIB