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