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 <steveb@workware.net.au>

1 files changed, 24 insertions, 0 deletions

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