diff options
Diffstat (limited to 'avl-1.4.0/thread-test.c')
-rw-r--r-- | avl-1.4.0/thread-test.c | 142 |
1 files changed, 142 insertions, 0 deletions
diff --git a/avl-1.4.0/thread-test.c b/avl-1.4.0/thread-test.c new file mode 100644 index 0000000..20eead4 --- /dev/null +++ b/avl-1.4.0/thread-test.c @@ -0,0 +1,142 @@ +/* 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: +*/ |