93#pragma warning (disable: 4018)
104prime_sieve(int32 max)
113 for (pp = p + p; pp <= max; pp += p)
115 for (++p; (p <= max) && notprime[p]; p++);
128const 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,
144prime_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);
216makekey(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++) {
278lookup(
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;
373enter(
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;
418delete(
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) {
Locale-independent implementation of case swapping operation.
#define UPPER_CASE(c)
Return upper case form for c.
Sphinx's memory allocation/deallocation routines.
SPHINXBASE_EXPORT void ckd_free(void *ptr)
Test and free a 1-D array.
#define ckd_calloc(n, sz)
Macros to simplify the use of above functions.
Implementation of logging routines.
#define E_WARN(...)
Print warning message to error log.
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...
Hash table implementation.
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...
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_display(hash_table_t *h, int32 showkey)
Display a hash-with-chaining representation on the screen.
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 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_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 void * hash_table_delete(hash_table_t *h, const char *key)
Delete an entry with given key and associated value to hash table h.
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 void hash_table_iter_free(hash_iter_t *itor)
Delete an unfinished iterator.
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,...
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 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_empty(hash_table_t *h)
Delete all entries from a hash_table.
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 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_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.
SPHINXBASE_EXPORT hash_table_t * hash_table_new(int32 size, int32 casearg)
Allocate a new hash table for a given expected size.
A node in a generic list.
A note by ARCHAN at 20050510: Technically what we use is so-called "hash table with buckets" which is...
void * val
Key-length; the key string does not have to be a C-style NULL terminated string; it can have arbitrar...
struct hash_entry_s * next
Value associated with above key.
size_t len
Key string, NULL if this is an empty slot.
hash_table_t * ht
Hash table we are iterating over.
hash_entry_t * ent
Current entry in that table.
size_t idx
Index of next bucket to search.
int32 nocase
Number of valid entries in the table.
int32 size
Primary hash table, excluding entries that collide.
int32 inuse
Primary hash table size, (is a prime#); NOTE: This is the number of primary entries ALLOCATED,...