usr/src/man/man9f/avl.9f

   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 2016 Joyent, Inc.
  13 .\"
  14 .Dd Mar 13, 2016
  15 .Dt AVL 9F
  16 .Os
  17 .Sh NAME
  18 .Nm avl ,
  19 .Nm avl_add ,
  20 .Nm avl_create ,
  21 .Nm avl_destroy ,
  22 .Nm avl_destroy_nodes ,
  23 .Nm avl_find  ,
  24 .Nm avl_first ,
  25 .Nm avl_insert ,
  26 .Nm avl_insert_here ,
  27 .Nm avl_is_empty ,
  28 .Nm avl_last ,
  29 .Nm avl_nearest ,
  30 .Nm avl_numnodes ,
  31 .Nm avl_remove ,
  32 .Nm avl_swap ,
  33 .Nm AVL_NEXT ,
  34 .Nm AVL_PREV
  35 .Nd AVL tree routines
  36 .Sh DESCRIPTION
  37 AVL trees are a general purpose, self-balancing binary tree that can be
  38 used instead of the standard linked list interfaces --
  39 .Xr list_create 9F .
  40 AVL trees are particularly useful either when order is important or
  41 better lookup performance is required.
  42 .Pp
  43 The AVL tree interfaces are identical in both userland and the kernel.
  44 For more general information on AVL trees, see
  45 .Xr libavl 3LIB .
  46 For more information on any of the funtions defined here, please see the
  47 corresponding manual page in section 3AVL.
  48 Please note, that while the descriptions in those manual pages are accurate for
  49 writers of Device Drivers, the examples provided use scaffolding not available
  50 in the kernel, such as the use of
  51 .Fn malloc ,
  52 and need to be adapated.
  53 .Sh CONTEXT
  54 All of the AVL routines may be used in user, kernel, and interrupt
  55 context.
  56 .Sh EXAMPLES
  57 See
  58 .Sy EXAMPLES
  59 in
  60 .Xr libavl 3LIB .
  61 .Sh INTERFACE STABILITY
  62 .Sy Committed
  63 .Sh MT-Safety
  64 AVL trees do not inherently have any internal locking, it is up to the
  65 consumer to use locks as appropriate.
  66 See
  67 .Xr mutex 9F
  68 and
  69 .Xr rwlock 9F
  70 for more information on synchronization primitives.
  71 .Sh SEE ALSO
  72 .Xr avl_add 3AVL ,
  73 .Xr avl_create 3AVL ,
  74 .Xr avl_destroy 3AVL ,
  75 .Xr avl_destroy_nodes 3AVL ,
  76 .Xr avl_find  3AVL ,
  77 .Xr avl_first 3AVL ,
  78 .Xr avl_insert 3AVL ,
  79 .Xr avl_insert_here 3AVL ,
  80 .Xr avl_is_empty 3AVL ,
  81 .Xr avl_last 3AVL ,
  82 .Xr avl_nearest 3AVL ,
  83 .Xr AVL_NEXT 3AVL ,
  84 .Xr avl_numnodes 3AVL ,
  85 .Xr AVL_PREV 3AVL ,
  86 .Xr avl_remove 3AVL ,
  87 .Xr avl_swap 3AVL ,
  88 .Xr libavl 3LIB
  89 .Rs
  90 .%T Writing Device Drivers
  91 .Re