avl/avl.h

   1 /*
   2  * Copyright (C) 1995 by Sam Rushing <rushing@nightmare.com>
   3  */
   4
   5 /* $Id: avl.h,v 1.7 2003/07/07 01:10:14 brendan Exp $ */
   6
   7 #ifndef __AVL_H
   8 #define __AVL_H
   9
  10 #ifdef __cplusplus
  11 extern "C" {
  12 #endif
  13
  14 #ifndef NO_THREAD
  15 #include <thread/thread.h>
  16 #else
  17 #define thread_rwlock_create(x) do{}while(0)
  18 #define thread_rwlock_destroy(x) do{}while(0)
  19 #define thread_rwlock_rlock(x) do{}while(0)
  20 #define thread_rwlock_wlock(x) do{}while(0)
  21 #define thread_rwlock_unlock(x) do{}while(0)
  22 #endif
  23
  24 typedef struct avl_node_tag {
  25   void *        key;
  26   struct avl_node_tag *    left;
  27   struct avl_node_tag *    right;
  28   struct avl_node_tag *    parent;
  29   /*
  30    * The lower 2 bits of <rank_and_balance> specify the balance
  31    * factor: 00==-1, 01==0, 10==+1.
  32    * The rest of the bits are used for <rank>
  33    */
  34   unsigned long        rank_and_balance;
  35 #ifndef NO_THREAD
  36   rwlock_t rwlock;
  37 #endif
  38 } avl_node;
  39
  40 #define AVL_GET_BALANCE(n)    ((int)(((n)->rank_and_balance & 3) - 1))
  41
  42 #define AVL_GET_RANK(n)    (((n)->rank_and_balance >> 2))
  43
  44 #define AVL_SET_BALANCE(n,b) \
  45   ((n)->rank_and_balance) = \
  46     (((n)->rank_and_balance & (~3)) | ((int)((b) + 1)))
  47
  48 #define AVL_SET_RANK(n,r) \
  49   ((n)->rank_and_balance) = \
  50     (((n)->rank_and_balance & 3) | (r << 2))
  51
  52 struct _avl_tree;
  53
  54 typedef int (*avl_key_compare_fun_type)    (void * compare_arg, void * a, void * b);
  55 typedef int (*avl_iter_fun_type)    (void * key, void * iter_arg);
  56 typedef int (*avl_iter_index_fun_type)    (unsigned long index, void * key, void * iter_arg);
  57 typedef int (*avl_free_key_fun_type)    (void * key);
  58 typedef int (*avl_key_printer_fun_type)    (char *, void *);
  59
  60 /*
  61  * <compare_fun> and <compare_arg> let us associate a particular compare
  62  * function with each tree, separately.
  63  */
  64
  65 #ifdef _mangle
  66 # define avl_tree_new _mangle(avl_tree_new)
  67 # define avl_node_new _mangle(avl_node_new)
  68 # define avl_tree_free _mangle(avl_tree_free)
  69 # define avl_insert _mangle(avl_insert)
  70 # define avl_delete _mangle(avl_delete)
  71 # define avl_get_by_index _mangle(avl_get_by_index)
  72 # define avl_get_by_key _mangle(avl_get_by_key)
  73 # define avl_iterate_inorder _mangle(avl_iterate_inorder)
  74 # define avl_iterate_index_range _mangle(avl_iterate_index_range)
  75 # define avl_tree_rlock _mangle(avl_tree_rlock)
  76 # define avl_tree_wlock _mangle(avl_tree_wlock)
  77 # define avl_tree_wlock _mangle(avl_tree_wlock)
  78 # define avl_tree_unlock _mangle(avl_tree_unlock)
  79 # define avl_node_rlock _mangle(avl_node_rlock)
  80 # define avl_node_wlock _mangle(avl_node_wlock)
  81 # define avl_node_unlock _mangle(avl_node_unlock)
  82 # define avl_get_span_by_key _mangle(avl_get_span_by_key)
  83 # define avl_get_span_by_two_keys _mangle(avl_get_span_by_two_keys)
  84 # define avl_verify _mangle(avl_verify)
  85 # define avl_print_tree _mangle(avl_print_tree)
  86 # define avl_get_first _mangle(avl_get_first)
  87 # define avl_get_prev _mangle(avl_get_prev)
  88 # define avl_get_next _mangle(avl_get_next)
  89 # define avl_get_item_by_key_most _mangle(avl_get_item_by_key_most)
  90 # define avl_get_item_by_key_least _mangle(avl_get_item_by_key_least)
  91 #endif
  92
  93 typedef struct _avl_tree {
  94   avl_node *            root;
  95   unsigned long            height;
  96   unsigned long            length;
  97   avl_key_compare_fun_type    compare_fun;
  98   void *             compare_arg;
  99 #ifndef NO_THREAD
 100   rwlock_t rwlock;
 101 #endif
 102 } avl_tree;
 103
 104 avl_tree * avl_tree_new (avl_key_compare_fun_type compare_fun, void * compare_arg);
 105 avl_node * avl_node_new (void * key, avl_node * parent);
 106
 107 void avl_tree_free (
 108   avl_tree *        tree,
 109   avl_free_key_fun_type    free_key_fun
 110   );
 111
 112 int avl_insert (
 113   avl_tree *        ob,
 114   void *        key
 115   );
 116
 117 int avl_delete (
 118   avl_tree *        tree,
 119   void *        key,
 120   avl_free_key_fun_type    free_key_fun
 121   );
 122
 123 int avl_get_by_index (
 124   avl_tree *        tree,
 125   unsigned long        index,
 126   void **        value_address
 127   );
 128
 129 int avl_get_by_key (
 130   avl_tree *        tree,
 131   void *        key,
 132   void **        value_address
 133   );
 134
 135 int avl_iterate_inorder (
 136   avl_tree *        tree,
 137   avl_iter_fun_type    iter_fun,
 138   void *        iter_arg
 139   );
 140
 141 int avl_iterate_index_range (
 142   avl_tree *        tree,
 143   avl_iter_index_fun_type iter_fun,
 144   unsigned long        low,
 145   unsigned long        high,
 146   void *        iter_arg
 147   );
 148
 149 int avl_get_span_by_key (
 150   avl_tree *        tree,
 151   void *        key,
 152   unsigned long *    low,
 153   unsigned long *    high
 154   );
 155
 156 int avl_get_span_by_two_keys (
 157   avl_tree *        tree,
 158   void *        key_a,
 159   void *        key_b,
 160   unsigned long *    low,
 161   unsigned long *    high
 162   );
 163
 164 int avl_verify (avl_tree * tree);
 165
 166 void avl_print_tree (
 167   avl_tree *        tree,
 168   avl_key_printer_fun_type key_printer
 169   );
 170
 171 avl_node *avl_get_first(avl_tree *tree);
 172
 173 avl_node *avl_get_prev(avl_node * node);
 174
 175 avl_node *avl_get_next(avl_node * node);
 176
 177 /* These two are from David Ascher <david_ascher@brown.edu> */
 178
 179 int avl_get_item_by_key_most (
 180   avl_tree *        tree,
 181   void *        key,
 182   void **        value_address
 183   );
 184
 185 int avl_get_item_by_key_least (
 186   avl_tree *        tree,
 187   void *        key,
 188   void **        value_address
 189   );
 190
 191 /* optional locking stuff */
 192 void avl_tree_rlock(avl_tree *tree);
 193 void avl_tree_wlock(avl_tree *tree);
 194 void avl_tree_unlock(avl_tree *tree);
 195 void avl_node_rlock(avl_node *node);
 196 void avl_node_wlock(avl_node *node);
 197 void avl_node_unlock(avl_node *node);
 198
 199 #ifdef __cplusplus
 200 }
 201 #endif
 202
 203 #endif /* __AVL_H */