diff options
Diffstat (limited to 'REORG.TODO/misc/tst-tsearch.c')
| -rw-r--r-- | REORG.TODO/misc/tst-tsearch.c | 356 |
1 files changed, 356 insertions, 0 deletions
diff --git a/REORG.TODO/misc/tst-tsearch.c b/REORG.TODO/misc/tst-tsearch.c new file mode 100644 index 0000000000..6c8fff0e3f --- /dev/null +++ b/REORG.TODO/misc/tst-tsearch.c @@ -0,0 +1,356 @@ +/* Test program for tsearch et al. + Copyright (C) 1997-2017 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 2.1 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 the GNU C Library; if not, see + <http://www.gnu.org/licenses/>. */ + +#ifndef _GNU_SOURCE +# define _GNU_SOURCE 1 +#endif + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <search.h> +#include <tst-stack-align.h> + +#define SEED 0 +#define BALANCED 1 +#define PASSES 100 + +#if BALANCED +#include <math.h> +#define SIZE 1000 +#else +#define SIZE 100 +#endif + +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; + +static int stack_align_check[2]; + +/* Compare two keys. */ +static int +cmp_fn (const void *a, const void *b) +{ + if (!stack_align_check[0]) + stack_align_check[0] = TEST_STACK_ALIGN () ? -1 : 1; + 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 (!stack_align_check[1]) + stack_align_check[1] = TEST_STACK_ALIGN () ? -1 : 1; + + 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; + + } + } +} + + +static int +do_test (void) +{ + int total_error = 0; + static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 }; + void *root = NULL; + int i, j; + + initstate (SEED, state, 8); + + 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; + } + + for (i = 0; i < 2; ++i) + if (stack_align_check[i] == 0) + { + printf ("stack alignment check %d not run\n", i); + total_error |= 1; + } + else if (stack_align_check[i] != 1) + { + printf ("stack insufficiently aligned in check %d\n", i); + total_error |= 1; + } + + return total_error; +} + +#define TIMEOUT 10 +#define TEST_FUNCTION do_test () +#include "../test-skeleton.c" |