docs

[pspp] / tests / libpspp / bt-test.c

diff --git a/tests/libpspp/bt-test.c b/tests/libpspp/bt-test.c
index e0979dafbbde014d9039e5ce5918dd737a4f56f1..60438df20abcbe5fdc9b617ed7671f0dcd0e44e9 100644 (file)
--- a/tests/libpspp/bt-test.c
+++ b/tests/libpspp/bt-test.c
@@ -1,20 +1,18 @@
-/* PSPP - computes sample statistics.
-   Copyright (C) 2007 Free Software Foundation, Inc.
+/* PSPP - a program for statistical analysis.
+   Copyright (C) 2007, 2010 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 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 3 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.
+   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
 
    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., 51 Franklin Street, Fifth Floor, Boston, MA
-   02110-1301, USA. */
+   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

 
 /* This is a test program for the bt_* routines defined in bt.c.
    This test program aims to be as comprehensive as possible.
 
 /* This is a test program for the bt_* routines defined in bt.c.
    This test program aims to be as comprehensive as possible.


@@ -28,7 +26,6 @@
 
 #include <libpspp/bt.h>
 
 
 #include <libpspp/bt.h>
 

-#include <assert.h>

 #include <stdbool.h>
 #include <stddef.h>
 #include <stdint.h>
 #include <stdbool.h>
 #include <stddef.h>
 #include <stdint.h>


@@ -38,26 +35,22 @@
 
 #include <libpspp/compiler.h>
 \f
 
 #include <libpspp/compiler.h>
 \f

-/* Currently running test. */
-static const char *test_name;
-

 /* Exit with a failure code.
    (Place a breakpoint on this function while debugging.) */
 static void
 /* Exit with a failure code.
    (Place a breakpoint on this function while debugging.) */
 static void

-check_die (void) 
+check_die (void)

 {
 {

-  exit (EXIT_FAILURE);   
+  exit (EXIT_FAILURE);

 }
 
 /* If OK is not true, prints a message about failure on the
    current source file and the given LINE and terminates. */
 static void
 }
 
 /* If OK is not true, prints a message about failure on the
    current source file and the given LINE and terminates. */
 static void

-check_func (bool ok, int line) 
+check_func (bool ok, int line)

 {
 {

-  if (!ok) 
+  if (!ok)

     {
     {

-      printf ("Check failed in %s test at %s, line %d\n",
-              test_name, __FILE__, line);
+      fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);

       check_die ();
     }
 }
       check_die ();
     }
 }


@@ -78,9 +71,9 @@ xalloc_die (void)
 
 /* Allocates and returns N bytes of memory. */
 static void *
 
 /* Allocates and returns N bytes of memory. */
 static void *

