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 #ifndef VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IF_H_ 12 #define VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IF_H_ 13 14 /* Abstract AVL Tree Generic C Package. 15 ** Interface generation header file. 16 ** 17 ** This code is in the public domain. See cavl_tree.html for interface 18 ** documentation. 19 ** 20 ** Version: 1.5 Author: Walt Karas 21 */ 22 23 /* This header contains the definition of CHAR_BIT (number of bits in a 24 ** char). */ 25 #include <limits.h> 26 27 #undef L_ 28 #undef L_EST_LONG_BIT 29 #undef L_SIZE 30 #undef L_SC 31 #undef L_LONG_BIT 32 #undef L_BIT_ARR_DEFN 33 34 #ifndef AVL_SEARCH_TYPE_DEFINED_ 35 #define AVL_SEARCH_TYPE_DEFINED_ 36 37 typedef enum { 38 AVL_EQUAL = 1, 39 AVL_LESS = 2, 40 AVL_GREATER = 4, 41 AVL_LESS_EQUAL = AVL_EQUAL | AVL_LESS, 42 AVL_GREATER_EQUAL = AVL_EQUAL | AVL_GREATER 43 } 44 avl_search_type; 45 46 #endif 47 48 #ifdef AVL_UNIQUE 49 50 #define L_ AVL_UNIQUE 51 52 #else 53 54 #define L_(X) X 55 56 #endif 57 58 /* Determine storage class for function prototypes. */ 59 #ifdef AVL_PRIVATE 60 61 #define L_SC static 62 63 #else 64 65 #define L_SC extern 66 67 #endif 68 69 #ifdef AVL_SIZE 70 71 #define L_SIZE AVL_SIZE 72 73 #else 74 75 #define L_SIZE unsigned long 76 77 #endif 78 79 typedef struct { 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 /* Tree being iterated over. */ 169 L_(avl) *tree_; 170 171 /* Records a path into the tree. If bit n is true, indicates 172 ** take greater branch from the nth node in the path, otherwise 173 ** take the less branch. bit 0 gives branch from root, and 174 ** so on. */ 175 L_BIT_ARR_DEFN(branch) 176 177 /* Zero-based depth of path into tree. */ 178 unsigned depth; 179 180 /* Handles of nodes in path from root to current node (returned by *). */ 181 AVL_HANDLE path_h[(AVL_MAX_DEPTH) - 1]; 182 } 183 L_(iter); 184 185 /* Iterator function prototypes. */ 186 187 L_SC void L_(start_iter)( 188 L_(avl) *tree, L_(iter) *iter, AVL_KEY k, avl_search_type st); 189 190 L_SC void L_(start_iter_least)(L_(avl) *tree, L_(iter) *iter); 191 192 L_SC void L_(start_iter_greatest)(L_(avl) *tree, L_(iter) *iter); 193 194 L_SC AVL_HANDLE L_(get_iter)(L_(iter) *iter); 195 196 L_SC void L_(incr_iter)(L_(iter) *iter); 197 198 L_SC void L_(decr_iter)(L_(iter) *iter); 199 200 L_SC void L_(init_iter)(L_(iter) *iter); 201 202 #define AVL_IMPL_INIT 1 203 #define AVL_IMPL_IS_EMPTY (1 << 1) 204 #define AVL_IMPL_INSERT (1 << 2) 205 #define AVL_IMPL_SEARCH (1 << 3) 206 #define AVL_IMPL_SEARCH_LEAST (1 << 4) 207 #define AVL_IMPL_SEARCH_GREATEST (1 << 5) 208 #define AVL_IMPL_REMOVE (1 << 6) 209 #define AVL_IMPL_BUILD (1 << 7) 210 #define AVL_IMPL_START_ITER (1 << 8) 211 #define AVL_IMPL_START_ITER_LEAST (1 << 9) 212 #define AVL_IMPL_START_ITER_GREATEST (1 << 10) 213 #define AVL_IMPL_GET_ITER (1 << 11) 214 #define AVL_IMPL_INCR_ITER (1 << 12) 215 #define AVL_IMPL_DECR_ITER (1 << 13) 216 #define AVL_IMPL_INIT_ITER (1 << 14) 217 #define AVL_IMPL_SUBST (1 << 15) 218 219 #define AVL_IMPL_ALL (~0) 220 221 #undef L_ 222 #undef L_EST_LONG_BIT 223 #undef L_SIZE 224 #undef L_SC 225 #undef L_LONG_BIT 226 #undef L_BIT_ARR_DEFN 227 228 #endif // VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IF_H_ 229