X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=tests%2Flibpspp%2Fhmapx-test.c;h=42738b28caeb2325bcae1e4c216677a691c3c4ec;hb=339f1956cc72;hp=fc08ca6161040a89d1c54574cb6f6ec2866886fb;hpb=c3ac5a8af9c449072c7e872ca70a78c1755ae309;p=pspp

diff --git a/tests/libpspp/hmapx-test.c b/tests/libpspp/hmapx-test.c
index fc08ca6161..42738b28ca 100644
--- a/tests/libpspp/hmapx-test.c
+++ b/tests/libpspp/hmapx-test.c
@@ -1,5 +1,5 @@
 /* PSPP - a program for statistical analysis.
-   Copyright (C) 2007, 2008 Free Software Foundation, Inc.
+   Copyright (C) 2007, 2008, 2009, 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
@@ -27,7 +27,6 @@
 
 #include <libpspp/hmapx.h>
 
-#include <assert.h>
 #include <limits.h>
 #include <stdbool.h>
 #include <stddef.h>
@@ -38,9 +37,6 @@
 
 #include <libpspp/compiler.h>
 
-/* Currently running test. */
-static const char *test_name;
-
 /* If OK is not true, prints a message about failure on the
    current source file and the given LINE and terminates. */
 static void
@@ -48,8 +44,7 @@ check_func (bool ok, int line)
 {
   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);
       abort ();
     }
 }
@@ -208,13 +203,13 @@ random_shuffle (void *array_, size_t cnt, size_t size)
 typedef size_t hash_function (int data);
 
 static size_t
-identity_hash (int data) 
+identity_hash (int data)
 {
   return data;
 }
 
 static size_t
-constant_hash (int data UNUSED) 
+constant_hash (int data UNUSED)
 {
   return 0x12345678u;
 }
@@ -262,6 +257,7 @@ check_hmapx (struct hmapx *hmapx, const int data[], size_t cnt,
   size_t i, j;
   int *order;
 
+  check (hmapx_is_empty (hmapx) == (cnt == 0));
   check (hmapx_count (hmapx) == cnt);
   check (cnt <= hmapx_capacity (hmapx));
 
@@ -280,8 +276,8 @@ check_hmapx (struct hmapx *hmapx, const int data[], size_t cnt,
 
       count = 0;
       HMAPX_FOR_EACH_WITH_HASH (e, node, hash (order[i]), hmapx)
-        if (e->data == order[i]) 
-          count++; 
+        if (e->data == order[i])
+          count++;
 
       check (count == j - i);
     }
@@ -304,7 +300,7 @@ check_hmapx (struct hmapx *hmapx, const int data[], size_t cnt,
 
           check (hmapx_node_hash (p) == hash (e->data));
           for (j = 0; j < left; j++)
-            if (order[j] == e->data) 
+            if (order[j] == e->data)
               {
                 order[j] = order[--left];
                 goto next;
@@ -357,11 +353,11 @@ test_insert_delete (const int insertions[],
       check_hmapx (&hmapx, insertions, i + 1, hash);
 
       /* A series of insertions should not produce a shrinkable hmapx. */
-      if (i >= reserve) 
+      if (i >= reserve)
         {
           capacity = hmapx_capacity (&hmapx);
           hmapx_shrink (&hmapx);
-          check (capacity == hmapx_capacity (&hmapx)); 
+          check (capacity == hmapx_capacity (&hmapx));
         }
     }
   for (i = 0; i < cnt; i++)
@@ -387,7 +383,7 @@ test_insert_any_remove_any (hash_function *hash)
   for (cnt = 0; cnt <= max_elems; cnt++)
     {
       int *insertions, *deletions;
-      unsigned int ins_perm_cnt;
+      unsigned int ins_n_perms;
       int i;
 
       insertions = xnmalloc (cnt, sizeof *insertions);
@@ -395,24 +391,24 @@ test_insert_any_remove_any (hash_function *hash)
       for (i = 0; i < cnt; 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, cnt);
+           ins_n_perms++)
         {
-          unsigned int del_perm_cnt;
+          unsigned int del_n_perms;
           int i;
 
           for (i = 0; i < cnt; i++)
             deletions[i] = i;
 
-          for (del_perm_cnt = 0;
-               del_perm_cnt == 0 || next_permutation (deletions, cnt);
-               del_perm_cnt++)
+          for (del_n_perms = 0;
+               del_n_perms == 0 || next_permutation (deletions, cnt);
+               del_n_perms++)
             test_insert_delete (insertions, deletions, cnt, hash, 1);
 
-          check (del_perm_cnt == factorial (cnt));
+          check (del_n_perms == factorial (cnt));
         }
-      check (ins_perm_cnt == factorial (cnt));
+      check (ins_n_perms == factorial (cnt));
 
       free (insertions);
       free (deletions);
@@ -420,19 +416,19 @@ test_insert_any_remove_any (hash_function *hash)
 }
 
 static void
-test_insert_any_remove_any_random_hash (void) 
+test_insert_any_remove_any_random_hash (void)
 {
   test_insert_any_remove_any (random_hash);
 }
 
 static void
-test_insert_any_remove_any_identity_hash (void) 
+test_insert_any_remove_any_identity_hash (void)
 {
   test_insert_any_remove_any (identity_hash);
 }
 
 static void
-test_insert_any_remove_any_constant_hash (void) 
+test_insert_any_remove_any_constant_hash (void)
 {
   test_insert_any_remove_any (constant_hash);
 }
@@ -449,37 +445,37 @@ test_insert_any_remove_same (hash_function *hash)
   for (cnt = 0; cnt <= max_elems; cnt++)
     {
       int *values;
-      unsigned int permutation_cnt;
+      unsigned int n_permutations;
       int i;
 
       values = xnmalloc (cnt, sizeof *values);
       for (i = 0; i < cnt; 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, cnt);
+           n_permutations++)
         test_insert_delete (values, values, cnt, hash, cnt / 2);
-      check (permutation_cnt == factorial (cnt));
+      check (n_permutations == factorial (cnt));
 
       free (values);
     }
 }
 
 static void
