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 219