1 /* Test program for tsearch et al.
2 Copyright (C) 1997, 2000-2001, 2007-2010 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 License as
7 published by the Free Software Foundation; either version 3 of the
8 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 License
16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
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)));
39 /* The system's tsearch() is not expected to keep the tree balanced. */
42 /* The gnulib replacement tsearch() should keep the tree balanced. */
55 #define random() (int) ((unsigned int) rand () >> 3)
72 /* Set to 1 if a test is flunked. */
75 /* The keys we add to the tree. */
78 /* Pointers into the key array, possibly permutated, to define an order
79 for insertion/removal. */
82 /* Flags set for each element visited during a tree walk. */
85 /* Depths for all the elements, to check that the depth is constant for
87 static int depths[SIZE];
89 /* Maximum depth during a tree walk. */
92 /* Compare two keys. */
94 cmp_fn (const void *a, const void *b)
96 return *(const int *) a - *(const int *) b;
99 /* Permute an array of integers. */
105 for (i = 0; i < SIZE; ++i)
110 j = random () % SIZE;
113 string[i] = string[j];
119 walk_action (const void *nodep, const VISIT which, const int depth)
121 int key = **(int **) nodep;
123 if (depth > max_depth)
125 if (which == leaf || which == preorder)
132 if (depths[key] != depth)
134 fputs ("Depth for one element is not constant during tree walk.\n",
141 walk_tree (void *root, int expected_count)
145 memset (z, 0, sizeof z);
148 twalk (root, walk_action);
149 for (i = 0; i < expected_count; ++i)
152 fputs ("Node was not visited.\n", stdout);
157 if (max_depth > log (expected_count) * 2 + 2)
159 if (max_depth > expected_count)
162 fputs ("Depth too large during tree walk.\n", stdout);
167 /* Perform an operation on a tree. */
169 mangle_tree (enum order how, enum action what, void **root, int lag)
173 if (how == randomorder)
175 for (i = 0; i < SIZE; ++i)
180 for (i = 0; i < SIZE + lag; ++i)
191 /* Ensure that the array index is within bounds. */
192 k = y[(SIZE - i - 1 + lag) % SIZE];
202 k = SIZE - i - 1 + lag;
207 /* This never should happen, but gcc isn't smart enough to
218 if (tfind (x + j, (void *const *) root, cmp_fn) != NULL)
220 fputs ("Found element which is not in tree yet.\n", stdout);
223 elem = tsearch (x + j, root, cmp_fn);
225 || tfind (x + j, (void *const *) root, cmp_fn) == NULL)
227 fputs ("Couldn't find element after it was added.\n",
233 if (what == build || i < lag)
240 elem = tfind (x + j, (void *const *) root, cmp_fn);
241 if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
243 fputs ("Error deleting element.\n", stdout);
249 if (tfind (x + j, (void *const *) root, cmp_fn) == NULL)
251 fputs ("Couldn't find element after it was added.\n", stdout);
262 main (int argc, char **argv)
265 static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
270 initstate (SEED, state, 8);
273 for (i = 0; i < SIZE; ++i)
276 /* Do this loop several times to get different permutations for the
278 fputs ("Series I\n", stdout);
279 for (i = 0; i < PASSES; ++i)
281 fprintf (stdout, "Pass %d... ", i + 1);
285 mangle_tree (ascending, build, &root, 0);
286 mangle_tree (ascending, find, &root, 0);
287 mangle_tree (descending, find, &root, 0);
288 mangle_tree (randomorder, find, &root, 0);
289 walk_tree (root, SIZE);
290 mangle_tree (ascending, delete, &root, 0);
292 mangle_tree (ascending, build, &root, 0);
293 walk_tree (root, SIZE);
294 mangle_tree (descending, delete, &root, 0);
296 mangle_tree (ascending, build, &root, 0);
297 walk_tree (root, SIZE);
298 mangle_tree (randomorder, delete, &root, 0);
300 mangle_tree (descending, build, &root, 0);
301 mangle_tree (ascending, find, &root, 0);
302 mangle_tree (descending, find, &root, 0);
303 mangle_tree (randomorder, find, &root, 0);
304 walk_tree (root, SIZE);
305 mangle_tree (descending, delete, &root, 0);
307 mangle_tree (descending, build, &root, 0);
308 walk_tree (root, SIZE);
309 mangle_tree (descending, delete, &root, 0);
311 mangle_tree (descending, build, &root, 0);
312 walk_tree (root, SIZE);
313 mangle_tree (randomorder, delete, &root, 0);
315 mangle_tree (randomorder, build, &root, 0);
316 mangle_tree (ascending, find, &root, 0);
317 mangle_tree (descending, find, &root, 0);
318 mangle_tree (randomorder, find, &root, 0);
319 walk_tree (root, SIZE);
320 mangle_tree (randomorder, delete, &root, 0);
322 for (j = 1; j < SIZE; j *= 2)
324 mangle_tree (randomorder, build_and_del, &root, j);
327 fputs (error ? " failed!\n" : " ok.\n", stdout);
328 total_error |= error;
331 fputs ("Series II\n", stdout);
332 for (i = 1; i < SIZE; i *= 2)
334 fprintf (stdout, "For size %d... ", i);
338 mangle_tree (ascending, build_and_del, &root, i);
339 mangle_tree (descending, build_and_del, &root, i);
340 mangle_tree (ascending, build_and_del, &root, i);
341 mangle_tree (descending, build_and_del, &root, i);
342 mangle_tree (ascending, build_and_del, &root, i);
343 mangle_tree (descending, build_and_del, &root, i);
344 mangle_tree (ascending, build_and_del, &root, i);
345 mangle_tree (descending, build_and_del, &root, i);
347 fputs (error ? " failed!\n" : " ok.\n", stdout);
348 total_error |= error;