finish docs?

[pspp] / tests / libpspp / range-map-test.c

diff --git a/tests/libpspp/range-map-test.c b/tests/libpspp/range-map-test.c
index 2cb0ce66dd81c73177d9670b1f346a29d26d3c3b..5ac611f77aac84194134dad6826f22f6f26eb442 100644 (file)
--- a/tests/libpspp/range-map-test.c
+++ b/tests/libpspp/range-map-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 routines defined in
    range-map.c.  This test program aims to be as comprehensive as
 
 /* This is a test program for the routines defined in
    range-map.c.  This test program aims to be as comprehensive as


@@ -41,26 +39,22 @@
 
 #include "xalloc.h"
 \f
 
 #include "xalloc.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 ();
     }
 }


@@ -72,25 +66,25 @@ check_func (bool ok, int line)
 \f
 /* Swaps *A and *B. */
 static void
 \f
 /* 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 blocks in VALUES into the lexicographically
+/* Arranges the N blocks in VALUES into the lexicographically

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


@@ -98,39 +92,39 @@ 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;
   /* Disallow N values that overflow on 32-bit machines. */
   assert (n <= 12);
 {
   unsigned int value = 1;
   /* Disallow N values that overflow on 32-bit machines. */
   assert (n <= 12);

-  for (; n > 1; )
+  for (; n > 1;)

     value *= n--;
   return value;
 }
     value *= n--;
   return value;
 }


@@ -138,7 +132,7 @@ factorial (unsigned int n)
 /* Tests whether PARTS is a K-part integer composition of N.
    Returns true if so, false otherwise. */
 static bool UNUSED
 /* Tests whether PARTS is a K-part integer composition of N.
    Returns true if so, false otherwise. */
 static bool UNUSED

