From 70bdc32d6e4dc1b9239d062cf9e4e70f605f0679 Mon Sep 17 00:00:00 2001 From: Steve Bennett Date: Thu, 16 Dec 2021 07:29:04 +1000 Subject: dict: consider dummy entries when determining when to expand hash table This issue was caused by the fix in 24b234543c7322d2dd20339b45367fa3f4c53495 Because we used closed hashing for the dict hash table, it is important that the table doesn't get too full, as it gets very inefficient due to hash collisions. When allowing for space, also consider dummy entries that consume slots. If there are too many dummy slots, the hash table is expanded, clearing out the dummy slots. Without this fix it is possible to get unlucky when filling a dictionary and emptying it again (twice) will result all slots become dummy slots and thus no more entries can be added. See REGTEST 54 Signed-off-by: Steve Bennett --- regtest.tcl | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) (limited to 'regtest.tcl') diff --git a/regtest.tcl b/regtest.tcl index 5b7249c..b0cb70b 100644 --- a/regtest.tcl +++ b/regtest.tcl @@ -360,6 +360,30 @@ puts "TEST 52 PASSED" catch {string last foo bar -1} puts "TEST 53 PASSED" +# REGTEST 54 +# dict fills up with dummy entries, infinite loop +set d {} +# These two sets of chars yield different hashes (dict indexes) +set chars1 {a b c d e f g h} +set chars2 {i j k l m n o p} +# Fill and empty the first set +foreach i $chars1 { + dict set d $i 1 + dict unset d $i +} +# Fill and empty the second set +foreach i $chars2 { + dict set d $i 1 + dict unset d $i +} +# Now the dictionary is full of dummy entries and adding an entry will loop forever +alarm 1 +foreach i $chars1 { + dict set d $i 1 +} +alarm 0 +puts "TEST 54 PASSED" + # TAKE THE FOLLOWING puts AS LAST LINE -- cgit v1.1