SphinxBase  5prealpha
hash_table.h
Go to the documentation of this file.
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.h -- 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.h,v $
49  * Revision 1.7 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.8 2005/05/24 01:10:54 archan
53  * 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.
54  *
55  * Revision 1.7 2005/05/24 00:12:31 archan
56  * Also add function prototype for hash_display in hash.h
57  *
58  * Revision 1.4 2005/05/03 04:09:11 archan
59  * 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.
60  *
61  * Revision 1.3 2005/03/30 01:22:48 archan
62  * Fixed mistakes in last updates. Add
63  *
64  *
65  * 05-May-1999 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon
66  * Removed hash_key2hash(). Added hash_enter_bkey() and hash_lookup_bkey(),
67  * and len attribute to hash_entry_t.
68  *
69  * 30-Apr-1999 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon
70  * Added hash_key2hash().
71  *
72  * 18-Jun-97 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon
73  * Included case sensitive/insensitive option.
74  *
75  * 08-31-95 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon
76  * Created.
77  */
78 
79 
124 #ifndef _LIBUTIL_HASH_H_
125 #define _LIBUTIL_HASH_H_
126 
127 /* Win32/WinCE DLL gunk */
128 #include <sphinxbase/sphinxbase_export.h>
129 #include <sphinxbase/prim_type.h>
130 #include <sphinxbase/glist.h>
131 
132 #ifdef __cplusplus
133 extern "C" {
134 #endif
135 #if 0
136 /* Fool Emacs. */
137 }
138 #endif
139 
149 typedef struct hash_entry_s {
150  const char *key;
153  size_t len;
155  void *val;
156  struct hash_entry_s *next;
157 } hash_entry_t;
158 
159 typedef struct hash_table_s {
160  hash_entry_t *table;
161  int32 size;
164  int32 inuse;
165  int32 nocase;
166 } hash_table_t;
167 
168 typedef struct hash_iter_s {
171  size_t idx;
172 } hash_iter_t;
173 
175 #define hash_entry_val(e) ((e)->val)
176 #define hash_entry_key(e) ((e)->key)
177 #define hash_entry_len(e) ((e)->len)
178 #define hash_table_inuse(h) ((h)->inuse)
179 #define hash_table_size(h) ((h)->size)
180 
181 
190 SPHINXBASE_EXPORT
191 hash_table_t * hash_table_new(int32 size,
192  int32 casearg
195  );
196 
197 #define HASH_CASE_YES 0
198 #define HASH_CASE_NO 1
199 
204 SPHINXBASE_EXPORT
206  );
207 
208 
215 SPHINXBASE_EXPORT
217  const char *key,
219  void *val
220  );
221 
228 #define hash_table_enter_int32(h,k,v) \
229  ((int32)(long)hash_table_enter((h),(k),(void *)(long)(v)))
230 
244 SPHINXBASE_EXPORT
246  const char *key,
248  void *val
249  );
250 
257 #define hash_table_replace_int32(h,k,v) \
258  ((int32)(long)hash_table_replace((h),(k),(void *)(long)(v)))
259 
265 SPHINXBASE_EXPORT
268  const char *key
270  );
271 
279 SPHINXBASE_EXPORT
282  const char *key,
284  size_t len
285  );
286 
290 SPHINXBASE_EXPORT
292  );
293 
301 SPHINXBASE_EXPORT
304  const char *key,
305  size_t len,
306  void *val
307  );
308 
315 #define hash_table_enter_bkey_int32(h,k,l,v) \
316  ((int32)(long)hash_table_enter_bkey((h),(k),(l),(void *)(long)(v)))
317 
325 SPHINXBASE_EXPORT
327  const char *key,
328  size_t len,
329  void *val
330  );
331 
338 #define hash_table_replace_bkey_int32(h,k,l,v) \
339  ((int32)(long)hash_table_replace_bkey((h),(k),(l),(void *)(long)(v)))
340 
346 SPHINXBASE_EXPORT
348  const char *key,
349  void **val
351  );
352 
359 SPHINXBASE_EXPORT
361  const char *key,
362  int32 *val
364  );
365 
372 SPHINXBASE_EXPORT
374  const char *key,
375  size_t len,
376  void **val
378  );
379 
386 SPHINXBASE_EXPORT
388  const char *key,
389  size_t len,
390  int32 *val
392  );
393 
397 SPHINXBASE_EXPORT
399 
408 SPHINXBASE_EXPORT
410 
414 SPHINXBASE_EXPORT
416 
420 SPHINXBASE_EXPORT
422  int32 *count
425  );
426 
432 SPHINXBASE_EXPORT
434  int32 showkey
437  );
438 
439 #ifdef __cplusplus
440 }
441 #endif
442 
443 #endif
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
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
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
Basic type definitions used in Sphinx.
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 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
struct hash_entry_s hash_entry_t
A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot; which is...
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
Generic linked-lists maintenance.
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
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
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