-is_k_composition (int n, int k, const int parts[]) 
+is_k_composition (int n, int k, const int parts[])

 {
   int sum;
   int i;
 {
   int sum;
   int i;


@@ -159,7 +153,7 @@ is_k_composition (int n, int k, const int parts[])
    already the greatest K-part composition of N (in which case
    PARTS is unaltered). */
 static bool
    already the greatest K-part composition of N (in which case
    PARTS is unaltered). */
 static bool

-next_k_composition (int n UNUSED, int k, int parts[]) 
+next_k_composition (int n UNUSED, int k, int parts[])

 {
   int x, i;
 
 {
   int x, i;
 


@@ -185,7 +179,7 @@ next_k_composition (int n UNUSED, int k, int parts[])
 /* Sets the K integers in PARTS to the lexicographically first
    K-part composition of N. */
 static void
 /* Sets the K integers in PARTS to the lexicographically first
    K-part composition of N. */
 static void

-first_k_composition (int n, int k, int parts[]) 
+first_k_composition (int n, int k, int parts[])

 {
   int i;
 
 {
   int i;
 


@@ -206,7 +200,7 @@ first_k_composition (int n, int k, int parts[])
    Returns true if successful, false if the set of compositions
    has been exhausted. */
 static bool
    Returns true if successful, false if the set of compositions
    has been exhausted. */
 static bool

-next_composition (int n, int *k, int parts[]) 
+next_composition (int n, int *k, int parts[])

 {
   if (*k >= 1 && next_k_composition (n, *k, parts))
     return true;
 {
   if (*k >= 1 && next_k_composition (n, *k, parts))
     return true;


@@ -227,13 +221,13 @@ struct element
   };
 
 static struct element *
   };
 
 static struct element *

-range_map_node_to_element (struct range_map_node *node) 
+range_map_node_to_element (struct range_map_node *node)

 {
   return range_map_data (node, struct element, node);
 }
 
 /* Element we expect to find. */
 {
   return range_map_data (node, struct element, node);
 }
 
 /* Element we expect to find. */

-struct expected_element 
+struct expected_element

   {
     int x;                      /* Primary value. */
     unsigned long int start;    /* Start of region. */
   {
     int x;                      /* Primary value. */
     unsigned long int start;    /* Start of region. */


@@ -243,37 +237,37 @@ struct expected_element
 /* Compares expected_element A and B and returns a strcmp()-type
    result. */
 static int
 /* Compares expected_element A and B and returns a strcmp()-type
    result. */
 static int

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

 {
   const struct expected_element *a = (const struct expected_element *) a_;
   const struct expected_element *b = (const struct expected_element *) b_;
   return a->start < b->start ? -1 : a->start > b->start;
 }
 
 {
   const struct expected_element *a = (const struct expected_element *) a_;
   const struct expected_element *b = (const struct expected_element *) b_;
   return a->start < b->start ? -1 : a->start > b->start;
 }
 

-/* Checks that RM contains the ELEM_CNT elements described by
+/* Checks that RM contains the ELEM_N elements described by

    ELEMENTS[]. */
 static void
 check_range_map (struct range_map *rm,
    ELEMENTS[]. */
 static void
 check_range_map (struct range_map *rm,

-                 struct expected_element elements[], size_t elem_cnt) 
+                 struct expected_element elements[], size_t n_elems)

 {
   struct expected_element *sorted;
   struct range_map_node *node;
   size_t i;
 
 {
   struct expected_element *sorted;
   struct range_map_node *node;
   size_t i;
 

-  sorted = xnmalloc (elem_cnt, sizeof *sorted);
-  memcpy (sorted, elements, elem_cnt * sizeof *elements);
-  qsort (sorted, elem_cnt, sizeof *sorted, compare_expected_element);
-  
-  check (range_map_is_empty (rm) == (elem_cnt == 0));
+  sorted = xnmalloc (n_elems, sizeof *sorted);
+  memcpy (sorted, elements, n_elems * sizeof *elements);
+  qsort (sorted, n_elems, sizeof *sorted, compare_expected_element);

 
 

-  for (i = 0; i < elem_cnt; i++) 
+  check (range_map_is_empty (rm) == (n_elems == 0));
+
+  for (i = 0; i < n_elems; i++)

     {
       struct expected_element *e = &sorted[i];
       unsigned long int position;
 
       /* Check that range_map_lookup finds all the positions
          within the element. */
     {
       struct expected_element *e = &sorted[i];
       unsigned long int position;
 
       /* Check that range_map_lookup finds all the positions
          within the element. */

-      for (position = e->start; position < e->end; position++) 
+      for (position = e->start; position < e->end; position++)

         {
           struct range_map_node *found = range_map_lookup (rm, position);
           check (found != NULL);
         {
           struct range_map_node *found = range_map_lookup (rm, position);
           check (found != NULL);


@@ -288,19 +282,19 @@ check_range_map (struct range_map *rm,
          range_map_lookup doesn't find any there. */
       if (e->start > 0 && (i == 0 || e[-1].end < e->start))
         check (range_map_lookup (rm, e->start - 1) == NULL);
          range_map_lookup doesn't find any there. */
       if (e->start > 0 && (i == 0 || e[-1].end < e->start))
         check (range_map_lookup (rm, e->start - 1) == NULL);

-      if (i == elem_cnt - 1 || e->end < e[1].start)
+      if (i == n_elems - 1 || e->end < e[1].start)

         check (range_map_lookup (rm, e->end) == NULL);
     }
 
   for (node = (rand () % 2 ? range_map_first (rm) : range_map_next (rm, NULL)),
          i = 0;
        node != NULL;
         check (range_map_lookup (rm, e->end) == NULL);
     }
 
   for (node = (rand () % 2 ? range_map_first (rm) : range_map_next (rm, NULL)),
          i = 0;
        node != NULL;

-       node = range_map_next (rm, node), i++) 
+       node = range_map_next (rm, node), i++)

     {
       struct expected_element *e = &sorted[i];
       check (range_map_node_to_element (node)->x == e->x);
     }
     {
       struct expected_element *e = &sorted[i];
       check (range_map_node_to_element (node)->x == e->x);
     }

-  check (i == elem_cnt);
+  check (i == n_elems);

 
   free (sorted);
 }
 
   free (sorted);
 }


@@ -309,44 +303,44 @@ check_range_map (struct range_map *rm,
    in all possible orders, up to a specified maximum overall
    range. */
 static void
    in all possible orders, up to a specified maximum overall
    range. */
 static void

-test_insert (void) 
+test_insert (void)

 {
   const int max_range = 7;
 {
   const int max_range = 7;

-  int cnt;
+  int n;

 
 

-  for (cnt = 1; cnt <= max_range; cnt++) 
+  for (n = 1; n <= max_range; n++)

     {
     {

-      unsigned int composition_cnt;
+      unsigned int n_compositions;

       struct expected_element *expected;
       int *widths;
       struct expected_element *expected;
       int *widths;

-      int elem_cnt;
+      int n_elems;

       int *order;
       struct element *elements;
       int *order;
       struct element *elements;

-      
-      expected = xnmalloc (cnt, sizeof *expected);
-      widths = xnmalloc (cnt, sizeof *widths);
-      order = xnmalloc (cnt, sizeof *order);
-      elements = xnmalloc (cnt, sizeof *elements);
-
-      elem_cnt = 0;
-      composition_cnt = 0;
-      while (next_composition (cnt, &elem_cnt, widths)) 
+
+      expected = xnmalloc (n, sizeof *expected);
+      widths = xnmalloc (n, sizeof *widths);
+      order = xnmalloc (n, sizeof *order);
+      elements = xnmalloc (n, sizeof *elements);
+
+      n_elems = 0;
+      n_compositions = 0;
+      while (next_composition (n, &n_elems, widths))

         {
           int i, j;
         {
           int i, j;

-          unsigned int permutation_cnt;
+          unsigned int n_permutations;

 
 

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

             order[i] = i;
 
             order[i] = i;
 

-          permutation_cnt = 0;
-          while (permutation_cnt == 0 || next_permutation (order, elem_cnt)) 
+          n_permutations = 0;
+          while (n_permutations == 0 || next_permutation (order, n_elems))

             {
               struct range_map rm;
 
             {
               struct range_map rm;
 

-              /* Inserts the elem_cnt elements with the given
+              /* Inserts the n_elems elements with the given

                  widths[] into T in the order given by order[]. */
               range_map_init (&rm);
                  widths[] into T in the order given by order[]. */
               range_map_init (&rm);

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

                 {
                   unsigned long int start, end;
                   int idx;
                 {
                   unsigned long int start, end;
                   int idx;


@@ -370,13 +364,13 @@ test_insert (void)
                   expected[i].end = end;
                   check_range_map (&rm, expected, i + 1);
                 }
                   expected[i].end = end;
                   check_range_map (&rm, expected, i + 1);
                 }

-              permutation_cnt++;
+              n_permutations++;

             }
             }

-          check (permutation_cnt == factorial (elem_cnt));
-          
-          composition_cnt++;
+          check (n_permutations == factorial (n_elems));
+
+          n_compositions++;

         }
         }

-      check (composition_cnt == 1 << (cnt - 1));
+      check (n_compositions == 1 << (n - 1));

 
       free (expected);
       free (widths);
 
       free (expected);
       free (widths);


@@ -388,37 +382,37 @@ test_insert (void)
 /* Tests deleting ranges from a range map in all possible orders,
    up to a specified maximum overall range. */
 static void
 /* Tests deleting ranges from a range map in all possible orders,
    up to a specified maximum overall range. */
 static void

-test_delete (int gap) 
+test_delete (int gap)

 {
   const int max_range = 7;
 {
   const int max_range = 7;

-  int cnt;
+  int n;

 
 

-  for (cnt = 1; cnt <= max_range; cnt++) 
+  for (n = 1; n <= max_range; n++)

     {
     {

-      unsigned int composition_cnt;
+      unsigned int n_compositions;

       struct expected_element *expected;
       int *widths;
       struct expected_element *expected;
       int *widths;

-      int elem_cnt;
+      int n_elems;

       int *order;
       struct element *elements;
       int *order;
       struct element *elements;

-      
-      expected = xnmalloc (cnt, sizeof *expected);
-      widths = xnmalloc (cnt, sizeof *widths);
-      order = xnmalloc (cnt, sizeof *order);
-      elements = xnmalloc (cnt, sizeof *elements);
-
-      elem_cnt = 0;
-      composition_cnt = 0;
-      while (next_composition (cnt, &elem_cnt, widths)) 
+
+      expected = xnmalloc (n, sizeof *expected);
+      widths = xnmalloc (n, sizeof *widths);
+      order = xnmalloc (n, sizeof *order);
+      elements = xnmalloc (n, sizeof *elements);
+
+      n_elems = 0;
+      n_compositions = 0;
+      while (next_composition (n, &n_elems, widths))

         {
           int i, j;
         {
           int i, j;

-          unsigned int permutation_cnt;
+          unsigned int n_permutations;

 
 

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

             order[i] = i;
 
             order[i] = i;
 

-          permutation_cnt = 0;
-          while (permutation_cnt == 0 || next_permutation (order, elem_cnt)) 
+          n_permutations = 0;
+          while (n_permutations == 0 || next_permutation (order, n_elems))

             {
               struct range_map rm;
               unsigned long int start;
             {
               struct range_map rm;
               unsigned long int start;


@@ -426,7 +420,7 @@ test_delete (int gap)
               /* Insert all the elements. */
               range_map_init (&rm);
               start = 0;
               /* Insert all the elements. */
               range_map_init (&rm);
               start = 0;

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

                 {
                   int width = widths[i] > gap ? widths[i] - gap : widths[i];
                   unsigned long int end = start + width;
                 {
                   int width = widths[i] > gap ? widths[i] - gap : widths[i];
                   unsigned long int end = start + width;


@@ -435,10 +429,10 @@ test_delete (int gap)
                   range_map_insert (&rm, start, end - start,
                                     &elements[i].node);
 
                   range_map_insert (&rm, start, end - start,
                                     &elements[i].node);
 

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

                     {
                     {

-                      assert (j < elem_cnt);
-                      if (order[j] == i) 
+                      assert (j < n_elems);
+                      if (order[j] == i)

                         {
                           expected[j].x = i;
                           expected[j].start = start;
                         {
                           expected[j].x = i;
                           expected[j].start = start;


@@ -446,25 +440,25 @@ test_delete (int gap)
                           break;
                         }
                     }
                           break;
                         }
                     }

-                  
+

                   start += widths[i];
                 }
                   start += widths[i];
                 }

-              check_range_map (&rm, expected, elem_cnt);
+              check_range_map (&rm, expected, n_elems);

 
               /* Delete the elements in the specified order. */
 
               /* Delete the elements in the specified order. */

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

                 {
                   range_map_delete (&rm, &elements[order[i]].node);
                 {
                   range_map_delete (&rm, &elements[order[i]].node);

-                  check_range_map (&rm, expected + i + 1, elem_cnt - i - 1);
+                  check_range_map (&rm, expected + i + 1, n_elems - i - 1);

                 }
 
                 }
 

-              permutation_cnt++;
+              n_permutations++;

             }
             }

-          check (permutation_cnt == factorial (elem_cnt));
-          
-          composition_cnt++;
+          check (n_permutations == factorial (n_elems));
+
+          n_compositions++;

         }
         }

-      check (composition_cnt == 1 << (cnt - 1));
+      check (n_compositions == 1 << (n - 1));

 
       free (expected);
       free (widths);
 
       free (expected);
       free (widths);


@@ -477,7 +471,7 @@ test_delete (int gap)
    ranges in all possible orders, up to a specified maximum
    overall range. */
 static void
    ranges in all possible orders, up to a specified maximum
    overall range. */
 static void

-test_delete_contiguous (void) 
+test_delete_contiguous (void)

 {
   test_delete (0);
 }
 {
   test_delete (0);
 }


@@ -486,30 +480,71 @@ test_delete_contiguous (void)
    sometimes separated by gaps in all possible orders, up to a
    specified maximum overall range. */
 static void
    sometimes separated by gaps in all possible orders, up to a
    specified maximum overall range. */
 static void

-test_delete_gaps (void) 
+test_delete_gaps (void)

 {
   test_delete (1);
 }
 \f
 /* Main program. */
 
 {
   test_delete (1);
 }
 \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",
+      "insert",
+      test_insert
+    },
+    {
+      "delete-contiguous",
+      "delete from contiguous ranges",
+      test_delete_contiguous
+    },
+    {
+      "delete-gaps",
+      "delete from ranges separated by gaps",
+      test_delete_gaps
+    },
+  };
+
+enum { N_TESTS = sizeof tests / sizeof *tests };

 
 int
 
 int

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

 {
 {

-  run_test (test_insert, "insert");
-  run_test (test_delete_contiguous, "delete from contiguous ranges");
-  run_test (test_delete_gaps, "delete from ranges separated by gaps");
-  putchar ('\n');
+  int i;

 
 

-  return 0;
+  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 range map library\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;
+    }

 }
 }