45 uint32_t i, end, counter;
49 end = (uint32_t)1<<(t->logsize);
51 printf(
"error: end %lu apos %lu\n", end, t->apos);
56 for (h=t->table[t->apos]; h && h != t->ipos; h = h->next)
59 printf(
"error:ipos not in apos, apos is %lu\n", t->apos);
64 for (counter=0, i=0; i<end; ++i)
65 for (h=t->table[i]; h; h=h->next)
67 if (counter != t->count)
68 printf(
"error: counter %lu t->count %lu\n", counter, t->count);
82 register uint32_t newsize = (uint32_t)1<<(++t->logsize);
83 register uint32_t newmask = newsize-1;
85 register hitem **oldtab = t->table;
89 for (i=0; i<newsize; ++i) newtab[i] = (
hitem *)0;
94 for (i=newsize>>1; i--;)
96 register hitem *
this, *that;
97 for (
this = oldtab[i];
this;)
99 register hitem **newplace;
102 newplace = &newtab[(that->hval & newmask)];
103 that->next = *newplace;
112 free((
char *)oldtab);
122 len = ((uint32_t)1<<logsize);
123 t->table = (
hitem **)malloc(
sizeof(
hitem *)*(uint32_t)len);
124 for (i=0; i<len; ++i) t->table[i] = (
hitem *)0;
125 t->logsize = logsize;
128 t->apos = (uint32_t)0;
129 t->ipos = (
hitem *)0;
130 t->space = remkroot(
sizeof(
hitem));
140 free((
char *)t->table);
156 uint32_t x = lookup(key,keyl,0);
158 for (h = t->table[y=(x&t->mask)]; h; h = h->next)
160 if ((x == h->hval) &&
162 !memcmp(key, h->key, keyl))
182 register hitem *h,**hp;
183 register uint32_t y, x = lookup(key,keyl,0);
186 for (h = t->table[(y=(x&t->mask))]; h; h = h->next)
188 if ((x == h->hval) &&
190 !memcmp(key, h->key, keyl))
199 h = (
hitem *)renew(t->space);
202 if (++t->count > (uint32_t)1<<(t->logsize))
234 if (!(h = t->ipos))
return false;
237 for (ip = &t->table[t->apos]; *ip != h; ip = &(*ip)->next)
243 if (!(t->ipos = h->next)) hnbucket(t);
261 return (t->ipos != (
hitem *)0);
273 uint32_t oldapos = t->apos;
274 uint32_t end = (uint32_t)1<<(t->logsize);
278 for (i=oldapos+1; i<end; ++i)
280 if (t->table[i&t->mask])
283 t->ipos = t->table[i];
289 for (i=0; i<=oldapos; ++i)
294 t->ipos = t->table[i];
312 for (i=0; i<=t->mask; ++i)
314 for (h=t->table[i], j=0; h; ++j, h=h->next)
316 for (walk=stat; walk && (walk->keyl != j); walk=walk->next)
324 walk = (
hitem *)renew(t->space);
327 if (!stat || stat->keyl > j) {walk->next=stat; stat=walk;}
331 walk2->next && (walk2->next->keyl<j);
334 walk->next = walk2->next;
341 for (walk=stat; walk; walk=walk->next)
343 total+=(double)walk->hval*(
double)walk->keyl*(double)walk->keyl;
345 if (t->count) total /= (double)t->count;
346 else total = (double)0;
350 for (walk=stat; walk; walk=walk->next)
352 printf(
"items %ld: %ld buckets\n", walk->keyl, walk->hval);
354 printf(
"\nbuckets: %lu items: %ld existing: %g\n\n",
355 ((uint32_t)1<<t->logsize), t->count, total);
361 redel(t->space, stat);