diff options
author | Steve Bennett <steveb@workware.net.au> | 2021-12-13 16:43:06 +1000 |
---|---|---|
committer | Steve Bennett <steveb@workware.net.au> | 2021-12-13 21:04:18 +1000 |
commit | 24b234543c7322d2dd20339b45367fa3f4c53495 (patch) | |
tree | b3353c74bbd4104442438c00ebf84573da1a1b98 | |
parent | ececa1d3b24dc4298b831675f597a4a84a14e69a (diff) | |
download | jimtcl-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.c | 15 | ||||
-rw-r--r-- | tests/dict2.test | 13 |
2 files changed, 23 insertions, 5 deletions
@@ -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 |