Fix infinite loop when emplace() is called with no empty slots

[hugoam]

trafficstars

Hello

We encountered this, which I believe is a bug, in our usage of ExcaliburHash

Basically, if a HashMap has only Tombstones left, but no Empty slots anymore, emplace() will loop infinitely

My attempt to fix, with a very rough understanding of linear probing and tombstones, is that once we've completed a loop over all elements (reached startItem) we can safely insert in the first encountered tombstone as we are sure there are no duplicate keys

[codecov-commenter]

:warning: Please install the to ensure uploads and comments are reliably processed by Codecov.

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 100.00%. Comparing base (b99119a) to head (fb159c4).

:exclamation: Your organization needs to install the Codecov GitHub app to enable full functionality.

Additional details and impacted files

@@            Coverage Diff            @@
##              main       #14   +/-   ##
=========================================
  Coverage   100.00%   100.00%           
=========================================
  Files            6         6           
  Lines         1325      1326    +1     
=========================================
+ Hits          1325      1326    +1     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[SergeyMakeev]

I fixed the issue with the infinite loop by using a slightly different approach: https://github.com/SergeyMakeev/ExcaliburHash/commit/ae73086e47aa409c2a68c1a571703798e5e83cfc

Now, in emplace(), we take into account both occupied slots and tombstone slots. This prevents "poisoning" the hash_map and helps avoid the infinite loop issue, improving performance in general.