root/maint/gnulib/lib/hamt.c

/* */

DEFINITIONS

1. entry_type
2. init_ref_counter
3. inc_ref_counter
4. dec_ref_counter
5. create_function_table
6. copy_function_table
7. free_function_table
8. hash_element
9. compare_elements
10. free_element
11. init_element
12. alloc_bucket
13. is_shared
14. trienode_count
15. alloc_subtrie
16. copy_entry
17. replace_bucket_element
18. replace_entry
19. insert_entry
20. remove_subtrie_entry
21. remove_bucket_entry
22. hamt_create
23. hamt_copy
24. free_bucket
25. free_entry
26. free_subtrie
27. hamt_free
28. bucket_lookup
29. subtrie_lookup
30. entry_lookup
31. hamt_lookup
32. create_populated_bucket
33. create_populated_subtrie
34. bucket_insert
35. subtrie_insert
36. entry_insert
37. root_insert
38. hamt_insert
39. hamt_replace
40. bucket_remove
41. subtrie_remove
42. entry_remove
43. root_remove
44. hamt_remove
45. bucket_do_while
46. subtrie_do_while
47. entry_do_while
48. hamt_do_while
49. hamt_iterator
50. hamt_iterator_free
51. hamt_iterator_copy
52. bit_width
53. hamt_iterator_next
54. hamt_insert_x
55. hamt_replace_x
56. hamt_remove_x

   1 /* (Persistent) hash array mapped tries.
   2    Copyright (C) 2021 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 #define _GL_HAMT_INLINE _GL_EXTERN_INLINE
  21 #include "hamt.h"
  22 
  23 #include <flexmember.h>
  24 #include <inttypes.h>
  25 #include <stdlib.h>
  26 #include "count-one-bits.h"
  27 #include "verify.h"
  28 #include "xalloc.h"
  29 
  30 /* Reference counters can be shared between different threads if the
  31    entry they belong to is shared between different threads.
  32    Operations on them therefore have to be atomic so that no invalid
  33    state is observable.
  34 
  35    A thread must not modify an entry or its children (!) if its
  36    reference count implies that the entry is shared by at least two
  37    hamts.  */
  38 typedef
  39 #if GL_HAMT_THREAD_SAFE
  40 _Atomic
  41 #endif
  42 size_t ref_counter;
  43 
  44 /***************/
  45 /* Entry Types */
  46 /***************/
  47 
  48 /* Leaf nodes are of type element.  Non-leaf nodes are either subtries
  49    or, if at maximal depth, buckets.  The entry type is stored in the
  50    lower two bits of the reference counter, whereas reference counters
  51    for entries are incremented and decremented in multiples of 4.  */
  52 enum entry_type
  53 {
  54   element_entry = 0,
  55   subtrie_entry = 1,
  56   bucket_entry = 2
  57 };
  58 
  59 /* Return the type an entry.  */
  60 static enum entry_type
  61 entry_type (const Hamt_entry *entry)
     /*  */
  62 {
  63   return entry->ref_count & 3;
  64 }
  65 
  66 /********************/
  67 /* Reference Counts */
  68 /********************/
  69 
  70 /* Initialize the reference counter, storing its type.  */
  71 static void
  72 init_ref_counter (ref_counter *counter, enum entry_type type)
     /*  */
  73 {
  74   *counter = 4 + type;
  75 }
  76 
  77 /* Increase the reference counter of an entry.  */
  78 static void
  79 inc_ref_counter (ref_counter *counter)
     /*  */
  80 {
  81   *counter += 4;
  82 }
  83 
  84 /* Decrease the entry reference counter.  Return false if the entry
  85    can be deleted.  */
  86 static bool
  87 dec_ref_counter (ref_counter *counter)
     /*  */
  88 {
  89   *counter -= 4;
  90   return *counter >= 4;
  91 }
  92 
  93 /**************/
  94 /* Structures */
  95 /**************/
  96 
  97 /* Different generations of a hamt share a function table.  */
  98 struct function_table
  99 {
 100   Hamt_hasher *hasher;
 101   Hamt_comparator *comparator;
 102   Hamt_freer *freer;
 103   ref_counter ref_count;
 104 };
 105 
 106 /* Different generations of a hamt share subtries.  A singleton
 107    subtrie is modelled as a single element.  */
 108 struct subtrie
 109 {
 110   ref_counter ref_count;
 111   /* Nodes carry labels from 0 to 31.  The i-th bit in MAP is set if
 112      the node labelled i is present.  */
 113   uint32_t map;
 114   /* The length of the NODES array is the population count of MAP.
 115      The order of the nodes corresponds to the order of the 1-bits in
 116      MAP.  */
 117   Hamt_entry *nodes[FLEXIBLE_ARRAY_MEMBER];
 118 };
 119 
 120 /* Buckets are used when different elements have the same hash values.  */
 121 struct bucket
 122 {
 123   ref_counter ref_counter;
 124   size_t elt_count;
 125   Hamt_entry *elts[FLEXIBLE_ARRAY_MEMBER];
 126 };
 127 
 128 /* A hamt consists of its function table and the root entry.  */
 129 struct hamt
 130 {
 131   struct function_table *functions;
 132   /* The root entry is NULL for an empty HAMT.  */
 133   Hamt_entry *root;
 134 };
 135 
 136 /*******************/
 137 /* Function Tables */
 138 /*******************/
 139 
 140 /* Allocate and initialize a function table.  */
 141 static struct function_table *
 142 create_function_table (Hamt_hasher *hasher, Hamt_comparator *comparator,
     /*  */
 143                        Hamt_freer *freer)
 144 {
 145   struct function_table *functions = XMALLOC (struct function_table);
 146   functions->hasher = hasher;
 147   functions->comparator = comparator;
 148   functions->freer = freer;
 149   functions->ref_count = 1;
 150   return functions;
 151 }
 152 
 153 /* Increment the reference count and return the function table. */
 154 static struct function_table *
 155 copy_function_table (struct function_table *function_table)
     /*  */
 156 {
 157   ++function_table->ref_count;
 158   return function_table;
 159 }
 160 
 161 /* Decrease the reference count and free the function table if the
 162    reference count drops to zero.  */
 163 static void
 164 free_function_table (struct function_table *function_table)
     /*  */
 165 {
 166   if (--function_table->ref_count)
 167     return;
 168   free (function_table);
 169 }
 170 
 171 /************/
 172 /* Elements */
 173 /************/
 174 
 175 /* Return an element's hash.  */
 176 static size_t
 177 hash_element (const struct function_table *functions, const Hamt_entry *elt)
     /*  */
 178 {
 179   return functions->hasher (elt);
 180 }
 181 
 182 /* Compare two elements.  */
 183 static bool
 184 compare_elements (const struct function_table *functions,
     /*  */
 185                   const Hamt_entry *elt1, const Hamt_entry *elt2)
 186 {
 187   return functions->comparator (elt1, elt2);
 188 }
 189 
 190 /* Free an element.  */
 191 static void
 192 free_element (const struct function_table *functions, Hamt_entry *elt)
     /*  */
 193 {
 194   if (dec_ref_counter (&elt->ref_count))
 195     return;
 196   functions->freer (elt);
 197 }
 198 
 199 /* Return the initialized element.  */
 200 static Hamt_entry *
 201 init_element (Hamt_entry *elt)
     /*  */
 202 {
 203   init_ref_counter (&elt->ref_count, element_entry);
 204   return elt;
 205 }
 206 
 207 /***********/
 208 /* Buckets */
 209 /***********/
 210 
 211 /* Allocate a partially initialized bucket with a given number of elements.  */
 212 static struct bucket *
 213 alloc_bucket (size_t elt_count)
     /*  */
 214 {
 215   struct bucket *bucket
 216     = xmalloc (FLEXSIZEOF (struct bucket, elts,
 217                            sizeof (Hamt_entry) * elt_count));
 218   init_ref_counter (&bucket->ref_counter, bucket_entry);
 219   bucket->elt_count = elt_count;
 220   return bucket;
 221 }
 222 
 223 /***********/
 224 /* Entries */
 225 /***********/
 226 
 227 /* Return true if the entry is shared between two or more hamts.
 228    Otherwise, return false.
 229 
 230    This procedure is used for destructive updates.  If an entry and
 231    all its parents are not shared, it can be updated destructively
 232    without effecting other hamts.  */
 233 static bool
 234 is_shared (const Hamt_entry *entry)
     /*  */
 235 {
 236   return entry->ref_count >= 8;
 237 }
 238 
 239 /* Calculate and return the number of nodes in a subtrie.  */
 240 static int
 241 trienode_count (const struct subtrie *subtrie)
     /*  */
 242 {
 243   return count_one_bits (subtrie->map); /* In Gnulib, we assume that
 244                                            an integer has at least 32
 245                                            bits. */
 246 }
 247 
 248 /* Allocate a partially initialized subtrie with a given number of nodes.  */
 249 static struct subtrie *
 250 alloc_subtrie (int node_count)
     /*  */
 251 {
 252   struct subtrie *subtrie
 253     = xmalloc (FLEXSIZEOF (struct subtrie, nodes,
 254                            sizeof (Hamt_entry) * node_count));
 255   init_ref_counter (&subtrie->ref_count, subtrie_entry);
 256   return subtrie;
 257 }
 258 
 259 /* Return a conceptually copy of an entry.  */
 260 static Hamt_entry *
 261 copy_entry (Hamt_entry *entry)
     /*  */
 262 {
 263   inc_ref_counter (&entry->ref_count);
 264   return entry;
 265 }
 266 
 267 /* Return a new bucket that has the j-th element replaced.  */
 268 static struct bucket *
 269 replace_bucket_element (struct bucket *bucket, int j, Hamt_entry *elt)
     /*  */
 270 {
 271   int n = bucket->elt_count;
 272   struct bucket *new_bucket = alloc_bucket (n);
 273   for (int k = 0; k < n; ++k)
 274     if (k == j)
 275       new_bucket->elts[k] = elt;
 276     else
 277       new_bucket->elts[k] = copy_entry (bucket->elts[k]);
 278   return new_bucket;
 279 }
 280 
 281 /* Return a new subtrie that has the j-th node replaced.  */
 282 static struct subtrie *
 283 replace_entry (struct subtrie *subtrie, int j, Hamt_entry *entry)
     /*  */
 284 {
 285   int n = trienode_count (subtrie);
 286   struct subtrie *new_subtrie = alloc_subtrie (n);
 287   new_subtrie->map = subtrie->map;
 288   for (int k = 0; k < n; ++k)
 289     if (k == j)
 290       new_subtrie->nodes[k] = entry;
 291     else
 292       new_subtrie->nodes[k] = copy_entry (subtrie->nodes[k]);
 293   return new_subtrie;
 294 }
 295 
 296 /* Return a new subtrie that has an entry labelled i inserted at
 297    the j-th position.  */
 298 static struct subtrie *
 299 insert_entry (struct subtrie *subtrie, int i, int j, Hamt_entry *entry)
     /*  */
 300 {
 301   int n = trienode_count (subtrie) + 1;
 302   struct subtrie *new_subtrie = alloc_subtrie (n);
 303   new_subtrie->map = subtrie->map | (1 << i);
 304   for (int k = 0; k < n; ++k)
 305     {
 306       if (k < j)
 307         new_subtrie->nodes[k] = copy_entry (subtrie->nodes[k]);
 308       else if (k > j)
 309         new_subtrie->nodes[k] = copy_entry (subtrie->nodes[k - 1]);
 310       else
 311         new_subtrie->nodes[k] = entry;
 312     }
 313   return new_subtrie;
 314 }
 315 
 316 /* Return a new entry that has the entry labelled i removed from
 317    position j.  */
 318 static Hamt_entry *
 319 remove_subtrie_entry (struct subtrie *subtrie, int i, int j)
     /*  */
 320 {
 321   int n = trienode_count (subtrie) - 1;
 322   if (n == 1)
 323     {
 324       if (j == 0)
 325         return copy_entry (subtrie->nodes[1]);
 326       return copy_entry (subtrie->nodes[0]);
 327     }
 328   struct subtrie *new_subtrie = alloc_subtrie (n);
 329   new_subtrie->map = subtrie->map & ~(1 << i);
 330   for (int k = 0; k < n; ++k)
 331     {
 332       if (k < j)
 333         new_subtrie->nodes[k] = copy_entry (subtrie->nodes[k]);
 334       else if (k >= j)
 335         new_subtrie->nodes[k] = copy_entry (subtrie->nodes[k + 1]);
 336     }
 337   return (Hamt_entry *) new_subtrie;
 338 }
 339 
 340 /* Return a new entry that has the entry at position j removed.  */
 341 static Hamt_entry *
 342 remove_bucket_entry (struct bucket *bucket, int j)
     /*  */
 343 {
 344   int n = bucket->elt_count - 1;
 345   if (n == 1)
 346     {
 347       if (j == 0)
 348         return copy_entry (bucket->elts[1]);
 349       return copy_entry (bucket->elts[0]);
 350     }
 351   struct bucket *new_bucket = alloc_bucket (n);
 352   for (int k = 0; k < n; ++k)
 353     {
 354       if (k < j)
 355         new_bucket->elts[k] = copy_entry (bucket->elts[k]);
 356       else if (k >= j)
 357         new_bucket->elts[k] = copy_entry (bucket->elts[k + 1]);
 358     }
 359   return (Hamt_entry *) new_bucket;
 360 }
 361 
 362 /****************************/
 363 /* Creation and Destruction */
 364 /****************************/
 365 
 366 /* Create a new, empty hash array mapped trie.  */
 367 Hamt *
 368 hamt_create (Hamt_hasher *hasher, Hamt_comparator *comparator,
     /*  */
 369              Hamt_freer *freer)
 370 {
 371   struct function_table *functions
 372     = create_function_table (hasher, comparator, freer);
 373   Hamt *hamt = XMALLOC (Hamt);
 374   hamt->functions = functions;
 375   hamt->root = NULL;
 376   return hamt;
 377 }
 378 
 379 /* Return a copy of the hamt.  */
 380 Hamt *
 381 hamt_copy (Hamt *hamt)
     /*  */
 382 {
 383   Hamt *new_hamt = XMALLOC (Hamt);
 384   new_hamt->functions = copy_function_table (hamt->functions);
 385   new_hamt->root = hamt->root == NULL ? NULL : copy_entry (hamt->root);
 386   return new_hamt;
 387 }
 388 
 389 /* Free a bucket.  */
 390 static void
 391 free_bucket (struct function_table const *functions, struct bucket *bucket)
     /*  */
 392 {
 393   if (dec_ref_counter (&bucket->ref_counter))
 394     return;
 395   size_t elt_count = bucket->elt_count;
 396   Hamt_entry *const *elts = bucket->elts;
 397   for (size_t i = 0; i < elt_count; ++i)
 398     free_element (functions, elts[i]);
 399   free (bucket);
 400 }
 401 
 402 /* Forward declaration.  */
 403 static void free_subtrie (struct function_table const *functions,
 404                           struct subtrie *subtrie);
 405 
 406 /* Free an entry.  */
 407 static void
 408 free_entry (struct function_table const *functions, Hamt_entry *entry)
     /*  */
 409 {
 410   switch (entry_type (entry))
 411     {
 412     case element_entry:
 413       free_element (functions, entry);
 414       break;
 415     case subtrie_entry:
 416       free_subtrie (functions, (struct subtrie *) entry);
 417       break;
 418     case bucket_entry:
 419       free_bucket (functions, (struct bucket *) entry);
 420       break;
 421     default:
 422       assume (0);
 423     }
 424 }
 425 
 426 /* Free a trie recursively.  */
 427 static void
 428 free_subtrie (struct function_table const *functions, struct subtrie *subtrie)
     /*  */
 429 {
 430   if (dec_ref_counter (&subtrie->ref_count))
 431     return;
 432   int n = trienode_count (subtrie);
 433   Hamt_entry **node_ptr = subtrie->nodes;
 434   for (int j = 0; j < n; ++j)
 435     free_entry (functions, *node_ptr++);
 436   free (subtrie);
 437 }
 438 
 439 /* Free a hamt.  */
 440 void
 441 hamt_free (Hamt *hamt)
     /*  */
 442 {
 443   if (hamt->root != NULL)
 444     free_entry (hamt->functions, hamt->root);
 445   free_function_table (hamt->functions);
 446   free (hamt);
 447 }
 448 
 449 /**********/
 450 /* Lookup */
 451 /**********/
 452 
 453 /* Lookup an element in a bucket.  */
 454 static Hamt_entry *
 455 bucket_lookup (const struct function_table *functions,
     /*  */
 456                const struct bucket *bucket, const void *elt)
 457 {
 458   size_t elt_count = bucket->elt_count;
 459   Hamt_entry *const *elts = bucket->elts;
 460   for (size_t i = 0; i < elt_count; ++i)
 461     {
 462       if (compare_elements (functions, elt, elts[i]))
 463         return *elts;
 464     }
 465   return NULL;
 466 }
 467 
 468 /* Forward declaration.  */
 469 static Hamt_entry *entry_lookup (const struct function_table *functions,
 470                                  Hamt_entry *entry,
 471                                  const void *elt, size_t hash);
 472 
 473 /* Lookup an element in a bucket.  */
 474 static Hamt_entry *
 475 subtrie_lookup (const struct function_table *functions,
     /*  */
 476                 const struct subtrie *subtrie, const void *elt,
 477                 size_t hash)
 478 {
 479   uint32_t map = subtrie->map;
 480   int i = hash & 31;
 481 
 482   if (! (map & (1 << i)))
 483     return NULL;
 484 
 485   int j = i == 0 ? 0 : count_one_bits (map << (32 - i));
 486   return entry_lookup (functions, subtrie->nodes[j], elt, hash >> 5);
 487 }
 488 
 489 /* Lookup an element in an entry.  */
 490 static Hamt_entry *
 491 entry_lookup (const struct function_table *functions, Hamt_entry *entry,
     /*  */
 492               const void *elt, size_t hash)
 493 {
 494   switch (entry_type (entry))
 495     {
 496     case element_entry:
 497       if (compare_elements (functions, elt, entry))
 498         return entry;
 499       return NULL;
 500     case subtrie_entry:
 501       return subtrie_lookup (functions, (struct subtrie *) entry, elt, hash);
 502     case bucket_entry:
 503       return bucket_lookup (functions, (struct bucket *) entry, elt);
 504     default:
 505       assume (0);
 506     }
 507 }
 508 
 509 /* If ELT matches an entry in HAMT, return this entry.  Otherwise,
 510    return NULL.  */
 511 Hamt_entry *
 512 hamt_lookup (const Hamt *hamt, const void *elt)
     /*  */
 513 {
 514   if (hamt->root == NULL)
 515     return NULL;
 516 
 517   return entry_lookup (hamt->functions, hamt->root, elt,
 518                        hash_element (hamt->functions, elt));
 519 }
 520 
 521 /**************************/
 522 /* Insertion and Deletion */
 523 /**************************/
 524 
 525 /* Create a bucket populated with two elements.  */
 526 static struct bucket *
 527 create_populated_bucket (Hamt_entry *elt1, Hamt_entry *elt2)
     /*  */
 528 {
 529   struct bucket *bucket = alloc_bucket (2);
 530   bucket->elts[0] = elt1;
 531   bucket->elts[1] = elt2;
 532   return bucket;
 533 }
 534 
 535 /* Create a chain of subtrie nodes so that the resulting trie is
 536    populated with exactly two elements.  */
 537 static Hamt_entry *
 538 create_populated_subtrie (Hamt_entry *elt1, Hamt_entry *elt2, size_t hash1,
     /*  */
 539                           size_t hash2, int depth)
 540 {
 541   if (depth >= _GL_HAMT_MAX_DEPTH)
 542     return (Hamt_entry *) create_populated_bucket (elt1, elt2);
 543 
 544   struct subtrie *subtrie;
 545   int i1 = hash1 & 31;
 546   int i2 = hash2 & 31;
 547   if (i1 != i2)
 548     {
 549       subtrie = alloc_subtrie (2);
 550       subtrie->map = (1 << i1) | (1 << i2);
 551       if (i1 < i2)
 552         {
 553           subtrie->nodes[0] = elt1;
 554           subtrie->nodes[1] = elt2;
 555         }
 556       else
 557         {
 558           subtrie->nodes[0] = elt2;
 559           subtrie->nodes[1] = elt1;
 560         }
 561     }
 562   else
 563     {
 564       subtrie = alloc_subtrie (1);
 565       subtrie->map = 1 << i1;
 566       subtrie->nodes[0]
 567         = create_populated_subtrie (elt1, elt2, hash1 >> 5, hash2 >> 5,
 568                                     depth + 1);
 569     }
 570   return (Hamt_entry *) subtrie;
 571 }
 572 
 573 /* Insert or replace an element in a bucket.  */
 574 static struct bucket *
 575 bucket_insert (const struct function_table *functions, struct bucket *bucket,
     /*  */
 576                Hamt_entry **elt_ptr, bool replace, bool shared)
 577 {
 578   size_t elt_count = bucket->elt_count;
 579   Hamt_entry **elts = bucket->elts;
 580   for (size_t i = 0; i < elt_count; ++i)
 581     {
 582       if (compare_elements (functions, *elt_ptr, elts[i]))
 583         {
 584           if (replace)
 585             {
 586               if (shared)
 587                 {
 588                   struct bucket *new_bucket
 589                     = replace_bucket_element (bucket, i,
 590                                               copy_entry (*elt_ptr));
 591                   *elt_ptr = elts[i];
 592                   return new_bucket;
 593                 }
 594               free_element (functions, elts[i]);
 595               elts[i] = copy_entry (*elt_ptr);
 596               return bucket;
 597             }
 598           *elt_ptr = *elt_ptr == elts[i] ? NULL : elts[i];
 599           return bucket;
 600         }
 601     }
 602   struct bucket *new_bucket = alloc_bucket (elt_count + 1);
 603   new_bucket->elts[0] = copy_entry (*elt_ptr);
 604   for (size_t i = 0; i < elt_count; ++i)
 605     {
 606       new_bucket->elts[i + 1] = copy_entry (bucket->elts[i]);
 607     }
 608   if (replace)
 609     *elt_ptr = NULL;
 610   return new_bucket;
 611 }
 612 
 613 /* Forward declaration.  */
 614 static Hamt_entry *entry_insert (const struct function_table *functions,
 615                                  Hamt_entry *subtrie, Hamt_entry **elt_ptr,
 616                                  size_t hash, int depth, bool replace,
 617                                  bool shared);
 618 
 619 /* Insert or replace an element in a subtrie.  */
 620 static struct subtrie *
 621 subtrie_insert (const struct function_table *functions, struct subtrie *subtrie,
     /*  */
 622                 Hamt_entry **elt_ptr, size_t hash, int depth, bool replace,
 623                 bool shared)
 624 {
 625   uint32_t map = subtrie->map;
 626   int i = hash & 31;
 627   int j = i == 0 ? 0 : count_one_bits (map << (32 - i));
 628   if (map & (1 << i))
 629     {
 630       Hamt_entry *entry = subtrie->nodes[j];
 631       Hamt_entry *new_entry
 632         = entry_insert (functions, entry, elt_ptr, hash >> 5, depth + 1,
 633                         replace, shared);
 634       if (new_entry != entry)
 635         {
 636           if (shared)
 637             return replace_entry (subtrie, j, new_entry);
 638           free_entry (functions, entry);
 639           subtrie->nodes[j] = new_entry;
 640         }
 641       return subtrie;
 642     }
 643   Hamt_entry *entry = copy_entry (*elt_ptr);
 644   if (replace)
 645     *elt_ptr = NULL;
 646   return insert_entry (subtrie, i, j, entry);
 647 }
 648 
 649 /* Insert or replace an element in an entry.
 650 
 651    REPLACE is true if we want replace instead of insert semantics.
 652    SHARED is false if a destructive update has been requested and none
 653    of the parent nodes are shared.  If an entry cannot be inserted
 654    because the same entry with respect to pointer equality is already
 655    present, *ELT_PTR is set to NULL to mark this special case.  */
 656 static Hamt_entry *
 657 entry_insert (const struct function_table *functions, Hamt_entry *entry,
     /*  */
 658               Hamt_entry **elt_ptr, size_t hash, int depth, bool replace,
 659               bool shared)
 660 {
 661   shared |= is_shared (entry);
 662   switch (entry_type (entry))
 663     {
 664     case element_entry:
 665       if (compare_elements (functions, *elt_ptr, entry))
 666         {
 667           if (replace)
 668             {
 669               if (shared)
 670                 {
 671                   Hamt_entry *new_entry = copy_entry (*elt_ptr);
 672                   *elt_ptr = entry;
 673                   return new_entry;
 674                 }
 675               return copy_entry (*elt_ptr);
 676             }
 677           *elt_ptr = *elt_ptr == entry ? NULL : entry;
 678           return entry;
 679         }
 680       Hamt_entry *new_entry = copy_entry (*elt_ptr);
 681       if (replace)
 682         *elt_ptr = NULL;
 683       return create_populated_subtrie (new_entry, copy_entry (entry), hash,
 684                                        (hash_element (functions, entry)
 685                                         >> (5 * depth)), depth);
 686     case subtrie_entry:
 687       return (Hamt_entry *)
 688         subtrie_insert (functions, (struct subtrie *) entry, elt_ptr, hash,
 689                         depth, replace, shared);
 690     case bucket_entry:
 691       return (Hamt_entry *)
 692         bucket_insert (functions, (struct bucket *) entry, elt_ptr, replace,
 693                        shared);
 694     default:
 695       assume (0);
 696     }
 697 }
 698 
 699 /* Insert or replace an element in the root.  */
 700 static Hamt_entry *
 701 root_insert (const struct function_table *functions, Hamt_entry *root,
     /*  */
 702              Hamt_entry **elt_ptr, bool replace, bool shared)
 703 {
 704   if (root == NULL)
 705     return copy_entry (*elt_ptr);
 706 
 707  return entry_insert (functions, root, elt_ptr,
 708                       hash_element (functions, *elt_ptr), 0, replace, shared);
 709 }
 710 
 711 /* If *ELT_PTR matches an element already in HAMT, set *ELT_PTR to the
 712    element from the table and return HAMT.  Otherwise, insert *ELT_PTR
 713    into a copy of the HAMT and return the copy.  */
 714 Hamt *
 715 hamt_insert (Hamt *hamt, Hamt_entry **elt_ptr)
     /*  */
 716 {
 717   Hamt_entry *elt = *elt_ptr;
 718   Hamt_entry *new_entry = root_insert (hamt->functions, hamt->root,
 719                                        elt_ptr, false, true);
 720   if (*elt_ptr == NULL)
 721     *elt_ptr = elt;
 722 
 723   if (new_entry == hamt->root)
 724     return hamt;
 725 
 726   Hamt *new_hamt = XMALLOC (Hamt);
 727   new_hamt->functions = copy_function_table (hamt->functions);
 728   new_hamt->root = new_entry;
 729   return new_hamt;
 730 }
 731 
 732 /* Insert *ELT_PTR into a copy of HAMT and return the copy.  If an
 733    existing element was replaced, set *ELT_PTR to this element, and to
 734    NULL otherwise. */
 735 Hamt *
 736 hamt_replace (Hamt *hamt, Hamt_entry **elt_ptr)
     /*  */
 737 {
 738   Hamt *new_hamt = XMALLOC (Hamt);
 739   new_hamt->functions = copy_function_table (hamt->functions);
 740   new_hamt->root = root_insert (hamt->functions, hamt->root, elt_ptr, true,
 741                                 true);
 742   return new_hamt;
 743 }
 744 
 745 /* Remove an element in a bucket if found.  */
 746 static Hamt_entry *
 747 bucket_remove (const struct function_table *functions, struct bucket *bucket,
     /*  */
 748                Hamt_entry **elt_ptr)
 749 {
 750   size_t elt_count = bucket->elt_count;
 751   Hamt_entry *const *elts = bucket->elts;
 752   for (size_t i = 0; i < elt_count; ++i)
 753     {
 754       if (compare_elements (functions, *elt_ptr, elts[i]))
 755         {
 756           *elt_ptr = elts[i];
 757           return remove_bucket_entry (bucket, i);
 758         }
 759     }
 760   *elt_ptr = NULL;
 761   return (Hamt_entry *) bucket;
 762 }
 763 
 764 /* Forward declaration.  */
 765 static Hamt_entry *entry_remove (const struct function_table *functions,
 766                                  Hamt_entry *entry, Hamt_entry **elt_ptr,
 767                                  size_t hash, int depth, bool shared);
 768 
 769 /* Remove an element in a subtrie if found.  */
 770 static Hamt_entry *
 771 subtrie_remove (const struct function_table *functions, struct subtrie *subtrie,
     /*  */
 772                 Hamt_entry **elt_ptr, size_t hash, int depth, bool shared)
 773 {
 774   uint32_t map = subtrie->map;
 775   int i = hash & 31;
 776   int j = i == 0 ? 0 : count_one_bits (map << (32 - i));
 777   if (map & (1 << i))
 778     {
 779       Hamt_entry *entry = subtrie->nodes[j];
 780       Hamt_entry *new_entry
 781         = entry_remove (functions, entry, elt_ptr, hash >> 5, depth + 1,
 782                         shared);
 783       if (new_entry == NULL)
 784         return remove_subtrie_entry (subtrie, i, j);
 785       if (new_entry != entry)
 786         {
 787           if (shared)
 788             return (Hamt_entry *) replace_entry (subtrie, j, new_entry);
 789           free_entry (functions, entry);
 790           subtrie->nodes[j] = new_entry;
 791         }
 792       return (Hamt_entry *) subtrie;
 793     }
 794   *elt_ptr = NULL;
 795   return (Hamt_entry *) subtrie;
 796 }
 797 
 798 /* Remove an element in an entry if found.
 799 
 800    SHARED is false if a destructive update has been requested and none
 801    of the parent nodes are shared.  If an entry cannot be
 802    removed, *ELT_PTR is set to NULL.  */
 803 static Hamt_entry *
 804 entry_remove (const struct function_table *functions, Hamt_entry *entry,
     /*  */
 805               Hamt_entry **elt_ptr, size_t hash, int depth, bool shared)
 806 {
 807   shared |= is_shared (entry);
 808   switch (entry_type (entry))
 809     {
 810     case element_entry:
 811       if (compare_elements (functions, *elt_ptr, entry))
 812         {
 813           *elt_ptr = entry;
 814           return NULL;
 815         }
 816       *elt_ptr = NULL;
 817       return entry;
 818     case subtrie_entry:
 819       return subtrie_remove (functions, (struct subtrie *) entry, elt_ptr, hash,
 820                              depth, shared);
 821     case bucket_entry:
 822       return bucket_remove (functions, (struct bucket *) entry, elt_ptr);
 823     default:
 824       assume (0);
 825     }
 826 }
 827 
 828 /* Remove an element in the root.  */
 829 static Hamt_entry *
 830 root_remove (const struct function_table *functions, Hamt_entry *root,
     /*  */
 831              Hamt_entry **elt_ptr, bool shared)
 832 {
 833   if (root == NULL)
 834     return NULL;
 835 
 836   return entry_remove (functions, root, elt_ptr,
 837                        hash_element (functions, *elt_ptr), 0, shared);
 838 }
 839 
 840 /* If *ELT_PTR matches an element already in HAMT, set *ELT_PTR to the
 841 element from the table, remove the element from a copy of the hamt and
 842 return the copy.  Otherwise, return HAMT.  */
 843 Hamt *
 844 hamt_remove (Hamt *hamt, Hamt_entry **elt_ptr)
     /*  */
 845 {
 846   Hamt_entry *elt = *elt_ptr;
 847   Hamt_entry *new_entry = root_remove (hamt->functions, hamt->root, elt_ptr,
 848                                        true);
 849   if (*elt_ptr == NULL)
 850     *elt_ptr = elt;
 851 
 852   if (new_entry == hamt->root)
 853     return hamt;
 854 
 855   Hamt *new_hamt = XMALLOC (Hamt);
 856   new_hamt->functions = copy_function_table (hamt->functions);
 857   new_hamt->root = new_entry;
 858   return new_hamt;
 859 }
 860 
 861 /*************/
 862 /* Iteration */
 863 /*************/
 864 
 865 /* Walk a bucket.  */
 866 static size_t
 867 bucket_do_while (const struct bucket *bucket, Hamt_processor *proc, void *data,
     /*  */
 868                  bool *success)
 869 {
 870   size_t cnt = 0;
 871   size_t elt_count = bucket->elt_count;
 872   Hamt_entry *const *elts = bucket->elts;
 873   for (size_t i = 0; i < elt_count; ++i)
 874     {
 875       *success = proc (elts[i], data);
 876       if (*success == false)
 877         return cnt;
 878       ++cnt;
 879     }
 880   return cnt;
 881 }
 882 
 883 /* Forward declaration.  */
 884 static size_t entry_do_while (Hamt_entry *entry, Hamt_processor *proc,
 885                               void *data, bool *success);
 886 
 887 /* Walk a subtrie.  */
 888 static size_t subtrie_do_while (const struct subtrie *subtrie,
     /*  */
 889                                 Hamt_processor *proc, void *data, bool *success)
 890 {
 891   size_t cnt = 0;
 892   int n = trienode_count (subtrie);
 893   Hamt_entry *const *node_ptr = subtrie->nodes;
 894   for (int j = 0; j < n; ++j)
 895     {
 896       cnt += entry_do_while (*node_ptr++, proc, data, success);
 897       if (!success)
 898         return cnt;
 899     }
 900   return cnt;
 901 }
 902 
 903 /* Walk an entry.  */
 904 static size_t
 905 entry_do_while (Hamt_entry *entry, Hamt_processor *proc, void *data,
     /*  */
 906                 bool *success)
 907 {
 908   switch (entry_type (entry))
 909     {
 910     case element_entry:
 911       *success = proc (entry, data);
 912       return *success ? 1 : 0;
 913     case subtrie_entry:
 914       return subtrie_do_while ((struct subtrie *) entry, proc, data, success);
 915     case bucket_entry:
 916       return bucket_do_while ((struct bucket *) entry, proc, data, success);
 917     default:
 918       assume (0);
 919     }
 920 }
 921 
 922 /* Call PROC for every entry of the hamt until it returns false.  The
 923    first argument of PROC is the entry, the second argument is the value
 924    of DATA as received.  Return the number of calls that returned
 925    true.  */
 926 size_t
 927 hamt_do_while (const Hamt *hamt, Hamt_processor *proc, void *data)
     /*  */
 928 {
 929   if (hamt->root == NULL)
 930     return 0;
 931 
 932   bool success = true;
 933   return entry_do_while (hamt->root, proc, data, &success);
 934 }
 935 
 936 /* Create an iterator with a copy of the hamt.
 937 
 938    For a valid iterator state the following is true: If DEPTH is
 939    negative, the iterator is exhausted.  Otherwise, ENTRY[DEPTH] is
 940    either the element that is produced next, or a bucket such that the
 941    element at POSITION of the bucket is produced next.
 942 */
 943 Hamt_iterator
 944 hamt_iterator (Hamt *hamt)
     /*  */
 945 {
 946   Hamt_iterator iter;
 947   iter.hamt = hamt_copy (hamt);
 948   Hamt_entry *entry = hamt->root;
 949   iter.path = 0;
 950   iter.position = 0;
 951   if (entry == NULL)
 952     {
 953       iter.depth = -1;
 954       return iter;
 955     }
 956   iter.depth = 0;
 957   while (iter.entry[iter.depth] = entry, entry_type (entry) == subtrie_entry)
 958     {
 959       const struct subtrie *subtrie = (const struct subtrie *) entry;
 960       ++iter.depth;
 961       entry = subtrie->nodes[0];
 962     }
 963   return iter;
 964 }
 965 
 966 /* Free the iterator and the associated hamt copy.  */
 967 void
 968 hamt_iterator_free (Hamt_iterator *iter)
     /*  */
 969 {
 970   hamt_free (iter->hamt);
 971 }
 972 
 973 /* Create a copy of the complete iterator state, including the
 974    hamt.  */
 975 Hamt_iterator
 976 hamt_iterator_copy (Hamt_iterator *iter)
     /*  */
 977 {
 978   Hamt_iterator new_iter = *iter;
 979   new_iter.hamt = hamt_copy (iter->hamt);
 980   return new_iter;
 981 }
 982 
 983 /* Return the number of significant bits at DEPTH.  */
 984 static int
 985 bit_width (int depth)
     /*  */
 986 {
 987   if (depth < _GL_HAMT_MAX_DEPTH - 1)
 988     return 5;
 989   return SIZE_WIDTH - 5 * (_GL_HAMT_MAX_DEPTH - 1);
 990 }
 991 
 992 /* The actual iteration.  */
 993 bool
 994 hamt_iterator_next (Hamt_iterator *iter, Hamt_entry **elt_ptr)
     /*  */
 995 {
 996   int depth = iter->depth;
 997   if (depth < 0)
 998     return false;
 999 
1000   Hamt_entry *entry = iter->entry[depth];
1001   if (entry_type (entry) == bucket_entry)
1002     {
1003       struct bucket *bucket = (struct bucket *) entry;
1004       *elt_ptr = bucket->elts[iter->position];
1005       if (++iter->position < bucket->elt_count)
1006         return true;
1007     }
1008   else
1009     *elt_ptr = entry;
1010 
1011   struct subtrie *subtrie;
1012   while (iter->depth-- > 0)
1013     {
1014       int width = bit_width (iter->depth);
1015       int j = (iter->path & ((1 << width) - 1)) + 1;
1016       subtrie = (struct subtrie *) iter->entry[iter->depth];
1017       if (j < trienode_count (subtrie))
1018         {
1019           ++iter->path;
1020           while (iter->entry[++iter->depth] = subtrie->nodes[j],
1021                  entry_type (iter->entry[iter->depth]) == subtrie_entry)
1022             {
1023               width = bit_width (iter->depth);
1024               iter->path <<= width;
1025               j = 0;
1026               subtrie = (struct subtrie *) iter->entry[iter->depth];
1027             }
1028           iter->position = 0;
1029           break;
1030         }
1031       iter->path >>= width;
1032     }
1033 
1034   return true;
1035 }
1036 
1037 /***********************/
1038 /* Destructive Updates */
1039 /***********************/
1040 
1041 /* If *ELT_PTR matches an element already in HAMT, set *ELT_PTR to the
1042    element from the table and return false.  Otherwise, insert *ELT_PTR
1043    destructively into the hamt and return true.  */
1044 bool
1045 hamt_insert_x (Hamt *hamt, Hamt_entry **elt_ptr)
     /*  */
