ref: 86c36a504dd7834e934707b86aa81ceb6384154c
dir: /vpx_mem/memory_manager/include/cavl_if.h/
/*
* 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.
*/
#ifndef VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IF_H_
#define VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IF_H_
/* 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
#endif // VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IF_H_