]>
Commit | Line | Data |
---|---|---|
993b3242 | 1 | /* Test program for tsearch et al. |
2b778ceb | 2 | Copyright (C) 1997-2021 Free Software Foundation, Inc. |
993b3242 UD |
3 | This file is part of the GNU C Library. |
4 | ||
5 | The GNU C Library is free software; you can redistribute it and/or | |
41bdb6e2 AJ |
6 | modify it under the terms of the GNU Lesser General Public |
7 | License as published by the Free Software Foundation; either | |
8 | version 2.1 of the License, or (at your option) any later version. | |
993b3242 UD |
9 | |
10 | The GNU C Library is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
41bdb6e2 | 13 | Lesser General Public License for more details. |
993b3242 | 14 | |
41bdb6e2 | 15 | You should have received a copy of the GNU Lesser General Public |
59ba27a6 | 16 | License along with the GNU C Library; if not, see |
5a82c748 | 17 | <https://www.gnu.org/licenses/>. */ |
993b3242 | 18 | |
c131718c UD |
19 | #ifndef _GNU_SOURCE |
20 | # define _GNU_SOURCE 1 | |
21 | #endif | |
993b3242 UD |
22 | |
23 | #include <stdio.h> | |
24 | #include <stdlib.h> | |
c131718c | 25 | #include <string.h> |
993b3242 | 26 | #include <search.h> |
06f6ca90 | 27 | #include <tst-stack-align.h> |
7b807a35 | 28 | #include <support/check.h> |
993b3242 UD |
29 | |
30 | #define SEED 0 | |
31 | #define BALANCED 1 | |
32 | #define PASSES 100 | |
33 | ||
34 | #if BALANCED | |
35 | #include <math.h> | |
36 | #define SIZE 1000 | |
37 | #else | |
38 | #define SIZE 100 | |
39 | #endif | |
40 | ||
41 | enum order | |
42 | { | |
43 | ascending, | |
44 | descending, | |
45 | randomorder | |
46 | }; | |
47 | ||
48 | enum action | |
49 | { | |
50 | build, | |
51 | build_and_del, | |
52 | delete, | |
53 | find | |
54 | }; | |
55 | ||
56 | /* Set to 1 if a test is flunked. */ | |
57 | static int error = 0; | |
58 | ||
59 | /* The keys we add to the tree. */ | |
60 | static int x[SIZE]; | |
61 | ||
62 | /* Pointers into the key array, possibly permutated, to define an order | |
63 | for insertion/removal. */ | |
64 | static int y[SIZE]; | |
65 | ||
66 | /* Flags set for each element visited during a tree walk. */ | |
67 | static int z[SIZE]; | |
68 | ||
69 | /* Depths for all the elements, to check that the depth is constant for | |
70 | all three visits. */ | |
71 | static int depths[SIZE]; | |
72 | ||
73 | /* Maximum depth during a tree walk. */ | |
74 | static int max_depth; | |
75 | ||
06f6ca90 UD |
76 | static int stack_align_check[2]; |
77 | ||
7b807a35 FW |
78 | /* Used to compare walk traces between the two implementations. */ |
79 | struct walk_trace_element | |
80 | { | |
81 | const void *key; | |
82 | VISIT which; | |
83 | int depth; | |
84 | }; | |
85 | #define DYNARRAY_STRUCT walk_trace_list | |
86 | #define DYNARRAY_ELEMENT struct walk_trace_element | |
87 | #define DYNARRAY_PREFIX walk_trace_ | |
88 | #define DYNARRAY_INITIAL_SIZE 0 | |
89 | #include <malloc/dynarray-skeleton.c> | |
90 | static struct walk_trace_list walk_trace; | |
91 | ||
993b3242 UD |
92 | /* Compare two keys. */ |
93 | static int | |
94 | cmp_fn (const void *a, const void *b) | |
95 | { | |
06f6ca90 UD |
96 | if (!stack_align_check[0]) |
97 | stack_align_check[0] = TEST_STACK_ALIGN () ? -1 : 1; | |
993b3242 UD |
98 | return *(const int *) a - *(const int *) b; |
99 | } | |
100 | ||
101 | /* Permute an array of integers. */ | |
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 | ||
7b807a35 FW |
120 | struct twalk_with_twalk_r_closure |
121 | { | |
122 | void (*action) (const void *, VISIT, int); | |
123 | int depth; | |
124 | }; | |
125 | ||
126 | static void | |
127 | twalk_with_twalk_r_action (const void *nodep, VISIT which, void *closure0) | |
128 | { | |
129 | struct twalk_with_twalk_r_closure *closure = closure0; | |
130 | ||
131 | switch (which) | |
132 | { | |
133 | case leaf: | |
134 | closure->action (nodep, which, closure->depth); | |
135 | break; | |
136 | case preorder: | |
137 | closure->action (nodep, which, closure->depth); | |
138 | ++closure->depth; | |
139 | break; | |
140 | case postorder: | |
141 | /* The preorder action incremented the depth. */ | |
142 | closure->action (nodep, which, closure->depth - 1); | |
143 | break; | |
144 | case endorder: | |
145 | --closure->depth; | |
146 | closure->action (nodep, which, closure->depth); | |
147 | break; | |
148 | } | |
149 | } | |
150 | ||
151 | static void | |
152 | twalk_with_twalk_r (const void *root, | |
153 | void (*action) (const void *, VISIT, int)) | |
154 | { | |
155 | struct twalk_with_twalk_r_closure closure = { action, 0 }; | |
156 | twalk_r (root, twalk_with_twalk_r_action, &closure); | |
157 | TEST_COMPARE (closure.depth, 0); | |
158 | } | |
159 | ||
993b3242 UD |
160 | static void |
161 | walk_action (const void *nodep, const VISIT which, const int depth) | |
162 | { | |
163 | int key = **(int **) nodep; | |
164 | ||
7b807a35 FW |
165 | walk_trace_add (&walk_trace, |
166 | (struct walk_trace_element) { nodep, which, depth }); | |
167 | ||
06f6ca90 UD |
168 | if (!stack_align_check[1]) |
169 | stack_align_check[1] = TEST_STACK_ALIGN () ? -1 : 1; | |
170 | ||
993b3242 UD |
171 | if (depth > max_depth) |
172 | max_depth = depth; | |
173 | if (which == leaf || which == preorder) | |
174 | { | |
175 | ++z[key]; | |
176 | depths[key] = depth; | |
177 | } | |
178 | else | |
179 | { | |
180 | if (depths[key] != depth) | |
181 | { | |
182 | fputs ("Depth for one element is not constant during tree walk.\n", | |
5929563f | 183 | stdout); |
993b3242 UD |
184 | } |
185 | } | |
186 | } | |
187 | ||
188 | static void | |
7b807a35 FW |
189 | walk_tree_with (void *root, int expected_count, |
190 | void (*walk) (const void *, | |
191 | void (*) (const void *, VISIT, int))) | |
993b3242 UD |
192 | { |
193 | int i; | |
194 | ||
195 | memset (z, 0, sizeof z); | |
196 | max_depth = 0; | |
197 | ||
7b807a35 | 198 | walk (root, walk_action); |
993b3242 UD |
199 | for (i = 0; i < expected_count; ++i) |
200 | if (z[i] != 1) | |
201 | { | |
5929563f | 202 | fputs ("Node was not visited.\n", stdout); |
993b3242 UD |
203 | error = 1; |
204 | } | |
205 | ||
206 | #if BALANCED | |
207 | if (max_depth > log (expected_count) * 2 + 2) | |
208 | #else | |
209 | if (max_depth > expected_count) | |
210 | #endif | |
211 | { | |
5929563f | 212 | fputs ("Depth too large during tree walk.\n", stdout); |
993b3242 UD |
213 | error = 1; |
214 | } | |
215 | } | |
216 | ||
7b807a35 FW |
217 | static void |
218 | walk_tree (void *root, int expected_count) | |
219 | { | |
220 | walk_trace_clear (&walk_trace); | |
221 | walk_tree_with (root, expected_count, twalk); | |
222 | TEST_VERIFY (!walk_trace_has_failed (&walk_trace)); | |
223 | size_t first_list_size; | |
224 | struct walk_trace_element *first_list | |
225 | = walk_trace_finalize (&walk_trace, &first_list_size); | |
ac3da35d | 226 | TEST_VERIFY_EXIT (first_list != NULL); |
7b807a35 FW |
227 | |
228 | walk_tree_with (root, expected_count, twalk_with_twalk_r); | |
ac3da35d | 229 | TEST_VERIFY (!walk_trace_has_failed (&walk_trace)); |
7b807a35 FW |
230 | |
231 | /* Compare the two traces. */ | |
232 | TEST_COMPARE (first_list_size, walk_trace_size (&walk_trace)); | |
233 | for (size_t i = 0; i < first_list_size && i < walk_trace_size (&walk_trace); | |
234 | ++i) | |
235 | { | |
236 | TEST_VERIFY (first_list[i].key == walk_trace_at (&walk_trace, i)->key); | |
237 | TEST_COMPARE (first_list[i].which, walk_trace_at (&walk_trace, i)->which); | |
238 | TEST_COMPARE (first_list[i].depth, walk_trace_at (&walk_trace, i)->depth); | |
239 | } | |
240 | ||
241 | walk_trace_free (&walk_trace); | |
242 | } | |
243 | ||
993b3242 UD |
244 | /* Perform an operation on a tree. */ |
245 | static void | |
246 | mangle_tree (enum order how, enum action what, void **root, int lag) | |
247 | { | |
248 | int i; | |
249 | ||
250 | if (how == randomorder) | |
251 | { | |
252 | for (i = 0; i < SIZE; ++i) | |
253 | y[i] = i; | |
254 | memfry (y); | |
255 | } | |
256 | ||
257 | for (i = 0; i < SIZE + lag; ++i) | |
258 | { | |
259 | void *elem; | |
260 | int j, k; | |
261 | ||
262 | switch (how) | |
263 | { | |
264 | case randomorder: | |
265 | if (i >= lag) | |
266 | k = y[i - lag]; | |
267 | else | |
673c34e0 AJ |
268 | /* Ensure that the array index is within bounds. */ |
269 | k = y[(SIZE - i - 1 + lag) % SIZE]; | |
270 | j = y[i % SIZE]; | |
993b3242 UD |
271 | break; |
272 | ||
273 | case ascending: | |
274 | k = i - lag; | |
275 | j = i; | |
276 | break; | |
277 | ||
278 | case descending: | |
279 | k = SIZE - i - 1 + lag; | |
280 | j = SIZE - i - 1; | |
281 | break; | |
282 | ||
283 | default: | |
284 | /* This never should happen, but gcc isn't smart enough to | |
285 | recognize it. */ | |
286 | abort (); | |
287 | } | |
288 | ||
289 | switch (what) | |
290 | { | |
291 | case build_and_del: | |
292 | case build: | |
293 | if (i < SIZE) | |
294 | { | |
f671aeab | 295 | if (tfind (x + j, (void *const *) root, cmp_fn) != NULL) |
993b3242 | 296 | { |
5929563f | 297 | fputs ("Found element which is not in tree yet.\n", stdout); |
993b3242 UD |
298 | error = 1; |
299 | } | |
300 | elem = tsearch (x + j, root, cmp_fn); | |
301 | if (elem == 0 | |
f671aeab | 302 | || tfind (x + j, (void *const *) root, cmp_fn) == NULL) |
993b3242 UD |
303 | { |
304 | fputs ("Couldn't find element after it was added.\n", | |
5929563f | 305 | stdout); |
993b3242 UD |
306 | error = 1; |
307 | } | |
308 | } | |
309 | ||
310 | if (what == build || i < lag) | |
311 | break; | |
312 | ||
313 | j = k; | |
314 | /* fall through */ | |
315 | ||
316 | case delete: | |
f671aeab | 317 | elem = tfind (x + j, (void *const *) root, cmp_fn); |
993b3242 UD |
318 | if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL) |
319 | { | |
5929563f | 320 | fputs ("Error deleting element.\n", stdout); |
993b3242 UD |
321 | error = 1; |
322 | } | |
323 | break; | |
324 | ||
325 | case find: | |
f671aeab | 326 | if (tfind (x + j, (void *const *) root, cmp_fn) == NULL) |
993b3242 | 327 | { |
5929563f | 328 | fputs ("Couldn't find element after it was added.\n", stdout); |
993b3242 UD |
329 | error = 1; |
330 | } | |
331 | break; | |
332 | ||
333 | } | |
334 | } | |
335 | } | |
336 | ||
337 | ||
c1f41083 AS |
338 | static int |
339 | do_test (void) | |
993b3242 UD |
340 | { |
341 | int total_error = 0; | |
621d9092 | 342 | static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 }; |
993b3242 UD |
343 | void *root = NULL; |
344 | int i, j; | |
345 | ||
346 | initstate (SEED, state, 8); | |
347 | ||
348 | for (i = 0; i < SIZE; ++i) | |
349 | x[i] = i; | |
350 | ||
351 | /* Do this loop several times to get different permutations for the | |
352 | random case. */ | |
5929563f | 353 | fputs ("Series I\n", stdout); |
993b3242 UD |
354 | for (i = 0; i < PASSES; ++i) |
355 | { | |
5929563f | 356 | fprintf (stdout, "Pass %d... ", i + 1); |
993b3242 UD |
357 | fflush (stdout); |
358 | error = 0; | |
359 | ||
360 | mangle_tree (ascending, build, &root, 0); | |
361 | mangle_tree (ascending, find, &root, 0); | |
362 | mangle_tree (descending, find, &root, 0); | |
363 | mangle_tree (randomorder, find, &root, 0); | |
364 | walk_tree (root, SIZE); | |
365 | mangle_tree (ascending, delete, &root, 0); | |
366 | ||
367 | mangle_tree (ascending, build, &root, 0); | |
368 | walk_tree (root, SIZE); | |
369 | mangle_tree (descending, delete, &root, 0); | |
370 | ||
371 | mangle_tree (ascending, build, &root, 0); | |
372 | walk_tree (root, SIZE); | |
373 | mangle_tree (randomorder, delete, &root, 0); | |
374 | ||
375 | mangle_tree (descending, build, &root, 0); | |
376 | mangle_tree (ascending, find, &root, 0); | |
377 | mangle_tree (descending, find, &root, 0); | |
378 | mangle_tree (randomorder, find, &root, 0); | |
379 | walk_tree (root, SIZE); | |
380 | mangle_tree (descending, delete, &root, 0); | |
381 | ||
382 | mangle_tree (descending, build, &root, 0); | |
383 | walk_tree (root, SIZE); | |
384 | mangle_tree (descending, delete, &root, 0); | |
385 | ||
386 | mangle_tree (descending, build, &root, 0); | |
387 | walk_tree (root, SIZE); | |
388 | mangle_tree (randomorder, delete, &root, 0); | |
389 | ||
390 | mangle_tree (randomorder, build, &root, 0); | |
391 | mangle_tree (ascending, find, &root, 0); | |
392 | mangle_tree (descending, find, &root, 0); | |
393 | mangle_tree (randomorder, find, &root, 0); | |
394 | walk_tree (root, SIZE); | |
395 | mangle_tree (randomorder, delete, &root, 0); | |
396 | ||
397 | for (j = 1; j < SIZE; j *= 2) | |
398 | { | |
399 | mangle_tree (randomorder, build_and_del, &root, j); | |
400 | } | |
401 | ||
5929563f | 402 | fputs (error ? " failed!\n" : " ok.\n", stdout); |
993b3242 UD |
403 | total_error |= error; |
404 | } | |
405 | ||
5929563f | 406 | fputs ("Series II\n", stdout); |
993b3242 UD |
407 | for (i = 1; i < SIZE; i *= 2) |
408 | { | |
5929563f | 409 | fprintf (stdout, "For size %d... ", i); |
993b3242 UD |
410 | fflush (stdout); |
411 | error = 0; | |
412 | ||
413 | mangle_tree (ascending, build_and_del, &root, i); | |
414 | mangle_tree (descending, build_and_del, &root, i); | |
415 | mangle_tree (ascending, build_and_del, &root, i); | |
416 | mangle_tree (descending, build_and_del, &root, i); | |
417 | mangle_tree (ascending, build_and_del, &root, i); | |
418 | mangle_tree (descending, build_and_del, &root, i); | |
419 | mangle_tree (ascending, build_and_del, &root, i); | |
420 | mangle_tree (descending, build_and_del, &root, i); | |
421 | ||
5929563f | 422 | fputs (error ? " failed!\n" : " ok.\n", stdout); |
993b3242 UD |
423 | total_error |= error; |
424 | } | |
425 | ||
06f6ca90 UD |
426 | for (i = 0; i < 2; ++i) |
427 | if (stack_align_check[i] == 0) | |
428 | { | |
429 | printf ("stack alignment check %d not run\n", i); | |
430 | total_error |= 1; | |
431 | } | |
432 | else if (stack_align_check[i] != 1) | |
433 | { | |
434 | printf ("stack insufficiently aligned in check %d\n", i); | |
435 | total_error |= 1; | |
436 | } | |
437 | ||
993b3242 UD |
438 | return total_error; |
439 | } | |
c1f41083 AS |
440 | |
441 | #define TEST_FUNCTION do_test () | |
442 | #include "../test-skeleton.c" |