minix/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__(search_root)(L__(avl) *tree);
  94
  95 L__SC AVL_HANDLE L__(remove)(L__(avl) *tree, AVL_KEY k);
  96
  97 L__SC AVL_HANDLE L__(subst)(L__(avl) *tree, AVL_HANDLE new_node);
  98
  99 #ifdef AVL_BUILD_ITER_TYPE
 100
 101 L__SC int L__(build)(
 102   L__(avl) *tree, AVL_BUILD_ITER_TYPE p, L__SIZE num_nodes);
 103
 104 #endif
 105
 106 /* ANSI C/ISO C++ require that a long have at least 32 bits.  Set
 107 ** L__EST_LONG_BIT to be the greatest multiple of 8 in the range
 108 ** 32 - 64 (inclusive) that is less than or equal to the number of
 109 ** bits in a long.
 110 */
 111
 112 #if (((LONG_MAX >> 31) >> 7) == 0)
 113
 114 #define L__EST_LONG_BIT 32
 115
 116 #elif (((LONG_MAX >> 31) >> 15) == 0)
 117
 118 #define L__EST_LONG_BIT 40
 119
 120 #elif (((LONG_MAX >> 31) >> 23) == 0)
 121
 122 #define L__EST_LONG_BIT 48
 123
 124 #elif (((LONG_MAX >> 31) >> 31) == 0)
 125
 126 #define L__EST_LONG_BIT 56
 127
 128 #else
 129
 130 #define L__EST_LONG_BIT 64
 131
 132 #endif
 133
 134 /* Number of bits in a long. */
 135 #define L__LONG_BIT (sizeof(long) * CHAR_BIT)
 136
 137 /* The macro L__BIT_ARR_DEFN defines a bit array whose index is a (0-based)
 138 ** node depth.  The definition depends on whether the maximum depth is more
 139 ** or less than the number of bits in a single long.
 140 */
 141
 142 #if ((AVL_MAX_DEPTH) > L__EST_LONG_BIT)
 143
 144 /* Maximum depth may be more than number of bits in a long. */
 145
 146 #define L__BIT_ARR_DEFN(NAME) \
 147   unsigned long NAME[((AVL_MAX_DEPTH) + L__LONG_BIT - 1) / L__LONG_BIT];
 148
 149 #else
 150
 151 /* Maximum depth is definitely less than number of bits in a long. */
 152
 153 #define L__BIT_ARR_DEFN(NAME) unsigned long NAME;
 154
 155 #endif
 156
 157 /* Iterator structure. */
 158 typedef struct
 159   {
 160     /* Tree being iterated over. */
 161     L__(avl) *tree_;
 162
 163     /* Records a path into the tree.  If bit n is true, indicates
 164     ** take greater branch from the nth node in the path, otherwise
 165     ** take the less branch.  bit 0 gives branch from root, and
 166     ** so on. */
 167     L__BIT_ARR_DEFN(branch)
 168
 169     /* Zero-based depth of path into tree. */
 170     int depth;
 171
 172     /* Handles of nodes in path from root to current node (returned by *). */
 173     AVL_HANDLE path_h[(AVL_MAX_DEPTH) - 1];
 174   }
 175 L__(iter);
 176
 177 /* Iterator function prototypes. */
 178
 179 L__SC void L__(start_iter)(
 180   L__(avl) *tree, L__(iter) *iter, AVL_KEY k, avl_search_type st);
 181
 182 L__SC void L__(start_iter_least)(L__(avl) *tree, L__(iter) *iter);
 183
 184 L__SC void L__(start_iter_greatest)(L__(avl) *tree, L__(iter) *iter);
 185
 186 L__SC AVL_HANDLE L__(get_iter)(L__(iter) *iter);
 187
 188 L__SC void L__(incr_iter)(L__(iter) *iter);
 189
 190 L__SC void L__(decr_iter)(L__(iter) *iter);
 191
 192 L__SC void L__(init_iter)(L__(iter) *iter);
 193
 194 #define AVL_IMPL_INIT                   1
 195 #define AVL_IMPL_IS_EMPTY               (1 << 1)
 196 #define AVL_IMPL_INSERT                 (1 << 2)
 197 #define AVL_IMPL_SEARCH                 (1 << 3)
 198 #define AVL_IMPL_SEARCH_LEAST           (1 << 4)
 199 #define AVL_IMPL_SEARCH_GREATEST        (1 << 5)
 200 #define AVL_IMPL_REMOVE                 (1 << 6)
 201 #define AVL_IMPL_BUILD                  (1 << 7)
 202 #define AVL_IMPL_START_ITER             (1 << 8)
 203 #define AVL_IMPL_START_ITER_LEAST       (1 << 9)
 204 #define AVL_IMPL_START_ITER_GREATEST    (1 << 10)
 205 #define AVL_IMPL_GET_ITER               (1 << 11)
 206 #define AVL_IMPL_INCR_ITER              (1 << 12)
 207 #define AVL_IMPL_DECR_ITER              (1 << 13)
 208 #define AVL_IMPL_INIT_ITER              (1 << 14)
 209 #define AVL_IMPL_SUBST                  (1 << 15)
 210
 211 #define AVL_IMPL_ALL                    (~0)
 212
 213 #undef L__
 214 #undef L__EST_LONG_BIT
 215 #undef L__SIZE
 216 #undef L__SC
 217 #undef L__LONG_BIT
 218 #undef L__BIT_ARR_DEFN