pintos-os.org Git - pspp/blob - 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
  33 #define ASSERT(expr) \
  34   do                                                                         \
  35     {                                                                        \
  36       if (!(expr))                                                           \
  37         {                                                                    \
  38           fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \
  39           fflush (stderr);                                                   \
  40           abort ();                                                          \
  41         }                                                                    \
  42     }                                                                        \
  43   while (0)
  44
  45 static bool
  46 hash_compare_strings (void const *x, void const *y)
  47 {
  48   return STREQ (x, y) ? true : false;
  49 }
  50
  51 static void
  52 hash_freer (void *x)
  53 {
  54   free (x);
  55 }
  56
  57 static void
  58 insert_new (Hash_table *ht, void *ent)
  59 {
  60   void *e = hash_insert (ht, ent);
  61   ASSERT (e == ent);
  62 }
  63
  64 static bool
  65 walk (void *ent, void *data)
  66 {
  67   char *str = ent;
  68   unsigned int *map = data;
  69   switch (*str)
  70     {
  71     case 'a': *map |= 1; return true;
  72     case 'b': *map |= 2; return true;
  73     case 'c': *map |= 4; return true;
  74     }
  75   *map |= 8;
  76   return false;
  77 }
  78
  79 int
  80 main (void)
  81 {
  82   unsigned int i;
  83   Hash_table *ht = hash_initialize (53, NULL, hash_pjw,
  84                                     hash_compare_strings, NULL);
  85   Hash_tuning tuning;
  86
  87   ASSERT (ht);
  88   insert_new (ht, "a");
  89   {
  90     char *str1 = xstrdup ("a");
  91     char *str2 = hash_insert (ht, str1);
  92     ASSERT (str1 != str2);
  93     ASSERT (STREQ (str1, str2));
  94     free (str1);
  95   }
  96   insert_new (ht, "b");
  97   insert_new (ht, "c");
  98   i = 0;
  99   ASSERT (hash_do_for_each (ht, walk, &i) == 3);
 100   ASSERT (i == 7);
 101   {
 102     void *buf[5] = { NULL };
 103     ASSERT (hash_get_entries (ht, NULL, 0) == 0);
 104     ASSERT (hash_get_entries (ht, buf, 5) == 3);
 105     ASSERT (STREQ (buf[0], "a") || STREQ (buf[0], "b") || STREQ (buf[0], "c"));
 106   }
 107   ASSERT (hash_delete (ht, "a"));
 108   ASSERT (hash_delete (ht, "a") == NULL);
 109   ASSERT (hash_delete (ht, "b"));
 110   ASSERT (hash_delete (ht, "c"));
 111
 112   ASSERT (hash_rehash (ht, 47));
 113   ASSERT (hash_rehash (ht, 467));
 114
 115   /* Free an empty table. */
 116   hash_clear (ht);
 117   hash_free (ht);
 118
 119   ht = hash_initialize (53, NULL, hash_pjw, hash_compare_strings, NULL);
 120   ASSERT (ht);
 121
 122   insert_new (ht, "z");
 123   insert_new (ht, "y");
 124   insert_new (ht, "x");
 125   insert_new (ht, "w");
 126   insert_new (ht, "v");
 127   insert_new (ht, "u");
 128
 129   hash_clear (ht);
 130   ASSERT (hash_get_n_entries (ht) == 0);
 131   hash_free (ht);
 132
 133   /* Now, each entry is malloc'd.  */
 134   ht = hash_initialize (4651, NULL, hash_pjw, hash_compare_strings, hash_freer);
 135   ASSERT (ht);
 136   for (i = 0; i < 10000; i++)
 137     {
 138       unsigned int op = rand () % 10;
 139       switch (op)
 140         {
 141         case 0:
 142         case 1:
 143         case 2:
 144         case 3:
 145         case 4:
 146         case 5:
 147           {
 148             char buf[50];
 149             char const *p = uinttostr (i, buf);
 150             insert_new (ht, xstrdup (p));
 151           }
 152           break;
 153
 154         case 6:
 155           {
 156             size_t n = hash_get_n_entries (ht);
 157             ASSERT (hash_rehash (ht, n + rand () % 20));
 158           }
 159           break;
 160
 161         case 7:
 162           {
 163             size_t n = hash_get_n_entries (ht);
 164             size_t delta = rand () % 20;
 165             if (delta < n)
 166               ASSERT (hash_rehash (ht, n - delta));
 167           }
 168           break;
 169
 170         case 8:
 171         case 9:
 172           {
 173             /* Delete a random entry.  */
 174             size_t n = hash_get_n_entries (ht);
 175             if (n)
 176               {
 177                 size_t k = rand () % n;
 178                 void const *p;
 179                 void *v;
 180                 for (p = hash_get_first (ht); k; --k, p = hash_get_next (ht, p))
 181                   {
 182                     /* empty */
 183                   }
 184                 ASSERT (p);
 185                 v = hash_delete (ht, p);
 186                 ASSERT (v);
 187                 free (v);
 188               }
 189             break;
 190           }
 191         }
 192       ASSERT (hash_table_ok (ht));
 193     }
 194
 195   hash_free (ht);
 196
 197   hash_reset_tuning (&tuning);
 198   tuning.shrink_threshold = 0.3;
 199   tuning.shrink_factor = 0.707;
 200   tuning.growth_threshold = 1.5;
 201   tuning.growth_factor = 2.0;
 202   tuning.is_n_buckets = true;
 203   /* Invalid tuning.  */
 204   ht = hash_initialize (4651, &tuning, hash_pjw, hash_compare_strings,
 205                         hash_freer);
 206   ASSERT (!ht);
 207
 208   /* Alternate tuning.  */
 209   tuning.growth_threshold = 0.89;
 210   ht = hash_initialize (4651, &tuning, hash_pjw, hash_compare_strings,
 211                         hash_freer);
 212   ASSERT (ht);
 213   for (i = 0; i < 10000; i++)
 214     {
 215       unsigned int op = rand () % 10;
 216       switch (op)
 217         {
 218         case 0:
 219         case 1:
 220         case 2:
 221         case 3:
 222         case 4:
 223         case 5:
 224           {
 225             char buf[50];
 226             char const *p = uinttostr (i, buf);
 227             insert_new (ht, xstrdup (p));
 228           }
 229           break;
 230
 231         case 6:
 232           {
 233             size_t n = hash_get_n_entries (ht);
 234             ASSERT (hash_rehash (ht, n + rand () % 20));
 235           }
 236           break;
 237
 238         case 7:
 239           {
 240             size_t n = hash_get_n_entries (ht);
 241             size_t delta = rand () % 20;
 242             if (delta < n)
 243               ASSERT (hash_rehash (ht, n - delta));
 244           }
 245           break;
 246
 247         case 8:
 248         case 9:
 249           {
 250             /* Delete a random entry.  */
 251             size_t n = hash_get_n_entries (ht);
 252             if (n)
 253               {
 254                 size_t k = rand () % n;
 255                 void const *p;
 256                 void *v;
 257                 for (p = hash_get_first (ht); k; --k, p = hash_get_next (ht, p))
 258                   {
 259                     /* empty */
 260                   }
 261                 ASSERT (p);
 262                 v = hash_delete (ht, p);
 263                 ASSERT (v);
 264                 free (v);
 265               }
 266             break;
 267           }
 268         }
 269       ASSERT (hash_table_ok (ht));
 270     }
 271
 272   hash_free (ht);
 273
 274   return 0;
 275 }