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 is positive, when
 173    that percentage of table entries have been used, the table is
 174    deemed too small;  then a new, larger table (GROW_FACTOR times
 175    larger than the previous size) is allocated and all entries in
 176    the old table are rehashed into the new, larger one.  The old
 177    table is freed.  If WHEN_TO_REHASH is zero or negative, the
 178    table is never resized.
 179
 180    The function returns non-zero
 181    - if TABLE_SIZE is zero or negative
 182    - if EQUALITY_TESTER 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    FIXME: tell what happens to any existing hash table when this
 188    function is called (e.g. a second time).  */
 189
 190 HT *
 191 hash_initialize (unsigned int candidate_table_size,
 192                  Hash_key_freer_type key_freer,
 193                  unsigned int (*hash) (const void *, unsigned int),
 194                  int (*key_comparator) (const void *, const void *))
 195 {
 196   HT *ht;
 197   unsigned int i;
 198   unsigned int table_size;
 199
 200   if (candidate_table_size <= 0)
 201     return NULL;
 202
 203   if (hash == NULL || key_comparator == NULL)
 204     return NULL;
 205
 206   ht = (HT *) malloc (sizeof (HT));
 207   if (ht == NULL)
 208     return NULL;
 209
 210   table_size = next_prime (candidate_table_size);
 211   ht->hash_table = (HASH_ENT **) malloc (table_size * sizeof (HASH_ENT *));
 212   if (ht->hash_table == NULL)
 213     return NULL;
 214
 215   for (i = 0; i < table_size; i++)
 216     {
 217       BUCKET_HEAD (ht, i) = NULL;
 218     }
 219
 220   ht->hash_free_entry_list = NULL;
 221   ht->hash_table_size = table_size;
 222   ht->hash_hash = hash;
 223   ht->hash_key_comparator = key_comparator;
 224   ht->hash_key_freer = key_freer;
 225   ht->hash_n_slots_used = 0;
 226   ht->hash_max_chain_length = 0;
 227   ht->hash_n_keys = 0;
 228   ht->hash_dirty_max_chain_length = 0;
 229 #ifdef USE_OBSTACK
 230   obstack_init (&(ht->ht_obstack));
 231 #endif
 232
 233   return ht;
 234 }
 235
 236 /* This private function is used to help with insertion and deletion.
 237    If E does *not* compare equal to the key of any entry in the table,
 238    return NULL.
 239    When E matches an entry in the table, return a pointer to the matching
 240    entry.  When DELETE is non-zero and E matches an entry in the table,
 241    unlink the matching entry.  Set *CHAIN_LENGTH to the number of keys
 242    that have hashed to the bucket E hashed to.  */
 243
 244 static HASH_ENT *
 245 hash_find_entry (HT *ht, const void *e, unsigned int *table_idx,
 246                  unsigned int *chain_length, int delete)
 247 {
 248   unsigned int idx;
 249   int found;
 250   HASH_ENT *p, *prev;
 251
 252   idx = ht->hash_hash (e, ht->hash_table_size);
 253   assert (idx < ht->hash_table_size);
 254
 255   *table_idx = idx;
 256   *chain_length = 0;
 257
 258   prev = ht->hash_table[idx];
 259
 260   if (prev == NULL)
 261     return NULL;
 262
 263   *chain_length = 1;
 264   if (ht->hash_key_comparator (e, prev->key) == 0)
 265     {
 266       if (delete)
 267         ht->hash_table[idx] = prev->next;
 268       return prev;
 269     }
 270
 271   p = prev->next;
 272   found = 0;
 273   while (p)
 274     {
 275       ++(*chain_length);
 276       if (ht->hash_key_comparator (e, p->key) == 0)
 277         {
 278           found = 1;
 279           break;
 280         }
 281       prev = p;
 282       p = p->next;
 283     }
 284
 285   if (!found)
 286     return NULL;
 287
 288   assert (p != NULL);
 289   if (delete)
 290     prev->next = p->next;
 291
 292   return p;
 293 }
 294
 295 /* Return non-zero if E is already in the table, zero otherwise. */
 296
 297 int
 298 hash_query_in_table (const HT *ht, const void *e)
 299 {
 300   unsigned int idx;
 301   HASH_ENT *p;
 302
 303   idx = ht->hash_hash (e, ht->hash_table_size);
 304   assert (idx < ht->hash_table_size);
 305   for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next)
 306     if (ht->hash_key_comparator (e, p->key) == 0)
 307       return 1;
 308   return 0;
 309 }
 310
 311 void *
 312 hash_lookup (const HT *ht, const void *e)
 313 {
 314   unsigned int idx;
 315   HASH_ENT *p;
 316
 317   idx = ht->hash_hash (e, ht->hash_table_size);
 318   assert (idx < ht->hash_table_size);
 319   for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next)
 320     if (ht->hash_key_comparator (e, p->key) == 0)
 321       return p->key;
 322   return NULL;
 323 }
 324
 325 /* If E matches an entry already in the hash table, don't modify the
 326    table and return a pointer to the matched entry.  If E does not
 327    match any item in the table, insert E and return NULL.
 328    If the storage required for insertion cannot be allocated
 329    set *FAILED to non-zero and return NULL. */
 330
 331 void *
 332 hash_insert_if_absent (HT *ht, const void *e, int *failed)
 333 {
 334   const HASH_ENT *ent;
 335   HASH_ENT *new;
 336   unsigned int idx;
 337   unsigned int chain_length;
 338
 339   assert (e != NULL);           /* Can't insert a NULL key. */
 340
 341   *failed = 0;
 342   ent = hash_find_entry (ht, e, &idx, &chain_length, 0);
 343   if (ent != NULL)
 344     {
 345       /* E matches a key from an entry already in the table. */
 346       return ent->key;
 347     }
 348
 349   new = hash_allocate_entry (ht);
 350   if (new == NULL)
 351     {
 352       *failed = 1;
 353       return NULL;
 354     }
 355
 356   new->key = (void *) e;
 357   new->next = BUCKET_HEAD (ht, idx);
 358   BUCKET_HEAD (ht, idx) = new;
 359
 360   if (chain_length == 0)
 361     ++(ht->hash_n_slots_used);
 362
 363   /* The insertion has just increased chain_length by 1. */
 364   ++chain_length;
 365
 366   if (chain_length > ht->hash_max_chain_length)
 367     ht->hash_max_chain_length = chain_length;
 368
 369   ++(ht->hash_n_keys);
 370   if ((double) ht->hash_n_keys / ht->hash_table_size > 0.80)
 371     {
 372       unsigned int new_size;
 373       new_size = next_prime (2 * ht->hash_table_size + 1);
 374       *failed = hash_rehash (ht, new_size);
 375     }
 376
 377 #ifdef TESTING
 378   assert (hash_table_ok (ht));
 379 #endif
 380
 381   return NULL;
 382 }
 383
 384 /* If E is already in the table, remove it and return a pointer to
 385    the just-deleted key (the user may want to deallocate its storage).
 386    If E is not in the table, don't modify the table and return NULL. */
 387
 388 void *
 389 hash_delete_if_present (HT *ht, const void *e)
 390 {
 391   HASH_ENT *ent;
 392   void *key;
 393   unsigned int idx;
 394   unsigned int chain_length;
 395
 396   ent = hash_find_entry (ht, e, &idx, &chain_length, 1);
 397   if (ent == NULL)
 398     return NULL;
 399
 400   if (ent->next == NULL && chain_length == 1)
 401     --(ht->hash_n_slots_used);
 402
 403   key = ent->key;
 404
 405   --(ht->hash_n_keys);
 406   ht->hash_dirty_max_chain_length = 1;
 407   if (ent->next == NULL && chain_length < ht->hash_max_chain_length)
 408     ht->hash_dirty_max_chain_length = 0;
 409
 410   hash_free_entry (ht, ent);
 411
 412 #ifdef TESTING
 413   assert (hash_table_ok (ht));
 414 #endif
 415   return key;
 416 }
 417
 418 void
 419 hash_print_statistics (const HT *ht, FILE *stream)
 420 {
 421   unsigned int n_slots_used;
 422   unsigned int n_keys;
 423   unsigned int max_chain_length;
 424   int err;
 425
 426   err = hash_get_statistics (ht, &n_slots_used, &n_keys, &max_chain_length);
 427   assert (err == 0);
 428   fprintf (stream, "table size: %d\n", ht->hash_table_size);
 429   fprintf (stream, "# slots used: %u (%.2f%%)\n", n_slots_used,
 430            (100.0 * n_slots_used) / ht->hash_table_size);
 431   fprintf (stream, "# keys: %u\n", n_keys);
 432   fprintf (stream, "max chain length: %u\n", max_chain_length);
 433 }
 434
 435 /* If there is *NO* table (so, no meaningful stats) return non-zero
 436    and don't reference the argument pointers.  Otherwise compute the
 437    performance statistics and return non-zero. */
 438
 439 int
 440 hash_get_statistics (const HT *ht,
 441                      unsigned int *n_slots_used,
 442                      unsigned int *n_keys,
 443                      unsigned int *max_chain_length)
 444 {
 445   unsigned int i;
 446
 447   if (ht == NULL || ht->hash_table == NULL)
 448     return 1;
 449
 450   *max_chain_length = 0;
 451   *n_slots_used = 0;
 452   *n_keys = 0;
 453
 454   for (i = 0; i < ht->hash_table_size; i++)
 455     {
 456       unsigned int chain_length = 0;
 457       HASH_ENT *p;
 458
 459       p = BUCKET_HEAD (ht, i);
 460       if (p != NULL)
 461         ++(*n_slots_used);
 462
 463       for (; p; p = p->next)
 464         ++chain_length;
 465
 466       *n_keys += chain_length;
 467       if (chain_length > *max_chain_length)
 468         *max_chain_length = chain_length;
 469     }
 470   return 0;
 471 }
 472
 473 int
 474 hash_table_ok (HT *ht)
 475 {
 476   int code;
 477   unsigned int n_slots_used;
 478   unsigned int n_keys;
 479   unsigned int max_chain_length;
 480
 481   if (ht == NULL || ht->hash_table == NULL)
 482     return 1;
 483
 484   code = hash_get_statistics (ht, &n_slots_used, &n_keys,
 485                               &max_chain_length);
 486
 487   if (code != 0
 488       || n_slots_used != ht->hash_n_slots_used
 489       || n_keys != ht->hash_n_keys
 490       || max_chain_length != hash_get_max_chain_length (ht))
 491     return 0;
 492
 493   return 1;
 494 }
 495
 496 /* See hash_do_for_each_2 (below) for a variant.  */
 497
 498 void
 499 hash_do_for_each (HT *ht, void (*f) (void *e, void *aux), void *aux)
 500 {
 501   unsigned int i;
 502
 503 #ifdef TESTING
 504   assert (hash_table_ok (ht));
 505 #endif
 506
 507   if (ht->hash_table == NULL)
 508     return;
 509
 510   for (i = 0; i < ht->hash_table_size; i++)
 511     {
 512       HASH_ENT *p;
 513       for (p = BUCKET_HEAD (ht, i); p; p = p->next)
 514         {
 515           (*f) (p->key, aux);
 516         }
 517     }
 518 }
 519
 520 /* Just like hash_do_for_each, except that function F returns an int
 521    that can signal (when non-zero) we should return early.  */
 522
 523 int
 524 hash_do_for_each_2 (HT *ht, int (*f) (void *e, void *aux), void *aux)
 525 {
 526   unsigned int i;
 527
 528 #ifdef TESTING
 529   assert (hash_table_ok (ht));
 530 #endif
 531
 532   if (ht->hash_table == NULL)
 533     return 0;
 534
 535   for (i = 0; i < ht->hash_table_size; i++)
 536     {
 537       HASH_ENT *p;
 538       for (p = BUCKET_HEAD (ht, i); p; p = p->next)
 539         {
 540           int return_code;
 541
 542           return_code = (*f) (p->key, aux);
 543           if (return_code != 0)
 544             return return_code;
 545         }
 546     }
 547   return 0;
 548 }
 549
 550 /* For each entry in the bucket addressed by BUCKET_KEY of the hash
 551    table HT, invoke the function F.  If F returns non-zero, stop
 552    iterating and return that value.  Otherwise, apply F to all entries
 553    in the selected bucket and return zero.  The AUX argument to this
 554    function is passed as the last argument in each invocation of F.
 555    The first argument to F is BUCKET_KEY, and the second is the key of
 556    an entry in the selected bucket. */
 557
 558 int
 559 hash_do_for_each_in_selected_bucket (HT *ht, const void *bucket_key,
 560                                      int (*f) (const void *bucket_key,
 561                                                void *e, void *aux),
 562                                      void *aux)
 563 {
 564   int idx;
 565   HASH_ENT *p;
 566
 567 #ifdef TESTING
 568   assert (hash_table_ok (ht));
 569 #endif
 570
 571   if (ht->hash_table == NULL)
 572     return 0;
 573
 574   idx = ht->hash_hash (bucket_key, ht->hash_table_size);
 575
 576   for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next)
 577     {
 578       int return_code;
 579
 580       return_code = (*f) (bucket_key, p->key, aux);
 581       if (return_code != 0)
 582         return return_code;
 583     }
 584
 585   return 0;
 586 }
 587
 588 /* Make all buckets empty, placing any chained entries on the free list.
 589    As with hash_free, apply the user-specified function key_freer
 590    (if it's not NULL) to the keys of any affected entries. */
 591
 592 void
 593 hash_clear (HT *ht)
 594 {
 595   unsigned int i;
 596   HASH_ENT *p;
 597
 598   for (i = 0; i < ht->hash_table_size; i++)
 599     {
 600       HASH_ENT *tail = NULL;
 601       HASH_ENT *head = BUCKET_HEAD (ht, i);
 602
 603       /* Free any keys and get tail pointer to last entry in chain. */
 604       for (p = head; p; p = p->next)
 605         {
 606           if (ht->hash_key_freer != NULL)
 607             ht->hash_key_freer (p->key);
 608           p->key = NULL;        /* Make sure no one tries to use this key later. */
 609           tail = p;
 610         }
 611       BUCKET_HEAD (ht, i) = NULL;
 612
 613       /* If there's a chain in this bucket, tack it onto the
 614          beginning of the free list. */
 615       if (head != NULL)
 616         {
 617           assert (tail != NULL && tail->next == NULL);
 618           tail->next = ht->hash_free_entry_list;
 619           ht->hash_free_entry_list = head;
 620         }
 621     }
 622   ht->hash_n_slots_used = 0;
 623   ht->hash_max_chain_length = 0;
 624   ht->hash_n_keys = 0;
 625   ht->hash_dirty_max_chain_length = 0;
 626 }
 627
 628 /* Free all storage associated with HT that functions in this package
 629    have allocated.  If a key_freer function has been supplied (when HT
 630    was created), this function applies it to the key of each entry before
 631    freeing that entry. */
 632
 633 static void
 634 hash_free_0 (HT *ht, int free_user_data)
 635 {
 636   if (free_user_data && ht->hash_key_freer != NULL)
 637     {
 638       unsigned int i;
 639
 640       for (i = 0; i < ht->hash_table_size; i++)
 641         {
 642           HASH_ENT *p;
 643           HASH_ENT *next;
 644
 645           for (p = BUCKET_HEAD (ht, i); p; p = next)
 646             {
 647               next = p->next;
 648               ht->hash_key_freer (p->key);
 649             }
 650         }
 651     }
 652
 653 #ifdef USE_OBSTACK
 654   obstack_free (&(ht->ht_obstack), NULL);
 655 #else
 656   {
 657     unsigned int i;
 658     for (i = 0; i < ht->hash_table_size; i++)
 659       {
 660         HASH_ENT *p;
 661         HASH_ENT *next;
 662
 663         for (p = BUCKET_HEAD (ht, i); p; p = next)
 664           {
 665             next = p->next;
 666             free (p);
 667           }
 668       }
 669   }
 670 #endif
 671   ht->hash_free_entry_list = NULL;
 672   free (ht->hash_table);
 673 }
 674
 675 void
 676 hash_free (HT *ht)
 677 {
 678   hash_free_0 (ht, 1);
 679   free (ht);
 680 }
 681
 682 #ifdef TESTING
 683
 684 void
 685 hash_print (const HT *ht)
 686 {
 687   int i;
 688
 689   for (i = 0; i < ht->hash_table_size; i++)
 690     {
 691       HASH_ENT *p;
 692
 693       if (BUCKET_HEAD (ht, i) != NULL)
 694         printf ("%d:\n", i);
 695
 696       for (p = BUCKET_HEAD (ht, i); p; p = p->next)
 697         {
 698           char *s = (char *) p->key;
 699           /* FIXME */
 700           printf ("  %s\n", s);
 701         }
 702     }
 703 }
 704
 705 #endif /* TESTING */
 706
 707 void
 708 hash_get_key_list (const HT *ht, unsigned int bufsize, void **buf)
 709 {
 710   unsigned int i;
 711   unsigned int c = 0;
 712
 713   for (i = 0; i < ht->hash_table_size; i++)
 714     {
 715       HASH_ENT *p;
 716
 717       for (p = BUCKET_HEAD (ht, i); p; p = p->next)
 718         {
 719           if (c >= bufsize)
 720             return;
 721           buf[c++] = p->key;
 722         }
 723     }
 724 }
 725
 726 /* Return the first key in the table.  If the table is empty, return NULL.  */
 727
 728 void *
 729 hash_get_first (const HT *ht)
 730 {
 731   unsigned int idx;
 732   HASH_ENT *p;
 733
 734   if (ht->hash_n_keys == 0)
 735     return NULL;
 736
 737   for (idx = 0; idx < ht->hash_table_size; idx++)
 738     {
 739       if ((p = BUCKET_HEAD (ht, idx)) != NULL)
 740         return p->key;
 741     }
 742   abort ();
 743 }
 744
 745 /* Return the key in the entry following the entry whose key matches E.
 746    If there is the only one key in the table and that key matches E,
 747    return the matching key.  If E is not in the table, return NULL.  */
 748
 749 void *
 750 hash_get_next (const HT *ht, const void *e)
 751 {
 752   unsigned int idx;
 753   HASH_ENT *p;
 754
 755   idx = ht->hash_hash (e, ht->hash_table_size);
 756   assert (idx < ht->hash_table_size);
 757   for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next)
 758     {
 759       if (ht->hash_key_comparator (e, p->key) == 0)
 760         {
 761           if (p->next != NULL)
 762             {
 763               return p->next->key;
 764             }
 765           else
 766             {
 767               unsigned int bucket;
 768
 769               /* E is the last or only key in the bucket chain.  */
 770               if (ht->hash_n_keys == 1)
 771                 {
 772                   /* There is only one key in the table, and it matches E.  */
 773                   return p->key;
 774                 }
 775               bucket = idx;
 776               do
 777                 {
 778                   idx = (idx + 1) % ht->hash_table_size;
 779                   if ((p = BUCKET_HEAD (ht, idx)) != NULL)
 780                     return p->key;
 781                 }
 782               while (idx != bucket);
 783             }
 784         }
 785     }
 786
 787   /* E is not in the table.  */
 788   return NULL;
 789 }