tests/test-hash.c

   1 /*
   2  * Copyright (C) 2009-2020 Free Software Foundation, Inc.
   3  * Written by Jim Meyering
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 3 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 #include <config.h>
  19
  20 #include "hash.h"
  21 #include "hash-pjw.h"
  22 #include "inttostr.h"
  23
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <stdbool.h>
  27 #include <string.h>
  28 #include <unistd.h>
  29
  30 #include "macros.h"
  31
  32 #define STREQ(a, b) (strcmp (a, b) == 0)
  33 #define ARRAY_CARDINALITY(Array) (sizeof (Array) / sizeof *(Array))
  34
  35 static bool
  36 hash_compare_strings (void const *x, void const *y)
  37 {
  38   ASSERT (x != y);
  39   return STREQ (x, y) ? true : false;
  40 }
  41
  42 static void
  43 hash_freer (void *x)
  44 {
  45   free (x);
  46 }
  47
  48 static void
  49 insert_new (Hash_table *ht, const void *ent)
  50 {
  51   void *e = hash_insert (ht, ent);
  52   ASSERT (e == ent);
  53 }
  54
  55 static bool
  56 walk (void *ent, void *data)
  57 {
  58   char *str = ent;
  59   unsigned int *map = data;
  60   switch (*str)
  61     {
  62     case 'a': *map |= 1; return true;
  63     case 'b': *map |= 2; return true;
  64     case 'c': *map |= 4; return true;
  65     }
  66   *map |= 8;
  67   return false;
  68 }
  69
  70 static int
  71 get_seed (char const *str, unsigned int *seed)
  72 {
  73   size_t len = strlen (str);
  74   if (len == 0 || strspn (str, "0123456789") != len || 10 < len)
  75     return 1;
  76
  77   *seed = atoi (str);
  78   return 0;
  79 }
  80
  81 int
  82 main (int argc, char **argv)
  83 {
  84   unsigned int i;
  85   unsigned int k;
  86   unsigned int table_size[] = {1, 2, 3, 4, 5, 23, 53};
  87   Hash_table *ht;
  88   Hash_tuning tuning;
  89
  90   hash_reset_tuning (&tuning);
  91   tuning.shrink_threshold = 0.3;
  92   tuning.shrink_factor = 0.707;
  93   tuning.growth_threshold = 1.5;
  94   tuning.growth_factor = 2.0;
  95   tuning.is_n_buckets = true;
  96
  97   if (1 < argc)
  98     {
  99       unsigned int seed;
 100       if (get_seed (argv[1], &seed) != 0)
 101         {
 102           fprintf (stderr, "invalid seed: %s\n", argv[1]);
 103           exit (EXIT_FAILURE);
 104         }
 105
 106       srand (seed);
 107     }
 108
 109   for (i = 0; i < ARRAY_CARDINALITY (table_size); i++)
 110     {
 111       size_t sz = table_size[i];
 112       ht = hash_initialize (sz, NULL, hash_pjw, hash_compare_strings, NULL);
 113       ASSERT (ht);
 114       insert_new (ht, "a");
 115       {
 116         char *str1 = strdup ("a");
 117         char *str2;
 118         ASSERT (str1);
 119         str2 = hash_insert (ht, str1);
 120         ASSERT (str1 != str2);
 121         ASSERT (STREQ (str1, str2));
 122         free (str1);
 123       }
 124       insert_new (ht, "b");
 125       insert_new (ht, "c");
 126       i = 0;
 127       ASSERT (hash_do_for_each (ht, walk, &i) == 3);
 128       ASSERT (i == 7);
 129       {
 130         void *buf[5] = { NULL };
 131         ASSERT (hash_get_entries (ht, NULL, 0) == 0);
 132         ASSERT (hash_get_entries (ht, buf, 5) == 3);
 133         ASSERT (STREQ (buf[0], "a") || STREQ (buf[0], "b") || STREQ (buf[0], "c"));
 134       }
 135       ASSERT (hash_delete (ht, "a"));
 136       ASSERT (hash_delete (ht, "a") == NULL);
 137       ASSERT (hash_delete (ht, "b"));
 138       ASSERT (hash_delete (ht, "c"));
 139
 140       ASSERT (hash_rehash (ht, 47));
 141       ASSERT (hash_rehash (ht, 467));
 142
 143       /* Free an empty table. */
 144       hash_clear (ht);
 145       hash_free (ht);
 146
 147       ht = hash_initialize (sz, NULL, hash_pjw, hash_compare_strings, NULL);
 148       ASSERT (ht);
 149
 150       insert_new (ht, "z");
 151       insert_new (ht, "y");
 152       insert_new (ht, "x");
 153       insert_new (ht, "w");
 154       insert_new (ht, "v");
 155       insert_new (ht, "u");
 156
 157       hash_clear (ht);
 158       ASSERT (hash_get_n_entries (ht) == 0);
 159       hash_free (ht);
 160
 161       /* Test pointer hashing.  */
 162       ht = hash_initialize (sz, NULL, NULL, NULL, NULL);
 163       ASSERT (ht);
 164       {
 165         char *str = strdup ("a");
 166         ASSERT (str);
 167         insert_new (ht, "a");
 168         insert_new (ht, str);
 169         ASSERT (hash_lookup (ht, str) == str);
 170         free (str);
 171       }
 172       hash_free (ht);
 173     }
 174
 175   hash_reset_tuning (&tuning);
 176   tuning.shrink_threshold = 0.3;
 177   tuning.shrink_factor = 0.707;
 178   tuning.growth_threshold = 1.5;
 179   tuning.growth_factor = 2.0;
 180   tuning.is_n_buckets = true;
 181   /* Invalid tuning.  */
 182   ht = hash_initialize (4651, &tuning, hash_pjw, hash_compare_strings,
 183                         hash_freer);
 184   ASSERT (!ht);
 185
 186   /* Alternate tuning.  */
 187   tuning.growth_threshold = 0.89;
 188
 189   /* Run with default tuning, then with custom tuning settings.  */
 190   for (k = 0; k < 2; k++)
 191     {
 192       Hash_tuning const *tune = (k == 0 ? NULL : &tuning);
 193       /* Now, each entry is malloc'd.  */
 194       ht = hash_initialize (4651, tune, hash_pjw,
 195                             hash_compare_strings, hash_freer);
 196       ASSERT (ht);
 197       for (i = 0; i < 10000; i++)
 198         {
 199           unsigned int op = rand () % 10;
 200           switch (op)
 201             {
 202             case 0:
 203             case 1:
 204             case 2:
 205             case 3:
 206             case 4:
 207             case 5:
 208               {
 209                 char buf[50];
 210                 char const *p = uinttostr (i, buf);
 211                 char *p_dup = strdup (p);
 212                 ASSERT (p_dup);
 213                 insert_new (ht, p_dup);
 214               }
 215               break;
 216
 217             case 6:
 218               {
 219                 size_t n = hash_get_n_entries (ht);
 220                 ASSERT (hash_rehash (ht, n + rand () % 20));
 221               }
 222               break;
 223
 224             case 7:
 225               {
 226                 size_t n = hash_get_n_entries (ht);
 227                 size_t delta = rand () % 20;
 228                 if (delta < n)
 229                   ASSERT (hash_rehash (ht, n - delta));
 230               }
 231               break;
 232
 233             case 8:
 234             case 9:
 235               {
 236                 /* Delete a random entry.  */
 237                 size_t n = hash_get_n_entries (ht);
 238                 if (n)
 239                   {
 240                     size_t kk = rand () % n;
 241                     void const *p;
 242                     void *v;
 243                     for (p = hash_get_first (ht); kk;
 244                          --kk, p = hash_get_next (ht, p))
 245                       {
 246                         /* empty */
 247                       }
 248                     ASSERT (p);
 249                     v = hash_delete (ht, p);
 250                     ASSERT (v);
 251                     free (v);
 252                   }
 253                 break;
 254               }
 255             }
 256           ASSERT (hash_table_ok (ht));
 257         }
 258
 259       hash_free (ht);
 260     }
 261
 262   return 0;
 263 }