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