1 files changed, 226 insertions, 0 deletions
diff --git a/vpx_mem/memory_manager/include/cavl_if.h b/vpx_mem/memory_manager/include/cavl_if.h
new file mode 100644
index 000000000..e2733ef2f
--- /dev/null
+++ b/vpx_mem/memory_manager/include/cavl_if.h
@@ -0,0 +1,226 @@
+/*
+ *  Copyright (c) 2010 The VP8 project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license and patent
+ *  grant that can be found in the LICENSE file in the root of the source
+ *  tree. 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