src/libsphinxbase/util/hash_table.c

   1 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
   2 /* ====================================================================
   3  * Copyright (c) 1999-2004 Carnegie Mellon University.  All rights
   4  * reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  *
  18  * This work was supported in part by funding from the Defense Advanced
  19  * Research Projects Agency and the National Science Foundation of the
  20  * United States of America, and the CMU Sphinx Speech Consortium.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
  23  * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  24  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  25  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
  26  * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  27  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  28  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  29  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  30  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  31  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  32  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  33  *
  34  * ====================================================================
  35  *
  36  */
  37 /*
  38  * hash.c -- Hash table module.
  39  *
  40  * **********************************************
  41  * CMU ARPA Speech Project
  42  *
  43  * Copyright (c) 1999 Carnegie Mellon University.
  44  * ALL RIGHTS RESERVED.
  45  * **********************************************
  46  *
  47  * HISTORY
  48  * $Log: hash.c,v $
  49  * Revision 1.5  2005/06/22 03:04:01  arthchan2003
  50  * 1, Implemented hash_delete and hash_display, 2, Fixed doxygen documentation, 3, Added  keyword.
  51  *
  52  * Revision 1.9  2005/05/25 06:17:53  archan
  53  * Delete the test code in cmd_ln.c and fixed platform specific code of hash.c
  54  *
  55  * Revision 1.8  2005/05/24 01:10:54  archan
  56  * Fix a bug when the value only appear in the hash but there is no chain.   Also make sure that prev was initialized to NULL. All success cases were tested, but not tested with the deletion is tested.
  57  *
  58  * Revision 1.6  2005/05/24 00:00:45  archan
  59  * Added basic functionalities to hash_t: 1, display and 2, delete a key from a hash. \n
  60  *
  61  * Revision 1.5  2005/05/11 07:01:38  archan
  62  * Added comments on the usage of the current implementation of hash tables.
  63  *
  64  * Revision 1.4  2005/05/03 04:09:11  archan
  65  * Implemented the heart of word copy search. For every ci-phone, every word end, a tree will be allocated to preserve its pathscore.  This is different from 3.5 or below, only the best score for a particular ci-phone, regardless of the word-ends will be preserved at every frame.  The graph propagation will not collect unused word tree at this point. srch_WST_propagate_wd_lv2 is also as the most stupid in the century.  But well, after all, everything needs a start.  I will then really get the results from the search and see how it looks.
  66  *
  67  * Revision 1.3  2005/03/30 01:22:48  archan
  68  * Fixed mistakes in last updates. Add
  69  *
  70  *
  71  * 05-May-1999  M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon
  72  *              Removed hash_key2hash().  Added hash_enter_bkey() and hash_lookup_bkey(),
  73  *              and len attribute to hash_entry_t.
  74  *
  75  * 30-Apr-1999  M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon
  76  *              Added hash_key2hash().
  77  *
  78  * 18-Jun-97    M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon
  79  *              Included case sensitive/insensitive option.  Removed local, static
  80  *              maintenance of all hash tables.
  81  *
  82  * 31-Jul-95    M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon
  83  *              Created.
  84  */
  85
  86
  87 #include <stdio.h>
  88 #include <stdlib.h>
  89 #include <string.h>
  90 #include <assert.h>
  91
  92 #ifdef _MSC_VER
  93 #pragma warning (disable: 4018)
  94 #endif
  95
  96 #include "sphinxbase/hash_table.h"
  97 #include "sphinxbase/err.h"
  98 #include "sphinxbase/ckd_alloc.h"
  99 #include "sphinxbase/case.h"
 100
 101
 102 #if 0
 103 static void
 104 prime_sieve(int32 max)
 105 {
 106     char *notprime;
 107     int32 p, pp;
 108
 109     notprime = (char *) ckd_calloc(max + 1, 1);
 110     p = 2;
 111     for (;;) {
 112         printf("%d\n", p);
 113         for (pp = p + p; pp <= max; pp += p)
 114             notprime[pp] = 1;
 115         for (++p; (p <= max) && notprime[p]; p++);
 116         if (p > max)
 117             break;
 118     }
 119 }
 120 #endif
 121
 122
 123 /*
 124  * HACK!!  Initial hash table size is restricted by this set of primes.  (Of course,
 125  * collision resolution by chaining will accommodate more entries indefinitely, but
 126  * efficiency will drop.)
 127  */
 128 const int32 prime[] = {
 129     101, 211, 307, 401, 503, 601, 701, 809, 907,
 130     1009, 1201, 1601, 2003, 2411, 3001, 4001, 5003, 6007, 7001, 8009,
 131     9001,
 132     10007, 12007, 16001, 20011, 24001, 30011, 40009, 50021, 60013,
 133     70001, 80021, 90001,
 134     100003, 120011, 160001, 200003, 240007, 300007, 400009, 500009,
 135     600011, 700001, 800011, 900001,
 136     -1
 137 };
 138
 139
 140 /**
 141  * This function returns a very large prime.
 142  */
 143 static int32
 144 prime_size(int32 size)
 145 {
 146     int32 i;
 147
 148     for (i = 0; (prime[i] > 0) && (prime[i] < size); i++);
 149     if (prime[i] <= 0) {
 150         E_WARN("Very large hash table requested (%d entries)\n", size);
 151         --i;
 152     }
 153     return (prime[i]);
 154 }
 155
 156
 157 hash_table_t *
 158 hash_table_new(int32 size, int32 casearg)
 159 {
 160     hash_table_t *h;
 161
 162     h = (hash_table_t *) ckd_calloc(1, sizeof(hash_table_t));
 163     h->size = prime_size(size + (size >> 1));
 164     h->nocase = (casearg == HASH_CASE_NO);
 165     h->table = (hash_entry_t *) ckd_calloc(h->size, sizeof(hash_entry_t));
 166     /* The above calloc clears h->table[*].key and .next to NULL, i.e. an empty table */
 167
 168     return h;
 169 }
 170
 171
 172 /*
 173  * Compute hash value for given key string.
 174  * Somewhat tuned for English text word strings.
 175  */
 176 static uint32
 177 key2hash(hash_table_t * h, const char *key)
 178 {
 179
 180     register const char *cp;
 181
 182     /** ARCHAN 20050712:
 183         [1236322] libutil\str2words special character bgu
 184         HACK Apply suggested hack of fixing the hash table such that
 185         it can work with extended ascii code . This is a hack because
 186         the best way to solve it is to make sure all character
 187         representation is unsigned character in the first place. (or
 188         better unicode.)
 189     **/
 190
 191     /*register char c; */
 192     register unsigned char c;
 193     register int32 s;
 194     register uint32 hash;
 195
 196     hash = 0;
 197     s = 0;
 198
 199     if (h->nocase) {
 200         for (cp = key; *cp; cp++) {
 201             c = *cp;
 202             c = UPPER_CASE(c);
 203             hash += c << s;
 204             s += 5;
 205             if (s >= 25)
 206                 s -= 24;
 207         }
 208     }
 209     else {
 210         for (cp = key; *cp; cp++) {
 211             hash += (*cp) << s;
 212             s += 5;
 213             if (s >= 25)
 214                 s -= 24;
 215         }
 216     }
 217
 218     return (hash % h->size);
 219 }
 220
 221
 222 static char *
 223 makekey(uint8 * data, int32 len, char *key)
 224 {
 225     int32 i, j;
 226
 227     if (!key)
 228         key = (char *) ckd_calloc(len * 2 + 1, sizeof(char));
 229
 230     for (i = 0, j = 0; i < len; i++, j += 2) {
 231         key[j] = 'A' + (data[i] & 0x000f);
 232         key[j + 1] = 'J' + ((data[i] >> 4) & 0x000f);
 233     }
 234     key[j] = '\0';
 235
 236     return key;
 237 }
 238
 239
 240 static int32
 241 keycmp_nocase(hash_entry_t * entry, const char *key)
 242 {
 243     char c1, c2;
 244     int32 i;
 245     const char *str;
 246
 247     str = entry->key;
 248     for (i = 0; i < entry->len; i++) {
 249         c1 = *(str++);
 250         c1 = UPPER_CASE(c1);
 251         c2 = *(key++);
 252         c2 = UPPER_CASE(c2);
 253         if (c1 != c2)
 254             return (c1 - c2);
 255     }
 256
 257     return 0;
 258 }
 259
 260
 261 static int32
 262 keycmp_case(hash_entry_t * entry, const char *key)
 263 {
 264     char c1, c2;
 265     int32 i;
 266     const char *str;
 267
 268     str = entry->key;
 269     for (i = 0; i < entry->len; i++) {
 270         c1 = *(str++);
 271         c2 = *(key++);
 272         if (c1 != c2)
 273             return (c1 - c2);
 274     }
 275
 276     return 0;
 277 }
 278
 279
 280 /*
 281  * Lookup entry with hash-value hash in table h for given key
 282  * Return value: hash_entry_t for key
 283  */
 284 static hash_entry_t *
 285 lookup(hash_table_t * h, uint32 hash, const char *key, size_t len)
 286 {
 287     hash_entry_t *entry;
 288
 289     entry = &(h->table[hash]);
 290     if (entry->key == NULL)
 291         return NULL;
 292
 293     if (h->nocase) {
 294         while (entry && ((entry->len != len)
 295                          || (keycmp_nocase(entry, key) != 0)))
 296             entry = entry->next;
 297     }
 298     else {
 299         while (entry && ((entry->len != len)
 300                          || (keycmp_case(entry, key) != 0)))
 301             entry = entry->next;
 302     }
 303
 304     return entry;
 305 }
 306
 307
 308 int32
 309 hash_table_lookup(hash_table_t * h, const char *key, void ** val)
 310 {
 311     hash_entry_t *entry;
 312     uint32 hash;
 313     int32 len;
 314
 315     hash = key2hash(h, key);
 316     len = strlen(key);
 317
 318     entry = lookup(h, hash, key, len);
 319     if (entry) {
 320         if (val)
 321             *val = entry->val;
 322         return 0;
 323     }
 324     else
 325         return -1;
 326 }
 327
 328 int32
 329 hash_table_lookup_int32(hash_table_t * h, const char *key, int32 *val)
 330 {
 331     void *vval;
 332     int32 rv;
 333
 334     rv = hash_table_lookup(h, key, &vval);
 335     if (rv != 0)
 336         return rv;
 337     if (val)
 338         *val = (int32)(long)vval;
 339     return 0;
 340 }
 341
 342
 343 int32
 344 hash_table_lookup_bkey(hash_table_t * h, const char *key, size_t len, void ** val)
 345 {
 346     hash_entry_t *entry;
 347     uint32 hash;
 348     char *str;
 349
 350     str = makekey((uint8 *) key, len, NULL);
 351     hash = key2hash(h, str);
 352     ckd_free(str);
 353
 354     entry = lookup(h, hash, key, len);
 355     if (entry) {
 356         if (val)
 357             *val = entry->val;
 358         return 0;
 359     }
 360     else
 361         return -1;
 362 }
 363
 364 int32
 365 hash_table_lookup_bkey_int32(hash_table_t * h, const char *key, size_t len, int32 *val)
 366 {
 367     void *vval;
 368     int32 rv;
 369
 370     rv = hash_table_lookup_bkey(h, key, len, &vval);
 371     if (rv != 0)
 372         return rv;
 373     if (val)
 374         *val = (int32)(long)vval;
 375     return 0;
 376 }
 377
 378
 379 static void *
 380 enter(hash_table_t * h, uint32 hash, const char *key, size_t len, void *val, int32 replace)
 381 {
 382     hash_entry_t *cur, *new;
 383
 384     if ((cur = lookup(h, hash, key, len)) != NULL) {
 385         void *oldval;
 386         /* Key already exists. */
 387         oldval = cur->val;
 388         if (replace) {
 389             /* Replace the pointer if replacement is requested,
 390              * because this might be a different instance of the same
 391              * string (this verges on magic, sorry) */
 392             cur->key = key;
 393             cur->val = val;
 394         }
 395         return oldval;
 396     }
 397
 398     cur = &(h->table[hash]);
 399     if (cur->key == NULL) {
 400         /* Empty slot at hashed location; add this entry */
 401         cur->key = key;
 402         cur->len = len;
 403         cur->val = val;
 404
 405         /* Added by ARCHAN at 20050515. This allows deletion could work. */
 406         cur->next = NULL;
 407
 408     }
 409     else {
 410         /* Key collision; create new entry and link to hashed location */
 411         new = (hash_entry_t *) ckd_calloc(1, sizeof(hash_entry_t));
 412         new->key = key;
 413         new->len = len;
 414         new->val = val;
 415         new->next = cur->next;
 416         cur->next = new;
 417     }
 418     ++h->inuse;
 419
 420     return val;
 421 }
 422
 423 /* 20050523 Added by ARCHAN  to delete a key from a hash table */
 424 static void *
 425 delete(hash_table_t * h, uint32 hash, const char *key, size_t len)
 426 {
 427     hash_entry_t *entry, *prev;
 428     void *val;
 429
 430     prev = NULL;
 431     entry = &(h->table[hash]);
 432     if (entry->key == NULL)
 433         return NULL;
 434
 435     if (h->nocase) {
 436         while (entry && ((entry->len != len)
 437                          || (keycmp_nocase(entry, key) != 0))) {
 438             prev = entry;
 439             entry = entry->next;
 440         }
 441     }
 442     else {
 443         while (entry && ((entry->len != len)
 444                          || (keycmp_case(entry, key) != 0))) {
 445             prev = entry;
 446             entry = entry->next;
 447         }
 448     }
 449
 450     if (entry == NULL)
 451         return NULL;
 452
 453     /* At this point, entry will be the one required to be deleted, prev
 454        will contain the previous entry
 455      */
 456     val = entry->val;
 457
 458     if (prev == NULL) {
 459         /* That is to say the entry in the hash table (not the chain) matched the key. */
 460         /* We will then copy the things from the next entry to the hash table */
 461         prev = entry;
 462         if (entry->next) {      /* There is a next entry, great, copy it. */
 463             entry = entry->next;
 464             prev->key = entry->key;
 465             prev->len = entry->len;
 466             prev->val = entry->val;
 467             prev->next = entry->next;
 468             ckd_free(entry);
 469         }
 470         else {                  /* There is not a next entry, just set the key to null */
 471             prev->key = NULL;
 472             prev->len = 0;
 473             prev->next = NULL;
 474         }
 475
 476     }
 477     else {                      /* This case is simple */
 478         prev->next = entry->next;
 479         ckd_free(entry);
 480     }
 481
 482     /* Do wiring and free the entry */
 483
 484     --h->inuse;
 485
 486     return val;
 487 }
 488
 489 void
 490 hash_table_empty(hash_table_t *h)
 491 {
 492     hash_entry_t *e, *e2;
 493     int32 i;
 494
 495     for (i = 0; i < h->size; i++) {
 496         /* Free collision lists. */
 497         for (e = h->table[i].next; e; e = e2) {
 498             e2 = e->next;
 499             ckd_free((void *) e);
 500         }
 501         memset(&h->table[i], 0, sizeof(h->table[i]));
 502     }
 503     h->inuse = 0;
 504 }
 505
 506
 507 void *
 508 hash_table_enter(hash_table_t * h, const char *key, void *val)
 509 {
 510     uint32 hash;
 511     size_t len;
 512
 513     hash = key2hash(h, key);
 514     len = strlen(key);
 515     return (enter(h, hash, key, len, val, 0));
 516 }
 517
 518 void *
 519 hash_table_replace(hash_table_t * h, const char *key, void *val)
 520 {
 521     uint32 hash;
 522     size_t len;
 523
 524     hash = key2hash(h, key);
 525     len = strlen(key);
 526     return (enter(h, hash, key, len, val, 1));
 527 }
 528
 529 void *
 530 hash_table_delete(hash_table_t * h, const char *key)
 531 {
 532     uint32 hash;
 533     size_t len;
 534
 535     hash = key2hash(h, key);
 536     len = strlen(key);
 537
 538     return (delete(h, hash, key, len));
 539 }
 540
 541 void *
 542 hash_table_enter_bkey(hash_table_t * h, const char *key, size_t len, void *val)
 543 {
 544     uint32 hash;
 545     char *str;
 546
 547     str = makekey((uint8 *) key, len, NULL);
 548     hash = key2hash(h, str);
 549     ckd_free(str);
 550
 551     return (enter(h, hash, key, len, val, 0));
 552 }
 553
 554 void *
 555 hash_table_replace_bkey(hash_table_t * h, const char *key, size_t len, void *val)
 556 {
 557     uint32 hash;
 558     char *str;
 559
 560     str = makekey((uint8 *) key, len, NULL);
 561     hash = key2hash(h, str);
 562     ckd_free(str);
 563
 564     return (enter(h, hash, key, len, val, 1));
 565 }
 566
 567 void *
 568 hash_table_delete_bkey(hash_table_t * h, const char *key, size_t len)
 569 {
 570     uint32 hash;
 571     char *str;
 572
 573     str = makekey((uint8 *) key, len, NULL);
 574     hash = key2hash(h, str);
 575
 576     return (delete(h, hash, key, len));
 577 }
 578
 579 void
 580 hash_table_display(hash_table_t * h, int32 showdisplay)
 581 {
 582     hash_entry_t *e;
 583     int i, j;
 584     j = 0;
 585
 586     E_INFOCONT("Hash with chaining representation of the hash table\n");
 587
 588     for (i = 0; i < h->size; i++) {
 589         e = &(h->table[i]);
 590         if (e->key != NULL) {
 591             E_INFOCONT("|key:");
 592             if (showdisplay)
 593                 E_INFOCONT("%s", e->key);
 594             else
 595                 E_INFOCONT("%p", e->key);
 596
 597             E_INFOCONT("|len:%d|val=%ld|->", e->len, (long)e->val);
 598             if (e->next == NULL) {
 599                 E_INFOCONT("NULL\n");
 600             }
 601             j++;
 602
 603             for (e = e->next; e; e = e->next) {
 604                 E_INFOCONT("|key:");
 605                 if (showdisplay)
 606                     E_INFOCONT("%s", e->key);
 607
 608                 E_INFOCONT("|len:%d|val=%ld|->", e->len, (long)e->val);
 609                 if (e->next == NULL) {
 610                     E_INFOCONT("NULL\n");
 611                 }
 612                 j++;
 613             }
 614         }
 615     }
 616
 617     E_INFOCONT("The total number of keys =%d\n", j);
 618 }
 619
 620
 621 glist_t
 622 hash_table_tolist(hash_table_t * h, int32 * count)
 623 {
 624     glist_t g;
 625     hash_entry_t *e;
 626     int32 i, j;
 627
 628     g = NULL;
 629
 630     j = 0;
 631     for (i = 0; i < h->size; i++) {
 632         e = &(h->table[i]);
 633
 634         if (e->key != NULL) {
 635             g = glist_add_ptr(g, (void *) e);
 636             j++;
 637
 638             for (e = e->next; e; e = e->next) {
 639                 g = glist_add_ptr(g, (void *) e);
 640                 j++;
 641             }
 642         }
 643     }
 644
 645     if (count)
 646         *count = j;
 647
 648     return g;
 649 }
 650
 651 hash_iter_t *
 652 hash_table_iter(hash_table_t *h)
 653 {
 654         hash_iter_t *itor;
 655
 656         itor = ckd_calloc(1, sizeof(*itor));
 657         itor->ht = h;
 658         return hash_table_iter_next(itor);
 659 }
 660
 661 hash_iter_t *
 662 hash_table_iter_next(hash_iter_t *itor)
 663 {
 664         /* If there is an entry, walk down its list. */
 665         if (itor->ent)
 666                 itor->ent = itor->ent->next;
 667         /* If we got to the end of the chain, or we had no entry, scan
 668          * forward in the table to find the next non-empty bucket. */
 669         if (itor->ent == NULL) {
 670                 while (itor->idx < itor->ht->size
 671                        && itor->ht->table[itor->idx].key == NULL)
 672                         ++itor->idx;
 673                 /* If we did not find one then delete the iterator and
 674                  * return NULL. */
 675                 if (itor->idx == itor->ht->size) {
 676                         hash_table_iter_free(itor);
 677                         return NULL;
 678                 }
 679                 /* Otherwise use this next entry. */
 680                 itor->ent = itor->ht->table + itor->idx;
 681                 /* Increase idx for the next time around. */
 682                 ++itor->idx;
 683         }
 684         return itor;
 685 }
 686
 687 void
 688 hash_table_iter_free(hash_iter_t *itor)
 689 {
 690         ckd_free(itor);
 691 }
 692
 693 void
 694 hash_table_free(hash_table_t * h)
 695 {
 696     hash_entry_t *e, *e2;
 697     int32 i;
 698
 699     if (h == NULL)
 700         return;
 701
 702     /* Free additional entries created for key collision cases */
 703     for (i = 0; i < h->size; i++) {
 704         for (e = h->table[i].next; e; e = e2) {
 705             e2 = e->next;
 706             ckd_free((void *) e);
 707         }
 708     }
 709
 710     ckd_free((void *) h->table);
 711     ckd_free((void *) h);
 712 }