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 228