utility/genhash.c

   1 /**********************************************************************
   2  Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
   3    This program is free software; you can redistribute it and/or modify
   4    it under the terms of the GNU General Public License as published by
   5    the Free Software Foundation; either version 2, or (at your option)
   6    any later version.
   7
   8    This program is distributed in the hope that it will be useful,
   9    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11    GNU General Public License for more details.
  12 ***********************************************************************/
  13
  14 /****************************************************************************
  15    A general-purpose generic hash table implementation.
  16
  17    Based on implementation previous included in registry.c, but separated
  18    out so that can be used more generally.  Maybe we should just use glib?
  19
  20       Original author:  David Pfitzner  dwp@mso.anu.edu.au
  21
  22    A hash table maps keys to user data values, using a user-supplied hash
  23    function to do this efficiently. Here both keys and values are general
  24    data represented by (void*) pointers. Memory management of both keys
  25    and data is the responsibility of the caller: that is, the caller must
  26    ensure that the memory (especially for keys) remains valid (allocated)
  27    for as long as required (typically, the life of the genhash table).
  28    (Otherwise, to allocate keys internally would either have to restrict
  29    key type (e.g., strings), or have user-supplied function to duplicate
  30    a key type.  See further comments below.)
  31
  32    User-supplied functions required are:
  33    key_val_func: map key to bucket number given number of buckets; should
  34                  map keys fairly evenly to range 0 to (num_buckets - 1)
  35                  inclusive.
  36
  37    key_comp_func: compare keys for equality, necessary for lookups for keys
  38                   which map to the same genhash value. Keys which compare
  39                   equal should map to the same hash value. Returns 0 for
  40                   equality, so can use qsort-type comparison function (but
  41                   the hash table does not make use of the ordering
  42                   information if the return value is non-zero).
  43
  44    Some constructors also accept following functions to be registered:
  45    key_copy_func: This is called when assigning a new value to a bucket.
  46    key_free_func: This is called when genhash no longer needs key construct.
  47                   Note that one key construct gets freed even when it is
  48                   replaced with another that is considered identical by
  49                   key_comp_func().
  50    data_copy_func: same as 'key_copy_func', but for data.
  51    data_free_func: same as 'key_free_func', but for data.
  52
  53    Implementation uses open hashing. Collision resolution is done by
  54    separate chaining with linked lists. Resize hash table when deemed
  55    necessary by making and populating a new table.
  56 ****************************************************************************/
  57
  58 #ifdef HAVE_CONFIG_H
  59 #include <fc_config.h>
  60 #endif
  61
  62 #include <string.h>
  63
  64 /* utility */
  65 #include "log.h"
  66 #include "mem.h"
  67 #include "shared.h"     /* ARRAY_SIZE */
  68 #include "support.h"
  69
  70 #include "genhash.h"
  71
  72 #define FULL_RATIO 0.75         /* consider expanding when above this */
  73 #define MIN_RATIO 0.24          /* shrink when below this */
  74
  75 struct genhash_entry {
  76   void *key;
  77   void *data;
  78   genhash_val_t hash_val;
  79   struct genhash_entry *next;
  80 };
  81
  82 /* Contents of the opaque type: */
  83 struct genhash {
  84   struct genhash_entry **buckets;
  85   genhash_val_fn_t key_val_func;
  86   genhash_comp_fn_t key_comp_func;
  87   genhash_copy_fn_t key_copy_func;
  88   genhash_free_fn_t key_free_func;
  89   genhash_copy_fn_t data_copy_func;
  90   genhash_free_fn_t data_free_func;
  91   size_t num_buckets;
  92   size_t num_entries;
  93   bool no_shrink;               /* Do not auto-shrink when set. */
  94 };
  95
  96 struct genhash_iter {
  97   struct iterator vtable;
  98   struct genhash_entry *const *bucket, *const *end;
  99   const struct genhash_entry *iterator;
 100 };
 101
 102 #define GENHASH_ITER(p) ((struct genhash_iter *) (p))
 103
 104
 105 /****************************************************************************
 106   A supplied genhash function appropriate to nul-terminated strings.
 107   Prefers table sizes that are prime numbers.
 108 ****************************************************************************/
 109 genhash_val_t genhash_str_val_func(const char *vkey)
 110 {
 111   unsigned long result = 0;
 112
 113   for (; *vkey != '\0'; vkey++) {
 114     result *= 5;
 115     result += *vkey;
 116   }
 117   result &= 0xFFFFFFFF; /* To make results independent of sizeof(long) */
 118   return result;
 119 }
 120
 121 /****************************************************************************
 122   A supplied function for comparison of nul-terminated strings:
 123 ****************************************************************************/
 124 bool genhash_str_comp_func(const char *vkey1, const char *vkey2)
 125 {
 126   return 0 == strcmp(vkey1, vkey2);
 127 }
 128
 129 /****************************************************************************
 130   Copy function for string allocation.
 131 ****************************************************************************/
 132 char *genhash_str_copy_func(const char *vkey)
 133 {
 134   return fc_strdup(NULL != vkey ? vkey : "");
 135 }
 136
 137 /****************************************************************************
 138   Free function for string allocation.
 139 ****************************************************************************/
 140 void genhash_str_free_func(char *vkey)
 141 {
 142 #ifdef DEBUG
 143   fc_assert_ret(NULL != vkey);
 144 #endif
 145   free(vkey);
 146 }
 147
 148
 149 /****************************************************************************
 150   Calculate a "reasonable" number of buckets for a given number of entries.
 151   Gives a prime number far from powers of 2, allowing at least a factor of
 152   2 from the given number of entries for breathing room.
 153
 154   Generalized restrictions on the behavior of this function:
 155   * MIN_BUCKETS <= genhash_calc_num_buckets(x)
 156   * genhash_calc_num_buckets(x) * MIN_RATIO < x  whenever
 157     x > MIN_BUCKETS * MIN_RATIO.
 158   * genhash_calc_num_buckets(x) * FULL_RATIO > x.
 159   This one is more of a recommendation, to ensure enough free space:
 160   * genhash_calc_num_buckets(x) >= 2 * x.
 161 ****************************************************************************/
 162 #define MIN_BUCKETS 29  /* Historical purposes. */
 163 static size_t genhash_calc_num_buckets(size_t num_entries)
 164 {
 165   /* A bunch of prime numbers close to successive elements of the sequence
 166    * A_n = 3 * 2 ^ n; to be used for table sizes. */
 167   static const size_t sizes[] = {
 168     MIN_BUCKETS,          53,         97,           193,
 169     389,       769,       1543,       3079,         6151,
 170     12289,     24593,     49157,      98317,        196613,
 171     393241,    786433,    1572869,    3145739,      6291469,
 172     12582917,  25165843,  50331653,   100663319,    201326611,
 173     402653189, 805306457, 1610612741, 3221225473ul, 4294967291ul
 174   };
 175   const size_t *pframe = sizes, *pmid;
 176   int fsize = ARRAY_SIZE(sizes) - 1, lpart;
 177
 178   num_entries <<= 1; /* breathing room */
 179
 180   while (fsize > 0) {
 181     lpart = fsize >> 1;
 182     pmid = pframe + lpart;
 183     if (*pmid < num_entries) {
 184       pframe = pmid + 1;
 185       fsize = fsize - lpart - 1;
 186     } else {
 187       fsize = lpart;
 188     }
 189   }
 190   return *pframe;
 191 }
 192
 193 /****************************************************************************
 194   Internal constructor, specifying exact number of buckets.
 195   Allows to specify functions to free the memory allocated for the key and
 196   user-data that get called when removing the bucket from the hash table or
 197   changing key/user-data values.
 198
 199   NB: Be sure to check the "copy constructor" genhash_copy() if you change
 200   this function significantly.
 201 ****************************************************************************/
 202 static struct genhash *
 203 genhash_new_nbuckets(genhash_val_fn_t key_val_func,
 204                      genhash_comp_fn_t key_comp_func,
 205                      genhash_copy_fn_t key_copy_func,
 206                      genhash_free_fn_t key_free_func,
 207                      genhash_copy_fn_t data_copy_func,
 208                      genhash_free_fn_t data_free_func,
 209                      size_t num_buckets)
 210 {
 211   struct genhash *pgenhash = fc_malloc(sizeof(*pgenhash));
 212
 213   log_debug("New genhash table with %lu buckets",
 214             (long unsigned) num_buckets);
 215
 216   pgenhash->buckets = fc_calloc(num_buckets, sizeof(*pgenhash->buckets));
 217   pgenhash->key_val_func = key_val_func;
 218   pgenhash->key_comp_func = key_comp_func;
 219   pgenhash->key_copy_func = key_copy_func;
 220   pgenhash->key_free_func = key_free_func;
 221   pgenhash->data_copy_func = data_copy_func;
 222   pgenhash->data_free_func = data_free_func;
 223   pgenhash->num_buckets = num_buckets;
 224   pgenhash->num_entries = 0;
 225   pgenhash->no_shrink = FALSE;
 226
 227   return pgenhash;
 228 }
 229
 230 /****************************************************************************
 231   Constructor specifying number of entries.
 232   Allows to specify functions to free the memory allocated for the key and
 233   user-data that get called when removing the bucket from the hash table or
 234   changing key/user-data values.
 235 ****************************************************************************/
 236 struct genhash *
 237 genhash_new_nentries_full(genhash_val_fn_t key_val_func,
 238                           genhash_comp_fn_t key_comp_func,
 239                           genhash_copy_fn_t key_copy_func,
 240                           genhash_free_fn_t key_free_func,
 241                           genhash_copy_fn_t data_copy_func,
 242                           genhash_free_fn_t data_free_func,
 243                           size_t nentries)
 244 {
 245   return genhash_new_nbuckets(key_val_func, key_comp_func,
 246                               key_copy_func, key_free_func,
 247                               data_copy_func, data_free_func,
 248                               genhash_calc_num_buckets(nentries));
 249 }
 250
 251 /****************************************************************************
 252   Constructor specifying number of entries.
 253 ****************************************************************************/
 254 struct genhash *genhash_new_nentries(genhash_val_fn_t key_val_func,
 255                                      genhash_comp_fn_t key_comp_func,
 256                                      size_t nentries)
 257 {
 258   return genhash_new_nbuckets(key_val_func, key_comp_func,
 259                               NULL, NULL, NULL, NULL,
 260                               genhash_calc_num_buckets(nentries));
 261 }
 262
 263 /****************************************************************************
 264   Constructor with unspecified number of entries.
 265   Allows to specify functions to free the memory allocated for the key and
 266   user-data that get called when removing the bucket from the hash table or
 267   changing key/user-data values.
 268 ****************************************************************************/
 269 struct genhash *genhash_new_full(genhash_val_fn_t key_val_func,
 270                                  genhash_comp_fn_t key_comp_func,
 271                                  genhash_copy_fn_t key_copy_func,
 272                                  genhash_free_fn_t key_free_func,
 273                                  genhash_copy_fn_t data_copy_func,
 274                                  genhash_free_fn_t data_free_func)
 275 {
 276   return genhash_new_nbuckets(key_val_func, key_comp_func,
 277                               key_copy_func, key_free_func,
 278                               data_copy_func, data_free_func, MIN_BUCKETS);
 279 }
 280
 281 /****************************************************************************
 282   Constructor with unspecified number of entries.
 283 ****************************************************************************/
 284 struct genhash *genhash_new(genhash_val_fn_t key_val_func,
 285                             genhash_comp_fn_t key_comp_func)
 286 {
 287   return genhash_new_nbuckets(key_val_func, key_comp_func,
 288                               NULL, NULL, NULL, NULL, MIN_BUCKETS);
 289 }
 290
 291 /**************************************************************************
 292   Destructor: free internal memory.
 293 **************************************************************************/
 294 void genhash_destroy(struct genhash *pgenhash)
 295 {
 296   fc_assert_ret(NULL != pgenhash);
 297   pgenhash->no_shrink = TRUE;
 298   genhash_clear(pgenhash);
 299   free(pgenhash->buckets);
 300   free(pgenhash);
 301 }
 302
 303
 304 /****************************************************************************
 305   Resize the genhash table: relink entries.
 306 ****************************************************************************/
 307 static void genhash_resize_table(struct genhash *pgenhash,
 308                                  size_t new_nbuckets)
 309 {
 310   struct genhash_entry **new_buckets, **bucket, **end, **slot;
 311   struct genhash_entry *iter, *next;
 312
 313   fc_assert(new_nbuckets >= pgenhash->num_entries);
 314
 315   new_buckets = fc_calloc(new_nbuckets, sizeof(*pgenhash->buckets));
 316
 317   bucket = pgenhash->buckets;
 318   end = bucket + pgenhash->num_buckets;
 319   for (; bucket < end; bucket++) {
 320     for (iter = *bucket; NULL != iter; iter = next) {
 321       slot = new_buckets + (iter->hash_val % new_nbuckets);
 322       next = iter->next;
 323       iter->next = *slot;
 324       *slot = iter;
 325     }
 326   }
 327
 328   free(pgenhash->buckets);
 329   pgenhash->buckets = new_buckets;
 330   pgenhash->num_buckets = new_nbuckets;
 331 }
 332
 333 /****************************************************************************
 334   Call this when an entry might be added or deleted: resizes the genhash
 335   table if seems like a good idea.  Count deleted entries in check
 336   because efficiency may be degraded if there are too many deleted
 337   entries.  But for determining new size, ignore deleted entries,
 338   since they'll be removed by rehashing.
 339 ****************************************************************************/
 340 #define genhash_maybe_expand(htab) genhash_maybe_resize((htab), TRUE)
 341 #define genhash_maybe_shrink(htab) genhash_maybe_resize((htab), FALSE)
 342 static bool genhash_maybe_resize(struct genhash *pgenhash, bool expandingp)
 343 {
 344   size_t limit, new_nbuckets;
 345
 346   if (!expandingp && pgenhash->no_shrink) {
 347     return FALSE;
 348   }
 349   if (expandingp) {
 350     limit = FULL_RATIO * pgenhash->num_buckets;
 351     if (pgenhash->num_entries < limit) {
 352       return FALSE;
 353     }
 354   } else {
 355     if (pgenhash->num_buckets <= MIN_BUCKETS) {
 356       return FALSE;
 357     }
 358     limit = MIN_RATIO * pgenhash->num_buckets;
 359     if (pgenhash->num_entries > limit) {
 360       return FALSE;
 361     }
 362   }
 363
 364   new_nbuckets = genhash_calc_num_buckets(pgenhash->num_entries);
 365
 366   log_debug("%s genhash (entries = %lu, buckets =  %lu, new = %lu, "
 367             "%s limit = %lu)",
 368             (new_nbuckets < pgenhash->num_buckets ? "Shrinking"
 369              : (new_nbuckets > pgenhash->num_buckets
 370                 ? "Expanding" : "Rehashing")),
 371             (long unsigned) pgenhash->num_entries,
 372             (long unsigned) pgenhash->num_buckets,
 373             (long unsigned) new_nbuckets,
 374             expandingp ? "up": "down", (long unsigned) limit);
 375   genhash_resize_table(pgenhash, new_nbuckets);
 376   return TRUE;
 377 }
 378
 379
 380 /****************************************************************************
 381   Calculate genhash value given hash table and key.
 382 ****************************************************************************/
 383 static inline genhash_val_t genhash_val_calc(const struct genhash *pgenhash,
 384                                              const void *key)
 385 {
 386   if (NULL != pgenhash->key_val_func) {
 387     return pgenhash->key_val_func(key);
 388   } else {
 389     return ((intptr_t) key);
 390   }
 391 }
 392
 393 /****************************************************************************
 394   Return slot (entry pointer) in genhash table where key resides, or where
 395   it should go if it is to be a new key.
 396 ****************************************************************************/
 397 static inline struct genhash_entry **
 398 genhash_slot_lookup(const struct genhash *pgenhash,
 399                     const void *key,
 400                     genhash_val_t hash_val)
 401 {
 402   struct genhash_entry **slot;
 403   genhash_comp_fn_t key_comp_func = pgenhash->key_comp_func;
 404
 405   slot = pgenhash->buckets + (hash_val % pgenhash->num_buckets);
 406   if (NULL != key_comp_func) {
 407     for (; NULL != *slot; slot = &(*slot)->next) {
 408       if (hash_val == (*slot)->hash_val
 409           && key_comp_func((*slot)->key, key)) {
 410         return slot;
 411       }
 412     }
 413   } else {
 414     for (; NULL != *slot; slot = &(*slot)->next) {
 415       if (key == (*slot)->key) {
 416         return slot;
 417       }
 418     }
 419   }
 420   return slot;
 421 }
 422
 423 /****************************************************************************
 424   Function to store from invalid data.
 425 ****************************************************************************/
 426 static inline void genhash_default_get(void **pkey, void **data)
 427 {
 428   if (NULL != pkey) {
 429     *pkey = NULL;
 430   }
 431   if (NULL != data) {
 432     *data = NULL;
 433   }
 434 }
 435
 436 /****************************************************************************
 437   Function to store data.
 438 ****************************************************************************/
 439 static inline void genhash_slot_get(struct genhash_entry *const *slot,
 440                                     void **pkey, void **data)
 441 {
 442   const struct genhash_entry *entry = *slot;
 443
 444   if (NULL != pkey) {
 445     *pkey = entry->key;
 446   }
 447   if (NULL != data) {
 448     *data = entry->data;
 449   }
 450 }
 451
 452 /****************************************************************************
 453   Create the entry and call the copy callbacks.
 454 ****************************************************************************/
 455 static inline void genhash_slot_create(struct genhash *pgenhash,
 456                                        struct genhash_entry **slot,
 457                                        const void *key, const void *data,
 458                                        genhash_val_t hash_val)
 459 {
 460   struct genhash_entry *entry = fc_malloc(sizeof(*entry));
 461
 462   entry->key = (NULL != pgenhash->key_copy_func
 463                 ? pgenhash->key_copy_func(key) : (void *) key);
 464   entry->data = (NULL != pgenhash->data_copy_func
 465                  ? pgenhash->data_copy_func(data) : (void *) data);
 466   entry->hash_val = hash_val;
 467   entry->next = *slot;
 468   *slot = entry;
 469 }
 470
 471 /****************************************************************************
 472   Free the entry slot and call the free callbacks.
 473 ****************************************************************************/
 474 static inline void genhash_slot_free(struct genhash *pgenhash,
 475                                      struct genhash_entry **slot)
 476 {
 477   struct genhash_entry *entry = *slot;
 478
 479   if (NULL != pgenhash->key_free_func) {
 480     pgenhash->key_free_func(entry->key);
 481   }
 482   if (NULL != pgenhash->data_free_func) {
 483     pgenhash->data_free_func(entry->data);
 484   }
 485   *slot = entry->next;
 486   free(entry);
 487 }
 488
 489 /****************************************************************************
 490   Clear previous values (with free callback) and call the copy callbacks.
 491 ****************************************************************************/
 492 static inline void genhash_slot_set(struct genhash *pgenhash,
 493                                     struct genhash_entry **slot,
 494                                     const void *key, const void *data)
 495 {
 496   struct genhash_entry *entry = *slot;
 497
 498   if (NULL != pgenhash->key_free_func) {
 499     pgenhash->key_free_func(entry->key);
 500   }
 501   if (NULL != pgenhash->data_free_func) {
 502     pgenhash->data_free_func(entry->data);
 503   }
 504   entry->key = (NULL != pgenhash->key_copy_func
 505                 ? pgenhash->key_copy_func(key) : (void *) key);
 506   entry->data = (NULL != pgenhash->data_copy_func
 507                  ? pgenhash->data_copy_func(data) : (void *) data);
 508 }
 509
 510
 511 /****************************************************************************
 512   Prevent or allow the genhash table automatically shrinking. Returns the
 513   old value of the setting.
 514 ****************************************************************************/
 515 bool genhash_set_no_shrink(struct genhash *pgenhash, bool no_shrink)
 516 {
 517   bool old;
 518
 519   fc_assert_ret_val(NULL != pgenhash, FALSE);
 520   old = pgenhash->no_shrink;
 521   pgenhash->no_shrink = no_shrink;
 522   return old;
 523 }
 524
 525 /****************************************************************************
 526   Returns the number of entries in the genhash table.
 527 ****************************************************************************/
 528 size_t genhash_size(const struct genhash *pgenhash)
 529 {
 530   fc_assert_ret_val(NULL != pgenhash, 0);
 531   return pgenhash->num_entries;
 532 }
 533
 534 /****************************************************************************
 535   Returns the number of buckets in the genhash table.
 536 ****************************************************************************/
 537 size_t genhash_capacity(const struct genhash *pgenhash)
 538 {
 539   fc_assert_ret_val(NULL != pgenhash, 0);
 540   return pgenhash->num_buckets;
 541 }
 542
 543 /****************************************************************************
 544   Returns a newly allocated mostly deep copy of the given genhash table.
 545 ****************************************************************************/
 546 struct genhash *genhash_copy(const struct genhash *pgenhash)
 547 {
 548   struct genhash *new_genhash;
 549   struct genhash_entry *const *src_bucket, *const *end;
 550   const struct genhash_entry *src_iter;
 551   struct genhash_entry **dest_slot, **dest_bucket;
 552
 553   fc_assert_ret_val(NULL != pgenhash, NULL);
 554
 555   new_genhash = fc_malloc(sizeof(*new_genhash));
 556
 557   /* Copy fields. */
 558   *new_genhash = *pgenhash;
 559
 560   /* But make fresh buckets. */
 561   new_genhash->buckets = fc_calloc(new_genhash->num_buckets,
 562                                    sizeof(*new_genhash->buckets));
 563
 564   /* Let's re-insert all data */
 565   src_bucket = pgenhash->buckets;
 566   end = src_bucket + pgenhash->num_buckets;
 567   dest_bucket = new_genhash->buckets;
 568
 569   for (; src_bucket < end; src_bucket++, dest_bucket++) {
 570     dest_slot = dest_bucket;
 571     for (src_iter = *src_bucket; NULL != src_iter;
 572          src_iter = src_iter->next) {
 573       genhash_slot_create(new_genhash, dest_slot, src_iter->key,
 574                           src_iter->data, src_iter->hash_val);
 575       dest_slot = &(*dest_slot)->next;
 576     }
 577   }
 578
 579   return new_genhash;
 580 }
 581
 582 /****************************************************************************
 583   Remove all entries of the genhash table.
 584 ****************************************************************************/
 585 void genhash_clear(struct genhash *pgenhash)
 586 {
 587   struct genhash_entry **bucket, **end;
 588
 589   fc_assert_ret(NULL != pgenhash);
 590
 591   bucket = pgenhash->buckets;
 592   end = bucket + pgenhash->num_buckets;
 593   for (; bucket < end; bucket++) {
 594     while (NULL != *bucket) {
 595       genhash_slot_free(pgenhash, bucket);
 596     }
 597   }
 598
 599   pgenhash->num_entries = 0;
 600   genhash_maybe_shrink(pgenhash);
 601 }
 602
 603 /****************************************************************************
 604   Insert entry: returns TRUE if inserted, or FALSE if there was already an
 605   entry with the same key, in which case the entry was not inserted.
 606 ****************************************************************************/
 607 bool genhash_insert(struct genhash *pgenhash, const void *key,
 608                     const void *data)
 609 {
 610   struct genhash_entry **slot;
 611   genhash_val_t hash_val;
 612
 613   fc_assert_ret_val(NULL != pgenhash, FALSE);
 614
 615   hash_val = genhash_val_calc(pgenhash, key);
 616   slot = genhash_slot_lookup(pgenhash, key, hash_val);
 617   if (NULL != *slot) {
 618     return FALSE;
 619   } else {
 620     if (genhash_maybe_expand(pgenhash)) {
 621       /* Recalculate slot. */
 622       slot = pgenhash->buckets + (hash_val % pgenhash->num_buckets);
 623     }
 624     genhash_slot_create(pgenhash, slot, key, data, hash_val);
 625     pgenhash->num_entries++;
 626     return TRUE;
 627   }
 628 }
 629
 630 /****************************************************************************
 631   Insert entry, replacing any existing entry which has the same key.
 632   Returns TRUE if a data have been replaced, FALSE if it was a simple
 633   insertion.
 634 ****************************************************************************/
 635 bool genhash_replace(struct genhash *pgenhash, const void *key,
 636                      const void *data)
 637 {
 638   return genhash_replace_full(pgenhash, key, data, NULL, NULL);
 639 }
 640
 641 /****************************************************************************
 642   Insert entry, replacing any existing entry which has the same key.
 643   Returns TRUE if a data have been replaced, FALSE if it was a simple
 644   insertion.
 645
 646   Returns in 'old_pkey' and 'old_pdata' the old content of the bucket if
 647   they are not NULL. NB: It can returns freed pointers if free functions
 648   were supplied to the genhash table.
 649 ****************************************************************************/
 650 bool genhash_replace_full(struct genhash *pgenhash, const void *key,
 651                           const void *data, void **old_pkey,
 652                           void **old_pdata)
 653 {
 654   struct genhash_entry **slot;
 655   genhash_val_t hash_val;
 656
 657   fc_assert_action(NULL != pgenhash,
 658                    genhash_default_get(old_pkey, old_pdata); return FALSE);
 659
 660   hash_val = genhash_val_calc(pgenhash, key);
 661   slot = genhash_slot_lookup(pgenhash, key, hash_val);
 662   if (NULL != *slot) {
 663     /* Replace. */
 664     genhash_slot_get(slot, old_pkey, old_pdata);
 665     genhash_slot_set(pgenhash, slot, key, data);
 666     return TRUE;
 667   } else {
 668     /* Insert. */
 669     if (genhash_maybe_expand(pgenhash)) {
 670       /* Recalculate slot. */
 671       slot = pgenhash->buckets + (hash_val % pgenhash->num_buckets);
 672     }
 673     genhash_default_get(old_pkey, old_pdata);
 674     genhash_slot_create(pgenhash, slot, key, data, hash_val);
 675     pgenhash->num_entries++;
 676     return FALSE;
 677   }
 678 }
 679
 680 /****************************************************************************
 681   Lookup data. Return TRUE on success, then pdata - if not NULL will be set
 682   to the data value.
 683 ****************************************************************************/
 684 bool genhash_lookup(const struct genhash *pgenhash, const void *key,
 685                     void **pdata)
 686 {
 687   struct genhash_entry **slot;
 688
 689   fc_assert_action(NULL != pgenhash,
 690                    genhash_default_get(NULL, pdata); return FALSE);
 691
 692   slot = genhash_slot_lookup(pgenhash, key, genhash_val_calc(pgenhash, key));
 693   if (NULL != *slot) {
 694     genhash_slot_get(slot, NULL, pdata);
 695     return TRUE;
 696   } else {
 697     genhash_default_get(NULL, pdata);
 698     return FALSE;
 699   }
 700 }
 701
 702 /****************************************************************************
 703   Delete an entry from the genhash table. Returns TRUE on success.
 704 ****************************************************************************/
 705 bool genhash_remove(struct genhash *pgenhash, const void *key)
 706 {
 707   return genhash_remove_full(pgenhash, key, NULL, NULL);
 708 }
 709
 710 /****************************************************************************
 711   Delete an entry from the genhash table. Returns TRUE on success.
 712
 713   Returns in 'deleted_pkey' and 'deleted_pdata' the old contents of the
 714   deleted entry if not NULL. NB: It can returns freed pointers if free
 715   functions were supplied to the genhash table.
 716 ****************************************************************************/
 717 bool genhash_remove_full(struct genhash *pgenhash, const void *key,
 718                          void **deleted_pkey, void **deleted_pdata)
 719 {
 720   struct genhash_entry **slot;
 721
 722   fc_assert_action(NULL != pgenhash,
 723                    genhash_default_get(deleted_pkey, deleted_pdata);
 724                    return FALSE);
 725
 726   slot = genhash_slot_lookup(pgenhash, key, genhash_val_calc(pgenhash, key));
 727   if (NULL != *slot) {
 728     genhash_slot_get(slot, deleted_pkey, deleted_pdata);
 729     genhash_slot_free(pgenhash, slot);
 730     genhash_maybe_shrink(pgenhash);
 731     fc_assert(0 < pgenhash->num_entries);
 732     pgenhash->num_entries--;
 733     return TRUE;
 734   } else {
 735     genhash_default_get(deleted_pkey, deleted_pdata);
 736     return FALSE;
 737   }
 738 }
 739
 740
 741 /****************************************************************************
 742   Returns TRUE iff the hash tables contains the same pairs of key/data.
 743 ****************************************************************************/
 744 bool genhashs_are_equal(const struct genhash *pgenhash1,
 745                         const struct genhash *pgenhash2)
 746 {
 747   return genhashs_are_equal_full(pgenhash1, pgenhash2, NULL);
 748 }
 749
 750 /****************************************************************************
 751   Returns TRUE iff the hash tables contains the same pairs of key/data.
 752 ****************************************************************************/
 753 bool genhashs_are_equal_full(const struct genhash *pgenhash1,
 754                              const struct genhash *pgenhash2,
 755                              genhash_comp_fn_t data_comp_func)
 756 {
 757   struct genhash_entry *const *bucket1, *const *max1, *const *slot2;
 758   const struct genhash_entry *iter1;
 759
 760   /* Check pointers. */
 761   if (pgenhash1 == pgenhash2) {
 762     return TRUE;
 763   } else if (NULL == pgenhash1 || NULL == pgenhash2) {
 764     return FALSE;
 765   }
 766
 767   /* General check. */
 768   if (pgenhash1->num_entries != pgenhash2->num_entries
 769       /* If the key functions is not the same, we cannot know if the
 770        * keys are equals. */
 771       || pgenhash1->key_val_func != pgenhash2->key_val_func
 772       || pgenhash1->key_comp_func != pgenhash2->key_comp_func) {
 773     return FALSE;
 774   }
 775
 776   /* Compare buckets. */
 777   bucket1 = pgenhash1->buckets;
 778   max1 = bucket1 + pgenhash1->num_buckets;
 779   for (; bucket1 < max1; bucket1++) {
 780     for (iter1 = *bucket1; NULL != iter1; iter1 = iter1->next) {
 781       slot2 = genhash_slot_lookup(pgenhash2, iter1->key, iter1->hash_val);
 782       if (NULL == *slot2
 783           || (iter1->data != (*slot2)->data
 784               && (NULL == data_comp_func
 785                   || !data_comp_func(iter1->data, (*slot2)->data)))) {
 786         return FALSE;
 787       }
 788     }
 789   }
 790
 791   return TRUE;
 792 }
 793
 794
 795 /****************************************************************************
 796   "Sizeof" function implementation for generic_iterate genhash iterators.
 797 ****************************************************************************/
 798 size_t genhash_iter_sizeof(void)
 799 {
 800   return sizeof(struct genhash_iter);
 801 }
 802
 803 /****************************************************************************
 804   Helper function for genhash (key, value) pair iteration.
 805 ****************************************************************************/
 806 void *genhash_iter_key(const struct iterator *genhash_iter)
 807 {
 808   struct genhash_iter *iter = GENHASH_ITER(genhash_iter);
 809   return (void *) iter->iterator->key;
 810 }
 811
 812 /****************************************************************************
 813   Helper function for genhash (key, value) pair iteration.
 814 ****************************************************************************/
 815 void *genhash_iter_value(const struct iterator *genhash_iter)
 816 {
 817   struct genhash_iter *iter = GENHASH_ITER(genhash_iter);
 818   return (void *) iter->iterator->data;
 819 }
 820
 821 /****************************************************************************
 822   Iterator interface 'next' function implementation.
 823 ****************************************************************************/
 824 static void genhash_iter_next(struct iterator *genhash_iter)
 825 {
 826   struct genhash_iter *iter = GENHASH_ITER(genhash_iter);
 827
 828   iter->iterator = iter->iterator->next;
 829   if (NULL != iter->iterator) {
 830     return;
 831   }
 832
 833   for (iter->bucket++; iter->bucket < iter->end; iter->bucket++) {
 834     if (NULL != *iter->bucket) {
 835       iter->iterator = *iter->bucket;
 836       return;
 837     }
 838   }
 839 }
 840
 841 /****************************************************************************
 842   Iterator interface 'get' function implementation. This just returns the
 843   iterator itself, so you would need to use genhash_iter_get_key/value to
 844   get the actual keys and values.
 845 ****************************************************************************/
 846 static void *genhash_iter_get(const struct iterator *genhash_iter)
 847 {
 848   return (void *) genhash_iter;
 849 }
 850
 851 /****************************************************************************
 852   Iterator interface 'valid' function implementation.
 853 ****************************************************************************/
 854 static bool genhash_iter_valid(const struct iterator *genhash_iter)
 855 {
 856   struct genhash_iter *iter = GENHASH_ITER(genhash_iter);
 857   return iter->bucket < iter->end;
 858 }
 859
 860 /****************************************************************************
 861   Common genhash iterator initializer.
 862 ****************************************************************************/
 863 static inline struct iterator *
 864 genhash_iter_init_common(struct genhash_iter *iter,
 865                          const struct genhash *pgenhash,
 866                          void * (*get) (const struct iterator *))
 867 {
 868   if (NULL == pgenhash) {
 869     return invalid_iter_init(ITERATOR(iter));
 870   }
 871
 872   iter->vtable.next = genhash_iter_next;
 873   iter->vtable.get = get;
 874   iter->vtable.valid = genhash_iter_valid;
 875   iter->bucket = pgenhash->buckets;
 876   iter->end = pgenhash->buckets + pgenhash->num_buckets;
 877
 878   /* Seek to the first used bucket. */
 879   for (; iter->bucket < iter->end; iter->bucket++) {
 880     if (NULL != *iter->bucket) {
 881       iter->iterator = *iter->bucket;
 882       break;
 883     }
 884   }
 885
 886   return ITERATOR(iter);
 887 }
 888
 889 /****************************************************************************
 890   Returns an iterator that iterates over both keys and values of the genhash
 891   table. NB: iterator_get() returns an iterator pointer, so use the helper
 892   functions genhash_iter_get_{key,value} to access the key and value.
 893 ****************************************************************************/
 894 struct iterator *genhash_iter_init(struct genhash_iter *iter,
 895                                    const struct genhash *pgenhash)
 896 {
 897   return genhash_iter_init_common(iter, pgenhash, genhash_iter_get);
 898 }
 899
 900 /****************************************************************************
 901   Returns an iterator over the genhash table's k genhashgenhashenhashys.
 902 ****************************************************************************/
 903 struct iterator *genhash_key_iter_init(struct genhash_iter *iter,
 904                                        const struct genhash *pgenhash)
 905 {
 906   return genhash_iter_init_common(iter, pgenhash, genhash_iter_key);
 907 }
 908
 909 /****************************************************************************
 910   Returns an iterator over the hash table's values.
 911 ****************************************************************************/
 912 struct iterator *genhash_value_iter_init(struct genhash_iter *iter,
 913                                          const struct genhash *pgenhash)
 914 {
 915   return genhash_iter_init_common(iter, pgenhash, genhash_iter_value);
 916 }