benchtests: Add arc4random benchtest
[glibc.git] / misc / tst-tsearch.c
blobe23d2689029affbbf151a5d78ae50e0a351b2d4f
1 /* Test program for tsearch et al.
2 Copyright (C) 1997-2022 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
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.
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.
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/>. */
19 #ifndef _GNU_SOURCE
20 # define _GNU_SOURCE 1
21 #endif
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>
30 #define SEED 0
31 #define BALANCED 1
32 #define PASSES 100
34 #if BALANCED
35 #include <math.h>
36 #define SIZE 1000
37 #else
38 #define SIZE 100
39 #endif
41 enum order
43 ascending,
44 descending,
45 randomorder
48 enum action
50 build,
51 build_and_del,
52 delete,
53 find
56 /* Set to 1 if a test is flunked. */
57 static int error = 0;
59 /* The keys we add to the tree. */
60 static int x[SIZE];
62 /* Pointers into the key array, possibly permutated, to define an order
63 for insertion/removal. */
64 static int y[SIZE];
66 /* Flags set for each element visited during a tree walk. */
67 static int z[SIZE];
69 /* Depths for all the elements, to check that the depth is constant for
70 all three visits. */
71 static int depths[SIZE];
73 /* Maximum depth during a tree walk. */
74 static int max_depth;
76 static int stack_align_check[2];
78 /* Used to compare walk traces between the two implementations. */
79 struct walk_trace_element
81 const void *key;
82 VISIT which;
83 int depth;
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;
92 /* Compare two keys. */
93 static int
94 cmp_fn (const void *a, const void *b)
96 if (!stack_align_check[0])
97 stack_align_check[0] = TEST_STACK_ALIGN () ? -1 : 1;
98 return *(const int *) a - *(const int *) b;
101 /* Permute an array of integers. */
102 static void
103 memfry (int *string)
105 int i;
107 for (i = 0; i < SIZE; ++i)
109 int32_t j;
110 int c;
112 j = random () % SIZE;
114 c = string[i];
115 string[i] = string[j];
116 string[j] = c;
120 struct twalk_with_twalk_r_closure
122 void (*action) (const void *, VISIT, int);
123 int depth;
126 static void
127 twalk_with_twalk_r_action (const void *nodep, VISIT which, void *closure0)
129 struct twalk_with_twalk_r_closure *closure = closure0;
131 switch (which)
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;
151 static void
152 twalk_with_twalk_r (const void *root,
153 void (*action) (const void *, VISIT, int))
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);
160 static void
161 walk_action (const void *nodep, const VISIT which, const int depth)
163 int key = **(int **) nodep;
165 walk_trace_add (&walk_trace,
166 (struct walk_trace_element) { nodep, which, depth });
168 if (!stack_align_check[1])
169 stack_align_check[1] = TEST_STACK_ALIGN () ? -1 : 1;
171 if (depth > max_depth)
172 max_depth = depth;
173 if (which == leaf || which == preorder)
175 ++z[key];
176 depths[key] = depth;
178 else
180 if (depths[key] != depth)
182 fputs ("Depth for one element is not constant during tree walk.\n",
183 stdout);
188 static void
189 walk_tree_with (void *root, int expected_count,
190 void (*walk) (const void *,
191 void (*) (const void *, VISIT, int)))
193 int i;
195 memset (z, 0, sizeof z);
196 max_depth = 0;
198 walk (root, walk_action);
199 for (i = 0; i < expected_count; ++i)
200 if (z[i] != 1)
202 fputs ("Node was not visited.\n", stdout);
203 error = 1;
206 #if BALANCED
207 if (max_depth > log (expected_count) * 2 + 2)
208 #else
209 if (max_depth > expected_count)
210 #endif
212 fputs ("Depth too large during tree walk.\n", stdout);
213 error = 1;
217 static void
218 walk_tree (void *root, int expected_count)
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);
228 walk_tree_with (root, expected_count, twalk_with_twalk_r);
229 TEST_VERIFY (!walk_trace_has_failed (&walk_trace));
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)
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);
241 walk_trace_free (&walk_trace);
244 /* Perform an operation on a tree. */
245 static void
246 mangle_tree (enum order how, enum action what, void **root, int lag)
248 int i;
250 if (how == randomorder)
252 for (i = 0; i < SIZE; ++i)
253 y[i] = i;
254 memfry (y);
257 for (i = 0; i < SIZE + lag; ++i)
259 void *elem;
260 int j, k;
262 switch (how)
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;
273 case ascending:
274 k = i - lag;
275 j = i;
276 break;
278 case descending:
279 k = SIZE - i - 1 + lag;
280 j = SIZE - i - 1;
281 break;
283 default:
284 /* This never should happen, but gcc isn't smart enough to
285 recognize it. */
286 abort ();
289 switch (what)
291 case build_and_del:
292 case build:
293 if (i < SIZE)
295 if (tfind (x + j, (void *const *) root, cmp_fn) != NULL)
297 fputs ("Found element which is not in tree yet.\n", stdout);
298 error = 1;
300 elem = tsearch (x + j, root, cmp_fn);
301 if (elem == 0
302 || tfind (x + j, (void *const *) root, cmp_fn) == NULL)
304 fputs ("Couldn't find element after it was added.\n",
305 stdout);
306 error = 1;
310 if (what == build || i < lag)
311 break;
313 j = k;
314 /* fall through */
316 case delete:
317 elem = tfind (x + j, (void *const *) root, cmp_fn);
318 if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
320 fputs ("Error deleting element.\n", stdout);
321 error = 1;
323 break;
325 case find:
326 if (tfind (x + j, (void *const *) root, cmp_fn) == NULL)
328 fputs ("Couldn't find element after it was added.\n", stdout);
329 error = 1;
331 break;
338 static int
339 do_test (void)
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;
346 initstate (SEED, state, 8);
348 for (i = 0; i < SIZE; ++i)
349 x[i] = i;
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)
356 fprintf (stdout, "Pass %d... ", i + 1);
357 fflush (stdout);
358 error = 0;
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);
367 mangle_tree (ascending, build, &root, 0);
368 walk_tree (root, SIZE);
369 mangle_tree (descending, delete, &root, 0);
371 mangle_tree (ascending, build, &root, 0);
372 walk_tree (root, SIZE);
373 mangle_tree (randomorder, delete, &root, 0);
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);
382 mangle_tree (descending, build, &root, 0);
383 walk_tree (root, SIZE);
384 mangle_tree (descending, delete, &root, 0);
386 mangle_tree (descending, build, &root, 0);
387 walk_tree (root, SIZE);
388 mangle_tree (randomorder, delete, &root, 0);
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);
397 for (j = 1; j < SIZE; j *= 2)
399 mangle_tree (randomorder, build_and_del, &root, j);
402 fputs (error ? " failed!\n" : " ok.\n", stdout);
403 total_error |= error;
406 fputs ("Series II\n", stdout);
407 for (i = 1; i < SIZE; i *= 2)
409 fprintf (stdout, "For size %d... ", i);
410 fflush (stdout);
411 error = 0;
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);
422 fputs (error ? " failed!\n" : " ok.\n", stdout);
423 total_error |= error;
426 for (i = 0; i < 2; ++i)
427 if (stack_align_check[i] == 0)
429 printf ("stack alignment check %d not run\n", i);
430 total_error |= 1;
432 else if (stack_align_check[i] != 1)
434 printf ("stack insufficiently aligned in check %d\n", i);
435 total_error |= 1;
438 return total_error;
441 #define TEST_FUNCTION do_test ()
442 #include "../test-skeleton.c"