tests/test-hamt.c

   1 /* Test of persistent hash array mapped trie implementation.
   2    Copyright (C) 2021-2024 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  16
  17 /* Written by Marc Nieper-Wißkirchen <marc@nieper-wisskirchen.de>, 2021.  */
  18
  19 #include <config.h>
  20
  21 #include "hamt.h"
  22 #include "macros.h"
  23 #include "xalloc.h"
  24
  25 typedef struct
  26 {
  27   Hamt_entry entry;
  28   int val;
  29 } Element;
  30
  31 static int
  32 entry_value (const void *elt)
  33 {
  34   return ((Element *) elt)->val;
  35 }
  36
  37 static size_t
  38 hash_element (const void *elt)
  39 {
  40   return entry_value (elt) & ~3; /* We drop the last bits so that we
  41                                     can test hash collisions. */
  42 }
  43
  44 static bool
  45 compare_element (const void *elt1, const void *elt2)
  46 {
  47   return entry_value (elt1) == entry_value (elt2);
  48 }
  49
  50 static void
  51 free_element (Hamt_entry *elt)
  52 {
  53   free (elt);
  54 }
  55
  56 static Hamt_entry *
  57 make_element (int n)
  58 {
  59   Element *elt = XMALLOC (Element);
  60   elt->val = n;
  61   return hamt_element (&elt->entry);
  62 }
  63
  64 static Hamt *
  65 test_hamt_create (void)
  66 {
  67   return hamt_create (hash_element, compare_element, free_element);
  68 }
  69
  70
  71 static int sum = 0;
  72 static int flag;
  73
  74 static bool
  75 proc (Hamt_entry *elt, void *data)
  76 {
  77   if (data == &flag)
  78     {
  79       sum += entry_value (elt);
  80       return true;
  81     }
  82   if (sum > 0)
  83     {
  84       sum = 0;
  85       return true;
  86     }
  87   return false;
  88 }
  89
  90 static void
  91 test_general (void)
  92 {
  93   Hamt *hamt = test_hamt_create ();
  94
  95   Hamt_entry *x5 = make_element (5);
  96   Hamt_entry *p = x5;
  97   Hamt *hamt1 = hamt_insert (hamt, &p);
  98   ASSERT (hamt1 != hamt);
  99   ASSERT (hamt_lookup (hamt, x5) == NULL);
 100   ASSERT (hamt_lookup (hamt1, x5) == x5);
 101   hamt_free (hamt);
 102
 103   Hamt_entry *y5 = make_element (5);
 104   p = y5;
 105   Hamt *hamt2 = hamt_insert (hamt1, &p);
 106   ASSERT (hamt2 == hamt1);
 107   ASSERT (p == x5);
 108   ASSERT (hamt_lookup (hamt1, y5) == x5);
 109
 110   p = y5;
 111   hamt = hamt_replace (hamt1, &p);
 112   ASSERT (p == x5);
 113   ASSERT (hamt_lookup (hamt, y5) == y5);
 114   hamt_free (hamt);
 115   y5 = make_element (5);
 116
 117   Hamt_entry *z37 = make_element (37);
 118   p = z37;
 119   hamt2 = hamt_insert (hamt1, &p);
 120   ASSERT (hamt2 != hamt1);
 121   ASSERT (p == z37);
 122   ASSERT (hamt_lookup (hamt1, z37) == NULL);
 123   ASSERT (hamt_lookup (hamt2, z37) == z37);
 124   hamt_free (hamt1);
 125
 126   ASSERT (hamt_lookup (hamt2, x5) == x5);
 127   ASSERT (hamt_lookup (hamt2, z37) == z37);
 128
 129   ASSERT (hamt_do_while (hamt2, proc, &flag) == 2);
 130   ASSERT (sum == 42);
 131   ASSERT (hamt_do_while (hamt2, proc, NULL) == 1);
 132   ASSERT (sum == 0);
 133
 134   p = y5;
 135   hamt1 = hamt_remove (hamt2, &p);
 136   ASSERT (hamt1 != hamt2);
 137   ASSERT (p == x5);
 138
 139   ASSERT (hamt_lookup (hamt1, x5) == NULL);
 140   ASSERT (hamt_lookup (hamt2, x5) == x5);
 141
 142   hamt_free (hamt1);
 143   Hamt_entry *x4 = make_element (4);
 144   hamt1 = hamt_insert (hamt2, &x4);
 145   hamt_free (hamt2);
 146   Hamt_entry *x6 = make_element (6);
 147   hamt2 = hamt_insert (hamt1, &x6);
 148   hamt_free (hamt1);
 149   ASSERT (hamt_do_while (hamt2, proc, &flag) == 4);
 150   ASSERT (sum == 52);
 151
 152   hamt1 = hamt_remove (hamt2, &x4);
 153   sum = 0;
 154   ASSERT (hamt_do_while (hamt2, proc, &flag) == 4);
 155   ASSERT (sum == 52);
 156   sum = 0;
 157   ASSERT (hamt_do_while (hamt1, proc, &flag) == 3);
 158   ASSERT (sum == 48);
 159
 160   hamt_free (hamt1);
 161   hamt_free (hamt2);
 162   free_element (y5);
 163 }
 164
 165 static bool
 166 true_processor (_GL_ATTRIBUTE_MAYBE_UNUSED Hamt_entry *elt,
 167                 _GL_ATTRIBUTE_MAYBE_UNUSED void *data)
 168 {
 169   return true;
 170 }
 171
 172 static size_t
 173 element_count (Hamt *hamt)
 174 {
 175   return hamt_do_while (hamt, true_processor, NULL);
 176 }
 177
 178 struct find_values_context
 179 {
 180   size_t n;
 181   int *elts;
 182   bool *found;
 183 };
 184
 185 static bool
 186 find_values_processor (Hamt_entry *entry, void *data)
 187 {
 188   struct find_values_context *ctx = data;
 189   int val = entry_value (entry);
 190   for (size_t i = 0; i < ctx->n; ++i)
 191     if (ctx->elts [i] == val && !ctx->found [i])
 192       {
 193         ctx->found [i] = true;
 194         return true;
 195       }
 196   return false;
 197 }
 198
 199 static bool
 200 find_values (Hamt *hamt, size_t n, int *elts)
 201 {
 202   bool *found = XCALLOC (n, bool);
 203   struct find_values_context ctx = {n, elts, found};
 204   bool res = hamt_do_while (hamt, find_values_processor, &ctx) == n;
 205   free (found);
 206   return res;
 207 }
 208
 209 static size_t
 210 insert_values (Hamt **hamt, size_t n, int *elts, bool destructive)
 211 {
 212   size_t cnt = 0;
 213   for (size_t i = 0; i < n; ++i)
 214     {
 215       Hamt_entry *p = make_element (elts [i]);
 216       Hamt_entry *q = p;
 217       if (destructive)
 218         {
 219           if (hamt_insert_x (*hamt, &p))
 220             ++cnt;
 221           else
 222             free_element (q);
 223         }
 224       else
 225         {
 226           Hamt *new_hamt = hamt_insert (*hamt, &p);
 227           if (new_hamt != *hamt)
 228             {
 229               hamt_free (*hamt);
 230               *hamt = new_hamt;
 231               ++cnt;
 232             }
 233           else
 234             {
 235               free_element (q);
 236             }
 237         }
 238     }
 239   return cnt;
 240 }
 241
 242 static size_t
 243 replace_values (Hamt **hamt, size_t n, int *elts, bool destructive)
 244 {
 245   size_t cnt = 0;
 246   for (size_t i = 0; i < n; ++i)
 247     {
 248       Hamt_entry *p = make_element (elts [i]);
 249       if (destructive)
 250         {
 251           if (hamt_replace_x (*hamt, p))
 252             ++cnt;
 253         }
 254       else
 255         {
 256           Hamt *new_hamt = hamt_replace (*hamt, &p);
 257           hamt_free (*hamt);
 258           *hamt = new_hamt;
 259           if (p != NULL)
 260             ++cnt;
 261         }
 262     }
 263   return cnt;
 264 }
 265
 266 static size_t
 267 remove_values (Hamt **hamt, size_t n, int *elts, bool destructive)
 268 {
 269   size_t cnt = 0;
 270   for (size_t i = 0; i < n; ++i)
 271     {
 272       Hamt_entry *p = make_element (elts [i]);
 273       Hamt_entry *q = p;
 274       if (destructive)
 275         {
 276           if (hamt_remove_x (*hamt, p))
 277             ++cnt;
 278         }
 279       else
 280         {
 281           Hamt *new_hamt = hamt_remove (*hamt, &p);
 282           if (new_hamt != *hamt)
 283             {
 284               hamt_free (*hamt);
 285               *hamt = new_hamt;
 286               ++cnt;
 287             }
 288         }
 289       free (q);
 290     }
 291   return cnt;
 292 }
 293
 294 static int val_array1 [10] = {1, 2, 3, 4, 33, 34, 35, 36, 1024, 1025};
 295 static int val_array2 [10] = {1, 2, 34, 36, 1025, 32768, 32769, 32770, 32771,
 296                               32772};
 297
 298 static void
 299 test_functional_update (void)
 300 {
 301   Hamt *hamt = test_hamt_create ();
 302
 303   ASSERT (insert_values (&hamt, 10, val_array1, false) == 10);
 304   ASSERT (element_count (hamt) == 10);
 305   ASSERT (find_values (hamt, 10, val_array1));
 306   ASSERT (insert_values (&hamt, 10, val_array2, false) == 5);
 307   ASSERT (element_count (hamt) == 15);
 308   ASSERT (remove_values (&hamt, 10, val_array1, false) == 10);
 309   ASSERT (element_count (hamt) == 5);
 310   ASSERT (remove_values (&hamt, 10, val_array2, false) == 5);
 311   ASSERT (element_count (hamt) == 0);
 312
 313   ASSERT (replace_values (&hamt, 10, val_array1, false) == 0);
 314   ASSERT (element_count (hamt) == 10);
 315   ASSERT (find_values (hamt, 10, val_array1));
 316   ASSERT (replace_values (&hamt, 10, val_array2, false) == 5);
 317   ASSERT (element_count (hamt) == 15);
 318
 319   hamt_free (hamt);
 320 }
 321
 322 static void
 323 test_destructive_update (void)
 324 {
 325   Hamt *hamt = test_hamt_create ();
 326
 327   ASSERT (insert_values (&hamt, 10, val_array1, true) == 10);
 328   ASSERT (element_count (hamt) == 10);
 329   ASSERT (find_values (hamt, 10, val_array1));
 330   ASSERT (insert_values (&hamt, 10, val_array2, true) == 5);
 331   ASSERT (element_count (hamt) == 15);
 332   ASSERT (remove_values (&hamt, 10, val_array1, true) == 10);
 333   ASSERT (element_count (hamt) == 5);
 334   ASSERT (remove_values (&hamt, 10, val_array2, true) == 5);
 335   ASSERT (element_count (hamt) == 0);
 336
 337   ASSERT (replace_values (&hamt, 10, val_array1, true) == 0);
 338   ASSERT (element_count (hamt) == 10);
 339   ASSERT (find_values (hamt, 10, val_array1));
 340   ASSERT (replace_values (&hamt, 10, val_array2, true) == 5);
 341   ASSERT (element_count (hamt) == 15);
 342
 343   hamt_free (hamt);
 344 }
 345
 346 static void
 347 test_iterator (void)
 348 {
 349   Hamt *hamt = test_hamt_create ();
 350   ASSERT (insert_values (&hamt, 10, val_array1, true) == 10);
 351   Hamt_iterator iter[1];
 352   iter[0] = hamt_iterator (hamt);
 353   size_t cnt = 0;
 354   bool found [10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
 355   Hamt_entry *p;
 356   while (hamt_iterator_next (iter, &p))
 357     {
 358       for (size_t i = 0; i < 10; ++i)
 359         if (val_array1 [i] == entry_value (p))
 360           {
 361             ASSERT (!found [i]);
 362             found [i] = true;
 363             ++cnt;
 364             break;
 365           }
 366     }
 367   ASSERT (cnt == 10);
 368   hamt_iterator_free (iter);
 369   hamt_free (hamt);
 370 }
 371
 372 int
 373 main (void)
 374 {
 375   test_general ();
 376   test_functional_update ();
 377   test_destructive_update ();
 378   test_iterator ();
 379
 380   return test_exit_status;
 381 }