-test_insert_any_remove_same_random_hash (void) 
+test_insert_any_remove_same_random_hash (void)
 {
   test_insert_any_remove_same (random_hash);
 }
 
 static void
-test_insert_any_remove_same_identity_hash (void) 
+test_insert_any_remove_same_identity_hash (void)
 {
   test_insert_any_remove_same (identity_hash);
 }
 
 static void
-test_insert_any_remove_same_constant_hash (void) 
+test_insert_any_remove_same_constant_hash (void)
 {
   test_insert_any_remove_same (constant_hash);
 }
@@ -496,7 +492,7 @@ test_insert_any_remove_reverse (hash_function *hash)
   for (cnt = 0; cnt <= max_elems; cnt++)
     {
       int *insertions, *deletions;
-      unsigned int permutation_cnt;
+      unsigned int n_permutations;
       int i;
 
       insertions = xnmalloc (cnt, sizeof *insertions);
@@ -504,16 +500,16 @@ test_insert_any_remove_reverse (hash_function *hash)
       for (i = 0; i < cnt; 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, cnt);
+           n_permutations++)
         {
           memcpy (deletions, insertions, sizeof *insertions * cnt);
           reverse (deletions, cnt);
 
           test_insert_delete (insertions, deletions, cnt, hash, cnt);
         }
-      check (permutation_cnt == factorial (cnt));
+      check (n_permutations == factorial (cnt));
 
       free (insertions);
       free (deletions);
@@ -573,19 +569,19 @@ test_random_sequence (int max_elems, hash_function *hash)
 }
 
 static void
-test_random_sequence_random_hash (void) 
+test_random_sequence_random_hash (void)
 {
   test_random_sequence (64, random_hash);
 }
 
 static void
-test_random_sequence_identity_hash (void) 
+test_random_sequence_identity_hash (void)
 {
   test_random_sequence (64, identity_hash);
 }
 
 static void
