Mercurial > gnulib

changeset 28225:d6fda65df378

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Tests for module 'tsearch'.
author Bruno Haible <bruno@clisp.org>
date Sun, 25 Mar 2007 02:48:08 +0000
parents af4f033ba0cb
children 84d40162ecf6
files ChangeLog modules/tsearch-tests tests/test-tsearch.c tests/test-tsearch.sh
diffstat 4 files changed, 385 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- a/ChangeLog	Sun Mar 25 02:46:43 2007 +0000
+++ b/ChangeLog	Sun Mar 25 02:48:08 2007 +0000
@@ -1,5 +1,9 @@
 2007-03-24  Bruno Haible  <bruno@clisp.org>
 
+	* 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.
 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/modules/tsearch-tests	Sun Mar 25 02:48:08 2007 +0000
@@ -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 <math.h>
+   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
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test-tsearch.c	Sun Mar 25 02:48:08 2007 +0000
@@ -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 <config.h>
+
+#include <search.h>
+
+#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;
+
+  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;
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test-tsearch.sh	Sun Mar 25 02:48:08 2007 +0000
@@ -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