Debian Codegraph @

src/libsphinxbase/util/hash_table.c

raw
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 ([email protected]) 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 ([email protected]) at Carnegie Mellon
76 * Added hash_key2hash().
77 *
78 * 18-Jun-97 M K Ravishankar ([email protected]) 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 ([email protected]) 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 /* This is a hack because the best way to solve it is to make sure
183 all character representation is unsigned character in the first place.
184 (or better unicode.) */
185 register unsigned char c;
186 register int32 s;
187 register uint32 hash;
188
189 hash = 0;
190 s = 0;
191
192 if (h->nocase) {
193 for (cp = key; *cp; cp++) {
194 c = *cp;
195 c = UPPER_CASE(c);
196 hash += c << s;
197 s += 5;
198 if (s >= 25)
199 s -= 24;
200 }
201 }
202 else {
203 for (cp = key; *cp; cp++) {
204 hash += (*cp) << s;
205 s += 5;
206 if (s >= 25)
207 s -= 24;
208 }
209 }
210
211 return (hash % h->size);
212 }
213
214
215 static char *
216 makekey(uint8 * data, size_t len, char *key)
217 {
218 size_t i, j;
219
220 if (!key)
221 key = (char *) ckd_calloc(len * 2 + 1, sizeof(char));
222
223 for (i = 0, j = 0; i < len; i++, j += 2) {
224 key[j] = 'A' + (data[i] & 0x000f);
225 key[j + 1] = 'J' + ((data[i] >> 4) & 0x000f);
226 }
227 key[j] = '\0';
228
229 return key;
230 }
231
232
233 static int32
234 keycmp_nocase(hash_entry_t * entry, const char *key)
235 {
236 char c1, c2;
237 int32 i;
238 const char *str;
239
240 str = entry->key;
241 for (i = 0; i < entry->len; i++) {
242 c1 = *(str++);
243 c1 = UPPER_CASE(c1);
244 c2 = *(key++);
245 c2 = UPPER_CASE(c2);
246 if (c1 != c2)
247 return (c1 - c2);
248 }
249
250 return 0;
251 }
252
253
254 static int32
255 keycmp_case(hash_entry_t * entry, const char *key)
256 {
257 char c1, c2;
258 int32 i;
259 const char *str;
260
261 str = entry->key;
262 for (i = 0; i < entry->len; i++) {
263 c1 = *(str++);
264 c2 = *(key++);
265 if (c1 != c2)
266 return (c1 - c2);
267 }
268
269 return 0;
270 }
271
272
273 /*
274 * Lookup entry with hash-value hash in table h for given key
275 * Return value: hash_entry_t for key
276 */
277 static hash_entry_t *
278 lookup(hash_table_t * h, uint32 hash, const char *key, size_t len)
279 {
280 hash_entry_t *entry;
281
282 entry = &(h->table[hash]);
283 if (entry->key == NULL)
284 return NULL;
285
286 if (h->nocase) {
287 while (entry && ((entry->len != len)
288 || (keycmp_nocase(entry, key) != 0)))
289 entry = entry->next;
290 }
291 else {
292 while (entry && ((entry->len != len)
293 || (keycmp_case(entry, key) != 0)))
294 entry = entry->next;
295 }
296
297 return entry;
298 }
299
300
301 int32
302 hash_table_lookup(hash_table_t * h, const char *key, void ** val)
303 {
304 hash_entry_t *entry;
305 uint32 hash;
306 size_t len;
307
308 hash = key2hash(h, key);
309 len = strlen(key);
310
311 entry = lookup(h, hash, key, len);
312 if (entry) {
313 if (val)
314 *val = entry->val;
315 return 0;
316 }
317 else
318 return -1;
319 }
320
321 int32
322 hash_table_lookup_int32(hash_table_t * h, const char *key, int32 *val)
323 {
324 void *vval;
325 int32 rv;
326
327 rv = hash_table_lookup(h, key, &vval);
328 if (rv != 0)
329 return rv;
330 if (val)
331 *val = (int32)(long)vval;
332 return 0;
333 }
334
335
336 int32
337 hash_table_lookup_bkey(hash_table_t * h, const char *key, size_t len, void ** val)
338 {
339 hash_entry_t *entry;
340 uint32 hash;
341 char *str;
342
343 str = makekey((uint8 *) key, len, NULL);
344 hash = key2hash(h, str);
345 ckd_free(str);
346
347 entry = lookup(h, hash, key, len);
348 if (entry) {
349 if (val)
350 *val = entry->val;
351 return 0;
352 }
353 else
354 return -1;
355 }
356
357 int32
358 hash_table_lookup_bkey_int32(hash_table_t * h, const char *key, size_t len, int32 *val)
359 {
360 void *vval;
361 int32 rv;
362
363 rv = hash_table_lookup_bkey(h, key, len, &vval);
364 if (rv != 0)
365 return rv;
366 if (val)
367 *val = (int32)(long)vval;
368 return 0;
369 }
370
371
372 static void *
373 enter(hash_table_t * h, uint32 hash, const char *key, size_t len, void *val, int32 replace)
374 {
375 hash_entry_t *cur, *new;
376
377 if ((cur = lookup(h, hash, key, len)) != NULL) {
378 void *oldval;
379 /* Key already exists. */
380 oldval = cur->val;
381 if (replace) {
382 /* Replace the pointer if replacement is requested,
383 * because this might be a different instance of the same
384 * string (this verges on magic, sorry) */
385 cur->key = key;
386 cur->val = val;
387 }
388 return oldval;
389 }
390
391 cur = &(h->table[hash]);
392 if (cur->key == NULL) {
393 /* Empty slot at hashed location; add this entry */
394 cur->key = key;
395 cur->len = len;
396 cur->val = val;
397
398 /* Added by ARCHAN at 20050515. This allows deletion could work. */
399 cur->next = NULL;
400
401 }
402 else {
403 /* Key collision; create new entry and link to hashed location */
404 new = (hash_entry_t *) ckd_calloc(1, sizeof(hash_entry_t));
405 new->key = key;
406 new->len = len;
407 new->val = val;
408 new->next = cur->next;
409 cur->next = new;
410 }
411 ++h->inuse;
412
413 return val;
414 }
415
416 /* 20050523 Added by ARCHAN to delete a key from a hash table */
417 static void *
418 delete(hash_table_t * h, uint32 hash, const char *key, size_t len)
419 {
420 hash_entry_t *entry, *prev;
421 void *val;
422
423 prev = NULL;
424 entry = &(h->table[hash]);
425 if (entry->key == NULL)
426 return NULL;
427
428 if (h->nocase) {
429 while (entry && ((entry->len != len)
430 || (keycmp_nocase(entry, key) != 0))) {
431 prev = entry;
432 entry = entry->next;
433 }
434 }
435 else {
436 while (entry && ((entry->len != len)
437 || (keycmp_case(entry, key) != 0))) {
438 prev = entry;
439 entry = entry->next;
440 }
441 }
442
443 if (entry == NULL)
444 return NULL;
445
446 /* At this point, entry will be the one required to be deleted, prev
447 will contain the previous entry
448 */
449 val = entry->val;
450
451 if (prev == NULL) {
452 /* That is to say the entry in the hash table (not the chain) matched the key. */
453 /* We will then copy the things from the next entry to the hash table */
454 prev = entry;
455 if (entry->next) { /* There is a next entry, great, copy it. */
456 entry = entry->next;
457 prev->key = entry->key;
458 prev->len = entry->len;
459 prev->val = entry->val;
460 prev->next = entry->next;
461 ckd_free(entry);
462 }
463 else { /* There is not a next entry, just set the key to null */
464 prev->key = NULL;
465 prev->len = 0;
466 prev->next = NULL;
467 }
468
469 }
470 else { /* This case is simple */
471 prev->next = entry->next;
472 ckd_free(entry);
473 }
474
475 /* Do wiring and free the entry */
476
477 --h->inuse;
478
479 return val;
480 }
481
482 void
483 hash_table_empty(hash_table_t *h)
484 {
485 hash_entry_t *e, *e2;
486 int32 i;
487
488 for (i = 0; i < h->size; i++) {
489 /* Free collision lists. */
490 for (e = h->table[i].next; e; e = e2) {
491 e2 = e->next;
492 ckd_free((void *) e);
493 }
494 memset(&h->table[i], 0, sizeof(h->table[i]));
495 }
496 h->inuse = 0;
497 }
498
499
500 void *
501 hash_table_enter(hash_table_t * h, const char *key, void *val)
502 {
503 uint32 hash;
504 size_t len;
505
506 hash = key2hash(h, key);
507 len = strlen(key);
508 return (enter(h, hash, key, len, val, 0));
509 }
510
511 void *
512 hash_table_replace(hash_table_t * h, const char *key, void *val)
513 {
514 uint32 hash;
515 size_t len;
516
517 hash = key2hash(h, key);
518 len = strlen(key);
519 return (enter(h, hash, key, len, val, 1));
520 }
521
522 void *
523 hash_table_delete(hash_table_t * h, const char *key)
524 {
525 uint32 hash;
526 size_t len;
527
528 hash = key2hash(h, key);
529 len = strlen(key);
530
531 return (delete(h, hash, key, len));
532 }
533
534 void *
535 hash_table_enter_bkey(hash_table_t * h, const char *key, size_t len, void *val)
536 {
537 uint32 hash;
538 char *str;
539
540 str = makekey((uint8 *) key, len, NULL);
541 hash = key2hash(h, str);
542 ckd_free(str);
543
544 return (enter(h, hash, key, len, val, 0));
545 }
546
547 void *
548 hash_table_replace_bkey(hash_table_t * h, const char *key, size_t len, void *val)
549 {
550 uint32 hash;
551 char *str;
552
553 str = makekey((uint8 *) key, len, NULL);
554 hash = key2hash(h, str);
555 ckd_free(str);
556
557 return (enter(h, hash, key, len, val, 1));
558 }
559
560 void *
561 hash_table_delete_bkey(hash_table_t * h, const char *key, size_t len)
562 {
563 uint32 hash;
564 char *str;
565
566 str = makekey((uint8 *) key, len, NULL);
567 hash = key2hash(h, str);
568 ckd_free(str);
569
570 return (delete(h, hash, key, len));
571 }
572
573 void
574 hash_table_display(hash_table_t * h, int32 showdisplay)
575 {
576 hash_entry_t *e;
577 int i, j;
578 j = 0;
579
580 printf("Hash with chaining representation of the hash table\n");
581
582 for (i = 0; i < h->size; i++) {
583 e = &(h->table[i]);
584 if (e->key != NULL) {
585 printf("|key:");
586 if (showdisplay)
587 printf("%s", e->key);
588 else
589 printf("%p", e->key);
590
591 printf("|len:%zd|val=%ld|->", e->len, (long)e->val);
592 if (e->next == NULL) {
593 printf("NULL\n");
594 }
595 j++;
596
597 for (e = e->next; e; e = e->next) {
598 printf("|key:");
599 if (showdisplay)
600 printf("%s", e->key);
601
602 printf("|len:%zd|val=%ld|->", e->len, (long)e->val);
603 if (e->next == NULL) {
604 printf("NULL\n");
605 }
606 j++;
607 }
608 }
609 }
610
611 printf("The total number of keys =%d\n", j);
612 }
613
614
615 glist_t
616 hash_table_tolist(hash_table_t * h, int32 * count)
617 {
618 glist_t g;
619 hash_entry_t *e;
620 int32 i, j;
621
622 g = NULL;
623
624 j = 0;
625 for (i = 0; i < h->size; i++) {
626 e = &(h->table[i]);
627
628 if (e->key != NULL) {
629 g = glist_add_ptr(g, (void *) e);
630 j++;
631
632 for (e = e->next; e; e = e->next) {
633 g = glist_add_ptr(g, (void *) e);
634 j++;
635 }
636 }
637 }
638
639 if (count)
640 *count = j;
641
642 return g;
643 }
644
645 hash_iter_t *
646 hash_table_iter(hash_table_t *h)
647 {
648 hash_iter_t *itor;
649
650 itor = ckd_calloc(1, sizeof(*itor));
651 itor->ht = h;
652 return hash_table_iter_next(itor);
653 }
654
655 hash_iter_t *
656 hash_table_iter_next(hash_iter_t *itor)
657 {
658 /* If there is an entry, walk down its list. */
659 if (itor->ent)
660 itor->ent = itor->ent->next;
661 /* If we got to the end of the chain, or we had no entry, scan
662 * forward in the table to find the next non-empty bucket. */
663 if (itor->ent == NULL) {
664 while (itor->idx < itor->ht->size
665 && itor->ht->table[itor->idx].key == NULL)
666 ++itor->idx;
667 /* If we did not find one then delete the iterator and
668 * return NULL. */
669 if (itor->idx == itor->ht->size) {
670 hash_table_iter_free(itor);
671 return NULL;
672 }
673 /* Otherwise use this next entry. */
674 itor->ent = itor->ht->table + itor->idx;
675 /* Increase idx for the next time around. */
676 ++itor->idx;
677 }
678 return itor;
679 }
680
681 void
682 hash_table_iter_free(hash_iter_t *itor)
683 {
684 ckd_free(itor);
685 }
686
687 void
688 hash_table_free(hash_table_t * h)
689 {
690 hash_entry_t *e, *e2;
691 int32 i;
692
693 if (h == NULL)
694 return;
695
696 /* Free additional entries created for key collision cases */
697 for (i = 0; i < h->size; i++) {
698 for (e = h->table[i].next; e; e = e2) {
699 e2 = e->next;
700 ckd_free((void *) e);
701 }
702 }
703
704 ckd_free((void *) h->table);
705 ckd_free((void *) h);
706 }