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

/* Test program for tsearch et al.
   Copyright (C) 1997-2021 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
   <https://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>
#include <support/check.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];

/* Used to compare walk traces between the two implementations.  */
struct walk_trace_element
{
  const void *key;
  VISIT which;
  int depth;
};
#define DYNARRAY_STRUCT walk_trace_list
#define DYNARRAY_ELEMENT struct walk_trace_element
#define DYNARRAY_PREFIX walk_trace_
#define DYNARRAY_INITIAL_SIZE 0
#include <malloc/dynarray-skeleton.c>
static struct walk_trace_list walk_trace;

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

struct twalk_with_twalk_r_closure
{
  void (*action) (const void *, VISIT, int);
  int depth;
};

static void
twalk_with_twalk_r_action (const void *nodep, VISIT which, void *closure0)
{
  struct twalk_with_twalk_r_closure *closure = closure0;

  switch (which)
    {
    case leaf:
      closure->action (nodep, which, closure->depth);
      break;
    case preorder:
      closure->action (nodep, which, closure->depth);
      ++closure->depth;
      break;
    case postorder:
      /* The preorder action incremented the depth.  */
      closure->action (nodep, which, closure->depth - 1);
      break;
    case endorder:
      --closure->depth;
      closure->action (nodep, which, closure->depth);
      break;
    }
}

static void
twalk_with_twalk_r (const void *root,
		    void (*action) (const void *, VISIT, int))
{
  struct twalk_with_twalk_r_closure closure = { action, 0 };
  twalk_r (root, twalk_with_twalk_r_action, &closure);
  TEST_COMPARE (closure.depth, 0);
}

