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 int
  82 main (void)
  83 {
  84   unsigned int i;
  85   unsigned int table_size[] = {1, 2, 3, 4, 5, 23, 53};
  86   Hash_table *ht;
  87   Hash_tuning tuning;
  88
  89   for (i = 0; i < ARRAY_CARDINALITY (table_size); i++)
  90     {
  91       size_t sz = table_size[i];
  92       ht = hash_initialize (sz, NULL, hash_pjw, hash_compare_strings, NULL);
  93       ASSERT (ht);
  94       insert_new (ht, "a");
  95       {
  96         char *str1 = xstrdup ("a");
  97         char *str2 = hash_insert (ht, str1);
  98         ASSERT (str1 != str2);
  99         ASSERT (STREQ (str1, str2));
 100         free (str1);
 101       }
 102       insert_new (ht, "b");
 103       insert_new (ht, "c");
 104       i = 0;
 105       ASSERT (hash_do_for_each (ht, walk, &i) == 3);
 106       ASSERT (i == 7);
 107       {
 108         void *buf[5] = { NULL };
 109         ASSERT (hash_get_entries (ht, NULL, 0) == 0);
 110         ASSERT (hash_get_entries (ht, buf, 5) == 3);
 111         ASSERT (STREQ (buf[0], "a") || STREQ (buf[0], "b") || STREQ (buf[0], "c"));
 112       }
 113       ASSERT (hash_delete (ht, "a"));
 114       ASSERT (hash_delete (ht, "a") == NULL);
 115       ASSERT (hash_delete (ht, "b"));
 116       ASSERT (hash_delete (ht, "c"));
 117
 118       ASSERT (hash_rehash (ht, 47));
 119       ASSERT (hash_rehash (ht, 467));
 120
 121       /* Free an empty table. */
 122       hash_clear (ht);
 123       hash_free (ht);
 124
 125       ht = hash_initialize (sz, NULL, hash_pjw, hash_compare_strings, NULL);
 126       ASSERT (ht);
 127
 128       insert_new (ht, "z");
 129       insert_new (ht, "y");
 130       insert_new (ht, "x");
 131       insert_new (ht, "w");
 132       insert_new (ht, "v");
 133       insert_new (ht, "u");
 134
 135       hash_clear (ht);
 136       ASSERT (hash_get_n_entries (ht) == 0);
 137       hash_free (ht);
 138
 139       /* Test pointer hashing.  */
 140       ht = hash_initialize (sz, NULL, NULL, NULL, NULL);
 141       ASSERT (ht);
 142       {
 143         char *str = xstrdup ("a");
 144         insert_new (ht, "a");
 145         insert_new (ht, str);
 146         ASSERT (hash_lookup (ht, str) == str);
 147         free (str);
 148       }
 149       hash_free (ht);
 150     }
 151
 152   /* Now, each entry is malloc'd.  */
 153   ht = hash_initialize (4651, NULL, hash_pjw, hash_compare_strings, hash_freer);
 154   ASSERT (ht);
 155   for (i = 0; i < 10000; i++)
 156     {
 157       unsigned int op = rand () % 10;
 158       switch (op)
 159         {
 160         case 0:
 161         case 1:
 162         case 2:
 163         case 3:
 164         case 4:
 165         case 5:
 166           {
 167             char buf[50];
 168             char const *p = uinttostr (i, buf);
 169             insert_new (ht, xstrdup (p));
 170           }
 171           break;
 172
 173         case 6:
 174           {
 175             size_t n = hash_get_n_entries (ht);
 176             ASSERT (hash_rehash (ht, n + rand () % 20));
 177           }
 178           break;
 179
 180         case 7:
 181           {
 182             size_t n = hash_get_n_entries (ht);
 183             size_t delta = rand () % 20;
 184             if (delta < n)
 185               ASSERT (hash_rehash (ht, n - delta));
 186           }
 187           break;
 188
 189         case 8:
 190         case 9:
 191           {
 192             /* Delete a random entry.  */
 193             size_t n = hash_get_n_entries (ht);
 194             if (n)
 195               {
 196                 size_t k = rand () % n;
 197                 void const *p;
 198                 void *v;
 199                 for (p = hash_get_first (ht); k; --k, p = hash_get_next (ht, p))
 200                   {
 201                     /* empty */
 202                   }
 203                 ASSERT (p);
 204                 v = hash_delete (ht, p);
 205                 ASSERT (v);
 206                 free (v);
 207               }
 208             break;
 209           }
 210         }
 211       ASSERT (hash_table_ok (ht));
 212     }
 213
 214   hash_free (ht);
 215
 216   hash_reset_tuning (&tuning);
 217   tuning.shrink_threshold = 0.3;
 218   tuning.shrink_factor = 0.707;
 219   tuning.growth_threshold = 1.5;
 220   tuning.growth_factor = 2.0;
 221   tuning.is_n_buckets = true;
 222   /* Invalid tuning.  */
 223   ht = hash_initialize (4651, &tuning, hash_pjw, hash_compare_strings,
 224                         hash_freer);
 225   ASSERT (!ht);
 226
 227   /* Alternate tuning.  */
 228   tuning.growth_threshold = 0.89;
 229   ht = hash_initialize (4651, &tuning, hash_pjw, hash_compare_strings,
 230                         hash_freer);
 231   ASSERT (ht);
 232   for (i = 0; i < 10000; i++)
 233     {
 234       unsigned int op = rand () % 10;
 235       switch (op)
 236         {
 237         case 0:
 238         case 1:
 239         case 2:
 240         case 3:
 241         case 4:
 242         case 5:
 243           {
 244             char buf[50];
 245             char const *p = uinttostr (i, buf);
 246             insert_new (ht, xstrdup (p));
 247           }
 248           break;
 249
 250         case 6:
 251           {
 252             size_t n = hash_get_n_entries (ht);
 253             ASSERT (hash_rehash (ht, n + rand () % 20));
 254           }
 255           break;
 256
 257         case 7:
 258           {
 259             size_t n = hash_get_n_entries (ht);
 260             size_t delta = rand () % 20;
 261             if (delta < n)
 262               ASSERT (hash_rehash (ht, n - delta));
 263           }
 264           break;
 265
 266         case 8:
 267         case 9:
 268           {
 269             /* Delete a random entry.  */
 270             size_t n = hash_get_n_entries (ht);
 271             if (n)
 272               {
 273                 size_t k = rand () % n;
 274                 void const *p;
 275                 void *v;
 276                 for (p = hash_get_first (ht); k; --k, p = hash_get_next (ht, p))
 277                   {
 278                     /* empty */
 279                   }
 280                 ASSERT (p);
 281                 v = hash_delete (ht, p);
 282                 ASSERT (v);
 283                 free (v);
 284               }
 285             break;
 286           }
 287         }
 288       ASSERT (hash_table_ok (ht));
 289     }
 290
 291   hash_free (ht);
 292
 293   return 0;
 294 }