SphinxBase  5prealpha
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 
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
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 *
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 *
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
683 {
684  ckd_free(itor);
685 }
686 
687 void
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 }
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:561
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:322
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:535
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:302
#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:574
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:337
int32 nocase
Number of valid entries in the table.
Definition: hash_table.h:165
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:512
Sphinx&#39;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:682
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:616
int32 size
Primary hash table, excluding entries that collide.
Definition: hash_table.h:161
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:646
int32 inuse
Primary hash table size, (is a prime#); NOTE: This is the number of primary entries ALLOCATED...
Definition: hash_table.h:164
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:483
SPHINXBASE_EXPORT void ckd_free(void *ptr)
Test and free a 1-D array.
Definition: ckd_alloc.c:244
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 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:688
A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot; 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:358
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
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:501
#define E_WARN(...)
Print warning message to error log.
Definition: err.h:109
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:656
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:523
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:548
Locale-independent implementation of case swapping operation.