vpx_mem/memory_manager/include/cavl_if.h

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