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
133extern "C" {
134#endif
135#if 0
136/* Fool Emacs. */
137}
138#endif
139
149typedef struct hash_entry_s {
150 const char *key;
153 size_t len;
155 void *val;
158
159typedef struct hash_table_s {
160 hash_entry_t *table;
161 int32 size;
164 int32 inuse;
165 int32 nocase;
167
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
190SPHINXBASE_EXPORT
191hash_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
204SPHINXBASE_EXPORT
206 );
207
208
215SPHINXBASE_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
244SPHINXBASE_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
265SPHINXBASE_EXPORT
268 const char *key
270 );
271
279SPHINXBASE_EXPORT
282 const char *key,
284 size_t len
285 );
286
290SPHINXBASE_EXPORT
292 );
293
301SPHINXBASE_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
325SPHINXBASE_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
346SPHINXBASE_EXPORT
348 const char *key,
349 void **val
351 );
352
359SPHINXBASE_EXPORT
361 const char *key,
362 int32 *val
364 );
365
372SPHINXBASE_EXPORT
374 const char *key,
375 size_t len,
376 void **val
378 );
379
386SPHINXBASE_EXPORT
388 const char *key,
389 size_t len,
390 int32 *val
392 );
393
397SPHINXBASE_EXPORT
399
408SPHINXBASE_EXPORT
410
414SPHINXBASE_EXPORT
416
420SPHINXBASE_EXPORT
422 int32 *count
425 );
426
432SPHINXBASE_EXPORT
434 int32 showkey
437 );
438
439#ifdef __cplusplus
440}
441#endif
442
443#endif
Generic linked-lists maintenance.
struct hash_entry_s hash_entry_t
A note by ARCHAN at 20050510: Technically what we use is so-called "hash table with buckets" which is...
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
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_display(hash_table_t *h, int32 showkey)
Display a hash-with-chaining representation on the screen.
Definition hash_table.c:574
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
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
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,...
Definition hash_table.c:535
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
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
SPHINXBASE_EXPORT void hash_table_iter_free(hash_iter_t *itor)
Delete an unfinished iterator.
Definition hash_table.c:682
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,...
Definition hash_table.c:337
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_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 void hash_table_empty(hash_table_t *h)
Delete all entries from a hash_table.
Definition hash_table.c:483
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 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
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(hash_table_t *h)
Start iterating over key-value pairs in a hash table.
Definition hash_table.c:646
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
Basic type definitions used in Sphinx.
A node in a generic list.
Definition glist.h:100
A note by ARCHAN at 20050510: Technically what we use is so-called "hash table with buckets" which is...
Definition hash_table.h:149
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
struct hash_entry_s * next
Value associated with above key.
Definition hash_table.h:156
size_t len
Key string, NULL if this is an empty slot.
Definition hash_table.h:153
hash_table_t * ht
Hash table we are iterating over.
Definition hash_table.h:169
hash_entry_t * ent
Current entry in that table.
Definition hash_table.h:170
size_t idx
Index of next bucket to search.
Definition hash_table.h:171
int32 nocase
Number of valid entries in the table.
Definition hash_table.h:165
int32 size
Primary hash table, excluding entries that collide.
Definition hash_table.h:161
int32 inuse
Primary hash table size, (is a prime#); NOTE: This is the number of primary entries ALLOCATED,...
Definition hash_table.h:164