summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2015-08-24 11:38:32 -0700
committerOri Bernstein <ori@eigenstate.org>2015-08-24 11:38:32 -0700
commit7f071340643feb6c796f39d5a7acd160b1f6f7c3 (patch)
tree84e353e6dde7659a811f763da554103f3f7d740a
parent33241b151a0073b639892a6891f84bce94db2ccc (diff)
downloadmc-7f071340643feb6c796f39d5a7acd160b1f6f7c3.tar.gz
Actually fix the hash table implementation.
-rw-r--r--parse/htab.c14
-rw-r--r--parse/parse.h1
2 files changed, 11 insertions, 4 deletions
diff --git a/parse/htab.c b/parse/htab.c
index 8b69584..49bed75 100644
--- a/parse/htab.c
+++ b/parse/htab.c
@@ -19,6 +19,7 @@ Htab *mkht(ulong (*hash)(void *key), int (*cmp)(void *k1, void *k2))
ht = xalloc(sizeof(Htab));
ht->nelt = 0;
+ ht->ndead = 0;
ht->sz = Initsz;
ht->hash = hash;
ht->cmp = cmp;
@@ -74,6 +75,7 @@ static void grow(Htab *ht, int sz)
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,12 +117,16 @@ int htput(Htab *ht, void *k, void *v)
}
ht->nelt++;
conflicted:
+ if (ht->dead[i])
+ ht->ndead--;
ht->hashes[i] = h;
ht->keys[i] = k;
ht->vals[i] = v;
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 @@ static ssize_t htidx(Htab *ht, void *k)
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 @@ void htdel(Htab *ht, void *k)
i = htidx(ht, k);
if (i < 0)
return;
+ if (!ht->dead[i])
+ ht->ndead++;
ht->dead[i] = 1;
ht->nelt--;
}
diff --git a/parse/parse.h b/parse/parse.h
index 129ecab..2765bda 100644
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -105,6 +105,7 @@ struct Bitset {
struct Htab {
size_t nelt;
+ size_t ndead;
size_t sz;
ulong (*hash)(void *k);
int (*cmp)(void *a, void *b);