[thirdparty/glibc.git] / misc / tst-tsearch.c

/* Test program for tsearch et al.
   Copyright (C) 1997-2015 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;

	}
    }
}


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;
    }

  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;
}
Commit	Line	Data
993b3242	1	/* Test program for tsearch et al.
b168057a	2	Copyright (C) 1997-2015 Free Software Foundation, Inc.
993b3242 UD	3	This file is part of the GNU C Library.
	4
	5	The GNU C Library is free software; you can redistribute it and/or
41bdb6e2 AJ	6	modify it under the terms of the GNU Lesser General Public
	7	License as published by the Free Software Foundation; either
	8	version 2.1 of the License, or (at your option) any later version.
993b3242 UD	9
	10	The GNU C Library is distributed in the hope that it will be useful,
	11	but WITHOUT ANY WARRANTY; without even the implied warranty of
	12	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
41bdb6e2	13	Lesser General Public License for more details.
993b3242	14
41bdb6e2	15	You should have received a copy of the GNU Lesser General Public
59ba27a6 PE	16	License along with the GNU C Library; if not, see
59ba27a6 PE	17	<http://www.gnu.org/licenses/>. */
993b3242	18
c131718c UD	19	#ifndef _GNU_SOURCE
	20	# define _GNU_SOURCE 1
	21	#endif
993b3242 UD	22
	23	#include <stdio.h>
	24	#include <stdlib.h>
c131718c	25	#include <string.h>
993b3242	26	#include <search.h>
06f6ca90	27	#include <tst-stack-align.h>
993b3242 UD	28
	29	#define SEED 0
	30	#define BALANCED 1
	31	#define PASSES 100
	32
	33	#if BALANCED
	34	#include <math.h>
	35	#define SIZE 1000
	36	#else
	37	#define SIZE 100
	38	#endif
	39
	40	enum order
	41	{
	42	ascending,
	43	descending,
	44	randomorder
	45	};
	46
	47	enum action
	48	{
	49	build,
	50	build_and_del,
	51	delete,
	52	find
	53	};
	54
	55	/* Set to 1 if a test is flunked. */
	56	static int error = 0;
	57
	58	/* The keys we add to the tree. */
	59	static int x[SIZE];
	60
	61	/* Pointers into the key array, possibly permutated, to define an order
	62	for insertion/removal. */
	63	static int y[SIZE];
	64
	65	/* Flags set for each element visited during a tree walk. */
	66	static int z[SIZE];
	67
	68	/* Depths for all the elements, to check that the depth is constant for
	69	all three visits. */
	70	static int depths[SIZE];
	71
	72	/* Maximum depth during a tree walk. */
	73	static int max_depth;
	74