-test_random_sequence_constant_hash (void) 
+test_random_sequence_constant_hash (void)
 {
   test_random_sequence (32, constant_hash);
 }
@@ -612,7 +608,7 @@ test_insert_ordered (int max_elems, hash_function *hash)
       nodes[i] = hmapx_insert (&hmapx, &elements[i], hash (elements[i].data));
       check_hmapx (&hmapx, values, i + 1, hash);
 
-      if (hash == identity_hash) 
+      if (hash == identity_hash)
         {
           /* Check that every every hash bucket has (almost) the
              same number of nodes in it.  */
@@ -620,7 +616,7 @@ test_insert_ordered (int max_elems, hash_function *hash)
           int max = INT_MIN;
           int j;
 
-          for (j = 0; j <= hmapx.hmap.mask; j++) 
+          for (j = 0; j <= hmapx.hmap.mask; j++)
             {
               int count = 0;
               struct hmap_node *node;
@@ -706,19 +702,19 @@ test_moved (int max_elems, hash_function *hash)
 }
 
 static void
-test_moved_random_hash (void) 
+test_moved_random_hash (void)
 {
   test_moved (128, random_hash);
 }
 
 static void
-test_moved_identity_hash (void) 
+test_moved_identity_hash (void)
 {
   test_moved (128, identity_hash);
 }
 
 static void
-test_moved_constant_hash (void) 
+test_moved_constant_hash (void)
 {
   test_moved (32, constant_hash);
 }
@@ -736,7 +732,7 @@ test_changed (hash_function *hash)
       int *values, *changed_values;
       struct hmapx_node **nodes;
       struct element *elements;
-      unsigned int permutation_cnt;
+      unsigned int n_permutations;
       int i;
 
       values = xnmalloc (cnt, sizeof *values);
@@ -746,9 +742,9 @@ test_changed (hash_function *hash)
       for (i = 0; i < cnt; 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, cnt);
+           n_permutations++)
         {
           for (i = 0; i < cnt; i++)
             {
@@ -771,7 +767,7 @@ test_changed (hash_function *hash)
 
                   /* Change value i to j. */
                   elements[i].data = j;
-                  hmapx_changed (&hmapx, nodes[i], 
+                  hmapx_changed (&hmapx, nodes[i],
                                  hash (elements[i].data));
                   for (k = 0; k < cnt; k++)
                     changed_values[k] = k;
@@ -782,7 +778,7 @@ test_changed (hash_function *hash)
                 }
             }
         }
-      check (permutation_cnt == factorial (cnt));
+      check (n_permutations == factorial (cnt));
 
       free (values);
       free (changed_values);
@@ -823,7 +819,7 @@ test_change (hash_function *hash)
       struct hmapx_node **nodes;
       struct element *elements;
       struct element replacement;
-      unsigned int permutation_cnt;
+      unsigned int n_permutations;
       int i;
 
       values = xnmalloc (cnt, sizeof *values);
@@ -833,9 +829,9 @@ test_change (hash_function *hash)
       for (i = 0; i < cnt; 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, cnt);
+           n_permutations++)
         {
           for (i = 0; i < cnt; i++)
             {
@@ -868,7 +864,7 @@ test_change (hash_function *hash)
                 }
             }
         }
-      check (permutation_cnt == factorial (cnt));
+      check (n_permutations == factorial (cnt));
 
       free (values);
       free (changed_values);
@@ -896,7 +892,7 @@ test_change_constant_hash (void)
 }
 
 static void
-test_swap (int max_elems, hash_function *hash) 
+test_swap (int max_elems, hash_function *hash)
 {
   struct element *elements;
   int *values;
@@ -929,13 +925,51 @@ test_swap (int max_elems, hash_function *hash)
 }
 
 static void
-test_swap_random_hash (void) 
+test_swap_random_hash (void)
 {
   test_swap (128, random_hash);
 }
 
