Of course the reason why SF wants to keep the last entry empty is exactly to avoid having to wrap the index.
syzygy wrote: ↑Sun Jun 03, 2018 5:36 pm
One can then pick a size for which add_to_hash() happens to never exceed the last entry, so you don't even need to do any wrapping.
It would be sufficient to make sure that during insertion of all 7-men keys the index does not exceed the size of the table.
If the user has the complete 7-men set, any probe of the hash table will be successful, so there is no need to have an empty entry at the end of the table. This assumes that the TBs are probed only for positions with 7 men or less.
If the user does not have the complete 7-men set, not all probes will be successful, but there is still no chance of a boundary overflow since the probe will stop at the empty entry into which add_to_hash() would have inserted the key. Since we know that add_to_hash() does not overflow, everything is fine.
To play it safe, one could make the hash table array 1 entry larger. Then probes of arbitrary keys are guaranteed to stay within the allocated array. This could also solve your current problem:
Code: Select all
Entry hashTable[Size + N];
...
// Ensure last element is empty to avoid overflow when looking up
for ( ; entry - hashTable < Size + N - 1; ++entry)
if (std::get<KEY>(*entry) == key || !std::get<WDL>(*entry)) {
*entry = std::make_tuple(key, wdl, dtz);
return;
}
Try with N=1. If that stops working, try N = 2, etc.
So it is in fact always easy to avoid the need for the wrapping operation.
