This source file includes following definitions.
- cmp_fn
- memfry
- walk_action
- walk_tree
- mangle_tree
- main
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 #include <config.h>
19
20 #include <search.h>
21
22 #include "signature.h"
23 SIGNATURE_CHECK (tdelete, void *, (void const *, void **,
24 int (*) (void const *, void const *)));
25 SIGNATURE_CHECK (tfind, void *, (void const *, void * const *,
26 int (*) (void const *, void const *)));
27 SIGNATURE_CHECK (tsearch, void *, (void const *, void **,
28 int (*) (void const *, void const *)));
29 SIGNATURE_CHECK (twalk, void, (void const *,
30 void (*) (void const *, VISIT, int)));
31
32 #include <stdint.h>
33 #include <stdio.h>
34 #include <stdlib.h>
35 #include <string.h>
36
37 #include "macros.h"
38
39 #define SEED 0
40 #if HAVE_TSEARCH
41
42 # define BALANCED 0
43 #else
44
45 # define BALANCED 1
46 #endif
47 #define PASSES 100
48
49 #if BALANCED
50 #include <math.h>
51 #define SIZE 1000
52 #else
53 #define SIZE 100
54 #endif
55
56 #undef random
57 #define random() (int) ((unsigned int) rand () >> 3)
58
59 enum order
60 {
61 ascending,
62 descending,
63 randomorder
64 };
65
66 enum action
67 {
68 build,
69 build_and_del,
70 delete,
71 find
72 };
73
74
75 static int error = 0;
76
77
78 static int x[SIZE];
79
80
81
82 static int y[SIZE];
83
84
85 static int z[SIZE];
86
87
88
89 static int depths[SIZE];
90
91
92 static int max_depth;
93
94
95 static int
96 cmp_fn (const void *a, const void *b)
97 {
98 return *(const int *) a - *(const int *) b;
99 }
100
101
102 static void
103 memfry (int *string)
104 {
105 int i;
106
107 for (i = 0; i < SIZE; ++i)
108 {
109 int32_t j;
110 int c;
111
112 j = random () % SIZE;
113
114 c = string[i];
115 string[i] = string[j];
116 string[j] = c;
117 }
118 }
119
120 static void
121 walk_action (const void *nodep, const VISIT which, const int depth)
122 {
123 int key = **(int **) nodep;
124
125 if (depth > max_depth)
126 max_depth = depth;
127 if (which == leaf || which == preorder)
128 {
129 ++z[key];
130 depths[key] = depth;
131 }
132 else
133 {
134 if (depths[key] != depth)
135 {
136 fputs ("Depth for one element is not constant during tree walk.\n",
137 stdout);
138 }
139 }
140 }
141
142 static void
143 walk_tree (void *root, int expected_count)
144 {
145 int i;
146
147 memset (z, 0, sizeof z);
148 max_depth = 0;
149
150 twalk (root, walk_action);
151 for (i = 0; i < expected_count; ++i)
152 if (z[i] != 1)
153 {
154 fputs ("Node was not visited.\n", stdout);
155 error = 1;
156 }
157
158 #if BALANCED
159 if (max_depth > log (expected_count) * 2 + 2)
160 #else
161 if (max_depth > expected_count)
162 #endif
163 {
164 fputs ("Depth too large during tree walk.\n", stdout);
165 error = 1;
166 }
167 }
168
169
170 static void
171 mangle_tree (enum order how, enum action what, void **root, int lag)
172 {
173 int i;
174
175 if (how == randomorder)
176 {
177 for (i = 0; i < SIZE; ++i)
178 y[i] = i;
179 memfry (y);
180 }
181
182 for (i = 0; i < SIZE + lag; ++i)
183 {
184 void *elem;
185 int j, k;
186
187 switch (how)
188 {
189 case randomorder:
190 if (i >= lag)
191 k = y[i - lag];
192 else
193
194 k = y[(SIZE - i - 1 + lag) % SIZE];
195 j = y[i % SIZE];
196 break;
197
198 case ascending:
199 k = i - lag;
200 j = i;
201 break;
202
203 case descending:
204 k = SIZE - i - 1 + lag;
205 j = SIZE - i - 1;
206 break;
207
208 default:
209
210
211 abort ();
212 }
213
214 switch (what)
215 {
216 case build_and_del:
217 case build:
218 if (i < SIZE)
219 {
220 if (tfind (x + j, (void *const *) root, cmp_fn) != NULL)
221 {
222 fputs ("Found element which is not in tree yet.\n", stdout);
223 error = 1;
224 }
225 elem = tsearch (x + j, root, cmp_fn);
226 if (elem == NULL
227 || tfind (x + j, (void *const *) root, cmp_fn) == NULL)
228 {
229 fputs ("Couldn't find element after it was added.\n",
230 stdout);
231 error = 1;
232 }
233 }
234
235 if (what == build || i < lag)
236 break;
237
238 j = k;
239 FALLTHROUGH;
240
241 case delete:
242 elem = tfind (x + j, (void *const *) root, cmp_fn);
243 if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
244 {
245 fputs ("Error deleting element.\n", stdout);
246 error = 1;
247 }
248 break;
249
250 case find:
251 if (tfind (x + j, (void *const *) root, cmp_fn) == NULL)
252 {
253 fputs ("Couldn't find element after it was added.\n", stdout);
254 error = 1;
255 }
256 break;
257
258 }
259 }
260 }
261
262
263 int
264 main (int argc, char **argv)
265 {
266 int total_error = 0;
267 void *root = NULL;
268 int i, j;
269
270 #if HAVE_INITSTATE
271 static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
272
273 initstate (SEED, state, 8);
274 #endif
275
276 for (i = 0; i < SIZE; ++i)
277 x[i] = i;
278
279
280
281 fputs ("Series I\n", stdout);
282 for (i = 0; i < PASSES; ++i)
283 {
284 fprintf (stdout, "Pass %d... ", i + 1);
285 fflush (stdout);
286 error = 0;
287
288 mangle_tree (ascending, build, &root, 0);
289 mangle_tree (ascending, find, &root, 0);
290 mangle_tree (descending, find, &root, 0);
291 mangle_tree (randomorder, find, &root, 0);
292 walk_tree (root, SIZE);
293 mangle_tree (ascending, delete, &root, 0);
294
295 mangle_tree (ascending, build, &root, 0);
296 walk_tree (root, SIZE);
297 mangle_tree (descending, delete, &root, 0);
298
299 mangle_tree (ascending, build, &root, 0);
300 walk_tree (root, SIZE);
301 mangle_tree (randomorder, delete, &root, 0);
302
303 mangle_tree (descending, build, &root, 0);
304 mangle_tree (ascending, find, &root, 0);
305 mangle_tree (descending, find, &root, 0);
306 mangle_tree (randomorder, find, &root, 0);
307 walk_tree (root, SIZE);
308 mangle_tree (descending, delete, &root, 0);
309
310 mangle_tree (descending, build, &root, 0);
311 walk_tree (root, SIZE);
312 mangle_tree (descending, delete, &root, 0);
313
314 mangle_tree (descending, build, &root, 0);
315 walk_tree (root, SIZE);
316 mangle_tree (randomorder, delete, &root, 0);
317
318 mangle_tree (randomorder, build, &root, 0);
319 mangle_tree (ascending, find, &root, 0);
320 mangle_tree (descending, find, &root, 0);
321 mangle_tree (randomorder, find, &root, 0);
322 walk_tree (root, SIZE);
323 mangle_tree (randomorder, delete, &root, 0);
324
325 for (j = 1; j < SIZE; j *= 2)
326 {
327 mangle_tree (randomorder, build_and_del, &root, j);
328 }
329
330 fputs (error ? " failed!\n" : " ok.\n", stdout);
331 total_error |= error;
332 }
333
334 fputs ("Series II\n", stdout);
335 for (i = 1; i < SIZE; i *= 2)
336 {
337 fprintf (stdout, "For size %d... ", i);
338 fflush (stdout);
339 error = 0;
340
341 mangle_tree (ascending, build_and_del, &root, i);
342 mangle_tree (descending, build_and_del, &root, i);
343 mangle_tree (ascending, build_and_del, &root, i);
344 mangle_tree (descending, build_and_del, &root, i);
345 mangle_tree (ascending, build_and_del, &root, i);
346 mangle_tree (descending, build_and_del, &root, i);
347 mangle_tree (ascending, build_and_del, &root, i);
348 mangle_tree (descending, build_and_del, &root, i);
349
350 fputs (error ? " failed!\n" : " ok.\n", stdout);
351 total_error |= error;
352 }
353
354 return total_error;
355 }