93 #pragma warning (disable: 4018)
104 prime_sieve(int32 max)
113 for (pp = p + p; pp <= max; pp += p)
115 for (++p; (p <= max) && notprime[p]; p++);
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,
132 10007, 12007, 16001, 20011, 24001, 30011, 40009, 50021, 60013,
134 100003, 120011, 160001, 200003, 240007, 300007, 400009, 500009,
135 600011, 700001, 800011, 900001,
144 prime_size(int32 size)
148 for (i = 0; (prime[i] > 0) && (prime[i] < size); i++);
150 E_WARN(
"Very large hash table requested (%d entries)\n", size);
163 h->
size = prime_size(size + (size >> 1));
164 h->
nocase = (casearg == HASH_CASE_NO);
180 register const char *cp;
192 register unsigned char c;
194 register uint32 hash;
200 for (cp = key; *cp; cp++) {
210 for (cp = key; *cp; cp++) {
218 return (hash % h->
size);
223 makekey(uint8 * data, int32 len,
char *key)
228 key = (
char *)
ckd_calloc(len * 2 + 1,
sizeof(
char));
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);
248 for (i = 0; i < entry->
len; i++) {
269 for (i = 0; i < entry->
len; i++) {
285 lookup(
hash_table_t * h, uint32 hash,
const char *key,
size_t len)
289 entry = &(h->table[hash]);
290 if (entry->key == NULL)
294 while (entry && ((entry->
len != len)
295 || (keycmp_nocase(entry, key) != 0)))
299 while (entry && ((entry->
len != len)
300 || (keycmp_case(entry, key) != 0)))
315 hash = key2hash(h, key);
318 entry = lookup(h, hash, key, len);
338 *val = (int32)(
long)vval;
350 str = makekey((uint8 *) key, len, NULL);
351 hash = key2hash(h, str);
354 entry = lookup(h, hash, key, len);
374 *val = (int32)(
long)vval;
380 enter(
hash_table_t * h, uint32 hash,
const char *key,
size_t len,
void *val, int32 replace)
384 if ((cur = lookup(h, hash, key, len)) != NULL) {
398 cur = &(h->table[hash]);
399 if (cur->key == NULL) {
415 new->next = cur->
next;
425 delete(
hash_table_t * h, uint32 hash,
const char *key,
size_t len)
431 entry = &(h->table[hash]);
432 if (entry->key == NULL)
436 while (entry && ((entry->
len != len)
437 || (keycmp_nocase(entry, key) != 0))) {
443 while (entry && ((entry->
len != len)
444 || (keycmp_case(entry, key) != 0))) {
464 prev->key = entry->key;
495 for (i = 0; i < h->
size; i++) {
497 for (e = h->table[i].
next; e; e = e2) {
501 memset(&h->table[i], 0,
sizeof(h->table[i]));
513 hash = key2hash(h, key);
515 return (enter(h, hash, key, len, val, 0));
524 hash = key2hash(h, key);
526 return (enter(h, hash, key, len, val, 1));
535 hash = key2hash(h, key);
538 return (
delete(h, hash, key, len));
547 str = makekey((uint8 *) key, len, NULL);
548 hash = key2hash(h, str);
551 return (enter(h, hash, key, len, val, 0));
560 str = makekey((uint8 *) key, len, NULL);
561 hash = key2hash(h, str);
564 return (enter(h, hash, key, len, val, 1));
573 str = makekey((uint8 *) key, len, NULL);
574 hash = key2hash(h, str);
577 return (
delete(h, hash, key, len));
587 E_INFOCONT(
"Hash with chaining representation of the hash table\n");
589 for (i = 0; i < h->
size; i++) {
591 if (e->key != NULL) {
599 if (e->
next == NULL) {
610 if (e->
next == NULL) {
618 E_INFOCONT(
"The total number of keys =%d\n", j);
632 for (i = 0; i < h->
size; i++) {
635 if (e->key != NULL) {
670 if (itor->
ent == NULL) {
672 && itor->
ht->table[itor->
idx].key == NULL)
681 itor->
ent = itor->
ht->table + itor->
idx;
704 for (i = 0; i < h->
size; i++) {
705 for (e = h->table[i].
next; e; e = e2) {
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...
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.
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.
hash_entry_t * ent
Current entry in that table.
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.
#define ckd_calloc(n, sz)
Macros to simplify the use of above functions.
SPHINXBASE_EXPORT void hash_table_display(hash_table_t *h, int32 showkey)
Display a hash-with-chaining representation on the screen.
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.
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.
Sphinx's memory allocation/deallocation routines.
struct hash_entry_s * next
Value associated with above key.
SPHINXBASE_EXPORT void hash_table_iter_free(hash_iter_t *itor)
Delete an unfinished iterator.
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.
A node in a generic list.
SPHINXBASE_EXPORT hash_iter_t * hash_table_iter(hash_table_t *h)
Start iterating over key-value pairs in a hash table.
SPHINXBASE_EXPORT hash_table_t * hash_table_new(int32 size, int32 casearg)
Allocate a new hash table for a given expected size.
SPHINXBASE_EXPORT void hash_table_empty(hash_table_t *h)
Delete all entries from a hash_table.
SPHINXBASE_EXPORT void ckd_free(void *ptr)
Test and free a 1-D array.
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...
#define E_WARN
Print warning information to standard error stream.
#define UPPER_CASE(c)
Return upper case form for c.
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...
A note by ARCHAN at 20050510: Technically what we use is so-called "hash table with buckets" which is...
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.
int32 inuse
Primary hash table size, (is a prime#); NOTE: This is the number of primary entries ALLOCATED...
size_t len
Key string, NULL if this is an empty slot.
size_t idx
Index of next bucket to search.
hash_table_t * ht
Hash table we are iterating over.
int32 size
Primary hash table, excluding entries that collide.
#define E_INFOCONT
Print logging information without header, to standard error stream.
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.
SPHINXBASE_EXPORT hash_iter_t * hash_table_iter_next(hash_iter_t *itor)
Get the next key-value pair in iteration.
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.
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...
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...
int32 nocase
Number of valid entries in the table.
Locale-independent implementation of case swapping operation.