tests/test-hash.c

   1 /*
   2  * Copyright (C) 2009 Free Software Foundation
   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 <http://www.gnu.org/licenses/>.  */
  17
  18 #include <config.h>
  19
  20 #include "hash.h"
  21 #include "hash-pjw.h"
  22 #include "inttostr.h"
  23 #include "xalloc.h"
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <stdbool.h>
  28 #include <string.h>
  29 #include <unistd.h>
  30
  31 #define STREQ(a, b) (strcmp (a, b) == 0)
  32 #define ARRAY_CARDINALITY(Array) (sizeof (Array) / sizeof *(Array))
  33
  34 #define ASSERT(expr) \
  35   do                                                                         \
  36     {                                                                        \
  37       if (!(expr))                                                           \
  38         {                                                                    \
  39           fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \
  40           fflush (stderr);                                                   \
  41           abort ();                                                          \
  42         }                                                                    \
  43     }                                                                        \
  44   while (0)
  45
  46 static bool
  47 hash_compare_strings (void const *x, void const *y)
  48 {
  49   ASSERT (x != y);
  50   return STREQ (x, y) ? true : false;
  51 }
  52
  53 static void
  54 hash_freer (void *x)
  55 {
  56   free (x);
  57 }
  58
  59 static void
  60 insert_new (Hash_table *ht, void *ent)
  61 {
  62   void *e = hash_insert (ht, ent);
  63   ASSERT (e == ent);
  64 }
  65
  66 static bool
  67 walk (void *ent, void *data)
  68 {
  69   char *str = ent;
  70   unsigned int *map = data;
  71   switch (*str)
  72     {
  73     case 'a': *map |= 1; return true;
  74     case 'b': *map |= 2; return true;
  75     case 'c': *map |= 4; return true;
  76     }
  77   *map |= 8;
  78   return false;
  79 }
  80
  81 static int
  82 get_seed (char const *str, unsigned int *seed)
  83 {
  84   size_t len = strlen (str);
  85   if (len == 0 || strspn (str, "0123456789") != len || 10 < len)
  86     return 1;
  87
  88   *seed = atoi (str);
  89   return 0;
  90 }
  91
  92 int
  93 main (int argc, char **argv)
  94 {
  95   unsigned int i;
  96   unsigned int table_size[] = {1, 2, 3, 4, 5, 23, 53};
  97   Hash_table *ht;
  98   Hash_tuning tuning;
  99
 100   if (1 < argc)
 101     {
 102       unsigned int seed;
 103       if (get_seed (argv[1], &seed) != 0)
 104         {
 105           fprintf (stderr, "invalid seed: %s\n", argv[1]);
 106           exit (EXIT_FAILURE);
 107         }
 108
 109       srand (seed);
 110     }
 111
 112   for (i = 0; i < ARRAY_CARDINALITY (table_size); i++)
 113     {
 114       size_t sz = table_size[i];
 115       ht = hash_initialize (sz, NULL, hash_pjw, hash_compare_strings, NULL);
 116       ASSERT (ht);
 117       insert_new (ht, "a");
 118       {
 119         char *str1 = xstrdup ("a");
 120         char *str2 = hash_insert (ht, str1);
 121         ASSERT (str1 != str2);
 122         ASSERT (STREQ (str1, str2));
 123         free (str1);
 124       }
 125       insert_new (ht, "b");
 126       insert_new (ht, "c");
 127       i = 0;
 128       ASSERT (hash_do_for_each (ht, walk, &i) == 3);
 129       ASSERT (i == 7);
 130       {
 131         void *buf[5] = { NULL };
 132         ASSERT (hash_get_entries (ht, NULL, 0) == 0);
 133         ASSERT (hash_get_entries (ht, buf, 5) == 3);
 134         ASSERT (STREQ (buf[0], "a") || STREQ (buf[0], "b") || STREQ (buf[0], "c"));
 135       }
 136       ASSERT (hash_delete (ht, "a"));
 137       ASSERT (hash_delete (ht, "a") == NULL);
 138       ASSERT (hash_delete (ht, "b"));
 139       ASSERT (hash_delete (ht, "c"));
 140
 141       ASSERT (hash_rehash (ht, 47));
 142       ASSERT (hash_rehash (ht, 467));
 143
 144       /* Free an empty table. */
 145       hash_clear (ht);
 146       hash_free (ht);
 147
 148       ht = hash_initialize (sz, NULL, hash_pjw, hash_compare_strings, NULL);
 149       ASSERT (ht);
 150
 151       insert_new (ht, "z");
 152       insert_new (ht, "y");
 153       insert_new (ht, "x");
 154       insert_new (ht, "w");
 155       insert_new (ht, "v");
 156       insert_new (ht, "u");
 157
 158       hash_clear (ht);
 159       ASSERT (hash_get_n_entries (ht) == 0);
 160       hash_free (ht);
 161
 162       /* Test pointer hashing.  */
 163       ht = hash_initialize (sz, NULL, NULL, NULL, NULL);
 164       ASSERT (ht);
 165       {
 166         char *str = xstrdup ("a");
 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   /* Now, each entry is malloc'd.  */
 176   ht = hash_initialize (4651, NULL, hash_pjw, hash_compare_strings, hash_freer);
 177   ASSERT (ht);
 178   for (i = 0; i < 10000; i++)
 179     {
 180       unsigned int op = rand () % 10;
 181       switch (op)
 182         {
 183         case 0:
 184         case 1:
 185         case 2:
 186         case 3:
 187         case 4:
 188         case 5:
 189           {
 190             char buf[50];
 191             char const *p = uinttostr (i, buf);
 192             insert_new (ht, xstrdup (p));
 193           }
 194           break;
 195
 196         case 6:
 197           {
 198             size_t n = hash_get_n_entries (ht);
 199             ASSERT (hash_rehash (ht, n + rand () % 20));
 200           }
 201           break;
 202
 203         case 7:
 204           {
 205             size_t n = hash_get_n_entries (ht);
 206             size_t delta = rand () % 20;
 207             if (delta < n)
 208               ASSERT (hash_rehash (ht, n - delta));
 209           }
 210           break;
 211
 212         case 8:
 213         case 9:
 214           {
 215             /* Delete a random entry.  */
 216             size_t n = hash_get_n_entries (ht);
 217             if (n)
 218               {
 219                 size_t k = rand () % n;
 220                 void const *p;
 221                 void *v;
 222                 for (p = hash_get_first (ht); k; --k, p = hash_get_next (ht, p))
 223                   {
 224                     /* empty */
 225                   }
 226                 ASSERT (p);
 227                 v = hash_delete (ht, p);
 228                 ASSERT (v);
 229                 free (v);
 230               }
 231             break;
 232           }
 233         }
 234       ASSERT (hash_table_ok (ht));
 235     }
 236
 237   hash_free (ht);
 238
 239   hash_reset_tuning (&tuning);
 240   tuning.shrink_threshold = 0.3;
 241   tuning.shrink_factor = 0.707;
 242   tuning.growth_threshold = 1.5;
 243   tuning.growth_factor = 2.0;
 244   tuning.is_n_buckets = true;
 245   /* Invalid tuning.  */
 246   ht = hash_initialize (4651, &tuning, hash_pjw, hash_compare_strings,
 247                         hash_freer);
 248   ASSERT (!ht);
 249
 250   /* Alternate tuning.  */
 251   tuning.growth_threshold = 0.89;
 252   ht = hash_initialize (4651, &tuning, hash_pjw, hash_compare_strings,
 253                         hash_freer);
 254   ASSERT (ht);
 255   for (i = 0; i < 10000; i++)
 256     {
 257       unsigned int op = rand () % 10;
 258       switch (op)
 259         {
 260         case 0:
 261         case 1:
 262         case 2:
 263         case 3:
 264         case 4:
 265         case 5:
 266           {
 267             char buf[50];
 268             char const *p = uinttostr (i, buf);
 269             insert_new (ht, xstrdup (p));
 270           }
 271           break;
 272
 273         case 6:
 274           {
 275             size_t n = hash_get_n_entries (ht);
 276             ASSERT (hash_rehash (ht, n + rand () % 20));
 277           }
 278           break;
 279
 280         case 7:
 281           {
 282             size_t n = hash_get_n_entries (ht);
 283             size_t delta = rand () % 20;
 284             if (delta < n)
 285               ASSERT (hash_rehash (ht, n - delta));
 286           }
 287           break;
 288
 289         case 8:
 290         case 9:
 291           {
 292             /* Delete a random entry.  */
 293             size_t n = hash_get_n_entries (ht);
 294             if (n)
 295               {
 296                 size_t k = rand () % n;
 297                 void const *p;
 298                 void *v;
 299                 for (p = hash_get_first (ht); k; --k, p = hash_get_next (ht, p))
 300                   {
 301                     /* empty */
 302                   }
 303                 ASSERT (p);
 304                 v = hash_delete (ht, p);
 305                 ASSERT (v);
 306                 free (v);
 307               }
 308             break;
 309           }
 310         }
 311       ASSERT (hash_table_ok (ht));
 312     }
 313
 314   hash_free (ht);
 315
 316   return 0;
 317 }