-xmalloc (size_t n) 
+xmalloc (size_t n)

 {
 {

-  if (n != 0) 
+  if (n != 0)

     {
       void *p = malloc (n);
       if (p == NULL)
     {
       void *p = malloc (n);
       if (p == NULL)


@@ -93,7 +86,7 @@ xmalloc (size_t n)
 }
 
 static void *
 }
 
 static void *

-xmemdup (const void *p, size_t n) 
+xmemdup (const void *p, size_t n)

 {
   void *q = xmalloc (n);
   memcpy (q, p, n);
 {
   void *q = xmalloc (n);
   memcpy (q, p, n);


@@ -102,7 +95,7 @@ xmemdup (const void *p, size_t n)
 
 /* Allocates and returns N * M bytes of memory. */
 static void *
 
 /* Allocates and returns N * M bytes of memory. */
 static void *

-xnmalloc (size_t n, size_t m) 
+xnmalloc (size_t n, size_t m)

 {
   if ((size_t) -1 / m <= n)
     xalloc_die ();
 {
   if ((size_t) -1 / m <= n)
     xalloc_die ();


@@ -124,14 +117,14 @@ static int aux_data;
 static struct element *
 bt_node_to_element (const struct bt_node *node)
 {
 static struct element *
 bt_node_to_element (const struct bt_node *node)
 {

-  return bt_data (node, struct element, node);
+  return BT_DATA (node, struct element, node);

 }
 
 /* Compares the `x' values in A and B and returns a strcmp-type
    return value.  Verifies that AUX points to aux_data. */
 static int
 compare_elements (const struct bt_node *a_, const struct bt_node *b_,
 }
 
 /* Compares the `x' values in A and B and returns a strcmp-type
    return value.  Verifies that AUX points to aux_data. */
 static int
 compare_elements (const struct bt_node *a_, const struct bt_node *b_,

-                  const void *aux) 
+                  const void *aux)

 {
   const struct element *a = bt_node_to_element (a_);
   const struct element *b = bt_node_to_element (b_);
 {
   const struct element *a = bt_node_to_element (a_);
   const struct element *b = bt_node_to_element (b_);


@@ -142,7 +135,7 @@ compare_elements (const struct bt_node *a_, const struct bt_node *b_,
 
 /* Compares A and B and returns a strcmp-type return value. */
 static int
 
 /* Compares A and B and returns a strcmp-type return value. */
 static int

-compare_ints_noaux (const void *a_, const void *b_) 
+compare_ints_noaux (const void *a_, const void *b_)

 {
   const int *a = a_;
   const int *b = b_;
 {
   const int *a = a_;
   const int *b = b_;


@@ -152,25 +145,25 @@ compare_ints_noaux (const void *a_, const void *b_)
 
 /* Swaps *A and *B. */
 static void
 
 /* Swaps *A and *B. */
 static void

-swap (int *a, int *b) 
+swap (int *a, int *b)

 {
   int t = *a;
   *a = *b;
   *b = t;
 }
 
 {
   int t = *a;
   *a = *b;
   *b = t;
 }
 

-/* Reverses the order of the CNT integers starting at VALUES. */
+/* Reverses the order of the N integers starting at VALUES. */

 static void
 static void

-reverse (int *values, size_t cnt)
+reverse (int *values, size_t n)

 {
   size_t i = 0;
 {
   size_t i = 0;

-  size_t j = cnt;
+  size_t j = n;

 
   while (j > i)
     swap (&values[i++], &values[--j]);
 }
 
 
   while (j > i)
     swap (&values[i++], &values[--j]);
 }
 

-/* Arranges the CNT elements in VALUES into the lexicographically
+/* Arranges the N elements in VALUES into the lexicographically

    next greater permutation.  Returns true if successful.
    If VALUES is already the lexicographically greatest
    permutation of its elements (i.e. ordered from greatest to
    next greater permutation.  Returns true if successful.
    If VALUES is already the lexicographically greatest
    permutation of its elements (i.e. ordered from greatest to


@@ -178,34 +171,34 @@ reverse (int *values, size_t cnt)
    permutation (i.e. ordered from smallest to largest) and
    returns false. */
 static bool
    permutation (i.e. ordered from smallest to largest) and
    returns false. */
 static bool

-next_permutation (int *values, size_t cnt)
+next_permutation (int *values, size_t n)

 {
 {

-  if (cnt > 0)
+  if (n > 0)

     {
     {

-      size_t i = cnt - 1;
-      while (i != 0) 
+      size_t i = n - 1;
+      while (i != 0)

         {
           i--;
           if (values[i] < values[i + 1])
             {
               size_t j;
         {
           i--;
           if (values[i] < values[i + 1])
             {
               size_t j;

-              for (j = cnt - 1; values[i] >= values[j]; j--)
+              for (j = n - 1; values[i] >= values[j]; j--)

                 continue;
               swap (values + i, values + j);
                 continue;
               swap (values + i, values + j);

-              reverse (values + (i + 1), cnt - (i + 1));
+              reverse (values + (i + 1), n - (i + 1));

               return true;
               return true;

-            } 
+            }

         }
         }

-      
-      reverse (values, cnt);
+
+      reverse (values, n);

     }
     }

-  
+

   return false;
 }
 
 /* Returns N!. */
 static unsigned int
   return false;
 }
 
 /* Returns N!. */
 static unsigned int

-factorial (unsigned int n) 
+factorial (unsigned int n)

 {
   unsigned int value = 1;
   while (n > 1)
 {
   unsigned int value = 1;
   while (n > 1)


@@ -213,19 +206,19 @@ factorial (unsigned int n)
   return value;
 }
 
   return value;
 }
 

-/* Randomly shuffles the CNT elements in ARRAY, each of which is
+/* Randomly shuffles the N elements in ARRAY, each of which is

    SIZE bytes in size. */
 static void
    SIZE bytes in size. */
 static void

-random_shuffle (void *array_, size_t cnt, size_t size)
+random_shuffle (void *array_, size_t n, size_t size)

 {
   char *array = array_;
   char *tmp = xmalloc (size);
   size_t i;
 
 {
   char *array = array_;
   char *tmp = xmalloc (size);
   size_t i;
 

-  for (i = 0; i < cnt; i++) 
+  for (i = 0; i < n; i++)

     {
     {

-      size_t j = rand () % (cnt - i) + i;
-      if (i != j) 
+      size_t j = rand () % (n - i) + i;
+      if (i != j)

         {
           memcpy (tmp, array + j * size, size);
           memcpy (array + j * size, array + i * size, size);
         {
           memcpy (tmp, array + j * size, size);
           memcpy (array + j * size, array + i * size, size);


@@ -238,9 +231,9 @@ random_shuffle (void *array_, size_t cnt, size_t size)
 
 /* Calculates floor(log(n)/log(sqrt(2))). */
 static int
 
 /* Calculates floor(log(n)/log(sqrt(2))). */
 static int

-calculate_h_alpha (size_t n) 
+calculate_h_alpha (size_t n)

 {
 {

-  size_t thresholds[] = 
+  size_t thresholds[] =

     {
       0, 2, 2, 3, 4, 6, 8, 12, 16, 23, 32, 46, 64, 91, 128, 182, 256, 363,
       512, 725, 1024, 1449, 2048, 2897, 4096, 5793, 8192, 11586, 16384,
     {
       0, 2, 2, 3, 4, 6, 8, 12, 16, 23, 32, 46, 64, 91, 128, 182, 256, 363,
       512, 725, 1024, 1449, 2048, 2897, 4096, 5793, 8192, 11586, 16384,


@@ -250,10 +243,10 @@ calculate_h_alpha (size_t n)
       94906266, 134217728, 189812532, 268435456, 379625063, 536870912,
       759250125, 1073741824, 1518500250, 2147483648, 3037000500,
     };
       94906266, 134217728, 189812532, 268435456, 379625063, 536870912,
       759250125, 1073741824, 1518500250, 2147483648, 3037000500,
     };

-  size_t threshold_cnt = sizeof thresholds / sizeof *thresholds;
+  size_t n_thresholds = sizeof thresholds / sizeof *thresholds;

   size_t i;
 
   size_t i;
 

-  for (i = 0; i < threshold_cnt; i++)
+  for (i = 0; i < n_thresholds; i++)

     if (thresholds[i] > n)
       break;
   return i - 1;
     if (thresholds[i] > n)
       break;
   return i - 1;


@@ -261,11 +254,11 @@ calculate_h_alpha (size_t n)
 
 /* Returns the height of the tree rooted at NODE. */
 static int
 
 /* Returns the height of the tree rooted at NODE. */
 static int

-get_height (struct bt_node *node) 
+get_height (struct bt_node *node)

 {
   if (node == NULL)
     return 0;
 {
   if (node == NULL)
     return 0;

-  else 
+  else

     {
       int left = get_height (node->down[0]);
       int right = get_height (node->down[1]);
     {
       int left = get_height (node->down[0]);
       int right = get_height (node->down[1]);


@@ -277,7 +270,7 @@ get_height (struct bt_node *node)
    its height is no more than h_alpha(count) + 1, where
    h_alpha(n) = floor(log(n)/log(1/alpha)). */
 static void
    its height is no more than h_alpha(count) + 1, where
    h_alpha(n) = floor(log(n)/log(1/alpha)). */
 static void

-check_balance (struct bt *bt) 
+check_balance (struct bt *bt)

 {
   /* In the notation of the Galperin and Rivest paper (and of
      CLR), the height of a tree is the number of edges in the
 {
   /* In the notation of the Galperin and Rivest paper (and of
      CLR), the height of a tree is the number of edges in the


@@ -288,20 +281,20 @@ check_balance (struct bt *bt)
   check (height <= max_height);
 }
 
   check (height <= max_height);
 }
 

-/* Checks that BT contains the CNT ints in DATA, that its
+/* Checks that BT contains the N ints in DATA, that its

    structure is correct, and that certain operations on BT
    produce the expected results. */
 static void
    structure is correct, and that certain operations on BT
    produce the expected results. */
 static void

-check_bt (struct bt *bt, const int data[], size_t cnt) 
+check_bt (struct bt *bt, const int data[], size_t n)

 {
   struct element e;
   size_t i;
   int *order;
 
 {
   struct element e;
   size_t i;
   int *order;
 

-  order = xmemdup (data, cnt * sizeof *data);
-  qsort (order, cnt, sizeof *order, compare_ints_noaux);
+  order = xmemdup (data, n * sizeof *data);
+  qsort (order, n, sizeof *order, compare_ints_noaux);

 
 

-  for (i = 0; i < cnt; i++)
+  for (i = 0; i < n; i++)

     {
       struct bt_node *p;
 
     {
       struct bt_node *p;
 


@@ -320,57 +313,57 @@ check_bt (struct bt *bt, const int data[], size_t cnt)
 
   check_balance (bt);
 
 
   check_balance (bt);
 

-  if (cnt == 0) 
+  if (n == 0)

     {
       check (bt_first (bt) == NULL);
       check (bt_last (bt) == NULL);
       check (bt_next (bt, NULL) == NULL);
       check (bt_prev (bt, NULL) == NULL);
     }
     {
       check (bt_first (bt) == NULL);
       check (bt_last (bt) == NULL);
       check (bt_next (bt, NULL) == NULL);
       check (bt_prev (bt, NULL) == NULL);
     }

-  else 
+  else

     {
       struct bt_node *p;
     {
       struct bt_node *p;

-  
-      for (p = bt_first (bt), i = 0; i < cnt; p = bt_next (bt, p), i++)
+
+      for (p = bt_first (bt), i = 0; i < n; p = bt_next (bt, p), i++)

         check (bt_node_to_element (p)->data == order[i]);
       check (p == NULL);
 
         check (bt_node_to_element (p)->data == order[i]);
       check (p == NULL);
 

-      for (p = bt_last (bt), i = 0; i < cnt; p = bt_prev (bt, p), i++)
-        check (bt_node_to_element (p)->data == order[cnt - i - 1]);
+      for (p = bt_last (bt), i = 0; i < n; p = bt_prev (bt, p), i++)
+        check (bt_node_to_element (p)->data == order[n - i - 1]);

       check (p == NULL);
     }
 
   free (order);
 }
 
       check (p == NULL);
     }
 
   free (order);
 }
 

-/* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
+/* Inserts the N values from 0 to N - 1 (inclusive) into an

    BT in the order specified by INSERTIONS, then deletes them in
    the order specified by DELETIONS, checking the BT's contents
    for correctness after each operation. */
 static void
 test_insert_delete (const int insertions[],
                     const int deletions[],
    BT in the order specified by INSERTIONS, then deletes them in
    the order specified by DELETIONS, checking the BT's contents
    for correctness after each operation. */
 static void
 test_insert_delete (const int insertions[],
                     const int deletions[],

-                    size_t cnt) 
+                    size_t n)

 {
   struct element *elements;
   struct bt bt;
   size_t i;
 {
   struct element *elements;
   struct bt bt;
   size_t i;

-  
-  elements = xnmalloc (cnt, sizeof *elements);
-  for (i = 0; i < cnt; i++)
+
+  elements = xnmalloc (n, sizeof *elements);
+  for (i = 0; i < n; i++)

     elements[i].data = i;
 
   bt_init (&bt, compare_elements, &aux_data);
   check_bt (&bt, NULL, 0);
     elements[i].data = i;
 
   bt_init (&bt, compare_elements, &aux_data);
   check_bt (&bt, NULL, 0);

-  for (i = 0; i < cnt; i++)
+  for (i = 0; i < n; i++)

     {
       check (bt_insert (&bt, &elements[insertions[i]].node) == NULL);
       check_bt (&bt, insertions, i + 1);
     }
     {
       check (bt_insert (&bt, &elements[insertions[i]].node) == NULL);
       check_bt (&bt, insertions, i + 1);
     }

-  for (i = 0; i < cnt; i++)
+  for (i = 0; i < n; i++)

     {
       bt_delete (&bt, &elements[deletions[i]].node);
     {
       bt_delete (&bt, &elements[deletions[i]].node);

-      check_bt (&bt, deletions + i + 1, cnt - i - 1);
+      check_bt (&bt, deletions + i + 1, n - i - 1);

     }
 
   free (elements);
     }
 
   free (elements);


@@ -380,40 +373,40 @@ test_insert_delete (const int insertions[],
    removes them in each possible order, up to a specified maximum
    size. */
 static void
    removes them in each possible order, up to a specified maximum
    size. */
 static void

-test_insert_any_remove_any (void) 
+test_insert_any_remove_any (void)

 {
   const int max_elems = 5;
 {
   const int max_elems = 5;

-  int cnt;
+  int n;

 
 

-  for (cnt = 0; cnt <= max_elems; cnt++) 
+  for (n = 0; n <= max_elems; n++)

     {
       int *insertions, *deletions;
     {
       int *insertions, *deletions;

-      unsigned int ins_perm_cnt;
+      unsigned int ins_n_perms;

       int i;
 
       int i;
 

-      insertions = xnmalloc (cnt, sizeof *insertions);
-      deletions = xnmalloc (cnt, sizeof *deletions);
-      for (i = 0; i < cnt; i++) 
+      insertions = xnmalloc (n, sizeof *insertions);
+      deletions = xnmalloc (n, sizeof *deletions);
+      for (i = 0; i < n; i++)

         insertions[i] = i;
 
         insertions[i] = i;
 

-      for (ins_perm_cnt = 0;
-           ins_perm_cnt == 0 || next_permutation (insertions, cnt);
-           ins_perm_cnt++) 
+      for (ins_n_perms = 0;
+           ins_n_perms == 0 || next_permutation (insertions, n);
+           ins_n_perms++)

         {
         {

-          unsigned int del_perm_cnt;
+          unsigned int del_n_perms;

           int i;
 
           int i;
 

-          for (i = 0; i < cnt; i++) 
+          for (i = 0; i < n; i++)

             deletions[i] = i;
 
             deletions[i] = i;
 

-          for (del_perm_cnt = 0;
-               del_perm_cnt == 0 || next_permutation (deletions, cnt);
-               del_perm_cnt++) 
-            test_insert_delete (insertions, deletions, cnt);
+          for (del_n_perms = 0;
+               del_n_perms == 0 || next_permutation (deletions, n);
+               del_n_perms++)
+            test_insert_delete (insertions, deletions, n);

 
 

-          check (del_perm_cnt == factorial (cnt));
+          check (del_n_perms == factorial (n));

         }
         }

-      check (ins_perm_cnt == factorial (cnt));
+      check (ins_n_perms == factorial (n));

 
       free (insertions);
       free (deletions);
 
       free (insertions);
       free (deletions);


@@ -424,26 +417,26 @@ test_insert_any_remove_any (void)
    removes them in the same order, up to a specified maximum
    size. */
 static void
    removes them in the same order, up to a specified maximum
    size. */
 static void

-test_insert_any_remove_same (void) 
+test_insert_any_remove_same (void)

 {
   const int max_elems = 7;
 {
   const int max_elems = 7;

-  int cnt;
+  int n;

 
 

-  for (cnt = 0; cnt <= max_elems; cnt++) 
+  for (n = 0; n <= max_elems; n++)

     {
       int *values;
     {
       int *values;

-      unsigned int permutation_cnt;
+      unsigned int n_permutations;

       int i;
 
       int i;
 

-      values = xnmalloc (cnt, sizeof *values);
-      for (i = 0; i < cnt; i++) 
+      values = xnmalloc (n, sizeof *values);
+      for (i = 0; i < n; i++)

         values[i] = i;
 
         values[i] = i;
 

-      for (permutation_cnt = 0;
-           permutation_cnt == 0 || next_permutation (values, cnt);
-           permutation_cnt++)
-        test_insert_delete (values, values, cnt);
-      check (permutation_cnt == factorial (cnt));
+      for (n_permutations = 0;
+           n_permutations == 0 || next_permutation (values, n);
+           n_permutations++)
+        test_insert_delete (values, values, n);
+      check (n_permutations == factorial (n));

 
       free (values);
     }
 
       free (values);
     }


@@ -453,32 +446,32 @@ test_insert_any_remove_same (void)
    removes them in reverse order, up to a specified maximum
    size. */
 static void
    removes them in reverse order, up to a specified maximum
    size. */
 static void

-test_insert_any_remove_reverse (void) 
+test_insert_any_remove_reverse (void)

 {
   const int max_elems = 7;
 {
   const int max_elems = 7;

-  int cnt;
+  int n;

 
 

-  for (cnt = 0; cnt <= max_elems; cnt++) 
+  for (n = 0; n <= max_elems; n++)

     {
       int *insertions, *deletions;
     {
       int *insertions, *deletions;

-      unsigned int permutation_cnt;
+      unsigned int n_permutations;

       int i;
 
       int i;
 

-      insertions = xnmalloc (cnt, sizeof *insertions);
-      deletions = xnmalloc (cnt, sizeof *deletions);
-      for (i = 0; i < cnt; i++) 
+      insertions = xnmalloc (n, sizeof *insertions);
+      deletions = xnmalloc (n, sizeof *deletions);
+      for (i = 0; i < n; i++)

         insertions[i] = i;
 
         insertions[i] = i;
 

-      for (permutation_cnt = 0;
-           permutation_cnt == 0 || next_permutation (insertions, cnt);
-           permutation_cnt++) 
+      for (n_permutations = 0;
+           n_permutations == 0 || next_permutation (insertions, n);
+           n_permutations++)

         {
         {

-          memcpy (deletions, insertions, sizeof *insertions * cnt);
-          reverse (deletions, cnt);
-          
-          test_insert_delete (insertions, deletions, cnt); 
+          memcpy (deletions, insertions, sizeof *insertions * n);
+          reverse (deletions, n);
+
+          test_insert_delete (insertions, deletions, n);

         }
         }

-      check (permutation_cnt == factorial (cnt));
+      check (n_permutations == factorial (n));

 
       free (insertions);
       free (deletions);
 
       free (insertions);
       free (deletions);


@@ -487,31 +480,31 @@ test_insert_any_remove_reverse (void)
 
 /* Inserts and removes values in an BT in random orders. */
 static void
 
 /* Inserts and removes values in an BT in random orders. */
 static void

-test_random_sequence (void) 
+test_random_sequence (void)

 {
   const int max_elems = 128;
   const int max_trials = 8;
 {
   const int max_elems = 128;
   const int max_trials = 8;

-  int cnt;
+  int n;

 
 

-  for (cnt = 0; cnt <= max_elems; cnt += 2) 
+  for (n = 0; n <= max_elems; n += 2)

     {
       int *insertions, *deletions;
       int trial;
       int i;
 
     {
       int *insertions, *deletions;
       int trial;
       int i;
 

-      insertions = xnmalloc (cnt, sizeof *insertions);
-      deletions = xnmalloc (cnt, sizeof *deletions);
-      for (i = 0; i < cnt; i++) 
+      insertions = xnmalloc (n, sizeof *insertions);
+      deletions = xnmalloc (n, sizeof *deletions);
+      for (i = 0; i < n; i++)

         insertions[i] = i;
         insertions[i] = i;

-      for (i = 0; i < cnt; i++) 
+      for (i = 0; i < n; i++)

         deletions[i] = i;
 
         deletions[i] = i;
 

-      for (trial = 0; trial < max_trials; trial++) 
+      for (trial = 0; trial < max_trials; trial++)

         {
         {

-          random_shuffle (insertions, cnt, sizeof *insertions);
-          random_shuffle (deletions, cnt, sizeof *deletions);
-      
-          test_insert_delete (insertions, deletions, cnt); 
+          random_shuffle (insertions, n, sizeof *insertions);
+          random_shuffle (deletions, n, sizeof *deletions);
+
+          test_insert_delete (insertions, deletions, n);

         }
 
       free (insertions);
         }
 
       free (insertions);


@@ -521,7 +514,7 @@ test_random_sequence (void)
 
 /* Inserts elements into an BT in ascending order. */
 static void
 
 /* Inserts elements into an BT in ascending order. */
 static void

-test_insert_ordered (void) 
+test_insert_ordered (void)

 {
   const int max_elems = 1024;
   struct element *elements;
 {
   const int max_elems = 1024;
   struct element *elements;


@@ -532,7 +525,7 @@ test_insert_ordered (void)
   bt_init (&bt, compare_elements, &aux_data);
   elements = xnmalloc (max_elems, sizeof *elements);
   values = xnmalloc (max_elems, sizeof *values);
   bt_init (&bt, compare_elements, &aux_data);
   elements = xnmalloc (max_elems, sizeof *elements);
   values = xnmalloc (max_elems, sizeof *values);

-  for (i = 0; i < max_elems; i++) 
+  for (i = 0; i < max_elems; i++)

     {
       values[i] = elements[i].data = i;
       check (bt_insert (&bt, &elements[i].node) == NULL);
     {
       values[i] = elements[i].data = i;
       check (bt_insert (&bt, &elements[i].node) == NULL);


@@ -544,7 +537,7 @@ test_insert_ordered (void)
 
 /* Tests bt_find_ge and bt_find_le. */
 static void
 
 /* Tests bt_find_ge and bt_find_le. */
 static void

-test_find_ge_le (void) 
+test_find_ge_le (void)

 {
   const int max_elems = 10;
   struct element *elements;
 {
   const int max_elems = 10;
   struct element *elements;


@@ -553,32 +546,32 @@ test_find_ge_le (void)
 
   elements = xnmalloc (max_elems, sizeof *elements);
   values = xnmalloc (max_elems, sizeof *values);
 
   elements = xnmalloc (max_elems, sizeof *elements);
   values = xnmalloc (max_elems, sizeof *values);

-  for (inc_pat = 0; inc_pat < (1u << max_elems); inc_pat++) 
+  for (inc_pat = 0; inc_pat < (1u << max_elems); inc_pat++)

     {
       struct bt bt;
     {
       struct bt bt;

-      int elem_cnt = 0;
+      int n_elems = 0;

       int i;
 
       /* Insert the values in the pattern into BT. */
       bt_init (&bt, compare_elements, &aux_data);
       for (i = 0; i < max_elems; i++)
       int i;
 
       /* Insert the values in the pattern into BT. */
       bt_init (&bt, compare_elements, &aux_data);
       for (i = 0; i < max_elems; i++)

-        if (inc_pat & (1u << i)) 
+        if (inc_pat & (1u << i))

           {
           {

-            values[elem_cnt] = elements[elem_cnt].data = i;
-            check (bt_insert (&bt, &elements[elem_cnt].node) == NULL);
-            elem_cnt++;
+            values[n_elems] = elements[n_elems].data = i;
+            check (bt_insert (&bt, &elements[n_elems].node) == NULL);
+            n_elems++;

           }
           }

-      check_bt (&bt, values, elem_cnt);
+      check_bt (&bt, values, n_elems);

 
       /* Try find_ge and find_le for each possible element value. */
 
       /* Try find_ge and find_le for each possible element value. */

-      for (i = -1; i <= max_elems; i++) 
+      for (i = -1; i <= max_elems; i++)

         {
           struct element tmp;
           struct bt_node *ge, *le;
           int j;
         {
           struct element tmp;
           struct bt_node *ge, *le;
           int j;

-          
+

           ge = le = NULL;
           ge = le = NULL;

-          for (j = 0; j < elem_cnt; j++) 
+          for (j = 0; j < n_elems; j++)

             {
               if (ge == NULL && values[j] >= i)
                 ge = &elements[j].node;
             {
               if (ge == NULL && values[j] >= i)
                 ge = &elements[j].node;


@@ -598,7 +591,7 @@ test_find_ge_le (void)
 /* Inserts elements into an BT, then moves the nodes around in
    memory. */
 static void
 /* Inserts elements into an BT, then moves the nodes around in
    memory. */
 static void

-test_moved (void) 
+test_moved (void)

 {
   const int max_elems = 128;
   struct element *e[2];
 {
   const int max_elems = 128;
   struct element *e[2];


@@ -612,13 +605,13 @@ test_moved (void)
   e[1] = xnmalloc (max_elems, sizeof *e[1]);
   values = xnmalloc (max_elems, sizeof *values);
   cur = 0;
   e[1] = xnmalloc (max_elems, sizeof *e[1]);
   values = xnmalloc (max_elems, sizeof *values);
   cur = 0;

-  for (i = 0; i < max_elems; i++) 
+  for (i = 0; i < max_elems; i++)

     {
       values[i] = e[cur][i].data = i;
       check (bt_insert (&bt, &e[cur][i].node) == NULL);
       check_bt (&bt, values, i + 1);
 
     {
       values[i] = e[cur][i].data = i;
       check (bt_insert (&bt, &e[cur][i].node) == NULL);
       check_bt (&bt, values, i + 1);
 

-      for (j = 0; j <= i; j++) 
+      for (j = 0; j <= i; j++)

         {
           e[!cur][j] = e[cur][j];
           bt_moved (&bt, &e[!cur][j].node);
         {
           e[!cur][j] = e[cur][j];
           bt_moved (&bt, &e[!cur][j].node);


@@ -636,29 +629,29 @@ static void
 test_changed (void)
 {
   const int max_elems = 6;
 test_changed (void)
 {
   const int max_elems = 6;

-  int cnt;
+  int n;

 
 

-  for (cnt = 0; cnt <= max_elems; cnt++) 
+  for (n = 0; n <= max_elems; n++)

     {
       int *values, *changed_values;
       struct element *elements;
     {
       int *values, *changed_values;
       struct element *elements;

-      unsigned int permutation_cnt;
+      unsigned int n_permutations;

       int i;
 
       int i;
 

-      values = xnmalloc (cnt, sizeof *values);
-      changed_values = xnmalloc (cnt, sizeof *changed_values);
-      elements = xnmalloc (cnt, sizeof *elements);
-      for (i = 0; i < cnt; i++) 
+      values = xnmalloc (n, sizeof *values);
+      changed_values = xnmalloc (n, sizeof *changed_values);
+      elements = xnmalloc (n, sizeof *elements);
+      for (i = 0; i < n; i++)

         values[i] = i;
 
         values[i] = i;
 

-      for (permutation_cnt = 0;
-           permutation_cnt == 0 || next_permutation (values, cnt);
-           permutation_cnt++) 
+      for (n_permutations = 0;
+           n_permutations == 0 || next_permutation (values, n);
+           n_permutations++)

         {
         {

-          for (i = 0; i < cnt; i++) 
+          for (i = 0; i < n; i++)

             {
               int j, k;
             {
               int j, k;

-              for (j = 0; j <= cnt; j++) 
+              for (j = 0; j <= n; j++)

                 {
                   struct bt bt;
                   struct bt_node *changed_retval;
                 {
                   struct bt bt;
                   struct bt_node *changed_retval;


@@ -666,37 +659,37 @@ test_changed (void)
                   bt_init (&bt, compare_elements, &aux_data);
 
                   /* Add to BT in order. */
                   bt_init (&bt, compare_elements, &aux_data);
 
                   /* Add to BT in order. */

-                  for (k = 0; k < cnt; k++) 
+                  for (k = 0; k < n; k++)

                     {
                       int n = values[k];
                       elements[n].data = n;
                     {
                       int n = values[k];
                       elements[n].data = n;

-                      check (bt_insert (&bt, &elements[n].node) == NULL); 
+                      check (bt_insert (&bt, &elements[n].node) == NULL);

                     }
                     }

-                  check_bt (&bt, values, cnt);
+                  check_bt (&bt, values, n);

 
                   /* Change value i to j. */
                   elements[i].data = j;
 
                   /* Change value i to j. */
                   elements[i].data = j;

-                  for (k = 0; k < cnt; k++)
+                  for (k = 0; k < n; k++)

                     changed_values[k] = k;
                   changed_retval = bt_changed (&bt, &elements[i].node);
                     changed_values[k] = k;
                   changed_retval = bt_changed (&bt, &elements[i].node);

-                  if (i != j && j < cnt)
+                  if (i != j && j < n)

                     {
                       /* Will cause duplicate. */
                       check (changed_retval == &elements[j].node);
                     {
                       /* Will cause duplicate. */
                       check (changed_retval == &elements[j].node);

-                      changed_values[i] = changed_values[cnt - 1];
-                      check_bt (&bt, changed_values, cnt - 1);
+                      changed_values[i] = changed_values[n - 1];
+                      check_bt (&bt, changed_values, n - 1);

                     }
                   else
                     {
                       /* Succeeds. */
                       check (changed_retval == NULL);
                       changed_values[i] = j;
                     }
                   else
                     {
                       /* Succeeds. */
                       check (changed_retval == NULL);
                       changed_values[i] = j;

-                      check_bt (&bt, changed_values, cnt);
+                      check_bt (&bt, changed_values, n);

                     }
                 }
                     }
                 }

-            } 
+            }

         }
         }

-      check (permutation_cnt == factorial (cnt));
+      check (n_permutations == factorial (n));

 
       free (values);
       free (changed_values);
 
       free (values);
       free (changed_values);


@@ -706,33 +699,89 @@ test_changed (void)
 \f
 /* Main program. */
 
 \f
 /* Main program. */
 

-/* Runs TEST_FUNCTION and prints a message about NAME. */
-static void
-run_test (void (*test_function) (void), const char *name) 
-{
-  test_name = name;
-  putchar ('.');
-  fflush (stdout);
-  test_function ();
-}
+struct test
+  {
+    const char *name;
+    const char *description;
+    void (*function) (void);
+  };
+
+static const struct test tests[] =
+  {
+    {
+      "insert-any-remove-any",
+      "insert any order, delete any order",
+      test_insert_any_remove_any
+    },
+    {
+      "insert-any-remove-same",
+      "insert any order, delete same order",
+      test_insert_any_remove_same
+    },
+    {
+      "insert-any-remove-reverse",
+      "insert any order, delete reverse order",
+      test_insert_any_remove_reverse
+    },
+    {
+      "random-sequence",
+      "insert and delete in random sequence",
+      test_random_sequence
+    },
+    {
+      "insert-ordered",
+      "insert in ascending order",
+      test_insert_ordered
+    },
+    {
+      "find-ge-le",
+      "find_ge and find_le",
+      test_find_ge_le
+    },
+      {
+      "moved",
+      "move elements around in memory",
+      test_moved
+    },
+    {
+      "changed",
+      "change key data in nodes",
+      test_changed
+    }
+  };
+
+enum { N_TESTS = sizeof tests / sizeof *tests };

 
 int
 
 int

-main (void) 
+main (int argc, char *argv[])

 {
 {

-  run_test (test_insert_any_remove_any,
-            "insert any order, delete any order");
-  run_test (test_insert_any_remove_same,
-            "insert any order, delete same order");
-  run_test (test_insert_any_remove_reverse,
-            "insert any order, delete reverse order");
-  run_test (test_random_sequence,
-            "insert and delete in random sequence");
-  run_test (test_insert_ordered,
-            "insert in ascending order");
-  run_test (test_find_ge_le, "find_ge and find_le");
-  run_test (test_moved, "move elements around in memory");
-  run_test (test_changed, "change key data in nodes");
-  putchar ('\n');
-
-  return 0;
+  int i;
+
+  if (argc != 2)
+    {
+      fprintf (stderr, "exactly one argument required; use --help for help\n");
+      return EXIT_FAILURE;
+    }
+  else if (!strcmp (argv[1], "--help"))
+    {
+      printf ("%s: test balanced tree\n"
+              "usage: %s TEST-NAME\n"
+              "where TEST-NAME is one of the following:\n",
+              argv[0], argv[0]);
+      for (i = 0; i < N_TESTS; i++)
+        printf ("  %s\n    %s\n", tests[i].name, tests[i].description);
+      return 0;
+    }
+  else
+    {
+      for (i = 0; i < N_TESTS; i++)
+        if (!strcmp (argv[1], tests[i].name))
+          {
+            tests[i].function ();
+            return 0;
+          }
+
+      fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
+      return EXIT_FAILURE;
+    }

 }
 }