06f6ca90 UD	75	static int stack_align_check[2];
06f6ca90 UD	76
993b3242 UD	77	/* Compare two keys. */
	78	static int
	79	cmp_fn (const void a, const void b)
	80	{
06f6ca90 UD	81	if (!stack_align_check[0])
06f6ca90 UD	82	stack_align_check[0] = TEST_STACK_ALIGN () ? -1 : 1;
993b3242 UD	83	return (const int ) a - (const int ) b;
	84	}
	85
	86	/* Permute an array of integers. */
	87	static void
	88	memfry (int *string)
	89	{
	90	int i;
	91
	92	for (i = 0; i < SIZE; ++i)
	93	{
	94	int32_t j;
	95	int c;
	96
	97	j = random () % SIZE;
	98
	99	c = string[i];
	100	string[i] = string[j];
	101	string[j] = c;
	102	}
	103	}
	104
	105	static void
	106	walk_action (const void *nodep, const VISIT which, const int depth)
	107	{
	108	int key = (int ) nodep;
	109
06f6ca90 UD	110	if (!stack_align_check[1])
	111	stack_align_check[1] = TEST_STACK_ALIGN () ? -1 : 1;
	112
993b3242 UD	113	if (depth > max_depth)
	114	max_depth = depth;
	115	if (which == leaf \|\| which == preorder)
	116	{
	117	++z[key];
	118	depths[key] = depth;
	119	}
	120	else
	121	{
	122	if (depths[key] != depth)
	123	{
	124	fputs ("Depth for one element is not constant during tree walk.\n",
5929563f	125	stdout);
993b3242 UD	126	}
	127	}
	128	}
	129
	130	static void
	131	walk_tree (void *root, int expected_count)
	132	{
	133	int i;
	134
	135	memset (z, 0, sizeof z);
	136	max_depth = 0;
	137
	138	twalk (root, walk_action);
	139	for (i = 0; i < expected_count; ++i)
	140	if (z[i] != 1)
	141	{
5929563f	142	fputs ("Node was not visited.\n", stdout);
993b3242 UD	143	error = 1;
	144	}
	145
	146	#if BALANCED
	147	if (max_depth > log (expected_count) * 2 + 2)
	148	#else
	149	if (max_depth > expected_count)
	150	#endif
	151	{
5929563f	152	fputs ("Depth too large during tree walk.\n", stdout);
993b3242 UD	153	error = 1;
	154	}
	155	}
	156
	157	/* Perform an operation on a tree. */
	158	static void
	159	mangle_tree (enum order how, enum action what, void **root, int lag)
	160	{
	161	int i;
	162
	163	if (how == randomorder)
	164	{
	165	for (i = 0; i < SIZE; ++i)
	166	y[i] = i;
	167	memfry (y);
	168	}
	169
	170	for (i = 0; i < SIZE + lag; ++i)
	171	{
	172	void *elem;
	173	int j, k;
	174
	175	switch (how)
	176	{
	177	case randomorder:
	178	if (i >= lag)
	179	k = y[i - lag];
	180	else
673c34e0 AJ	181	/* Ensure that the array index is within bounds. */
	182	k = y[(SIZE - i - 1 + lag) % SIZE];
	183	j = y[i % SIZE];
993b3242 UD	184	break;
	185
	186	case ascending:
	187	k = i - lag;
	188	j = i;
	189	break;
	190
	191	case descending:
	192	k = SIZE - i - 1 + lag;
	193	j = SIZE - i - 1;
	194	break;
	195
	196	default:
	197	/* This never should happen, but gcc isn't smart enough to
	198	recognize it. */
	199	abort ();
	200	}
	201
	202	switch (what)
	203	{
	204	case build_and_del:
	205	case build:
	206	if (i < SIZE)
	207	{
f671aeab	208	if (tfind (x + j, (void const ) root, cmp_fn) != NULL)
993b3242	209	{
5929563f	210	fputs ("Found element which is not in tree yet.\n", stdout);
993b3242 UD	211	error = 1;
	212	}
	213	elem = tsearch (x + j, root, cmp_fn);
	214	if (elem == 0
f671aeab	215	\|\| tfind (x + j, (void const ) root, cmp_fn) == NULL)
993b3242 UD	216	{
993b3242 UD	217	fputs ("Couldn't find element after it was added.\n",
5929563f	218	stdout);
993b3242 UD	219	error = 1;
	220	}
	221	}
	222
	223	if (what == build \|\| i < lag)
	224	break;
	225
	226	j = k;
	227	/* fall through */
	228
	229	case delete:
f671aeab	230	elem = tfind (x + j, (void const ) root, cmp_fn);
993b3242 UD	231	if (elem == NULL \|\| tdelete (x + j, root, cmp_fn) == NULL)
993b3242 UD	232	{
5929563f	233	fputs ("Error deleting element.\n", stdout);
993b3242 UD	234	error = 1;
	235	}
	236	break;
	237
	238	case find:
f671aeab	239	if (tfind (x + j, (void const ) root, cmp_fn) == NULL)
993b3242	240	{
5929563f	241	fputs ("Couldn't find element after it was added.\n", stdout);
993b3242 UD	242	error = 1;
	243	}
	244	break;
	245
	246	}
	247	}
	248	}
	249
	250
	251	int
	252	main (int argc, char **argv)
	253	{
	254	int total_error = 0;
621d9092	255	static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
993b3242 UD	256	void *root = NULL;
	257	int i, j;
	258
	259	initstate (SEED, state, 8);
	260
	261	for (i = 0; i < SIZE; ++i)
	262	x[i] = i;
	263
	264	/* Do this loop several times to get different permutations for the
	265	random case. */
5929563f	266	fputs ("Series I\n", stdout);
993b3242 UD	267	for (i = 0; i < PASSES; ++i)
993b3242 UD	268	{
5929563f	269	fprintf (stdout, "Pass %d... ", i + 1);
993b3242 UD	270	fflush (stdout);
	271	error = 0;
	272
	273	mangle_tree (ascending, build, &root, 0);
	274	mangle_tree (ascending, find, &root, 0);
	275	mangle_tree (descending, find, &root, 0);
	276	mangle_tree (randomorder, find, &root, 0);
	277	walk_tree (root, SIZE);
	278	mangle_tree (ascending, delete, &root, 0);
	279
	280	mangle_tree (ascending, build, &root, 0);
	281	walk_tree (root, SIZE);
	282	mangle_tree (descending, delete, &root, 0);
	283
	284	mangle_tree (ascending, build, &root, 0);
	285	walk_tree (root, SIZE);
	286	mangle_tree (randomorder, delete, &root, 0);
	287
	288	mangle_tree (descending, build, &root, 0);
	289	mangle_tree (ascending, find, &root, 0);
	290	mangle_tree (descending, find, &root, 0);
	291	mangle_tree (randomorder, find, &root, 0);
	292	walk_tree (root, SIZE);
	293	mangle_tree (descending, delete, &root, 0);
	294
	295	mangle_tree (descending, build, &root, 0);
	296	walk_tree (root, SIZE);
	297	mangle_tree (descending, delete, &root, 0);
	298
	299	mangle_tree (descending, build, &root, 0);
	300	walk_tree (root, SIZE);
	301	mangle_tree (randomorder, delete, &root, 0);
	302
	303	mangle_tree (randomorder, build, &root, 0);
	304	mangle_tree (ascending, find, &root, 0);
	305	mangle_tree (descending, find, &root, 0);
	306	mangle_tree (randomorder, find, &root, 0);
	307	walk_tree (root, SIZE);
	308	mangle_tree (randomorder, delete, &root, 0);
	309
	310	for (j = 1; j < SIZE; j *= 2)
	311	{
	312	mangle_tree (randomorder, build_and_del, &root, j);
	313	}
	314
5929563f	315	fputs (error ? " failed!\n" : " ok.\n", stdout);
993b3242 UD	316	total_error \|= error;
	317	}
	318
5929563f	319	fputs ("Series II\n", stdout);
993b3242 UD	320	for (i = 1; i < SIZE; i *= 2)
993b3242 UD	321	{
5929563f	322	fprintf (stdout, "For size %d... ", i);
993b3242 UD	323	fflush (stdout);
	324	error = 0;
	325
	326	mangle_tree (ascending, build_and_del, &root, i);
	327	mangle_tree (descending, build_and_del, &root, i);
	328	mangle_tree (ascending, build_and_del, &root, i);
	329	mangle_tree (descending, build_and_del, &root, i);
	330	mangle_tree (ascending, build_and_del, &root, i);
	331	mangle_tree (descending, build_and_del, &root, i);
	332	mangle_tree (ascending, build_and_del, &root, i);
	333	mangle_tree (descending, build_and_del, &root, i);
	334
5929563f	335	fputs (error ? " failed!\n" : " ok.\n", stdout);
993b3242 UD	336	total_error \|= error;
	337	}
	338
06f6ca90 UD	339	for (i = 0; i < 2; ++i)
	340	if (stack_align_check[i] == 0)
	341	{
	342	printf ("stack alignment check %d not run\n", i);
	343	total_error \|= 1;
	344	}
	345	else if (stack_align_check[i] != 1)
	346	{
	347	printf ("stack insufficiently aligned in check %d\n", i);
	348	total_error \|= 1;
	349	}
	350
993b3242 UD	351	return total_error;
993b3242 UD	352	}