aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSteve Bennett <steveb@workware.net.au>2021-12-13 16:43:06 +1000
committerSteve Bennett <steveb@workware.net.au>2021-12-13 21:04:18 +1000
commit24b234543c7322d2dd20339b45367fa3f4c53495 (patch)
treeb3353c74bbd4104442438c00ebf84573da1a1b98
parentececa1d3b24dc4298b831675f597a4a84a14e69a (diff)
downloadjimtcl-24b234543c7322d2dd20339b45367fa3f4c53495.zip
jimtcl-24b234543c7322d2dd20339b45367fa3f4c53495.tar.gz
jimtcl-24b234543c7322d2dd20339b45367fa3f4c53495.tar.bz2
dict: Fix possible duplicate entries when setting
Due to the way hash collisions are managed it is possible to have a sequence where an entry is removed and then another entry is replaced, however the replacement adds an additional entry instead of updating the existing entry. Can be reproduced like this as there is a hash collision between these two keys: dict set d 0,13 X dict set d 8,4 Y dict unset d 0,13 dict set d 8,4 Z Should result in one entry in the dictionary, but instead ends with two. Signed-off-by: Steve Bennett <steveb@workware.net.au>
-rw-r--r--jim.c15
-rw-r--r--tests/dict2.test13
2 files changed, 23 insertions, 5 deletions
diff --git a/jim.c b/jim.c
index adcb9da..d01b147 100644
--- a/jim.c
+++ b/jim.c
@@ -7369,16 +7369,18 @@ static int JimDictHashFind(Jim_Dict *dict, Jim_Obj *keyObjPtr, int op_tvoffset)
unsigned idx = h & dict->sizemask;
int tvoffset = 0;
unsigned peturb = h;
+ unsigned first_removed = ~0;
if (dict->len) {
while ((tvoffset = dict->ht[idx].offset)) {
if (tvoffset == -1) {
/* An entry with offset=-1 is a removed entry
- * we need skip it when searching, but stop when adding.
+ * Need to keep going in case there is a non-removed entry later.
+ * But for adds we prefer to use the first available removed entry
+ * for performance reasons
*/
- if (op_tvoffset == DICT_HASH_ADD) {
- tvoffset = 0;
- break;
+ if (first_removed == ~0) {
+ first_removed = idx;
}
}
else if (dict->ht[idx].hash == h) {
@@ -7405,7 +7407,10 @@ static int JimDictHashFind(Jim_Dict *dict, Jim_Obj *keyObjPtr, int op_tvoffset)
break;
case DICT_HASH_ADD:
if (tvoffset == 0) {
- /* Not found so add it at the end */
+ /* Not found so add it at the the first removed entry, or the end */
+ if (first_removed != ~0) {
+ idx = first_removed;
+ }
dict->ht[idx].offset = dict->len + 1;
dict->ht[idx].hash = h;
}
diff --git a/tests/dict2.test b/tests/dict2.test
index 2a36dc1..99cf605 100644
--- a/tests/dict2.test
+++ b/tests/dict2.test
@@ -1279,5 +1279,18 @@ test dict-23.6 {dict with baddict} -body {
dict with dictbad {}
} -returnCodes error -result {missing value to go with key}
+test dict-24.1 {dict hash collision} {
+ set d {}
+ # 0,13 and 8,4 product a hash collision
+ # add both
+ dict set d 0,13 X
+ dict set d 8,4 Y
+ # Now remove the first and update the second
+ dict unset d 0,13
+ dict set d 8,4 Z
+ # There should be 1 entry, not 2
+ dict size $d
+} 1
+
testreport