From 192bd848d1106fc68d24e24e61534d6d9d49a335 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Sun, 25 Mar 2007 02:48:08 +0000 Subject: [PATCH] Tests for module 'tsearch'. --- ChangeLog | 4 + modules/tsearch-tests | 27 ++++ tests/test-tsearch.c | 342 ++++++++++++++++++++++++++++++++++++++++++++++++++ tests/test-tsearch.sh | 12 ++ 4 files changed, 385 insertions(+) create mode 100644 modules/tsearch-tests create mode 100644 tests/test-tsearch.c create mode 100755 tests/test-tsearch.sh diff --git a/ChangeLog b/ChangeLog index 8218f4274..d6fe99f76 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,9 @@ 2007-03-24 Bruno Haible + * modules/tsearch-tests: New file. + * tests/test-tsearch.sh: New file. + * tests/test-tsearch.c: New file, mostly copied from glibc. + * modules/search-tests: New file. * tests/test-search.c: New file. diff --git a/modules/tsearch-tests b/modules/tsearch-tests new file mode 100644 index 000000000..d258c0e35 --- /dev/null +++ b/modules/tsearch-tests @@ -0,0 +1,27 @@ +Files: +tests/test-tsearch.sh +tests/test-tsearch.c + +Depends-on: +stdint + +configure.ac: +TEST_TSEARCH_LIBM= +AC_TRY_LINK([ + #ifndef __NO_MATH_INLINES + # define __NO_MATH_INLINES 1 /* for glibc */ + #endif + #include + double x;], + [x = log (x);], , [TEST_TSEARCH_LIBM=-lm]) +AC_SUBST([TEST_TSEARCH_LIBM]) + +Makefile.am: +TESTS += test-tsearch.sh +TESTS_ENVIRONMENT += EXEEXT='@EXEEXT@' +check_PROGRAMS += test-tsearch +test_tsearch_LDADD = @TEST_TSEARCH_LIBM@ $(LDADD) +EXTRA_DIST += test-tsearch.sh + +License: +LGPL diff --git a/tests/test-tsearch.c b/tests/test-tsearch.c new file mode 100644 index 000000000..1d55824b6 --- /dev/null +++ b/tests/test-tsearch.c @@ -0,0 +1,342 @@ +/* Test program for tsearch et al. + Copyright (C) 1997, 2000, 2001, 2007 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, write to the Free + Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA + 02111-1307 USA. */ + +#include + +#include + +#include +#include +#include +#include + +#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 +#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; + + 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; + } + + return total_error; +} diff --git a/tests/test-tsearch.sh b/tests/test-tsearch.sh new file mode 100755 index 000000000..c206956bb --- /dev/null +++ b/tests/test-tsearch.sh @@ -0,0 +1,12 @@ +#!/bin/sh + +tmpfiles="" +trap 'rm -fr $tmpfiles' 1 2 3 15 + +tmpfiles="$tmpfiles t-tsearch.out" +./test-tsearch${EXEEXT} > t-tsearch.out 2>&1 +test $? = 0 || { cat t-tsearch.out 1>&2; rm -f $tmpfiles; exit 1; } + +rm -f $tmpfiles + +exit 0 -- 2.11.0