lib/hash.c

   1 /* Global assumptions:
   2    - ANSI C
   3    - a certain amount of library support, at least <stdlib.h>
   4    - C ints are at least 32-bits long
   5  */
   6
   7 /* Things to do:
   8    - add a sample do_all function for listing the hash table.
   9  */
  10
  11 #include <stdio.h>
  12 #include <stdlib.h>
  13 #include <assert.h>
  14
  15 #include "hash.h"
  16
  17 #ifdef USE_OBSTACK
  18 /* This macro assumes that there is an HT with an initialized
  19    HT_OBSTACK in scope.  */
  20 # define ZALLOC(n) obstack_alloc (&(ht->ht_obstack), (n))
  21 #else
  22 # define ZALLOC(n) malloc ((n))
  23 #endif
  24
  25 #define BUCKET_HEAD(ht, idx) ((ht)->hash_table[(idx)])
  26
  27 static void hash_free_0 (HT *, int);
  28
  29 static int
  30 is_prime (candidate)
  31      unsigned long candidate;
  32 {
  33   /* No even number and none less than 10 will be passed here.  */
  34   unsigned long divn = 3;
  35   unsigned long sq = divn * divn;
  36
  37   while (sq < candidate && (candidate % divn))
  38     {
  39       divn++;
  40       sq += 4 * divn;
  41       divn++;
  42     }
  43
  44   return (candidate % divn);
  45 }
  46
  47 /* Round a given number up to the nearest prime. */
  48
  49 static unsigned long
  50 next_prime (candidate)
  51      unsigned long candidate;
  52 {
  53   /* Make it definitely odd.  */
  54   candidate |= 1;
  55
  56   while (!is_prime (candidate))
  57     candidate += 2;
  58
  59   return candidate;
  60 }
  61
  62 static void
  63 hash_free_entry (HT *ht, HASH_ENT *e)
  64 {
  65   e->key = NULL;
  66   e->next = ht->hash_free_entry_list;
  67   ht->hash_free_entry_list = e;
  68 }
  69
  70 static HASH_ENT *
  71 hash_allocate_entry (HT *ht)
  72 {
  73   HASH_ENT *new;
  74   if (ht->hash_free_entry_list)
  75     {
  76       new = ht->hash_free_entry_list;
  77       ht->hash_free_entry_list = new->next;
  78     }
  79   else
  80     {
  81       new = (HASH_ENT *) ZALLOC (sizeof (HASH_ENT));
  82     }
  83   return new;
  84 }
  85
  86 unsigned int
  87 hash_get_n_slots_used (const HT *ht)
  88 {
  89   return ht->hash_n_slots_used;
  90 }
  91
  92 /* FIXME-comment */
  93
  94 int
  95 hash_rehash (HT *ht, unsigned int new_table_size)
  96 {
  97   HT *ht_new;
  98   unsigned int i;
  99
 100   if (ht->hash_table_size <= 0 || new_table_size == 0)
 101     return 1;
 102
 103   ht_new = hash_initialize (new_table_size, ht->hash_key_freer,
 104                             ht->hash_hash, ht->hash_key_comparator);
 105
 106   if (ht_new == NULL)
 107     return 1;
 108
 109   for (i = 0; i < ht->hash_table_size; i++)
 110     {
 111       HASH_ENT *p = BUCKET_HEAD (ht, i);
 112       for ( /* empty */ ; p; p = p->next)
 113         {
 114           int failed;
 115           const void *already_in_table;
 116           already_in_table = hash_insert_if_absent (ht_new, p->key, &failed);
 117           assert (failed == 0 && already_in_table == 0);
 118         }
 119     }
 120
 121   hash_free_0 (ht, 0);
 122
 123 #ifdef TESTING
 124   assert (hash_table_ok (ht_new));
 125 #endif
 126   *ht = *ht_new;
 127   free (ht_new);
 128
 129   /* FIXME: fill in ht_new->n_slots_used and other statistics fields. */
 130
 131   return 0;
 132 }
 133
 134 /* FIXME-comment */
 135
 136 unsigned int
 137 hash_get_max_chain_length (HT *ht)
 138 {
 139   unsigned int i;
 140   unsigned int max_chain_length = 0;
 141
 142   if (!ht->hash_dirty_max_chain_length)
 143     return ht->hash_max_chain_length;
 144
 145   for (i = 0; i < ht->hash_table_size; i++)
 146     {
 147       unsigned int chain_length = 0;
 148       HASH_ENT *p = BUCKET_HEAD (ht, i);
 149       for ( /* empty */ ; p; p = p->next)
 150         ++chain_length;
 151       if (chain_length > max_chain_length)
 152         max_chain_length = chain_length;
 153     }
 154
 155   ht->hash_max_chain_length = max_chain_length;
 156   ht->hash_dirty_max_chain_length = 0;
 157   return ht->hash_max_chain_length;
 158 }
 159
 160 unsigned int
 161 hash_get_n_keys (const HT *ht)
 162 {
 163   return ht->hash_n_keys;
 164 }
 165
 166 unsigned int
 167 hash_get_table_size (const HT *ht)
 168 {
 169   return ht->hash_table_size;
 170 }
 171
 172 /* CANDIDATE_TABLE_SIZE need not be prime.  If WHEN_TO_REHASH (FIXME: add
 173    this parameter) is positive, when that percentage of table entries have
 174    been used, the table size is increased;  then a new, larger table
 175    (GROW_FACTOR (FIXME: maybe add this parameter) times larger than the previous
 176    size) is allocated and all entries in the old table are rehashed into
 177    the new, larger one.  The old table is freed.  If WHEN_TO_REHASH is zero
 178    or negative, the table is never resized.
 179
 180    The function returns non-zero
 181    - if CANDIDATE_TABLE_SIZE is zero or negative
 182    - if KEY_COMPARATOR or HASH is null
 183    - if it was unable to allocate sufficient storage for the hash table
 184    - if WHEN_TO_REHASH is zero or negative
 185    Otherwise it returns zero.  */
 186
 187 HT *
 188 hash_initialize (unsigned int candidate_table_size,
 189                  Hash_key_freer_type key_freer,
 190                  unsigned int (*hash) (const void *, unsigned int),
 191                  int (*key_comparator) (const void *, const void *))
 192 {
 193   HT *ht;
 194   unsigned int i;
 195   unsigned int table_size;
 196
 197   if (candidate_table_size <= 0)
 198     return NULL;
 199
 200   if (hash == NULL || key_comparator == NULL)
 201     return NULL;
 202
 203   ht = (HT *) malloc (sizeof (HT));
 204   if (ht == NULL)
 205     return NULL;
 206
 207   table_size = next_prime (candidate_table_size);
 208   ht->hash_table = (HASH_ENT **) malloc (table_size * sizeof (HASH_ENT *));
 209   if (ht->hash_table == NULL)
 210     return NULL;
 211
 212   for (i = 0; i < table_size; i++)
 213     {
 214       BUCKET_HEAD (ht, i) = NULL;
 215     }
 216
 217   ht->hash_free_entry_list = NULL;
 218   ht->hash_table_size = table_size;
 219   ht->hash_hash = hash;
 220   ht->hash_key_comparator = key_comparator;
 221   ht->hash_key_freer = key_freer;
 222   ht->hash_n_slots_used = 0;
 223   ht->hash_max_chain_length = 0;
 224   ht->hash_n_keys = 0;
 225   ht->hash_dirty_max_chain_length = 0;
 226 #ifdef USE_OBSTACK
 227   obstack_init (&(ht->ht_obstack));
 228 #endif
 229
 230   return ht;
 231 }
 232
 233 /* This private function is used to help with insertion and deletion.
 234    If E does *not* compare equal to the key of any entry in the table,
 235    return NULL.
 236    When E matches an entry in the table, return a pointer to the matching
 237    entry.  When DELETE is non-zero and E matches an entry in the table,
 238    unlink the matching entry.  Set *CHAIN_LENGTH to the number of keys
 239    that have hashed to the bucket E hashed to.  */
 240
 241 static HASH_ENT *
 242 hash_find_entry (HT *ht, const void *e, unsigned int *table_idx,
 243                  unsigned int *chain_length, int delete)
 244 {
 245   unsigned int idx;
 246   int found;
 247   HASH_ENT *p, *prev;
 248
 249   idx = ht->hash_hash (e, ht->hash_table_size);
 250   assert (idx < ht->hash_table_size);
 251
 252   *table_idx = idx;
 253   *chain_length = 0;
 254
 255   prev = ht->hash_table[idx];
 256
 257   if (prev == NULL)
 258     return NULL;
 259
 260   *chain_length = 1;
 261   if (ht->hash_key_comparator (e, prev->key) == 0)
 262     {
 263       if (delete)
 264         ht->hash_table[idx] = prev->next;
 265       return prev;
 266     }
 267
 268   p = prev->next;
 269   found = 0;
 270   while (p)
 271     {
 272       ++(*chain_length);
 273       if (ht->hash_key_comparator (e, p->key) == 0)
 274         {
 275           found = 1;
 276           break;
 277         }
 278       prev = p;
 279       p = p->next;
 280     }
 281
 282   if (!found)
 283     return NULL;
 284
 285   assert (p != NULL);
 286   if (delete)
 287     prev->next = p->next;
 288
 289   return p;
 290 }
 291
 292 /* Return non-zero if E is already in the table, zero otherwise. */
 293
 294 int
 295 hash_query_in_table (const HT *ht, const void *e)
 296 {
 297   unsigned int idx;
 298   HASH_ENT *p;
 299
 300   idx = ht->hash_hash (e, ht->hash_table_size);
 301   assert (idx < ht->hash_table_size);
 302   for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next)
 303     if (ht->hash_key_comparator (e, p->key) == 0)
 304       return 1;
 305   return 0;
 306 }
 307
 308 void *
 309 hash_lookup (const HT *ht, const void *e)
 310 {
 311   unsigned int idx;
 312   HASH_ENT *p;
 313
 314   idx = ht->hash_hash (e, ht->hash_table_size);
 315   assert (idx < ht->hash_table_size);
 316   for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next)
 317     if (ht->hash_key_comparator (e, p->key) == 0)
 318       return p->key;
 319   return NULL;
 320 }
 321
 322 /* If E matches an entry already in the hash table, don't modify the
 323    table and return a pointer to the matched entry.  If E does not
 324    match any item in the table, insert E and return NULL.
 325    If the storage required for insertion cannot be allocated
 326    set *FAILED to non-zero and return NULL. */
 327
 328 void *
 329 hash_insert_if_absent (HT *ht, const void *e, int *failed)
 330 {
 331   const HASH_ENT *ent;
 332   HASH_ENT *new;
 333   unsigned int idx;
 334   unsigned int chain_length;
 335
 336   assert (e != NULL);           /* Can't insert a NULL key. */
 337
 338   *failed = 0;
 339   ent = hash_find_entry (ht, e, &idx, &chain_length, 0);
 340   if (ent != NULL)
 341     {
 342       /* E matches a key from an entry already in the table. */
 343       return ent->key;
 344     }
 345
 346   new = hash_allocate_entry (ht);
 347   if (new == NULL)
 348     {
 349       *failed = 1;
 350       return NULL;
 351     }
 352
 353   new->key = (void *) e;
 354   new->next = BUCKET_HEAD (ht, idx);
 355   BUCKET_HEAD (ht, idx) = new;
 356
 357   if (chain_length == 0)
 358     ++(ht->hash_n_slots_used);
 359
 360   /* The insertion has just increased chain_length by 1. */
 361   ++chain_length;
 362
 363   if (chain_length > ht->hash_max_chain_length)
 364     ht->hash_max_chain_length = chain_length;
 365
 366   ++(ht->hash_n_keys);
 367   if ((double) ht->hash_n_keys / ht->hash_table_size > 0.80)
 368     {
 369       unsigned int new_size;
 370       new_size = next_prime (2 * ht->hash_table_size + 1);
 371       *failed = hash_rehash (ht, new_size);
 372     }
 373
 374 #ifdef TESTING
 375   assert (hash_table_ok (ht));
 376 #endif
 377
 378   return NULL;
 379 }
 380
 381 /* If E is already in the table, remove it and return a pointer to
 382    the just-deleted key (the user may want to deallocate its storage).
 383    If E is not in the table, don't modify the table and return NULL. */
 384
 385 void *
 386 hash_delete_if_present (HT *ht, const void *e)
 387 {
 388   HASH_ENT *ent;
 389   void *key;
 390   unsigned int idx;
 391   unsigned int chain_length;
 392
 393   ent = hash_find_entry (ht, e, &idx, &chain_length, 1);
 394   if (ent == NULL)
 395     return NULL;
 396
 397   if (ent->next == NULL && chain_length == 1)
 398     --(ht->hash_n_slots_used);
 399
 400   key = ent->key;
 401
 402   --(ht->hash_n_keys);
 403   ht->hash_dirty_max_chain_length = 1;
 404   if (ent->next == NULL && chain_length < ht->hash_max_chain_length)
 405     ht->hash_dirty_max_chain_length = 0;
 406
 407   hash_free_entry (ht, ent);
 408
 409 #ifdef TESTING
 410   assert (hash_table_ok (ht));
 411 #endif
 412   return key;
 413 }
 414
 415 void
 416 hash_print_statistics (const HT *ht, FILE *stream)
 417 {
 418   unsigned int n_slots_used;
 419   unsigned int n_keys;
 420   unsigned int max_chain_length;
 421   int err;
 422
 423   err = hash_get_statistics (ht, &n_slots_used, &n_keys, &max_chain_length);
 424   assert (err == 0);
 425   fprintf (stream, "table size: %d\n", ht->hash_table_size);
 426   fprintf (stream, "# slots used: %u (%.2f%%)\n", n_slots_used,
 427            (100.0 * n_slots_used) / ht->hash_table_size);
 428   fprintf (stream, "# keys: %u\n", n_keys);
 429   fprintf (stream, "max chain length: %u\n", max_chain_length);
 430 }
 431
 432 /* If there is *NO* table (so, no meaningful stats) return non-zero
 433    and don't reference the argument pointers.  Otherwise compute the
 434    performance statistics and return non-zero. */
 435
 436 int
 437 hash_get_statistics (const HT *ht,
 438                      unsigned int *n_slots_used,
 439                      unsigned int *n_keys,
 440                      unsigned int *max_chain_length)
 441 {
 442   unsigned int i;
 443
 444   if (ht == NULL || ht->hash_table == NULL)
 445     return 1;
 446
 447   *max_chain_length = 0;
 448   *n_slots_used = 0;
 449   *n_keys = 0;
 450
 451   for (i = 0; i < ht->hash_table_size; i++)
 452     {
 453       unsigned int chain_length = 0;
 454       HASH_ENT *p;
 455
 456       p = BUCKET_HEAD (ht, i);
 457       if (p != NULL)
 458         ++(*n_slots_used);
 459
 460       for (; p; p = p->next)
 461         ++chain_length;
 462
 463       *n_keys += chain_length;
 464       if (chain_length > *max_chain_length)
 465         *max_chain_length = chain_length;
 466     }
 467   return 0;
 468 }
 469
 470 int
 471 hash_table_ok (HT *ht)
 472 {
 473   int code;
 474   unsigned int n_slots_used;
 475   unsigned int n_keys;
 476   unsigned int max_chain_length;
 477
 478   if (ht == NULL || ht->hash_table == NULL)
 479     return 1;
 480
 481   code = hash_get_statistics (ht, &n_slots_used, &n_keys,
 482                               &max_chain_length);
 483
 484   if (code != 0
 485       || n_slots_used != ht->hash_n_slots_used
 486       || n_keys != ht->hash_n_keys
 487       || max_chain_length != hash_get_max_chain_length (ht))
 488     return 0;
 489
 490   return 1;
 491 }
 492
 493 /* See hash_do_for_each_2 (below) for a variant.  */
 494
 495 void
 496 hash_do_for_each (HT *ht, void (*f) (void *e, void *aux), void *aux)
 497 {
 498   unsigned int i;
 499
 500 #ifdef TESTING
 501   assert (hash_table_ok (ht));
 502 #endif
 503
 504   if (ht->hash_table == NULL)
 505     return;
 506
 507   for (i = 0; i < ht->hash_table_size; i++)
 508     {
 509       HASH_ENT *p;
 510       for (p = BUCKET_HEAD (ht, i); p; p = p->next)
 511         {
 512           (*f) (p->key, aux);
 513         }
 514     }
 515 }
 516
 517 /* Just like hash_do_for_each, except that function F returns an int
 518    that can signal (when non-zero) we should return early.  */
 519
 520 int
 521 hash_do_for_each_2 (HT *ht, int (*f) (void *e, void *aux), void *aux)
 522 {
 523   unsigned int i;
 524
 525 #ifdef TESTING
 526   assert (hash_table_ok (ht));
 527 #endif
 528
 529   if (ht->hash_table == NULL)
 530     return 0;
 531
 532   for (i = 0; i < ht->hash_table_size; i++)
 533     {
 534       HASH_ENT *p;
 535       for (p = BUCKET_HEAD (ht, i); p; p = p->next)
 536         {
 537           int return_code;
 538
 539           return_code = (*f) (p->key, aux);
 540           if (return_code != 0)
 541             return return_code;
 542         }
 543     }
 544   return 0;
 545 }
 546
 547 /* For each entry in the bucket addressed by BUCKET_KEY of the hash
 548    table HT, invoke the function F.  If F returns non-zero, stop
 549    iterating and return that value.  Otherwise, apply F to all entries
 550    in the selected bucket and return zero.  The AUX argument to this
 551    function is passed as the last argument in each invocation of F.
 552    The first argument to F is BUCKET_KEY, and the second is the key of
 553    an entry in the selected bucket. */
 554
 555 int
 556 hash_do_for_each_in_selected_bucket (HT *ht, const void *bucket_key,
 557                                      int (*f) (const void *bucket_key,
 558                                                void *e, void *aux),
 559                                      void *aux)
 560 {
 561   int idx;
 562   HASH_ENT *p;
 563
 564 #ifdef TESTING
 565   assert (hash_table_ok (ht));
 566 #endif
 567
 568   if (ht->hash_table == NULL)
 569     return 0;
 570
 571   idx = ht->hash_hash (bucket_key, ht->hash_table_size);
 572
 573   for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next)
 574     {
 575       int return_code;
 576
 577       return_code = (*f) (bucket_key, p->key, aux);
 578       if (return_code != 0)
 579         return return_code;
 580     }
 581
 582   return 0;
 583 }
 584
 585 /* Make all buckets empty, placing any chained entries on the free list.
 586    As with hash_free, apply the user-specified function key_freer
 587    (if it's not NULL) to the keys of any affected entries. */
 588
 589 void
 590 hash_clear (HT *ht)
 591 {
 592   unsigned int i;
 593   HASH_ENT *p;
 594
 595   for (i = 0; i < ht->hash_table_size; i++)
 596     {
 597       HASH_ENT *tail = NULL;
 598       HASH_ENT *head = BUCKET_HEAD (ht, i);
 599
 600       /* Free any keys and get tail pointer to last entry in chain. */
 601       for (p = head; p; p = p->next)
 602         {
 603           if (ht->hash_key_freer != NULL)
 604             ht->hash_key_freer (p->key);
 605           p->key = NULL;        /* Make sure no one tries to use this key later. */
 606           tail = p;
 607         }
 608       BUCKET_HEAD (ht, i) = NULL;
 609
 610       /* If there's a chain in this bucket, tack it onto the
 611          beginning of the free list. */
 612       if (head != NULL)
 613         {
 614           assert (tail != NULL && tail->next == NULL);
 615           tail->next = ht->hash_free_entry_list;
 616           ht->hash_free_entry_list = head;
 617         }
 618     }
 619   ht->hash_n_slots_used = 0;
 620   ht->hash_max_chain_length = 0;
 621   ht->hash_n_keys = 0;
 622   ht->hash_dirty_max_chain_length = 0;
 623 }
 624
 625 /* Free all storage associated with HT that functions in this package
 626    have allocated.  If a key_freer function has been supplied (when HT
 627    was created), this function applies it to the key of each entry before
 628    freeing that entry. */
 629
 630 static void
 631 hash_free_0 (HT *ht, int free_user_data)
 632 {
 633   if (free_user_data && ht->hash_key_freer != NULL)
 634     {
 635       unsigned int i;
 636
 637       for (i = 0; i < ht->hash_table_size; i++)
 638         {
 639           HASH_ENT *p;
 640           HASH_ENT *next;
 641
 642           for (p = BUCKET_HEAD (ht, i); p; p = next)
 643             {
 644               next = p->next;
 645               ht->hash_key_freer (p->key);
 646             }
 647         }
 648     }
 649
 650 #ifdef USE_OBSTACK
 651   obstack_free (&(ht->ht_obstack), NULL);
 652 #else
 653   {
 654     unsigned int i;
 655     for (i = 0; i < ht->hash_table_size; i++)
 656       {
 657         HASH_ENT *p;
 658         HASH_ENT *next;
 659
 660         for (p = BUCKET_HEAD (ht, i); p; p = next)
 661           {
 662             next = p->next;
 663             free (p);
 664           }
 665       }
 666   }
 667 #endif
 668   ht->hash_free_entry_list = NULL;
 669   free (ht->hash_table);
 670 }
 671
 672 void
 673 hash_free (HT *ht)
 674 {
 675   hash_free_0 (ht, 1);
 676   free (ht);
 677 }
 678
 679 #ifdef TESTING
 680
 681 void
 682 hash_print (const HT *ht)
 683 {
 684   int i;
 685
 686   for (i = 0; i < ht->hash_table_size; i++)
 687     {
 688       HASH_ENT *p;
 689
 690       if (BUCKET_HEAD (ht, i) != NULL)
 691         printf ("%d:\n", i);
 692
 693       for (p = BUCKET_HEAD (ht, i); p; p = p->next)
 694         {
 695           char *s = (char *) p->key;
 696           /* FIXME */
 697           printf ("  %s\n", s);
 698         }
 699     }
 700 }
 701
 702 #endif /* TESTING */
 703
 704 void
 705 hash_get_key_list (const HT *ht, unsigned int bufsize, void **buf)
 706 {
 707   unsigned int i;
 708   unsigned int c = 0;
 709
 710   for (i = 0; i < ht->hash_table_size; i++)
 711     {
 712       HASH_ENT *p;
 713
 714       for (p = BUCKET_HEAD (ht, i); p; p = p->next)
 715         {
 716           if (c >= bufsize)
 717             return;
 718           buf[c++] = p->key;
 719         }
 720     }
 721 }
 722
 723 /* Return the first key in the table.  If the table is empty, return NULL.  */
 724
 725 void *
 726 hash_get_first (const HT *ht)
 727 {
 728   unsigned int idx;
 729   HASH_ENT *p;
 730
 731   if (ht->hash_n_keys == 0)
 732     return NULL;
 733
 734   for (idx = 0; idx < ht->hash_table_size; idx++)
 735     {
 736       if ((p = BUCKET_HEAD (ht, idx)) != NULL)
 737         return p->key;
 738     }
 739   abort ();
 740 }
 741
 742 /* Return the key in the entry following the entry whose key matches E.
 743    If there is the only one key in the table and that key matches E,
 744    return the matching key.  If E is not in the table, return NULL.  */
 745
 746 void *
 747 hash_get_next (const HT *ht, const void *e)
 748 {
 749   unsigned int idx;
 750   HASH_ENT *p;
 751
 752   idx = ht->hash_hash (e, ht->hash_table_size);
 753   assert (idx < ht->hash_table_size);
 754   for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next)
 755     {
 756       if (ht->hash_key_comparator (e, p->key) == 0)
 757         {
 758           if (p->next != NULL)
 759             {
 760               return p->next->key;
 761             }
 762           else
 763             {
 764               unsigned int bucket;
 765
 766               /* E is the last or only key in the bucket chain.  */
 767               if (ht->hash_n_keys == 1)
 768                 {
 769                   /* There is only one key in the table, and it matches E.  */
 770                   return p->key;
 771                 }
 772               bucket = idx;
 773               do
 774                 {
 775                   idx = (idx + 1) % ht->hash_table_size;
 776                   if ((p = BUCKET_HEAD (ht, idx)) != NULL)
 777                     return p->key;
 778                 }
 779               while (idx != bucket);
 780             }
 781         }
 782     }
 783
 784   /* E is not in the table.  */
 785   return NULL;
 786 }