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;
185 register unsigned char c;
187 register uint32 hash;
193 for (cp = key; *cp; cp++) {
203 for (cp = key; *cp; cp++) {
211 return (hash % h->
size);
216 makekey(uint8 * data,
size_t len,
char *key)
221 key = (
char *)
ckd_calloc(len * 2 + 1,
sizeof(
char));
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);
241 for (i = 0; i < entry->
len; i++) {
262 for (i = 0; i < entry->
len; i++) {
278 lookup(
hash_table_t * h, uint32 hash,
const char *key,
size_t len)
282 entry = &(h->table[hash]);
283 if (entry->key == NULL)
287 while (entry && ((entry->
len != len)
288 || (keycmp_nocase(entry, key) != 0)))
292 while (entry && ((entry->
len != len)
293 || (keycmp_case(entry, key) != 0)))
308 hash = key2hash(h, key);
311 entry = lookup(h, hash, key, len);
331 *val = (int32)(
long)vval;
343 str = makekey((uint8 *) key, len, NULL);
344 hash = key2hash(h, str);
347 entry = lookup(h, hash, key, len);
367 *val = (int32)(
long)vval;
373 enter(
hash_table_t * h, uint32 hash,
const char *key,
size_t len,
void *val, int32 replace)
377 if ((cur = lookup(h, hash, key, len)) != NULL) {
391 cur = &(h->table[hash]);
392 if (cur->key == NULL) {
408 new->next = cur->
next;
418 delete(
hash_table_t * h, uint32 hash,
const char *key,
size_t len)
424 entry = &(h->table[hash]);
425 if (entry->key == NULL)
429 while (entry && ((entry->
len != len)
430 || (keycmp_nocase(entry, key) != 0))) {
436 while (entry && ((entry->
len != len)
437 || (keycmp_case(entry, key) != 0))) {
457 prev->key = entry->key;
488 for (i = 0; i < h->
size; i++) {
490 for (e = h->table[i].
next; e; e = e2) {
494 memset(&h->table[i], 0,
sizeof(h->table[i]));
506 hash = key2hash(h, key);
508 return (enter(h, hash, key, len, val, 0));
517 hash = key2hash(h, key);
519 return (enter(h, hash, key, len, val, 1));
528 hash = key2hash(h, key);
531 return (
delete(h, hash, key, len));
540 str = makekey((uint8 *) key, len, NULL);
541 hash = key2hash(h, str);
544 return (enter(h, hash, key, len, val, 0));
553 str = makekey((uint8 *) key, len, NULL);
554 hash = key2hash(h, str);
557 return (enter(h, hash, key, len, val, 1));
566 str = makekey((uint8 *) key, len, NULL);
567 hash = key2hash(h, str);
570 return (
delete(h, hash, key, len));
580 printf(
"Hash with chaining representation of the hash table\n");
582 for (i = 0; i < h->
size; i++) {
584 if (e->key != NULL) {
587 printf(
"%s", e->key);
589 printf(
"%p", e->key);
591 printf(
"|len:%zd|val=%ld|->", e->
len, (
long)e->
val);
592 if (e->
next == NULL) {
600 printf(
"%s", e->key);
602 printf(
"|len:%zd|val=%ld|->", e->
len, (
long)e->
val);
603 if (e->
next == NULL) {
611 printf(
"The total number of keys =%d\n", j);
625 for (i = 0; i < h->
size; i++) {
628 if (e->key != NULL) {
632 for (e = e->next; e; e = e->next) {
663 if (itor->
ent == NULL) {
665 && itor->
ht->table[itor->
idx].key == NULL)
674 itor->
ent = itor->
ht->table + itor->
idx;
697 for (i = 0; i < h->
size; i++) {
698 for (e = h->table[i].
next; e; e = e2) {
hash_entry_t * ent
Current entry in that table.
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.
int32 inuse
Primary hash table size, (is a prime#); NOTE: This is the number of primary entries ALLOCATED,...
size_t idx
Index of next bucket to search.
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,...
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.
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_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,...
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.
SPHINXBASE_EXPORT void hash_table_empty(hash_table_t *h)
Delete all entries from a hash_table.
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.
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,...
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.
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 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 node in a generic list.
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 ckd_free(void *ptr)
Test and free a 1-D array.
SPHINXBASE_EXPORT hash_iter_t * hash_table_iter_next(hash_iter_t *itor)
Get the next key-value pair in iteration.
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.
Implementation of logging routines.
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...
Locale-independent implementation of case swapping operation.
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(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(hash_table_t *h)
Start iterating over key-value pairs in a hash table.
int32 size
Primary hash table, excluding entries that collide.
#define UPPER_CASE(c)
Return upper case form for c.
hash_table_t * ht
Hash table we are iterating over.
size_t len
Key string, NULL if this is an empty slot.
Sphinx's memory allocation/deallocation routines.
SPHINXBASE_EXPORT void hash_table_display(hash_table_t *h, int32 showkey)
Display a hash-with-chaining representation on the screen.
#define ckd_calloc(n, sz)
Macros to simplify the use of above functions.
int32 nocase
Number of valid entries in the table.
Hash table implementation.
#define E_WARN(...)
Print warning message to error log.