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 37typedef 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} 44avl_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 79typedef struct { 80#ifdef AVL_INSIDE_STRUCT 81 82 AVL_INSIDE_STRUCT 83 84#endif 85 86 AVL_HANDLE root; 87} 88L_(avl); 89 90/* Function prototypes. */ 91 92L_SC void L_(init)(L_(avl) *tree); 93 94L_SC int L_(is_empty)(L_(avl) *tree); 95 96L_SC AVL_HANDLE L_(insert)(L_(avl) *tree, AVL_HANDLE h); 97 98L_SC AVL_HANDLE L_(search)(L_(avl) *tree, AVL_KEY k, avl_search_type st); 99 100L_SC AVL_HANDLE L_(search_least)(L_(avl) *tree); 101 102L_SC AVL_HANDLE L_(search_greatest)(L_(avl) *tree); 103 104L_SC AVL_HANDLE L_(remove)(L_(avl) *tree, AVL_KEY k); 105 106L_SC AVL_HANDLE L_(subst)(L_(avl) *tree, AVL_HANDLE new_node); 107 108#ifdef AVL_BUILD_ITER_TYPE 109 110L_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. */ 167typedef 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} 183L_(iter); 184 185/* Iterator function prototypes. */ 186 187L_SC void L_(start_iter)( 188 L_(avl) *tree, L_(iter) *iter, AVL_KEY k, avl_search_type st); 189 190L_SC void L_(start_iter_least)(L_(avl) *tree, L_(iter) *iter); 191 192L_SC void L_(start_iter_greatest)(L_(avl) *tree, L_(iter) *iter); 193 194L_SC AVL_HANDLE L_(get_iter)(L_(iter) *iter); 195 196L_SC void L_(incr_iter)(L_(iter) *iter); 197 198L_SC void L_(decr_iter)(L_(iter) *iter); 199 200L_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