summaryrefslogtreecommitdiff
path: root/libstd/htab.myr
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2014-09-06 21:37:09 -0400
committerOri Bernstein <ori@eigenstate.org>2014-09-06 21:37:09 -0400
commitea38cf38273bcb1c0925393168574e398cc8ae8c (patch)
treebb8c3921c6ac43f27c8107450407959858d8a514 /libstd/htab.myr
parent4fa7514cc3af92e33262bde7860239d5e65ebbe2 (diff)
downloadmc-ea38cf38273bcb1c0925393168574e398cc8ae8c.tar.gz
Fix nkeys in hash table replacements
The number of keys should match the number of elements in the hash table. When we replace a live value, we shouldn't increment the number of keys.
Diffstat (limited to 'libstd/htab.myr')
-rw-r--r--libstd/htab.myr18
1 files changed, 12 insertions, 6 deletions
diff --git a/libstd/htab.myr b/libstd/htab.myr
index f4217f7..5c311b1 100644
--- a/libstd/htab.myr
+++ b/libstd/htab.myr
@@ -119,29 +119,35 @@ generic htfree = {ht
generic htput = {ht, k, v
var i, di
var h
- var done
+ var neltincr
di = 0
h = hash(ht, k)
i = h & (ht.keys.len - 1)
- done = false
- while ht.hashes[i] != 0 && !ht.dead[i] && !done
+ neltincr = 1
+ while ht.hashes[i] != 0 && !ht.dead[i]
/*
second insertion just overwrites first.
nb: comparing keys for dead values is bad.
*/
- if ht.hashes[i] == h && (ht.dead[i] || ht.eq(ht.keys[i], k))
- done = true
+ if ht.hashes[i] == h
+ if ht.dead[i]
+ break
+ /* replacing a key shouldn't grow the element count */
+ elif ht.eq(ht.keys[i], k)
+ neltincr = 0
+ break
+ ;;
else
di++
i = (h + di) & (ht.keys.len - 1)
;;
;;
+ ht.nelt += neltincr
ht.hashes[i] = h
ht.keys[i] = k
ht.vals[i] = v
ht.dead[i] = false
- ht.nelt++
if ht.keys.len < ht.nelt * 2
resize(ht)
;;