1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
|
/*
* Copyright (c) 2010 The VP8 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
|
