| /* | |
| * Copyright (c) 2010 The WebM project authors. All Rights Reserved. | |
| * | |
| * Use of this source code is governed by a BSD-style license | |
| * that can be found in the LICENSE file in the root of the source | |
| * tree. An additional intellectual property rights grant can be found | |
| * in the file PATENTS. All contributing project authors may | |
| * be found in the AUTHORS file in the root of the source tree. | |
| */ | |
| /* Abstract AVL Tree Generic C Package. | |
| ** Interface generation header file. | |
| ** | |
| ** This code is in the public domain. See cavl_tree.html for interface | |
| ** documentation. | |
| ** | |
| ** Version: 1.5 Author: Walt Karas | |
| */ | |
| /* This header contains the definition of CHAR_BIT (number of bits in a | |
| ** char). */ | |
| #include <limits.h> | |
| #undef L_ | |
| #undef L_EST_LONG_BIT | |
| #undef L_SIZE | |
| #undef L_SC | |
| #undef L_LONG_BIT | |
| #undef L_BIT_ARR_DEFN | |
| #ifndef AVL_SEARCH_TYPE_DEFINED_ | |
| #define AVL_SEARCH_TYPE_DEFINED_ | |
| typedef enum | |
| { | |
| AVL_EQUAL = 1, | |
| AVL_LESS = 2, | |
| AVL_GREATER = 4, | |
| AVL_LESS_EQUAL = AVL_EQUAL | AVL_LESS, | |
| AVL_GREATER_EQUAL = AVL_EQUAL | AVL_GREATER | |
| } | |
| avl_search_type; | |
| #endif | |
| #ifdef AVL_UNIQUE | |
| #define L_ AVL_UNIQUE | |
| #else | |
| #define L_(X) X | |
| #endif | |
| /* Determine storage class for function prototypes. */ | |
| #ifdef AVL_PRIVATE | |
| #define L_SC static | |
| #else | |
| #define L_SC extern | |
| #endif | |
| #ifdef AVL_SIZE | |
| #define L_SIZE AVL_SIZE | |
| #else | |
| #define L_SIZE unsigned long | |
| #endif | |
| typedef struct | |
| { | |
| #ifdef AVL_INSIDE_STRUCT | |
| AVL_INSIDE_STRUCT | |
| #endif | |
| AVL_HANDLE root; | |
| } | |
| L_(avl); | |
| /* Function prototypes. */ | |
| L_SC void L_(init)(L_(avl) *tree); | |
| L_SC int L_(is_empty)(L_(avl) *tree); | |
| L_SC AVL_HANDLE L_(insert)(L_(avl) *tree, AVL_HANDLE h); | |
| L_SC AVL_HANDLE L_(search)(L_(avl) *tree, AVL_KEY k, avl_search_type st); | |
| L_SC AVL_HANDLE L_(search_least)(L_(avl) *tree); | |
| L_SC AVL_HANDLE L_(search_greatest)(L_(avl) *tree); | |
| L_SC AVL_HANDLE L_(remove)(L_(avl) *tree, AVL_KEY k); | |
| L_SC AVL_HANDLE L_(subst)(L_(avl) *tree, AVL_HANDLE new_node); | |
| #ifdef AVL_BUILD_ITER_TYPE | |
| L_SC int L_(build)( | |
| L_(avl) *tree, AVL_BUILD_ITER_TYPE p, L_SIZE num_nodes); | |
| #endif | |
| /* ANSI C/ISO C++ require that a long have at least 32 bits. Set | |
| ** L_EST_LONG_BIT to be the greatest multiple of 8 in the range | |
| ** 32 - 64 (inclusive) that is less than or equal to the number of | |
| ** bits in a long. | |
| */ | |
| #if (((LONG_MAX >> 31) >> 7) == 0) | |
| #define L_EST_LONG_BIT 32 | |
| #elif (((LONG_MAX >> 31) >> 15) == 0) | |
| #define L_EST_LONG_BIT 40 | |
| #elif (((LONG_MAX >> 31) >> 23) == 0) | |
| #define L_EST_LONG_BIT 48 | |
| #elif (((LONG_MAX >> 31) >> 31) == 0) | |
| #define L_EST_LONG_BIT 56 | |
| #else | |
| #define L_EST_LONG_BIT 64 | |
| #endif | |
| /* Number of bits in a long. */ | |
| #define L_LONG_BIT (sizeof(long) * CHAR_BIT) | |
| /* The macro L_BIT_ARR_DEFN defines a bit array whose index is a (0-based) | |
| ** node depth. The definition depends on whether the maximum depth is more | |
| ** or less than the number of bits in a single long. | |
| */ | |
| #if ((AVL_MAX_DEPTH) > L_EST_LONG_BIT) | |
| /* Maximum depth may be more than number of bits in a long. */ | |
| #define L_BIT_ARR_DEFN(NAME) \ | |
| unsigned long NAME[((AVL_MAX_DEPTH) + L_LONG_BIT - 1) / L_LONG_BIT]; | |
| #else | |
| /* Maximum depth is definitely less than number of bits in a long. */ | |
| #define L_BIT_ARR_DEFN(NAME) unsigned long NAME; | |
| #endif | |
| /* Iterator structure. */ | |
| typedef struct | |
| { | |
| /* Tree being iterated over. */ | |
| L_(avl) *tree_; | |
| /* Records a path into the tree. If bit n is true, indicates | |
| ** take greater branch from the nth node in the path, otherwise | |
| ** take the less branch. bit 0 gives branch from root, and | |
| ** so on. */ | |
| L_BIT_ARR_DEFN(branch) | |
| /* Zero-based depth of path into tree. */ | |
| unsigned depth; | |
| /* Handles of nodes in path from root to current node (returned by *). */ | |
| AVL_HANDLE path_h[(AVL_MAX_DEPTH) - 1]; | |
| } | |
| L_(iter); | |
| /* Iterator function prototypes. */ | |
| L_SC void L_(start_iter)( | |
| L_(avl) *tree, L_(iter) *iter, AVL_KEY k, avl_search_type st); | |
| L_SC void L_(start_iter_least)(L_(avl) *tree, L_(iter) *iter); | |
| L_SC void L_(start_iter_greatest)(L_(avl) *tree, L_(iter) *iter); | |
| L_SC AVL_HANDLE L_(get_iter)(L_(iter) *iter); | |
| L_SC void L_(incr_iter)(L_(iter) *iter); | |
| L_SC void L_(decr_iter)(L_(iter) *iter); | |
| L_SC void L_(init_iter)(L_(iter) *iter); | |
| #define AVL_IMPL_INIT 1 | |
| #define AVL_IMPL_IS_EMPTY (1 << 1) | |
| #define AVL_IMPL_INSERT (1 << 2) | |
| #define AVL_IMPL_SEARCH (1 << 3) | |
| #define AVL_IMPL_SEARCH_LEAST (1 << 4) | |
| #define AVL_IMPL_SEARCH_GREATEST (1 << 5) | |
| #define AVL_IMPL_REMOVE (1 << 6) | |
| #define AVL_IMPL_BUILD (1 << 7) | |
| #define AVL_IMPL_START_ITER (1 << 8) | |
| #define AVL_IMPL_START_ITER_LEAST (1 << 9) | |
| #define AVL_IMPL_START_ITER_GREATEST (1 << 10) | |
| #define AVL_IMPL_GET_ITER (1 << 11) | |
| #define AVL_IMPL_INCR_ITER (1 << 12) | |
| #define AVL_IMPL_DECR_ITER (1 << 13) | |
| #define AVL_IMPL_INIT_ITER (1 << 14) | |
| #define AVL_IMPL_SUBST (1 << 15) | |
| #define AVL_IMPL_ALL (~0) | |
| #undef L_ | |
| #undef L_EST_LONG_BIT | |
| #undef L_SIZE | |
| #undef L_SC | |
| #undef L_LONG_BIT | |
| #undef L_BIT_ARR_DEFN |