+/* Inserts elements into an HMAPX in ascending order, then clears the hash
+   table using hmapx_clear(). */
+static void
+test_clear (void)
+{
+  const int max_elems = 128;
+  struct element *elements;
+  struct hmapx_node **nodes;
+  int *values;
+  struct hmapx hmapx;
+  int cnt;
+
+  elements = xnmalloc (max_elems, sizeof *elements);
+  nodes = xnmalloc (max_elems, sizeof *nodes);
+  values = xnmalloc (max_elems, sizeof *values);
+
+  hmapx_init (&hmapx);
+  for (cnt = 0; cnt <= max_elems; cnt++)
+    {
+      int i;
+
+      for (i = 0; i < cnt; i++)
+        {
+          values[i] = elements[i].data = i;
+          nodes[i] = hmapx_insert (&hmapx, &elements[i],
+                                   random_hash (elements[i].data));
+          check_hmapx (&hmapx, values, i + 1, random_hash);
+        }
+      hmapx_clear (&hmapx);
+      check_hmapx (&hmapx, NULL, 0, random_hash);
+    }
+  hmapx_destroy (&hmapx);
+
+  free (elements);
+  free (nodes);
+  free (values);
+}
+
 static void
-test_destroy_null (void) 
+test_destroy_null (void)
 {
   hmapx_destroy (NULL);
 }
