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);
576 return (
delete(h, hash, key, len));
586 E_INFOCONT(
"Hash with chaining representation of the hash table\n");
588 for (i = 0; i < h->
size; i++) {
590 if (e->key != NULL) {
598 if (e->
next == NULL) {
609 if (e->
next == NULL) {
617 E_INFOCONT(
"The total number of keys =%d\n", j);
631 for (i = 0; i < h->
size; i++) {
634 if (e->key != NULL) {
669 if (itor->
ent == NULL) {
671 && itor->
ht->table[itor->
idx].key == NULL)
680 itor->
ent = itor->
ht->table + itor->
idx;
703 for (i = 0; i < h->
size; i++) {
704 for (e = h->table[i].
next; e; e = e2) {