Print this page
4745 fix AVL code misspellings


  22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25 
  26 #ifndef _AVL_H
  27 #define _AVL_H
  28 
  29 /*
  30  * This is a private header file.  Applications should not directly include
  31  * this file.
  32  */
  33 
  34 #ifdef  __cplusplus
  35 extern "C" {
  36 #endif
  37 
  38 #include <sys/types.h>
  39 #include <sys/avl_impl.h>
  40 
  41 /*
  42  * This is a generic implemenatation of AVL trees for use in the Solaris kernel.
  43  * The interfaces provide an efficient way of implementing an ordered set of
  44  * data structures.
  45  *
  46  * AVL trees provide an alternative to using an ordered linked list. Using AVL
  47  * trees will usually be faster, however they requires more storage. An ordered
  48  * linked list in general requires 2 pointers in each data structure. The
  49  * AVL tree implementation uses 3 pointers. The following chart gives the
  50  * approximate performance of operations with the different approaches:
  51  *
  52  *      Operation        Link List      AVL tree
  53  *      ---------        --------       --------
  54  *      lookup             O(n)         O(log(n))
  55  *
  56  *      insert 1 node    constant       constant
  57  *
  58  *      delete 1 node    constant       between constant and O(log(n))
  59  *
  60  *      delete all nodes   O(n)         O(n)
  61  *
  62  *      visit the next


 158  * found. If not found, it returns NULL and then if "where" is not NULL it sets
 159  * "where" for use with avl_insert() or avl_nearest().
 160  *
 161  * node   - node that has the value being looked for
 162  * where  - position for use with avl_nearest() or avl_insert(), may be NULL
 163  */
 164 extern void *avl_find(avl_tree_t *tree, const void *node, avl_index_t *where);
 165 
 166 /*
 167  * Insert a node into the tree.
 168  *
 169  * node   - the node to insert
 170  * where  - position as returned from avl_find()
 171  */
 172 extern void avl_insert(avl_tree_t *tree, void *node, avl_index_t where);
 173 
 174 /*
 175  * Insert "new_data" in "tree" in the given "direction" either after
 176  * or before the data "here".
 177  *
 178  * This might be usefull for avl clients caching recently accessed
 179  * data to avoid doing avl_find() again for insertion.
 180  *
 181  * new_data     - new data to insert
 182  * here         - existing node in "tree"
 183  * direction    - either AVL_AFTER or AVL_BEFORE the data "here".
 184  */
 185 extern void avl_insert_here(avl_tree_t *tree, void *new_data, void *here,
 186     int direction);
 187 
 188 
 189 /*
 190  * Return the first or last valued node in the tree. Will return NULL
 191  * if the tree is empty.
 192  *
 193  */
 194 extern void *avl_first(avl_tree_t *tree);
 195 extern void *avl_last(avl_tree_t *tree);
 196 
 197 
 198 /*




  22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25 
  26 #ifndef _AVL_H
  27 #define _AVL_H
  28 
  29 /*
  30  * This is a private header file.  Applications should not directly include
  31  * this file.
  32  */
  33 
  34 #ifdef  __cplusplus
  35 extern "C" {
  36 #endif
  37 
  38 #include <sys/types.h>
  39 #include <sys/avl_impl.h>
  40 
  41 /*
  42  * This is a generic implementation of AVL trees for use in the Solaris kernel.
  43  * The interfaces provide an efficient way of implementing an ordered set of
  44  * data structures.
  45  *
  46  * AVL trees provide an alternative to using an ordered linked list. Using AVL
  47  * trees will usually be faster, however they requires more storage. An ordered
  48  * linked list in general requires 2 pointers in each data structure. The
  49  * AVL tree implementation uses 3 pointers. The following chart gives the
  50  * approximate performance of operations with the different approaches:
  51  *
  52  *      Operation        Link List      AVL tree
  53  *      ---------        --------       --------
  54  *      lookup             O(n)         O(log(n))
  55  *
  56  *      insert 1 node    constant       constant
  57  *
  58  *      delete 1 node    constant       between constant and O(log(n))
  59  *
  60  *      delete all nodes   O(n)         O(n)
  61  *
  62  *      visit the next


 158  * found. If not found, it returns NULL and then if "where" is not NULL it sets
 159  * "where" for use with avl_insert() or avl_nearest().
 160  *
 161  * node   - node that has the value being looked for
 162  * where  - position for use with avl_nearest() or avl_insert(), may be NULL
 163  */
 164 extern void *avl_find(avl_tree_t *tree, const void *node, avl_index_t *where);
 165 
 166 /*
 167  * Insert a node into the tree.
 168  *
 169  * node   - the node to insert
 170  * where  - position as returned from avl_find()
 171  */
 172 extern void avl_insert(avl_tree_t *tree, void *node, avl_index_t where);
 173 
 174 /*
 175  * Insert "new_data" in "tree" in the given "direction" either after
 176  * or before the data "here".
 177  *
 178  * This might be useful for avl clients caching recently accessed
 179  * data to avoid doing avl_find() again for insertion.
 180  *
 181  * new_data     - new data to insert
 182  * here         - existing node in "tree"
 183  * direction    - either AVL_AFTER or AVL_BEFORE the data "here".
 184  */
 185 extern void avl_insert_here(avl_tree_t *tree, void *new_data, void *here,
 186     int direction);
 187 
 188 
 189 /*
 190  * Return the first or last valued node in the tree. Will return NULL
 191  * if the tree is empty.
 192  *
 193  */
 194 extern void *avl_first(avl_tree_t *tree);
 195 extern void *avl_last(avl_tree_t *tree);
 196 
 197 
 198 /*