1046 {
1047   Hamt_entry *elt = *elt_ptr;
1048   Hamt_entry *old_root = hamt->root;
1049   hamt->root = root_insert (hamt->functions, old_root, elt_ptr, false, false);
1050   if (old_root != hamt->root && old_root != NULL)
1051     free_entry (hamt->functions, old_root);
1052   if (*elt_ptr == NULL)
1053     {
1054       *elt_ptr = elt;
1055       return false;
1056     }
1057   return *elt_ptr == elt;
1058 }
1059 
1060 /* Insert ELT destructively into HAMT.  If an existing element was
1061    replaced, return true.  Otherwise, return false.  */
1062 bool
1063 hamt_replace_x (Hamt *hamt, Hamt_entry *elt)
     /*  */
1064 {
1065   Hamt_entry *old_root = hamt->root;
1066   hamt->root = root_insert (hamt->functions, old_root, &elt, true, false);
1067   if (old_root != hamt->root && old_root != NULL)
1068     free_entry (hamt->functions, old_root);
1069   return elt != NULL;
1070 }
1071 
1072 /* If ELT matches an element already in HAMT, remove the element
1073    destructively from the hamt and return true.  Otherwise, return
1074    false.  */
1075 bool
1076 hamt_remove_x (Hamt *hamt, Hamt_entry *elt)
     /*  */
1077 {
1078   Hamt_entry *old_root = hamt->root;
1079   hamt->root = root_remove (hamt->functions, old_root, &elt, false);
1080   if (old_root != hamt->root)
1081     free_entry (hamt->functions, old_root);
1082   return elt != NULL;
1083 }

/* */