Adding upstream version 8.30.upstream/8.30upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 263 insertions, 0 deletions

diff --git a/gnulib-tests/test-hash.c b/gnulib-tests/test-hash.c
new file mode 100644
index 0000000..c0c1f34
--- /dev/null
+++ b/gnulib-tests/test-hash.c
@@ -0,0 +1,263 @@
+/*
+ * Copyright (C) 2009-2018 Free Software Foundation, Inc.
+ * Written by Jim Meyering
+ *
+ * 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.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
+
+#include <config.h>
+
+#include "hash.h"
+#include "hash-pjw.h"
+#include "inttostr.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "macros.h"
+
+#define STREQ(a, b) (strcmp (a, b) == 0)
+#define ARRAY_CARDINALITY(Array) (sizeof (Array) / sizeof *(Array))
+
+static bool
+hash_compare_strings (void const *x, void const *y)
+{
+  ASSERT (x != y);
+  return STREQ (x, y) ? true : false;
+}
+
+static void
+hash_freer (void *x)
+{
+  free (x);
+}
+
+static void
+insert_new (Hash_table *ht, const void *ent)
+{
+  void *e = hash_insert (ht, 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;
+}
+
+static int
+get_seed (char const *str, unsigned int *seed)
+{
+  size_t len = strlen (str);
+  if (len == 0 || strspn (str, "0123456789") != len || 10 < len)
+    return 1;
+
+  *seed = atoi (str);
+  return 0;
+}
+
+int
+main (int argc, char **argv)
+{
+  unsigned int i;
+  unsigned int k;
+  unsigned int table_size[] = {1, 2, 3, 4, 5, 23, 53};
+  Hash_table *ht;
+  Hash_tuning tuning;
+
+  hash_reset_tuning (&tuning);
+  tuning.shrink_threshold = 0.3;
+  tuning.shrink_factor = 0.707;
+  tuning.growth_threshold = 1.5;
+  tuning.growth_factor = 2.0;
+  tuning.is_n_buckets = true;
+
+  if (1 < argc)
+    {
+      unsigned int seed;
+      if (get_seed (argv[1], &seed) != 0)
+        {
+          fprintf (stderr, "invalid seed: %s\n", argv[1]);
+          exit (EXIT_FAILURE);
+        }
+
+      srand (seed);
+    }
+
+  for (i = 0; i < ARRAY_CARDINALITY (table_size); i++)
+    {
+      size_t sz = table_size[i];
+      ht = hash_initialize (sz, NULL, hash_pjw, hash_compare_strings, NULL);
+      ASSERT (ht);
+      insert_new (ht, "a");
+      {
+        char *str1 = strdup ("a");
+        char *str2;
+        ASSERT (str1);
+        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"));
+      ASSERT (hash_delete (ht, "c"));
+
+      ASSERT (hash_rehash (ht, 47));
+      ASSERT (hash_rehash (ht, 467));
+
+      /* Free an empty table. */
+      hash_clear (ht);
+      hash_free (ht);
+
+      ht = hash_initialize (sz, NULL, hash_pjw, hash_compare_strings, NULL);
+      ASSERT (ht);
+
+      insert_new (ht, "z");
+      insert_new (ht, "y");
+      insert_new (ht, "x");
+      insert_new (ht, "w");
+      insert_new (ht, "v");
+      insert_new (ht, "u");
+
+      hash_clear (ht);
+      ASSERT (hash_get_n_entries (ht) == 0);
+      hash_free (ht);
+
+      /* Test pointer hashing.  */
+      ht = hash_initialize (sz, NULL, NULL, NULL, NULL);
+      ASSERT (ht);
+      {
+        char *str = strdup ("a");
+        ASSERT (str);
+        insert_new (ht, "a");
+        insert_new (ht, str);
+        ASSERT (hash_lookup (ht, str) == str);
+        free (str);
+      }
+      hash_free (ht);
+    }
+
+  hash_reset_tuning (&tuning);
+  tuning.shrink_threshold = 0.3;
+  tuning.shrink_factor = 0.707;
+  tuning.growth_threshold = 1.5;
+  tuning.growth_factor = 2.0;
+  tuning.is_n_buckets = true;
+  /* Invalid tuning.  */
+  ht = hash_initialize (4651, &tuning, hash_pjw, hash_compare_strings,
+                        hash_freer);
+  ASSERT (!ht);
+
+  /* Alternate tuning.  */
+  tuning.growth_threshold = 0.89;
+
+  /* Run with default tuning, then with custom tuning settings.  */
+  for (k = 0; k < 2; k++)
+    {
+      Hash_tuning const *tune = (k == 0 ? NULL : &tuning);
+      /* Now, each entry is malloc'd.  */
+      ht = hash_initialize (4651, tune, hash_pjw,
+                            hash_compare_strings, hash_freer);
+      ASSERT (ht);
+      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);
+                char *p_dup = strdup (p);
+                ASSERT (p_dup);
+                insert_new (ht, p_dup);
+              }
+              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 kk = rand () % n;
+                    void const *p;
+                    void *v;
+                    for (p = hash_get_first (ht); kk;
+                         --kk, 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;
+}