aboutsummaryrefslogtreecommitdiff
path: root/misc/tst-tsearch.c
diff options
context:
space:
mode:
authorUlrich Drepper <drepper@redhat.com>1997-03-29 17:32:35 +0000
committerUlrich Drepper <drepper@redhat.com>1997-03-29 17:32:35 +0000
commit993b3242cdc37152fbbc7fbd5ce22b2734b04b23 (patch)
treed3c4fc94e027728055d96a370d034b6fb685cf85 /misc/tst-tsearch.c
parente7fd8a39abd3a9c9d2139e686b17efb5dc3bf444 (diff)
downloadglibc-993b3242cdc37152fbbc7fbd5ce22b2734b04b23.zip
glibc-993b3242cdc37152fbbc7fbd5ce22b2734b04b23.tar.gz
glibc-993b3242cdc37152fbbc7fbd5ce22b2734b04b23.tar.bz2
Update.
1997-03-29 17:39 Ulrich Drepper <drepper@cygnus.com> * math/Makefile (routines): Add carg, s_ccosh and s_csinh. * math/complex.h: Add C++ protection. * math/libm-test.c (cexp_test): Correct a few bugs. (csinh_test): New function. (ccosh_test): New function. (cacos_test): New function. (cacosh_test): New function. (casinh_test): New function. (catanh_test): New function. (main): Add calls to csinh_test and ccosh_test. * misc/Makefile (tests): Add tst-tsearch. Add rule to link tst-tsearch against libm. * misc/tsearch.c: Rewritten to use Red-Black-Tree algorithm by Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>. * misc/tst-tsearch.c: New file. * stdio-common/bug5.c: Clear LD_LIBRARY_PATH environment variable before using system. * stdio-common/test-popen.c: Clear LD_LIBRARY_PATH environment variable before using popen. * sysdeps/libm-ieee754/s_cexp.c: Correct handling of special cases. * sysdeps/libm-ieee754/s_cexpf.c: Likewise. * sysdeps/libm-ieee754/s_cexpl.c: Likewise. * sysdeps/libm-i387/s_cexp.S: New file. ix87 specific implementation of complex exponential function. * sysdeps/libm-i387/s_cexpf.S: New file. * sysdeps/libm-i387/s_cexpl.S: New file. * sysdeps/libm-ieee754/s_ccosh.c: New file. Implementation of complex cosh function. * sysdeps/libm-ieee754/s_ccoshf.c: New file. * sysdeps/libm-ieee754/s_ccoshl.c: New file. * sysdeps/libm-ieee754/s_csinh.c: New file. Implementation of complex sinh function. * sysdeps/libm-ieee754/s_csinhf.c: New file. * sysdeps/libm-ieee754/s_csinhl.c: New file. * math/carg.c: New file. Generic implementatio of carg function. * math/cargf.c: New file. * math/cargl.c: New file. 1997-03-29 16:07 Ulrich Drepper <drepper@cygnus.com> * sysdeps/posix/system.c: Update copyright. 1997-03-29 04:18 Ulrich Drepper <drepper@cygnus.com> * elf/dl-error.c (_dl_catch_error): Add another argument which is passed to OPERATE. (_dl_receive_error): Likewise. * elf/link.h: Change prototypes for _dl_catch_error and _dl_receive_error to reflect above change. * elf/dl-deps.c: Don't use nested function. Call _dl_catch_error with additional argument with pointer to data. * elf/dlclose.c: Likewise. * elf/dlerror.c: Likewise. * elf/dlopen.c: Likewise. * elf/dlsym.c: Likewise. * elf/dlvsym.c: Likewise. * elf/rtld.c: Likewise. * nss/nsswitch.c: Likewise. Patch by Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>. 1997-03-28 21:14 Miguel de Icaza <miguel@nuclecu.unam.mx> * elf/dl-error.c: Manually set up the values of "c", this avoids a call to memcpy and a zero 152 bytes structure. * sysdeps/sparc/dl-machine.h (elf_machine_rela): Test RTLD_BOOTSTRAP to avoid performing relative relocs on a second pass. * sysdeps/sparc/udiv_qrnnd.S: Make the code PIC aware. * sysdeps/unix/sysv/linux/sparc/Dist: Add kernel_stat.h and kernel_sigaction.h Add Linux/SPARC specific definitions. * sysdeps/unix/sysv/linux/sparc/fcntlbits.h: New file. * sysdeps/unix/sysv/linux/sparc/ioctls.h: New file. * sysdeps/unix/sysv/linux/sparc/kernel_sigaction.h: New file. * sysdeps/unix/sysv/linux/sparc/kernel_stat.h: New file. * sysdeps/unix/sysv/linux/sparc/sigaction.h: New file. * sysdeps/unix/sysv/linux/sparc/signum.h: New file. * sysdeps/unix/sysv/linux/sparc/termbits.h: New file. 1997-03-28 13:06 Philip Blundell <pjb27@cam.ac.uk> * sysdeps/posix/getaddrinfo.c (gaih_inet_serv): Use __getservbyname_r() not getservbyname(). (BROKEN_LIKE_POSIX): Define to 1 so we get strict POSIX behaviour.
Diffstat (limited to 'misc/tst-tsearch.c')
-rw-r--r--misc/tst-tsearch.c329
1 files changed, 329 insertions, 0 deletions
diff --git a/misc/tst-tsearch.c b/misc/tst-tsearch.c
new file mode 100644
index 0000000..eca11cb
--- /dev/null
+++ b/misc/tst-tsearch.c
@@ -0,0 +1,329 @@
+/* Test program for tsearch et al.
+ Copyright (C) 1997 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 Library General Public License as
+ published by the Free Software Foundation; either version 2 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
+ Library General Public License for more details.
+
+ You should have received a copy of the GNU Library General Public
+ License along with the GNU C Library; see the file COPYING.LIB. If not,
+ write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA. */
+
+#define _GNU_SOURCE 1
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <search.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;
+
+/* 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",
+ stderr);
+ }
+ }
+}
+
+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", stderr);
+ 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", stderr);
+ 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
+ k = y[SIZE - i - 1 + lag];
+ j = y[i];
+ 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, (const void **) root, cmp_fn) != NULL)
+ {
+ fputs ("Found element which is not in tree yet.\n", stderr);
+ error = 1;
+ }
+ elem = tsearch (x + j, root, cmp_fn);
+ if (elem == 0
+ || tfind (x + j, (const void **) root, cmp_fn) == NULL)
+ {
+ fputs ("Couldn't find element after it was added.\n",
+ stderr);
+ error = 1;
+ }
+ }
+
+ if (what == build || i < lag)
+ break;
+
+ j = k;
+ /* fall through */
+
+ case delete:
+ elem = tfind (x + j, (const void **) root, cmp_fn);
+ if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
+ {
+ fputs ("Error deleting element.\n", stderr);
+ error = 1;
+ }
+ break;
+
+ case find:
+ if (tfind (x + j, (const void **) root, cmp_fn) == NULL)
+ {
+ fputs ("Couldn't find element after it was added.\n", stderr);
+ error = 1;
+ }
+ break;
+
+ }
+ }
+}
+
+
+int
+main (int argc, char **argv)
+{
+ int total_error = 0;
+ static int 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", stderr);
+ for (i = 0; i < PASSES; ++i)
+ {
+ fprintf (stderr, "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", stderr);
+ total_error |= error;
+ }
+
+ fputs ("Series II\n", stderr);
+ for (i = 1; i < SIZE; i *= 2)
+ {
+ fprintf (stderr, "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", stderr);
+ total_error |= error;
+ }
+
+ return total_error;
+}