diff options
author | Steve Bennett <steveb@workware.net.au> | 2021-12-16 07:29:04 +1000 |
---|---|---|
committer | Steve Bennett <steveb@workware.net.au> | 2021-12-16 08:23:50 +1000 |
commit | 70bdc32d6e4dc1b9239d062cf9e4e70f605f0679 (patch) | |
tree | 95d347fa8a8b3b6e6bec0f73f29e163d03e4187a /jim.h | |
parent | 7a518896462aef645e278e7191bb5af12f0fc25a (diff) | |
download | jimtcl-70bdc32d6e4dc1b9239d062cf9e4e70f605f0679.zip jimtcl-70bdc32d6e4dc1b9239d062cf9e4e70f605f0679.tar.gz jimtcl-70bdc32d6e4dc1b9239d062cf9e4e70f605f0679.tar.bz2 |
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>
Diffstat (limited to 'jim.h')
-rw-r--r-- | jim.h | 1 |
1 files changed, 1 insertions, 0 deletions
@@ -478,6 +478,7 @@ typedef struct Jim_Dict { Jim_Obj **table; /* Table of alternating key, value elements */ int len; /* Number of used elements in table */ int maxLen; /* Allocated length of table */ + unsigned int dummy; /* Number of dummy entries */ } Jim_Dict; /* A command is implemented in C if isproc is 0, otherwise |