Re: [PATCH] hash-tests: new module (slightly improved)

[Eric Blake]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

According to Eric Blake on 6/17/2009 4:05 PM:
> Jim Meyering <jim <at> meyering.net> writes:
> 
>> Slight improvement.
>> This adds a key assertion at the end of the loop.
> 
> Looks good so far; how about also adding a test of hash_get_entries and 
> hash_do_for_each?

To make it easier to test all my other hash patches floating around, I
went ahead and pushed this after testing it on cygwin, with the following
modifications squashed in for even more exposure (and I may yet add more
tests as I explore my patches further):

- --
Don't work too hard, make some time for fun as well!

Eric Blake             address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAko5rU0ACgkQ84KuGfSFAYAhWACggLsBf+Aake6GMMooaggk/Z1N
dQwAn2XGQXCp5Aic5PhT3YRa5HqsGhOw
=z8+w
-----END PGP SIGNATURE-----

diff --git a/ChangeLog b/ChangeLog
index 47f7b0f..a8cf81a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2009-06-17  Jim Meyering  <address@hidden>
+       and Eric Blake  <address@hidden>
+
+       hash-tests: new module
+       * modules/hash-tests: New file.
+       * tests/test-hash.c: New file.
+
 2009-06-17  Eric Blake  <address@hidden>

        strstr-simple: document new module
diff --git a/modules/hash-tests b/modules/hash-tests
index fab9c88..0a83d8e 100644
--- a/modules/hash-tests
+++ b/modules/hash-tests
@@ -4,6 +4,7 @@ tests/test-hash.c
 Depends-on:
 hash-pjw
 inttostr
+progname
 stdbool
 xalloc

diff --git a/tests/test-hash.c b/tests/test-hash.c
index a09d6d1..e993d19 100644
--- a/tests/test-hash.c
+++ b/tests/test-hash.c
@@ -61,16 +61,49 @@ insert_new (Hash_table *ht, void *ent)
   ASSERT (e == ent);
 }

+static bool
+walk (void *ent, void *data)
+{
+  char *str = ent;
+  unsigned int *map = data;
+  switch (*str)
+    {
+    case 'a': *map |= 1; return true;
+    case 'b': *map |= 2; return true;
+    case 'c': *map |= 4; return true;
+    }
+  *map |= 8;
+  return false;
+}
+
 int
 main (void)
 {
   unsigned int i;
   Hash_table *ht = hash_initialize (53, NULL, hash_pjw,
                                    hash_compare_strings, NULL);
+  Hash_tuning tuning;
+
   ASSERT (ht);
   insert_new (ht, "a");
+  {
+    char *str1 = xstrdup ("a");
+    char *str2 = hash_insert (ht, str1);
+    ASSERT (str1 != str2);
+    ASSERT (STREQ (str1, str2));
+    free (str1);
+  }
   insert_new (ht, "b");
   insert_new (ht, "c");
+  i = 0;
+  ASSERT (hash_do_for_each (ht, walk, &i) == 3);
+  ASSERT (i == 7);
+  {
+    void *buf[5] = { NULL };
+    ASSERT (hash_get_entries (ht, NULL, 0) == 0);
+    ASSERT (hash_get_entries (ht, buf, 5) == 3);
+    ASSERT (STREQ (buf[0], "a") || STREQ (buf[0], "b") || STREQ (buf[0], "c"));
+  }
   ASSERT (hash_delete (ht, "a"));
   ASSERT (hash_delete (ht, "a") == NULL);
   ASSERT (hash_delete (ht, "b"));
@@ -80,6 +113,7 @@ main (void)
   ASSERT (hash_rehash (ht, 467));

   /* Free an empty table. */
+  hash_clear (ht);
   hash_free (ht);

   ht = hash_initialize (53, NULL, hash_pjw, hash_compare_strings, NULL);
@@ -92,6 +126,8 @@ main (void)
   insert_new (ht, "v");
   insert_new (ht, "u");

+  hash_clear (ht);
+  ASSERT (hash_get_n_entries (ht) == 0);
   hash_free (ht);

   /* Now, each entry is malloc'd.  */
@@ -157,5 +193,74 @@ main (void)

   hash_free (ht);

+  hash_reset_tuning (&tuning);
+  tuning.shrink_threshold = 0.3;
+  tuning.shrink_factor = 0.707;
+  tuning.growth_threshold = 0.9;
+  tuning.growth_factor = 2.0;
+  tuning.is_n_buckets = true;
+  ht = hash_initialize (4651, &tuning, hash_pjw, hash_compare_strings,
+                       hash_freer);
+  for (i = 0; i < 10000; i++)
+    {
+      unsigned int op = rand () % 10;
+      switch (op)
+       {
+       case 0:
+       case 1:
+       case 2:
+       case 3:
+       case 4:
+       case 5:
+         {
+           char buf[50];
+           char const *p = uinttostr (i, buf);
+           insert_new (ht, xstrdup (p));
+         }
+         break;
+
+       case 6:
+         {
+           size_t n = hash_get_n_entries (ht);
+           ASSERT (hash_rehash (ht, n + rand () % 20));
+         }
+         break;
+
+       case 7:
+         {
+           size_t n = hash_get_n_entries (ht);
+           size_t delta = rand () % 20;
+           if (delta < n)
+             ASSERT (hash_rehash (ht, n - delta));
+         }
+         break;
+
+       case 8:
+       case 9:
+         {
+           /* Delete a random entry.  */
+           size_t n = hash_get_n_entries (ht);
+           if (n)
+             {
+               size_t k = rand () % n;
+               void const *p;
+               void *v;
+               for (p = hash_get_first (ht); k; --k, p = hash_get_next (ht, p))
+                 {
+                   /* empty */
+                 }
+               ASSERT (p);
+               v = hash_delete (ht, p);
+               ASSERT (v);
+               free (v);
+             }
+           break;
+         }
+       }
+      ASSERT (hash_table_ok (ht));
+    }
+
+  hash_free (ht);
+
   return 0;
 }