lib/hash.c

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