usr/src/man/man3avl/avl_find.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_FIND 3AVL
  16 .Os
  17 .Sh NAME
  18 .Nm avl_find
  19 .Nd find a node in an AVL tree
  20 .Sh SYNOPSIS
  21 .Lb libavl
  22 .In sys/avl.h
  23 .Ft void *
  24 .Fo avl_find
  25 .Fa "avl_tree_t *tree"
  26 .Fa "const void *node"
  27 .Fa "avl_index_t *where"
  28 .Fc
  29 .Sh DESCRIPTION
  30 The
  31 .Fn avl_find
  32 function is used to look up a node in the tree rooted at
  33 .Fa tree .
  34 .Pp
  35 To perform a lookup, a caller should construct an instance of the data
  36 structure, the argument
  37 .Fa node .
  38 .Fn avl_find
  39 searches through the tree for a node which compares equal to the passed
  40 in
  41 .Fa node
  42 using the comparison function specified when the tree was created with
  43 .Xr avl_create 3AVL .
  44 The only fields of
  45 .Fa node
  46 that need to be initialized are those that the comparison function will
  47 use, the others may remain uninitialized.
  48 .Pp
  49 If a match exists in the tree, then that entry will be returned.
  50 Otherwise,
  51 .Sy NULL
  52 is returned.
  53 .Pp
  54 If
  55 .Fa node
  56 does not match anything in the tree and the value of
  57 .Fa where
  58 is a
  59 .Pf non- Sy NULL
  60 pointer, then
  61 .Fa where
  62 will be updated to a value that can be used with both
  63 .Xr avl_insert 3AVL
  64 and
  65 .Xr avl_nearest 3AVL .
  66 This value is only valid as long as the tree is not modified.
  67 If anything is added or removed from the tree, then the value of
  68 .Fa where
  69 is no longer valid.
  70 This is commonly used as part of a pattern to see if something that should be
  71 added to the tree already exists, and if not, insert it.
  72 For more information, see the examples in
  73 .Xr libavl 3LIB .
  74 .Pp
  75 If the lookup is successful, then the contents of
  76 .Fa where
  77 are undefined.
  78 .Sh RETURN VALUES
  79 If
  80 .Fa node
  81 matches an entry in the tree, the matching entry is returned.
  82 Otherwise,
  83 .Sy NULL
  84 is returned and if
  85 .Fa where
  86 is
  87 .Pf non- Sy NULL ,
  88 it is updated to point to a location in the tree.
  89 .Sh EXAMPLES
  90 See the
  91 .Sy EXAMPLES
  92 section in
  93 .Xr libavl 3LIB .
  94 .Sh INTERFACE STABILITY
  95 .Sy Committed
  96 .Sh MT-Level
  97 See
  98 .Sx Locking
  99 in
 100 .Xr libavl 3LIB .
 101 .Sh SEE ALSO
 102 .Xr avl_create 3AVL ,
 103 .Xr avl_insert 3AVL ,
 104 .Xr avl_nearest 3AVL ,
 105 .Xr libavl 3LIB