SphinxBase  0.6
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 
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 
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
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  ckd_free(str);
576 
577  return (delete(h, hash, key, len));
578 }
579 
580 void
581 hash_table_display(hash_table_t * h, int32 showdisplay)
582 {
583  hash_entry_t *e;
584  int i, j;
585  j = 0;
586 
587  E_INFOCONT("Hash with chaining representation of the hash table\n");
588 
589  for (i = 0; i < h->size; i++) {
590  e = &(h->table[i]);
591  if (e->key != NULL) {
592  E_INFOCONT("|key:");
593  if (showdisplay)
594  E_INFOCONT("%s", e->key);
595  else
596  E_INFOCONT("%p", e->key);
597 
598  E_INFOCONT("|len:%d|val=%ld|->", e->len, (long)e->val);
599  if (e->next == NULL) {
600  E_INFOCONT("NULL\n");
601  }
602  j++;
603 
604  for (e = e->next; e; e = e->next) {
605  E_INFOCONT("|key:");
606  if (showdisplay)
607  E_INFOCONT("%s", e->key);
608 
609  E_INFOCONT("|len:%d|val=%ld|->", e->len, (long)e->val);
610  if (e->next == NULL) {
611  E_INFOCONT("NULL\n");
612  }
613  j++;
614  }
615  }
616  }
617 
618  E_INFOCONT("The total number of keys =%d\n", j);
619 }
620 
621 
622 glist_t
623 hash_table_tolist(hash_table_t * h, int32 * count)
624 {
625  glist_t g;
626  hash_entry_t *e;
627  int32 i, j;
628 
629  g = NULL;
630 
631  j = 0;
632  for (i = 0; i < h->size; i++) {
633  e = &(h->table[i]);
634 
635  if (e->key != NULL) {
636  g = glist_add_ptr(g, (void *) e);
637  j++;
638 
639  for (e = e->next; e; e = e->next) {
640  g = glist_add_ptr(g, (void *) e);
641  j++;
642  }
643  }
644  }
645 
646  if (count)
647  *count = j;
648 
649  return g;
650 }
651 
652 hash_iter_t *
654 {
655  hash_iter_t *itor;
656 
657  itor = ckd_calloc(1, sizeof(*itor));
658  itor->ht = h;
659  return hash_table_iter_next(itor);
660 }
661 
662 hash_iter_t *
664 {
665  /* If there is an entry, walk down its list. */
666  if (itor->ent)
667  itor->ent = itor->ent->next;
668  /* If we got to the end of the chain, or we had no entry, scan
669  * forward in the table to find the next non-empty bucket. */
670  if (itor->ent == NULL) {
671  while (itor->idx < itor->ht->size
672  && itor->ht->table[itor->idx].key == NULL)
673  ++itor->idx;
674  /* If we did not find one then delete the iterator and
675  * return NULL. */
676  if (itor->idx == itor->ht->size) {
677  hash_table_iter_free(itor);
678  return NULL;
679  }
680  /* Otherwise use this next entry. */
681  itor->ent = itor->ht->table + itor->idx;
682  /* Increase idx for the next time around. */
683  ++itor->idx;
684  }
685  return itor;
686 }
687 
688 void
690 {
691  ckd_free(itor);
692 }
693 
694 void
696 {
697  hash_entry_t *e, *e2;
698  int32 i;
699 
700  if (h == NULL)
701  return;
702 
703  /* Free additional entries created for key collision cases */
704  for (i = 0; i < h->size; i++) {
705  for (e = h->table[i].next; e; e = e2) {
706  e2 = e->next;
707  ckd_free((void *) e);
708  }
709  }
710 
711  ckd_free((void *) h->table);
712  ckd_free((void *) h);
713 }
SPHINXBASE_EXPORT void * hash_table_delete_bkey(hash_table_t *h, const char *key, size_t len)
Like hash_table_delete, but with an explicitly specified key length, instead of a NULL-terminated...
Definition: hash_table.c:568
SPHINXBASE_EXPORT int32 hash_table_lookup_int32(hash_table_t *h, const char *key, int32 *val)
Look up a 32-bit integer value in a hash table.
Definition: hash_table.c:329
SPHINXBASE_EXPORT void * hash_table_enter_bkey(hash_table_t *h, const char *key, size_t len, void *val)
Like hash_table_enter, but with an explicitly specified key length, instead of a NULL-terminated, C-style key string.
Definition: hash_table.c:542
hash_entry_t * ent
Current entry in that table.
Definition: hash_table.h:170
SPHINXBASE_EXPORT int32 hash_table_lookup(hash_table_t *h, const char *key, void **val)
Look up a key in a hash table and optionally return the associated value.
Definition: hash_table.c:309
#define ckd_calloc(n, sz)
Macros to simplify the use of above functions.
Definition: ckd_alloc.h:248
SPHINXBASE_EXPORT void hash_table_display(hash_table_t *h, int32 showkey)
Display a hash-with-chaining representation on the screen.
Definition: hash_table.c:581
SPHINXBASE_EXPORT int32 hash_table_lookup_bkey(hash_table_t *h, const char *key, size_t len, void **val)
Like hash_lookup, but with an explicitly specified key length, instead of a NULL-terminated, C-style key string.
Definition: hash_table.c:344
SPHINXBASE_EXPORT void * hash_table_replace(hash_table_t *h, const char *key, void *val)
Add a new entry with given key and value to hash table h.
Definition: hash_table.c:519
Sphinx's memory allocation/deallocation routines.
struct hash_entry_s * next
Value associated with above key.
Definition: hash_table.h:156
SPHINXBASE_EXPORT void hash_table_iter_free(hash_iter_t *itor)
Delete an unfinished iterator.
Definition: hash_table.c:689
SPHINXBASE_EXPORT glist_t hash_table_tolist(hash_table_t *h, int32 *count)
Build a glist of valid hash_entry_t pointers from the given hash table.
Definition: hash_table.c:623
A node in a generic list.
Definition: glist.h:100
SPHINXBASE_EXPORT hash_iter_t * hash_table_iter(hash_table_t *h)
Start iterating over key-value pairs in a hash table.
Definition: hash_table.c:653
SPHINXBASE_EXPORT hash_table_t * hash_table_new(int32 size, int32 casearg)
Allocate a new hash table for a given expected size.
Definition: hash_table.c:158
SPHINXBASE_EXPORT void hash_table_empty(hash_table_t *h)
Delete all entries from a hash_table.
Definition: hash_table.c:490
SPHINXBASE_EXPORT void ckd_free(void *ptr)
Test and free a 1-D array.
Definition: ckd_alloc.c:241
SPHINXBASE_EXPORT glist_t glist_add_ptr(glist_t g, void *ptr)
Create and prepend a new list node, with the given user-defined data, at the HEAD of the given generi...
Definition: glist.c:74
#define E_WARN
Print warning information to standard error stream.
Definition: err.h:164
#define UPPER_CASE(c)
Return upper case form for c.
Definition: case.h:92
SPHINXBASE_EXPORT void hash_table_free(hash_table_t *h)
Free the specified hash table; the caller is responsible for freeing the key strings pointed to by th...
Definition: hash_table.c:695
A note by ARCHAN at 20050510: Technically what we use is so-called "hash table with buckets" which is...
Definition: hash_table.h:149
SPHINXBASE_EXPORT int32 hash_table_lookup_bkey_int32(hash_table_t *h, const char *key, size_t len, int32 *val)
Look up a 32-bit integer value in a hash table.
Definition: hash_table.c:365
int32 inuse
Primary hash table size, (is a prime#); NOTE: This is the number of primary entries ALLOCATED...
Definition: hash_table.h:164
size_t len
Key string, NULL if this is an empty slot.
Definition: hash_table.h:153
size_t idx
Index of next bucket to search.
Definition: hash_table.h:171
hash_table_t * ht
Hash table we are iterating over.
Definition: hash_table.h:169
int32 size
Primary hash table, excluding entries that collide.
Definition: hash_table.h:161
#define E_INFOCONT
Print logging information without header, to standard error stream.
Definition: err.h:153
Implementation of logging routines.
SPHINXBASE_EXPORT void * hash_table_enter(hash_table_t *h, const char *key, void *val)
Try to add a new entry with given key and associated value to hash table h.
Definition: hash_table.c:508
SPHINXBASE_EXPORT hash_iter_t * hash_table_iter_next(hash_iter_t *itor)
Get the next key-value pair in iteration.
Definition: hash_table.c:663
SPHINXBASE_EXPORT void * hash_table_delete(hash_table_t *h, const char *key)
Delete an entry with given key and associated value to hash table h.
Definition: hash_table.c:530
Hash table implementation.
void * val
Key-length; the key string does not have to be a C-style NULL terminated string; it can have arbitrar...
Definition: hash_table.h:155
SPHINXBASE_EXPORT void * hash_table_replace_bkey(hash_table_t *h, const char *key, size_t len, void *val)
Like hash_table_replace, but with an explicitly specified key length, instead of a NULL-terminated...
Definition: hash_table.c:555
int32 nocase
Number of valid entries in the table.
Definition: hash_table.h:165
Locale-independent implementation of case swapping operation.