/* libavl - manipulates AVL trees.
Copyright (C) 1998, 1999 Free Software Foundation, Inc.
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.
This program 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
General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.
The author may be contacted at <pfaffben@pilot.msu.edu> on the
Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA
through more mundane means. */
/* This is file thread-test.c in libavl. */
#if HAVE_CONFIG_H
#include <config.h>
#endif
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "avl.h"
#include "avlt.h"
#include "avltr.h"
#if __GNUC__ >= 2
#define unused __attribute__ ((unused))
#else
#define unused
#endif
/* Compare two integers A and B and return a strcmp()-type result. */
int
compare_ints (const void *a, const void *b, void unused *param)
{
return ((int) a) - ((int) b);
}
/* Arrange the N elements of ARRAY in random order. */
void
shuffle (int *array, int n)
{
int i;
for (i = 0; i < n; i++)
{
int j = i + rand () % (n - i);
int t = array[j];
array[j] = array[i];
array[i] = t;
}
}
/* Simple stress test procedure for the AVL tree threading/unthreading
routines. */
#define TREE_SIZE 1024
#define N_ITERATIONS 16
int
main (int argc, char **argv)
{
int array[TREE_SIZE];
int seed;
int iteration;
if (argc == 2)
seed = atoi (argv[1]);
else
seed = time (0) * 257 % 32768;
fputs ("Testing threading and unthreading...\n", stdout);
for (iteration = 1; iteration <= N_ITERATIONS; iteration++)
{
avl_tree *tree;
avl_traverser trav = AVL_TRAVERSER_INIT;
void **nodep = NULL;
void *node;
int i;
printf ("Iteration %4d/%4d: seed=%5d", iteration, N_ITERATIONS, seed);
fflush (stdout);
srand (seed++);
for (i = 0; i < TREE_SIZE; i++)
array[i] = i + 1;
shuffle (array, TREE_SIZE);
tree = avl_create (compare_ints, NULL);
for (i = 0; i < TREE_SIZE; i++)
avl_force_insert (tree, (void *) (array[i]));
shuffle (array, TREE_SIZE);
for (i = 0; i < TREE_SIZE; i++)
{
avlt_tree *t;
avltr_tree *tr;
avl_delete (tree, (void *) (array[i]));
while ((node = avl_traverse (tree, &trav)) != NULL);
t = avlt_thread (tree);
while ((nodep = avlt_next (t, nodep)) != NULL);
while ((nodep = avlt_prev (t, nodep)) != NULL);
avlt_unthread (t);
tr = avltr_thread (tree);
while ((nodep = avltr_next (tr, nodep)) != NULL);
avltr_unthread (tr);
while ((node = avl_traverse (tree, &trav)) != NULL);
if (i % 128 == 0)
{
putchar ('.');
fflush (stdout);
}
}
fputs (" good.\n", stdout);
avl_destroy (tree, NULL);
}
return 0;
}
/*
Local variables:
compile-command: "gcc -W -Wall -I. -o ./thread-test thread-test.c avl.c avlt.c avltr.c"
End:
*/