static void
walk_action (const void *nodep, const VISIT which, const int depth)
{
  int key = **(int **) nodep;

  walk_trace_add (&walk_trace,
		  (struct walk_trace_element) { nodep, which, depth });

  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_with (void *root, int expected_count,
		void (*walk) (const void *,
			      void (*) (const void *, VISIT, int)))
{
  int i;

  memset (z, 0, sizeof z);
  max_depth = 0;

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

static void
walk_tree (void *root, int expected_count)
{
  walk_trace_clear (&walk_trace);
  walk_tree_with (root, expected_count, twalk);
  TEST_VERIFY (!walk_trace_has_failed (&walk_trace));
  size_t first_list_size;
  struct walk_trace_element *first_list
    = walk_trace_finalize (&walk_trace, &first_list_size);
  TEST_VERIFY_EXIT (first_list != NULL);

  walk_tree_with (root, expected_count, twalk_with_twalk_r);
  TEST_VERIFY (!walk_trace_has_failed (&walk_trace));

  /* Compare the two traces.  */
  TEST_COMPARE (first_list_size, walk_trace_size (&walk_trace));
  for (size_t i = 0; i < first_list_size && i < walk_trace_size (&walk_trace);
       ++i)
    {
      TEST_VERIFY (first_list[i].key == walk_trace_at (&walk_trace, i)->key);
      TEST_COMPARE (first_list[i].which, walk_trace_at (&walk_trace, i)->which);
      TEST_COMPARE (first_list[i].depth, walk_trace_at (&walk_trace, i)->depth);
    }

  walk_trace_free (&walk_trace);
}

/* 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 TEST_FUNCTION do_test ()
#include "../test-skeleton.c"
Commit	Line	Data
993b3242	1	/* Test program for tsearch et al.
2b778ceb	2	Copyright (C) 1997-2021 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	16	License along with the GNU C Library; if not, see
5a82c748	17	<https://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>
7b807a35	28	#include <support/check.h>
993b3242 UD	29
	30	#define SEED 0
	31	#define BALANCED 1
	32	#define PASSES 100
	33
	34	#if BALANCED
	35	#include <math.h>
	36	#define SIZE 1000
	37	#else
	38	#define SIZE 100
	39	#endif
	40
	41	enum order
	42	{
	43	ascending,
	44	descending,
	45	randomorder
	46	};
	47
	48	enum action
	49	{
	50	build,
	51	build_and_del,
	52	delete,
	53	find
	54	};
	55
	56	/* Set to 1 if a test is flunked. */
	57	static int error = 0;
	58
	59	/* The keys we add to the tree. */
	60	static int x[SIZE];
	61
	62	/* Pointers into the key array, possibly permutated, to define an order
	63	for insertion/removal. */
	64	static int y[SIZE];
	65
	66	/* Flags set for each element visited during a tree walk. */
	67	static int z[SIZE];
	68
	69	/* Depths for all the elements, to check that the depth is constant for
	70	all three visits. */
	71	static int depths[SIZE];
	72
	73	/* Maximum depth during a tree walk. */
	74	static int max_depth;
	75
06f6ca90 UD	76	static int stack_align_check[2];
06f6ca90 UD	77
7b807a35 FW	78	/* Used to compare walk traces between the two implementations. */
	79	struct walk_trace_element
	80	{
	81	const void *key;
	82	VISIT which;
	83	int depth;
	84	};
	85	#define DYNARRAY_STRUCT walk_trace_list
	86	#define DYNARRAY_ELEMENT struct walk_trace_element
	87	#define DYNARRAY_PREFIX walk_trace_
	88	#define DYNARRAY_INITIAL_SIZE 0
	89	#include <malloc/dynarray-skeleton.c>
	90	static struct walk_trace_list walk_trace;
	91
993b3242 UD	92	/* Compare two keys. */
	93	static int
	94	cmp_fn (const void a, const void b)
	95	{
06f6ca90 UD	96	if (!stack_align_check[0])
06f6ca90 UD	97	stack_align_check[0] = TEST_STACK_ALIGN () ? -1 : 1;
993b3242 UD	98	return (const int ) a - (const int ) b;
	99	}
	100
	101	/* Permute an array of integers. */
	102	static void
	103	memfry (int *string)
	104	{
	105	int i;
	106
	107	for (i = 0; i < SIZE; ++i)
	108	{
	109	int32_t j;
	110	int c;
	111
	112	j = random () % SIZE;
	113
	114	c = string[i];
	115	string[i] = string[j];
	116	string[j] = c;
	117	}
	118	}
	119
7b807a35 FW	120	struct twalk_with_twalk_r_closure
	121	{
	122	void (action) (const void , VISIT, int);
	123	int depth;
	124	};
	125
	126	static void
	127	twalk_with_twalk_r_action (const void nodep, VISIT which, void closure0)
	128	{
	129	struct twalk_with_twalk_r_closure *closure = closure0;
	130
	131	switch (which)
	132	{
	133	case leaf:
	134	closure->action (nodep, which, closure->depth);
	135	break;
	136	case preorder:
	137	closure->action (nodep, which, closure->depth);
	138	++closure->depth;
	139	break;
	140	case postorder:
	141	/* The preorder action incremented the depth. */
	142	closure->action (nodep, which, closure->depth - 1);
	143	break;
	144	case endorder:
	145	--closure->depth;
	146	closure->action (nodep, which, closure->depth);
	147	break;
	148	}
	149	}
	150
	151	static void
	152	twalk_with_twalk_r (const void *root,
	153	void (action) (const void , VISIT, int))
	154	{
	155	struct twalk_with_twalk_r_closure closure = { action, 0 };
	156	twalk_r (root, twalk_with_twalk_r_action, &closure);
	157	TEST_COMPARE (closure.depth, 0);
	158	}
	159
993b3242 UD	160	static void
	161	walk_action (const void *nodep, const VISIT which, const int depth)
	162	{
	163	int key = (int ) nodep;
	164
7b807a35 FW	165	walk_trace_add (&walk_trace,
	166	(struct walk_trace_element) { nodep, which, depth });
	167
06f6ca90 UD	168	if (!stack_align_check[1])
	169	stack_align_check[1] = TEST_STACK_ALIGN () ? -1 : 1;
	170
993b3242 UD	171	if (depth > max_depth)
	172	max_depth = depth;
	173	if (which == leaf \|\| which == preorder)
	174	{
	175	++z[key];
	176	depths[key] = depth;
	177	}
	178	else
	179	{
	180	if (depths[key] != depth)
	181	{
	182	fputs ("Depth for one element is not constant during tree walk.\n",
5929563f	183	stdout);
993b3242 UD	184	}
	185	}
	186	}
	187
	188	static void
7b807a35 FW	189	walk_tree_with (void *root, int expected_count,
	190	void (walk) (const void ,
	191	void () (const void , VISIT, int)))
993b3242 UD	192	{
	193	int i;
	194
	195	memset (z, 0, sizeof z);
	196	max_depth = 0;
	197
7b807a35	198	walk (root, walk_action);
993b3242 UD	199	for (i = 0; i < expected_count; ++i)
	200	if (z[i] != 1)
	201	{
5929563f	202	fputs ("Node was not visited.\n", stdout);
993b3242 UD	203	error = 1;
	204	}
	205
	206	#if BALANCED
	207	if (max_depth > log (expected_count) * 2 + 2)
	208	#else
	209	if (max_depth > expected_count)
	210	#endif
	211	{
5929563f	212	fputs ("Depth too large during tree walk.\n", stdout);
993b3242 UD	213	error = 1;
	214	}
	215	}
	216
7b807a35 FW	217	static void
	218	walk_tree (void *root, int expected_count)
	219	{
	220	walk_trace_clear (&walk_trace);
	221	walk_tree_with (root, expected_count, twalk);
	222	TEST_VERIFY (!walk_trace_has_failed (&walk_trace));
	223	size_t first_list_size;
	224	struct walk_trace_element *first_list
	225	= walk_trace_finalize (&walk_trace, &first_list_size);
ac3da35d	226	TEST_VERIFY_EXIT (first_list != NULL);
7b807a35 FW	227
7b807a35 FW	228	walk_tree_with (root, expected_count, twalk_with_twalk_r);
ac3da35d	229	TEST_VERIFY (!walk_trace_has_failed (&walk_trace));
7b807a35 FW	230
	231	/* Compare the two traces. */
	232	TEST_COMPARE (first_list_size, walk_trace_size (&walk_trace));
	233	for (size_t i = 0; i < first_list_size && i < walk_trace_size (&walk_trace);
	234	++i)
	235	{
	236	TEST_VERIFY (first_list[i].key == walk_trace_at (&walk_trace, i)->key);
	237	TEST_COMPARE (first_list[i].which, walk_trace_at (&walk_trace, i)->which);
	238	TEST_COMPARE (first_list[i].depth, walk_trace_at (&walk_trace, i)->depth);
	239	}
	240
	241	walk_trace_free (&walk_trace);
	242	}
	243
993b3242 UD	244	/* Perform an operation on a tree. */
	245	static void
	246	mangle_tree (enum order how, enum action what, void **root, int lag)
	247	{
	248	int i;
	249
	250	if (how == randomorder)
	251	{
	252	for (i = 0; i < SIZE; ++i)
	253	y[i] = i;
	254	memfry (y);
	255	}
	256
	257	for (i = 0; i < SIZE + lag; ++i)
	258	{
	259	void *elem;
	260	int j, k;
	261
	262	switch (how)
	263	{
	264	case randomorder:
	265	if (i >= lag)
	266	k = y[i - lag];
	267	else
673c34e0 AJ	268	/* Ensure that the array index is within bounds. */
	269	k = y[(SIZE - i - 1 + lag) % SIZE];
	270	j = y[i % SIZE];
993b3242 UD	271	break;
	272
	273	case ascending:
	274	k = i - lag;
	275	j = i;
	276	break;
	277
	278	case descending:
	279	k = SIZE - i - 1 + lag;
	280	j = SIZE - i - 1;
	281	break;
	282
	283	default:
	284	/* This never should happen, but gcc isn't smart enough to
	285	recognize it. */
	286	abort ();
	287	}
	288
	289	switch (what)
	290	{
	291	case build_and_del:
	292	case build:
	293	if (i < SIZE)
	294	{
f671aeab	295	if (tfind (x + j, (void const ) root, cmp_fn) != NULL)
993b3242	296	{
5929563f	297	fputs ("Found element which is not in tree yet.\n", stdout);
993b3242 UD	298	error = 1;
	299	}
	300	elem = tsearch (x + j, root, cmp_fn);
	301	if (elem == 0
f671aeab	302	\|\| tfind (x + j, (void const ) root, cmp_fn) == NULL)
993b3242 UD	303	{
993b3242 UD	304	fputs ("Couldn't find element after it was added.\n",
5929563f	305	stdout);
993b3242 UD	306	error = 1;
	307	}
	308	}
	309
	310	if (what == build \|\| i < lag)
	311	break;
	312
	313	j = k;
	314	/* fall through */
	315
	316	case delete:
f671aeab	317	elem = tfind (x + j, (void const ) root, cmp_fn);
993b3242 UD	318	if (elem == NULL \|\| tdelete (x + j, root, cmp_fn) == NULL)
993b3242 UD	319	{
5929563f	320	fputs ("Error deleting element.\n", stdout);
993b3242 UD	321	error = 1;
	322	}
	323	break;
	324
	325	case find:
f671aeab	326	if (tfind (x + j, (void const ) root, cmp_fn) == NULL)
993b3242	327	{
5929563f	328	fputs ("Couldn't find element after it was added.\n", stdout);
993b3242 UD	329	error = 1;
	330	}
	331	break;
	332
	333	}
	334	}
	335	}
	336
	337
c1f41083 AS	338	static int
c1f41083 AS	339	do_test (void)
993b3242 UD	340	{
993b3242 UD	341	int total_error = 0;
621d9092	342	static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
993b3242 UD	343	void *root = NULL;
	344	int i, j;
	345
	346	initstate (SEED, state, 8);
	347
	348	for (i = 0; i < SIZE; ++i)
	349	x[i] = i;
	350
	351	/* Do this loop several times to get different permutations for the
	352	random case. */
5929563f	353	fputs ("Series I\n", stdout);
993b3242 UD	354	for (i = 0; i < PASSES; ++i)
993b3242 UD	355	{
5929563f	356	fprintf (stdout, "Pass %d... ", i + 1);
993b3242 UD	357	fflush (stdout);
	358	error = 0;
	359
	360	mangle_tree (ascending, build, &root, 0);
	361	mangle_tree (ascending, find, &root, 0);
	362	mangle_tree (descending, find, &root, 0);
	363	mangle_tree (randomorder, find, &root, 0);
	364	walk_tree (root, SIZE);
	365	mangle_tree (ascending, delete, &root, 0);
	366
	367	mangle_tree (ascending, build, &root, 0);
	368	walk_tree (root, SIZE);
	369	mangle_tree (descending, delete, &root, 0);
	370
	371	mangle_tree (ascending, build, &root, 0);
	372	walk_tree (root, SIZE);
	373	mangle_tree (randomorder, delete, &root, 0);
	374
	375	mangle_tree (descending, build, &root, 0);
	376	mangle_tree (ascending, find, &root, 0);
	377	mangle_tree (descending, find, &root, 0);
	378	mangle_tree (randomorder, find, &root, 0);
	379	walk_tree (root, SIZE);
	380	mangle_tree (descending, delete, &root, 0);
	381
	382	mangle_tree (descending, build, &root, 0);
	383	walk_tree (root, SIZE);
	384	mangle_tree (descending, delete, &root, 0);
	385
	386	mangle_tree (descending, build, &root, 0);
	387	walk_tree (root, SIZE);
	388	mangle_tree (randomorder, delete, &root, 0);
	389
	390	mangle_tree (randomorder, build, &root, 0);
	391	mangle_tree (ascending, find, &root, 0);
	392	mangle_tree (descending, find, &root, 0);
	393	mangle_tree (randomorder, find, &root, 0);
	394	walk_tree (root, SIZE);
	395	mangle_tree (randomorder, delete, &root, 0);
	396
	397	for (j = 1; j < SIZE; j *= 2)
	398	{
	399	mangle_tree (randomorder, build_and_del, &root, j);
	400	}
	401
5929563f	402	fputs (error ? " failed!\n" : " ok.\n", stdout);
993b3242 UD	403	total_error \|= error;
	404	}
	405
5929563f	406	fputs ("Series II\n", stdout);
993b3242 UD	407	for (i = 1; i < SIZE; i *= 2)
993b3242 UD	408	{
5929563f	409	fprintf (stdout, "For size %d... ", i);
993b3242 UD	410	fflush (stdout);
	411	error = 0;
	412
	413	mangle_tree (ascending, build_and_del, &root, i);
	414	mangle_tree (descending, build_and_del, &root, i);
	415	mangle_tree (ascending, build_and_del, &root, i);
	416	mangle_tree (descending, build_and_del, &root, i);
	417	mangle_tree (ascending, build_and_del, &root, i);
	418	mangle_tree (descending, build_and_del, &root, i);
	419	mangle_tree (ascending, build_and_del, &root, i);
	420	mangle_tree (descending, build_and_del, &root, i);
	421
5929563f	422	fputs (error ? " failed!\n" : " ok.\n", stdout);
993b3242 UD	423	total_error \|= error;
	424	}
	425
06f6ca90 UD	426	for (i = 0; i < 2; ++i)
	427	if (stack_align_check[i] == 0)
	428	{
	429	printf ("stack alignment check %d not run\n", i);
	430	total_error \|= 1;
	431	}
	432	else if (stack_align_check[i] != 1)
	433	{
	434	printf ("stack insufficiently aligned in check %d\n", i);
	435	total_error \|= 1;
	436	}
	437
993b3242 UD	438	return total_error;
993b3242 UD	439	}
c1f41083 AS	440
	441	#define TEST_FUNCTION do_test ()
	442	#include "../test-skeleton.c"