diff options
Diffstat (limited to 'gnulib/tests/test-tsearch.c')
| m--------- | gnulib | 0 | ||||
| -rw-r--r-- | gnulib/tests/test-tsearch.c | 352 |
2 files changed, 352 insertions, 0 deletions
diff --git a/gnulib b/gnulib deleted file mode 160000 -Subproject 4fc10daa05477586fea99b6b3ca02a87d1102fa diff --git a/gnulib/tests/test-tsearch.c b/gnulib/tests/test-tsearch.c new file mode 100644 index 00000000..454fef60 --- /dev/null +++ b/gnulib/tests/test-tsearch.c @@ -0,0 +1,352 @@ +/* Test program for tsearch et al. + Copyright (C) 1997, 2000-2001, 2007-2010 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software: you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License as + published by the Free Software Foundation; either version 3 of the + License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +#include <config.h> + +#include <search.h> + +#include "signature.h" +SIGNATURE_CHECK (tdelete, void *, (void const *, void **, + int (*) (void const *, void const *))); +SIGNATURE_CHECK (tfind, void *, (void const *, void * const *, + int (*) (void const *, void const *))); +SIGNATURE_CHECK (tsearch, void *, (void const *, void **, + int (*) (void const *, void const *))); +SIGNATURE_CHECK (twalk, void, (void const *, + void (*) (void const *, VISIT, int))); + +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define SEED 0 +#if HAVE_TSEARCH +/* The system's tsearch() is not expected to keep the tree balanced. */ +# define BALANCED 0 +#else +/* The gnulib replacement tsearch() should keep the tree balanced. */ +# define BALANCED 1 +#endif +#define PASSES 100 + +#if BALANCED +#include <math.h> +#define SIZE 1000 +#else +#define SIZE 100 +#endif + +#undef random +#define random() (int) ((unsigned int) rand () >> 3) + +enum order +{ + ascending, + descending, + randomorder +}; + +enum action +{ + build, + build_and_del, + delete, + find +}; + +/* Set to 1 if a test is flunked. */ +static int error = 0; + +/* The keys we add to the tree. */ +static int x[SIZE]; + +/* Pointers into the key array, possibly permutated, to define an order + for insertion/removal. */ +static int y[SIZE]; + +/* Flags set for each element visited during a tree walk. */ +static int z[SIZE]; + +/* Depths for all the elements, to check that the depth is constant for + all three visits. */ +static int depths[SIZE]; + +/* Maximum depth during a tree walk. */ +static int max_depth; + +/* Compare two keys. */ +static int +cmp_fn (const void *a, const void *b) +{ + return *(const int *) a - *(const int *) b; +} + +/* Permute an array of integers. */ +static void +memfry (int *string) +{ + int i; + + for (i = 0; i < SIZE; ++i) + { + int32_t j; + int c; + + j = random () % SIZE; + + c = string[i]; + string[i] = string[j]; + string[j] = c; + } +} + +static void +walk_action (const void *nodep, const VISIT which, const int depth) +{ + int key = **(int **) nodep; + + if (depth > max_depth) + max_depth = depth; + if (which == leaf || which == preorder) + { + ++z[key]; + depths[key] = depth; + } + else + { + if (depths[key] != depth) + { + fputs ("Depth for one element is not constant during tree walk.\n", + stdout); + } + } +} + +static void +walk_tree (void *root, int expected_count) +{ + int i; + + memset (z, 0, sizeof z); + max_depth = 0; + + twalk (root, walk_action); + for (i = 0; i < expected_count; ++i) + if (z[i] != 1) + { + fputs ("Node was not visited.\n", stdout); + error = 1; + } + +#if BALANCED + if (max_depth > log (expected_count) * 2 + 2) +#else + if (max_depth > expected_count) +#endif + { + fputs ("Depth too large during tree walk.\n", stdout); + error = 1; + } +} + +/* Perform an operation on a tree. */ +static void +mangle_tree (enum order how, enum action what, void **root, int lag) +{ + int i; + + if (how == randomorder) + { + for (i = 0; i < SIZE; ++i) + y[i] = i; + memfry (y); + } + + for (i = 0; i < SIZE + lag; ++i) + { + void *elem; + int j, k; + + switch (how) + { + case randomorder: + if (i >= lag) + k = y[i - lag]; + else + /* Ensure that the array index is within bounds. */ + k = y[(SIZE - i - 1 + lag) % SIZE]; + j = y[i % SIZE]; + break; + + case ascending: + k = i - lag; + j = i; + break; + + case descending: + k = SIZE - i - 1 + lag; + j = SIZE - i - 1; + break; + + default: + /* This never should happen, but gcc isn't smart enough to + recognize it. */ + abort (); + } + + switch (what) + { + case build_and_del: + case build: + if (i < SIZE) + { + if (tfind (x + j, (void *const *) root, cmp_fn) != NULL) + { + fputs ("Found element which is not in tree yet.\n", stdout); + error = 1; + } + elem = tsearch (x + j, root, cmp_fn); + if (elem == 0 + || tfind (x + j, (void *const *) root, cmp_fn) == NULL) + { + fputs ("Couldn't find element after it was added.\n", + stdout); + error = 1; + } + } + + if (what == build || i < lag) + break; + + j = k; + /* fall through */ + + case delete: + elem = tfind (x + j, (void *const *) root, cmp_fn); + if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL) + { + fputs ("Error deleting element.\n", stdout); + error = 1; + } + break; + + case find: + if (tfind (x + j, (void *const *) root, cmp_fn) == NULL) + { + fputs ("Couldn't find element after it was added.\n", stdout); + error = 1; + } + break; + + } + } +} + + +int +main (int argc, char **argv) +{ + int total_error = 0; + static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 }; + void *root = NULL; + int i, j; + +#if HAVE_INITSTATE + initstate (SEED, state, 8); +#endif + + for (i = 0; i < SIZE; ++i) + x[i] = i; + + /* Do this loop several times to get different permutations for the + random case. */ + fputs ("Series I\n", stdout); + for (i = 0; i < PASSES; ++i) + { + fprintf (stdout, "Pass %d... ", i + 1); + fflush (stdout); + error = 0; + + mangle_tree (ascending, build, &root, 0); + mangle_tree (ascending, find, &root, 0); + mangle_tree (descending, find, &root, 0); + mangle_tree (randomorder, find, &root, 0); + walk_tree (root, SIZE); + mangle_tree (ascending, delete, &root, 0); + + mangle_tree (ascending, build, &root, 0); + walk_tree (root, SIZE); + mangle_tree (descending, delete, &root, 0); + + mangle_tree (ascending, build, &root, 0); + walk_tree (root, SIZE); + mangle_tree (randomorder, delete, &root, 0); + + mangle_tree (descending, build, &root, 0); + mangle_tree (ascending, find, &root, 0); + mangle_tree (descending, find, &root, 0); + mangle_tree (randomorder, find, &root, 0); + walk_tree (root, SIZE); + mangle_tree (descending, delete, &root, 0); + + mangle_tree (descending, build, &root, 0); + walk_tree (root, SIZE); + mangle_tree (descending, delete, &root, 0); + + mangle_tree (descending, build, &root, 0); + walk_tree (root, SIZE); + mangle_tree (randomorder, delete, &root, 0); + + mangle_tree (randomorder, build, &root, 0); + mangle_tree (ascending, find, &root, 0); + mangle_tree (descending, find, &root, 0); + mangle_tree (randomorder, find, &root, 0); + walk_tree (root, SIZE); + mangle_tree (randomorder, delete, &root, 0); + + for (j = 1; j < SIZE; j *= 2) + { + mangle_tree (randomorder, build_and_del, &root, j); + } + + fputs (error ? " failed!\n" : " ok.\n", stdout); + total_error |= error; + } + + fputs ("Series II\n", stdout); + for (i = 1; i < SIZE; i *= 2) + { + fprintf (stdout, "For size %d... ", i); + fflush (stdout); + error = 0; + + mangle_tree (ascending, build_and_del, &root, i); + mangle_tree (descending, build_and_del, &root, i); + mangle_tree (ascending, build_and_del, &root, i); + mangle_tree (descending, build_and_del, &root, i); + mangle_tree (ascending, build_and_del, &root, i); + mangle_tree (descending, build_and_del, &root, i); + mangle_tree (ascending, build_and_del, &root, i); + mangle_tree (descending, build_and_del, &root, i); + + fputs (error ? " failed!\n" : " ok.\n", stdout); + total_error |= error; + } + + return total_error; +} |