1/* Test program for tsearch et al.
2 Copyright (C) 1997-2024 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
41enum order
42{
43 ascending,
44 descending,
45 randomorder
46};
47
48enum action
49{
50 build,
51 build_and_del,
52 delete,
53 find
54};
55
56/* Set to 1 if a test is flunked. */
57static int error = 0;
58
59/* The keys we add to the tree. */
60static int x[SIZE];
61
62/* Pointers into the key array, possibly permutated, to define an order
63 for insertion/removal. */
64static int y[SIZE];
65
66/* Flags set for each element visited during a tree walk. */
67static int z[SIZE];
68
69/* Depths for all the elements, to check that the depth is constant for
70 all three visits. */
71static int depths[SIZE];
72
73/* Maximum depth during a tree walk. */
74static int max_depth;
75
76static int stack_align_check[2];
77
78/* Used to compare walk traces between the two implementations. */
79struct 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>
90static struct walk_trace_list walk_trace;
91
92/* Compare two keys. */
93static int
94cmp_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. */
102static void
103memfry (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
120struct twalk_with_twalk_r_closure
121{
122 void (*action) (const void *, VISIT, int);
123 int depth;
124};
125
126static void
127twalk_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
151static void
152twalk_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: root, twalk_with_twalk_r_action, closure: &closure);
157 TEST_COMPARE (closure.depth, 0);
158}
159
160static void
161walk_action (const void *nodep, const VISIT which, const int depth)
162{
163 int key = **(int **) nodep;
164
165 walk_trace_add (list: &walk_trace,
166 item: (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
188static void
189walk_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 (x: 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
217static void
218walk_tree (void *root, int expected_count)
219{
220 walk_trace_clear (list: &walk_trace);
221 walk_tree_with (root, expected_count, walk: 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 (list: &walk_trace, lengthp: &first_list_size);
226 TEST_VERIFY_EXIT (first_list != NULL);
227
228 walk_tree_with (root, expected_count, walk: 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 (list: &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 (list: &walk_trace);
242}
243
244/* Perform an operation on a tree. */
245static void
246mangle_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 (string: 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 (key: x + j, rootp: (void *const *) root, compar: cmp_fn) != NULL)
296 {
297 fputs ("Found element which is not in tree yet.\n", stdout);
298 error = 1;
299 }
300 elem = tsearch (key: x + j, rootp: root, compar: cmp_fn);
301 if (elem == 0
302 || tfind (key: x + j, rootp: (void *const *) root, compar: 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 (key: x + j, rootp: (void *const *) root, compar: cmp_fn);
318 if (elem == NULL || tdelete (key: x + j, rootp: root, compar: cmp_fn) == NULL)
319 {
320 fputs ("Error deleting element.\n", stdout);
321 error = 1;
322 }
323 break;
324
325 case find:
326 if (tfind (key: x + j, rootp: (void *const *) root, compar: 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
338static int
339do_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, statebuf: state, statelen: 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 (how: ascending, what: build, root: &root, lag: 0);
361 mangle_tree (how: ascending, what: find, root: &root, lag: 0);
362 mangle_tree (how: descending, what: find, root: &root, lag: 0);
363 mangle_tree (how: randomorder, what: find, root: &root, lag: 0);
364 walk_tree (root, SIZE);
365 mangle_tree (how: ascending, what: delete, root: &root, lag: 0);
366
367 mangle_tree (how: ascending, what: build, root: &root, lag: 0);
368 walk_tree (root, SIZE);
369 mangle_tree (how: descending, what: delete, root: &root, lag: 0);
370
371 mangle_tree (how: ascending, what: build, root: &root, lag: 0);
372 walk_tree (root, SIZE);
373 mangle_tree (how: randomorder, what: delete, root: &root, lag: 0);
374
375 mangle_tree (how: descending, what: build, root: &root, lag: 0);
376 mangle_tree (how: ascending, what: find, root: &root, lag: 0);
377 mangle_tree (how: descending, what: find, root: &root, lag: 0);
378 mangle_tree (how: randomorder, what: find, root: &root, lag: 0);
379 walk_tree (root, SIZE);
380 mangle_tree (how: descending, what: delete, root: &root, lag: 0);
381
382 mangle_tree (how: descending, what: build, root: &root, lag: 0);
383 walk_tree (root, SIZE);
384 mangle_tree (how: descending, what: delete, root: &root, lag: 0);
385
386 mangle_tree (how: descending, what: build, root: &root, lag: 0);
387 walk_tree (root, SIZE);
388 mangle_tree (how: randomorder, what: delete, root: &root, lag: 0);
389
390 mangle_tree (how: randomorder, what: build, root: &root, lag: 0);
391 mangle_tree (how: ascending, what: find, root: &root, lag: 0);
392 mangle_tree (how: descending, what: find, root: &root, lag: 0);
393 mangle_tree (how: randomorder, what: find, root: &root, lag: 0);
394 walk_tree (root, SIZE);
395 mangle_tree (how: randomorder, what: delete, root: &root, lag: 0);
396
397 for (j = 1; j < SIZE; j *= 2)
398 {
399 mangle_tree (how: randomorder, what: build_and_del, root: &root, lag: 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 (how: ascending, what: build_and_del, root: &root, lag: i);
414 mangle_tree (how: descending, what: build_and_del, root: &root, lag: i);
415 mangle_tree (how: ascending, what: build_and_del, root: &root, lag: i);
416 mangle_tree (how: descending, what: build_and_del, root: &root, lag: i);
417 mangle_tree (how: ascending, what: build_and_del, root: &root, lag: i);
418 mangle_tree (how: descending, what: build_and_del, root: &root, lag: i);
419 mangle_tree (how: ascending, what: build_and_del, root: &root, lag: i);
420 mangle_tree (how: descending, what: build_and_del, root: &root, lag: 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 (format: "stack alignment check %d not run\n", i);
430 total_error |= 1;
431 }
432 else if (stack_align_check[i] != 1)
433 {
434 printf (format: "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"
443

source code of glibc/misc/tst-tsearch.c