servers/vm/cavl_if.h

   1 /* Abstract AVL Tree Generic C Package.
   2 ** Interface generation header file.
   3 **
   4 ** This code is in the public domain.  See cavl_tree.html for interface
   5 ** documentation.
   6 **
   7 ** Version: 1.5  Author: Walt Karas
   8 */
   9
  10 /* This header contains the definition of CHAR_BIT (number of bits in a
  11 ** char). */
  12 #include <limits.h>
  13
  14 #undef L__
  15 #undef L__EST_LONG_BIT
  16 #undef L__SIZE
  17 #undef L__SC
  18 #undef L__LONG_BIT
  19 #undef L__BIT_ARR_DEFN
  20
  21 #ifndef AVL_SEARCH_TYPE_DEFINED_
  22 #define AVL_SEARCH_TYPE_DEFINED_
  23
  24 typedef enum
  25   {
  26     AVL_EQUAL = 1,
  27     AVL_LESS = 2,
  28     AVL_GREATER = 4,
  29     AVL_LESS_EQUAL = AVL_EQUAL | AVL_LESS,
  30     AVL_GREATER_EQUAL = AVL_EQUAL | AVL_GREATER
  31   }
  32 avl_search_type;
  33
  34 #endif
  35
  36 #ifdef AVL_UNIQUE
  37
  38 #define L__ AVL_UNIQUE
  39
  40 #else
  41
  42 #define L__(X) X
  43
  44 #endif
  45
  46 /* Determine storage class for function prototypes. */
  47 #ifdef AVL_PRIVATE
  48
  49 #define L__SC static
  50
  51 #else
  52
  53 #define L__SC extern
  54
  55 #endif
  56
  57 #ifdef AVL_SIZE
  58
  59 #define L__SIZE AVL_SIZE
  60
  61 #else
  62
  63 #define L__SIZE unsigned long
  64
  65 #endif
  66
  67 typedef struct
  68   {
  69     #ifdef AVL_INSIDE_STRUCT
  70
  71     AVL_INSIDE_STRUCT
  72
  73     #endif
  74
  75     AVL_HANDLE root;
  76   }
  77 L__(avl);
  78
  79 /* Function prototypes. */
  80
  81 L__SC void L__(init)(L__(avl) *tree);
  82
  83 L__SC int L__(is_empty)(L__(avl) *tree);
  84
  85 L__SC AVL_HANDLE L__(insert)(L__(avl) *tree, AVL_HANDLE h);
  86
  87 L__SC AVL_HANDLE L__(search)(L__(avl) *tree, AVL_KEY k, avl_search_type st);
  88
  89 L__SC AVL_HANDLE L__(search_least)(L__(avl) *tree);
  90
  91 L__SC AVL_HANDLE L__(search_greatest)(L__(avl) *tree);
  92
  93 L__SC AVL_HANDLE L__(remove)(L__(avl) *tree, AVL_KEY k);
  94
  95 L__SC AVL_HANDLE L__(subst)(L__(avl) *tree, AVL_HANDLE new_node);
  96
  97 #ifdef AVL_BUILD_ITER_TYPE
  98
  99 L__SC int L__(build)(
 100   L__(avl) *tree, AVL_BUILD_ITER_TYPE p, L__SIZE num_nodes);
 101
 102 #endif
 103
 104 /* ANSI C/ISO C++ require that a long have at least 32 bits.  Set
 105 ** L__EST_LONG_BIT to be the greatest multiple of 8 in the range
 106 ** 32 - 64 (inclusive) that is less than or equal to the number of
 107 ** bits in a long.
 108 */
 109
 110 #if (((LONG_MAX >> 31) >> 7) == 0)
 111
 112 #define L__EST_LONG_BIT 32
 113
 114 #elif (((LONG_MAX >> 31) >> 15) == 0)
 115
 116 #define L__EST_LONG_BIT 40
 117
 118 #elif (((LONG_MAX >> 31) >> 23) == 0)
 119
 120 #define L__EST_LONG_BIT 48
 121
 122 #elif (((LONG_MAX >> 31) >> 31) == 0)
 123
 124 #define L__EST_LONG_BIT 56
 125
 126 #else
 127
 128 #define L__EST_LONG_BIT 64
 129
 130 #endif
 131
 132 /* Number of bits in a long. */
 133 #define L__LONG_BIT (sizeof(long) * CHAR_BIT)
 134
 135 /* The macro L__BIT_ARR_DEFN defines a bit array whose index is a (0-based)
 136 ** node depth.  The definition depends on whether the maximum depth is more
 137 ** or less than the number of bits in a single long.
 138 */
 139
 140 #if ((AVL_MAX_DEPTH) > L__EST_LONG_BIT)
 141
 142 /* Maximum depth may be more than number of bits in a long. */
 143
 144 #define L__BIT_ARR_DEFN(NAME) \
 145   unsigned long NAME[((AVL_MAX_DEPTH) + L__LONG_BIT - 1) / L__LONG_BIT];
 146
 147 #else
 148
 149 /* Maximum depth is definitely less than number of bits in a long. */
 150
 151 #define L__BIT_ARR_DEFN(NAME) unsigned long NAME;
 152
 153 #endif
 154
 155 /* Iterator structure. */
 156 typedef struct
 157   {
 158     /* Tree being iterated over. */
 159     L__(avl) *tree_;
 160
 161     /* Records a path into the tree.  If bit n is true, indicates
 162     ** take greater branch from the nth node in the path, otherwise
 163     ** take the less branch.  bit 0 gives branch from root, and
 164     ** so on. */
 165     L__BIT_ARR_DEFN(branch)
 166
 167     /* Zero-based depth of path into tree. */
 168     unsigned depth;
 169
 170     /* Handles of nodes in path from root to current node (returned by *). */
 171     AVL_HANDLE path_h[(AVL_MAX_DEPTH) - 1];
 172   }
 173 L__(iter);
 174
 175 /* Iterator function prototypes. */
 176
 177 L__SC void L__(start_iter)(
 178   L__(avl) *tree, L__(iter) *iter, AVL_KEY k, avl_search_type st);
 179
 180 L__SC void L__(start_iter_least)(L__(avl) *tree, L__(iter) *iter);
 181
 182 L__SC void L__(start_iter_greatest)(L__(avl) *tree, L__(iter) *iter);
 183
 184 L__SC AVL_HANDLE L__(get_iter)(L__(iter) *iter);
 185
 186 L__SC void L__(incr_iter)(L__(iter) *iter);
 187
 188 L__SC void L__(decr_iter)(L__(iter) *iter);
 189
 190 L__SC void L__(init_iter)(L__(iter) *iter);
 191
 192 #define AVL_IMPL_INIT                   1
 193 #define AVL_IMPL_IS_EMPTY               (1 << 1)
 194 #define AVL_IMPL_INSERT                 (1 << 2)
 195 #define AVL_IMPL_SEARCH                 (1 << 3)
 196 #define AVL_IMPL_SEARCH_LEAST           (1 << 4)
 197 #define AVL_IMPL_SEARCH_GREATEST        (1 << 5)
 198 #define AVL_IMPL_REMOVE                 (1 << 6)
 199 #define AVL_IMPL_BUILD                  (1 << 7)
 200 #define AVL_IMPL_START_ITER             (1 << 8)
 201 #define AVL_IMPL_START_ITER_LEAST       (1 << 9)
 202 #define AVL_IMPL_START_ITER_GREATEST    (1 << 10)
 203 #define AVL_IMPL_GET_ITER               (1 << 11)
 204 #define AVL_IMPL_INCR_ITER              (1 << 12)
 205 #define AVL_IMPL_DECR_ITER              (1 << 13)
 206 #define AVL_IMPL_INIT_ITER              (1 << 14)
 207 #define AVL_IMPL_SUBST                  (1 << 15)
 208
 209 #define AVL_IMPL_ALL                    (~0)
 210
 211 #undef L__
 212 #undef L__EST_LONG_BIT
 213 #undef L__SIZE
 214 #undef L__SC
 215 #undef L__LONG_BIT
 216 #undef L__BIT_ARR_DEFN