shithub: mc

Info  •  Files  •  Log  •  Branches

Actually fix the hash table implementation.

--- a/parse/htab.c

+++ b/parse/htab.c

@@ -19,6 +19,7 @@

     ht = xalloc(sizeof(Htab));

     ht->nelt = 0;

+    ht->ndead = 0;

     ht->sz = Initsz;

     ht->hash = hash;

     ht->cmp = cmp;

@@ -74,6 +75,7 @@

     oldsz = ht->sz;

     ht->nelt = 0;

+    ht->ndead = 0;

     ht->sz = sz;

     ht->keys = zalloc(sz*sizeof(void*));

     ht->vals = zalloc(sz*sizeof(void*));

@@ -115,6 +117,8 @@

     }

     ht->nelt++;

 conflicted:

+    if (ht->dead[i])

+        ht->ndead--;

     ht->hashes[i] = h;

     ht->keys[i] = k;

     ht->vals[i] = v;

@@ -121,6 +125,8 @@

     ht->dead[i] = 0;

     if (ht->sz < ht->nelt*2)

         grow(ht, ht->sz*2);

+    if (ht->sz < ht->ndead*4)

+        grow(ht, ht->sz);

     return 1;

 }

@@ -135,16 +141,14 @@

     di = 0;

     h = hash(ht, k);

     i = h & (ht->sz - 1);

-    while (ht->hashes[i] && ht->hashes[i] != h) {

+    while (ht->hashes[i] && !ht->dead[i] && ht->hashes[i] != h) {

 searchmore:

         di++;

         i = (h + di) & (ht->sz - 1);

     }

-    if (ht->dead[i])

-        goto searchmore;

     if (!ht->hashes[i]) 

         return -1;

-    if (!ht->cmp(ht->keys[i], k))

+    if (!ht->cmp(ht->keys[i], k) || (ht->hashes[i] == h && ht->dead[i]))

         goto searchmore; /* collision */

     return i;

 }

@@ -172,6 +176,8 @@

     i = htidx(ht, k);

     if (i < 0)

         return;

+    if (!ht->dead[i])

+        ht->ndead++;

     ht->dead[i] = 1;

     ht->nelt--;

 }

--- a/parse/parse.h

+++ b/parse/parse.h

@@ -105,6 +105,7 @@

 struct Htab {

     size_t nelt;

+    size_t ndead;

     size_t sz;

     ulong (*hash)(void *k);

     int (*cmp)(void *a, void *b);