usr/src/man/man3avl/avl_add.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 Apr 13, 2015
  15 .Dt AVL_ADD 3AVL
  16 .Os
  17 .Sh NAME
  18 .Nm avl_add ,
  19 .Nm avl_remove
  20 .Nd add and remove nodes from an AVL tree
  21 .Sh SYNOPSIS
  22 .Lb libavl
  23 .In sys/avl.h
  24 .Ft void
  25 .Fo avl_add
  26 .Fa "avl_tree_t *tree"
  27 .Fa "void *node"
  28 .Fc
  29 .Ft void
  30 .Fo avl_remove
  31 .Fa "avl_tree_t *tree"
  32 .Fa "void *node"
  33 .Fc
  34 .Sh DESCRIPTION
  35 The
  36 .Fn avl_add
  37 and
  38 .Fn avl_remove
  39 functions add and remove objects from the AVL tree rooted at
  40 .Fa tree .
  41 .Pp
  42 The
  43 .Fn avl_add
  44 function inserts
  45 .Fa node
  46 into the tree.
  47 .Fa node
  48 must not already be in the tree, thus implying it must not compare equal
  49 to any other node in the tree.
  50 Adding
  51 .Fa node
  52 to
  53 .Fa tree
  54 will take
  55 .Sy O(log(n))
  56 time, as it implicitly determines where to place it in the tree.
  57 If
  58 .Fa node Ns 's
  59 location has already been determined by
  60 .Xr avl_find 3AVL ,
  61 then instead use
  62 .Xr avl_insert 3AVL .
  63 .Pp
  64 The
  65 .Fn avl_remove
  66 function removes
  67 .Fa node
  68 from the tree rooted at
  69 .Fa tree .
  70 .Fa node
  71 must be present in the tree, otherwise, the behavior is undefined.
  72 Deleting
  73 .Fa node
  74 from
  75 .Fa tree
  76 occurs in
  77 .Sy O(log(n))
  78 time.
  79 .Sh EXAMPLES
  80 See the
  81 .Sy EXAMPLES
  82 section in
  83 .Xr libavl 3LIB .
  84 .Sh INTERFACE STABILITY
  85 .Sy Committed
  86 .Sh MT-Level
  87 See
  88 .Sx Locking
  89 in
  90 .Xr libavl 3LIB .
  91 .Sh SEE ALSO
  92 .Xr avl_create 3AVL ,
  93 .Xr avl_destroy 3AVL ,
  94 .Xr avl_insert 3AVL ,
  95 .Xr avl_insert_here 3AVL ,
  96 .Xr libavl 3LIB