@@ -954,81 +988,189 @@ test_shrink_empty (void)
 
 /* 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-random-hash",
+      "insert any order, delete any order (random hash)",
+      test_insert_any_remove_any_random_hash
+    },
+    {
+      "insert-any-remove-any-identity-hash",
+      "insert any order, delete any order (identity hash)",
+      test_insert_any_remove_any_identity_hash
+    },
+    {
+      "insert-any-remove-any-constant-hash",
+      "insert any order, delete any order (constant hash)",
+      test_insert_any_remove_any_constant_hash
+    },
+    {
+      "insert-any-remove-same-random-hash",
+      "insert any order, delete same order (random hash)",
+      test_insert_any_remove_same_random_hash
+    },
+    {
+      "insert-any-remove-same-identity-hash",
+      "insert any order, delete same order (identity hash)",
+      test_insert_any_remove_same_identity_hash
+    },
+    {
+      "insert-any-remove-same-constant-hash",
+      "insert any order, delete same order (constant hash)",
+      test_insert_any_remove_same_constant_hash
+    },
+    {
+      "insert-any-remove-reverse-random-hash",
+      "insert any order, delete reverse order (random hash)",
+      test_insert_any_remove_reverse_random_hash
+    },
+    {
+      "insert-any-remove-reverse-identity-hash",
+      "insert any order, delete reverse order (identity hash)",
+      test_insert_any_remove_reverse_identity_hash
+    },
+    {
+      "insert-any-remove-reverse-constant-hash",
+      "insert any order, delete reverse order (constant hash)",
+      test_insert_any_remove_reverse_constant_hash
+    },
+    {
+      "random-sequence-random-hash",
+      "insert and delete in random sequence (random hash)",
+      test_random_sequence_random_hash
+    },
+    {
+      "random-sequence-identity-hash",
+      "insert and delete in random sequence (identity hash)",
+      test_random_sequence_identity_hash
+    },
+    {
+      "random-sequence-constant-hash",
+      "insert and delete in random sequence (constant hash)",
+      test_random_sequence_constant_hash
+    },
+    {
+      "insert-ordered-random-hash",
+      "insert in ascending order (random hash)",
+      test_insert_ordered_random_hash
+    },
+    {
+      "insert-ordered-identity-hash",
+      "insert in ascending order (identity hash)",
+      test_insert_ordered_identity_hash
+    },
+    {
+      "insert-ordered-constant-hash",
+      "insert in ascending order (constant hash)",
+      test_insert_ordered_constant_hash
+    },
+    {
+      "moved-random-hash",
+      "move elements around in memory (random hash)",
+      test_moved_random_hash
+    },
+    {
+      "moved-identity-hash",
+      "move elements around in memory (identity hash)",
+      test_moved_identity_hash
+    },
+    {
+      "moved-constant-hash",
+      "move elements around in memory (constant hash)",
+      test_moved_constant_hash
+    },
+    {
+      "changed-random-hash",
+      "change key data in nodes (random hash)",
+      test_changed_random_hash
+    },
+    {
+      "changed-identity-hash",
+      "change key data in nodes (identity hash)",
+      test_changed_identity_hash
+    },
+    {
+      "changed-constant-hash",
+      "change key data in nodes (constant hash)",
+      test_changed_constant_hash
+    },
+    {
+      "change-random-hash",
+      "change and move key data in nodes (random hash)",
+      test_change_random_hash
+    },
+    {
+      "change-identity-hash",
+      "change and move key data in nodes (identity hash)",
+      test_change_identity_hash
+    },
+    {
+      "change-constant-hash",
+      "change and move key data in nodes (constant hash)",
+      test_change_constant_hash
+    },
+    {
+      "swap-random-hash",
+      "test swapping tables",
+      test_swap_random_hash
+    },
+    {
+      "clear",
+      "test clearing hash table",
+      test_clear
+    },
+    {
+      "destroy-null",
+      "test destroying null table",
+      test_destroy_null
+    },
+    {
+      "shrink-empty",
+      "test shrinking an empty table",
+      test_shrink_empty
+    },
+  };
+
+enum { N_TESTS = sizeof tests / sizeof *tests };
 
 int
-main (void)
+main (int argc, char *argv[])
 {
-  run_test (test_insert_any_remove_any_random_hash,
-            "insert any order, delete any order (random hash)");
-  run_test (test_insert_any_remove_any_identity_hash,
-            "insert any order, delete any order (identity hash)");
-  run_test (test_insert_any_remove_any_constant_hash,
-            "insert any order, delete any order (constant hash)");
-
-  run_test (test_insert_any_remove_same_random_hash,
-            "insert any order, delete same order (random hash)");
-  run_test (test_insert_any_remove_same_identity_hash,
-            "insert any order, delete same order (identity hash)");
-  run_test (test_insert_any_remove_same_constant_hash,
-            "insert any order, delete same order (constant hash)");
-
-  run_test (test_insert_any_remove_reverse_random_hash,
-            "insert any order, delete reverse order (random hash)");
-  run_test (test_insert_any_remove_reverse_identity_hash,
-            "insert any order, delete reverse order (identity hash)");
-  run_test (test_insert_any_remove_reverse_constant_hash,
-            "insert any order, delete reverse order (constant hash)");
-
-  run_test (test_random_sequence_random_hash,
-            "insert and delete in random sequence (random hash)");
-  run_test (test_random_sequence_identity_hash,
-            "insert and delete in random sequence (identity hash)");
-  run_test (test_random_sequence_constant_hash,
-            "insert and delete in random sequence (constant hash)");
-
-  run_test (test_insert_ordered_random_hash,
-            "insert in ascending order (random hash)");
-  run_test (test_insert_ordered_identity_hash,
-            "insert in ascending order (identity hash)");
-  run_test (test_insert_ordered_constant_hash,
-            "insert in ascending order (constant hash)");
-
-  run_test (test_moved_random_hash,
-            "move elements around in memory (random hash)");
-  run_test (test_moved_identity_hash,
-            "move elements around in memory (identity hash)");
-  run_test (test_moved_constant_hash,
-            "move elements around in memory (constant hash)");
-
-  run_test (test_changed_random_hash,
-            "change key data in nodes (random hash)");
-  run_test (test_changed_identity_hash,
-            "change key data in nodes (identity hash)");
-  run_test (test_changed_constant_hash,
-            "change key data in nodes (constant hash)");
-
-  run_test (test_change_random_hash,
-            "change and move key data in nodes (random hash)");
-  run_test (test_change_identity_hash,
-            "change and move key data in nodes (identity hash)");
-  run_test (test_change_constant_hash,
-            "change and move key data in nodes (constant hash)");
-
-  run_test (test_swap_random_hash, "test swapping tables");
-
-  run_test (test_destroy_null, "test destroying null table");
-  run_test (test_shrink_empty, "test shrinking an empty table");
-
-  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 hash map of pointers\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;
+    }
 }