1 /* Test program for tsearch et al.
2 Copyright (C) 1997-2023 Free Software Foundation, Inc.
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
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.
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
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, see
17 <https://www.gnu.org/licenses/>. */
18
19 #ifndef _GNU_SOURCE
20 # define _GNU_SOURCE 1
21 #endif
22
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <search.h>
27 #include <tst-stack-align.h>
28 #include <support/check.h>
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
76 static int stack_align_check[2];
77
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
92 /* Compare two keys. */
93 static int
94 cmp_fn (const void *a, const void *b)
95 {
96 if (!stack_align_check[0])
97 stack_align_check[0] = TEST_STACK_ALIGN () ? -1 : 1;
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
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
160 static void
161 walk_action (const void *nodep, const VISIT which, const int depth)
162 {
163 int key = **(int **) nodep;
164
165 walk_trace_add (&walk_trace,
166 (struct walk_trace_element) { nodep, which, depth });
167
168 if (!stack_align_check[1])
169 stack_align_check[1] = TEST_STACK_ALIGN () ? -1 : 1;
170
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",
183 stdout);
184 }
185 }
186 }
187
188 static void
189 walk_tree_with (void *root, int expected_count,
190 void (*walk) (const void *,
191 void (*) (const void *, VISIT, int)))
192 {
193 int i;
194
195 memset (z, 0, sizeof z);
196 max_depth = 0;
197
198 walk (root, walk_action);
199 for (i = 0; i < expected_count; ++i)
200 if (z[i] != 1)
201 {
202 fputs ("Node was not visited.\n", stdout);
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 {
212 fputs ("Depth too large during tree walk.\n", stdout);
213 error = 1;
214 }
215 }
216
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);
226 TEST_VERIFY_EXIT (first_list != NULL);
227
228 walk_tree_with (root, expected_count, twalk_with_twalk_r);
229 TEST_VERIFY (!walk_trace_has_failed (&walk_trace));
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
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
268 /* Ensure that the array index is within bounds. */
269 k = y[(SIZE - i - 1 + lag) % SIZE];
270 j = y[i % SIZE];
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 {
295 if (tfind (x + j, (void *const *) root, cmp_fn) != NULL)
296 {
297 fputs ("Found element which is not in tree yet.\n", stdout);
298 error = 1;
299 }
300 elem = tsearch (x + j, root, cmp_fn);
301 if (elem == 0
302 || tfind (x + j, (void *const *) root, cmp_fn) == NULL)
303 {
304 fputs ("Couldn't find element after it was added.\n",
305 stdout);
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:
317 elem = tfind (x + j, (void *const *) root, cmp_fn);
318 if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
319 {
320 fputs ("Error deleting element.\n", stdout);
321 error = 1;
322 }
323 break;
324
325 case find:
326 if (tfind (x + j, (void *const *) root, cmp_fn) == NULL)
327 {
328 fputs ("Couldn't find element after it was added.\n", stdout);
329 error = 1;
330 }
331 break;
332
333 }
334 }
335 }
336
337
338 static int
339 do_test (void)
340 {
341 int total_error = 0;
342 static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
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. */
353 fputs ("Series I\n", stdout);
354 for (i = 0; i < PASSES; ++i)
355 {
356 fprintf (stdout, "Pass %d... ", i + 1);
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
402 fputs (error ? " failed!\n" : " ok.\n", stdout);
403 total_error |= error;
404 }
405
406 fputs ("Series II\n", stdout);
407 for (i = 1; i < SIZE; i *= 2)
408 {
409 fprintf (stdout, "For size %d... ", i);
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
422 fputs (error ? " failed!\n" : " ok.\n", stdout);
423 total_error |= error;
424 }
425
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
438 return total_error;
439 }
440
441 #define TEST_FUNCTION do_test ()
442 #include "../test-skeleton.c"