- TTEntry* const tte = first_entry(key);
- const uint16_t key16 = key >> 48; // Use the high 16 bits as key inside the cluster
-
- for (int i = 0; i < ClusterSize; ++i)
- if (!tte[i].key16 || tte[i].key16 == key16)
- {
- tte[i].genBound8 = uint8_t(generation8 | (tte[i].genBound8 & 0x7)); // Refresh
-
- return found = (bool)tte[i].key16, &tte[i];
- }
-
- // Find an entry to be replaced according to the replacement strategy
- TTEntry* replace = tte;
- for (int i = 1; i < ClusterSize; ++i)
- // Due to our packed storage format for generation and its cyclic
- // nature we add 263 (256 is the modulus plus 7 to keep the unrelated
- // lowest three bits from affecting the result) to calculate the entry
- // age correctly even after generation8 overflows into the next cycle.
- if ( replace->depth8 - ((263 + generation8 - replace->genBound8) & 0xF8)
- > tte[i].depth8 - ((263 + generation8 - tte[i].genBound8) & 0xF8))
- replace = &tte[i];
-
- return found = false, replace;
+ TTEntry* const tte = first_entry(key);
+ const uint16_t key16 = uint16_t(key); // Use the low 16 bits as key inside the cluster
+
+ for (int i = 0; i < ClusterSize; ++i)
+ if (tte[i].key16 == key16 || !tte[i].depth8)
+ {
+ tte[i].genBound8 =
+ uint8_t(generation8 | (tte[i].genBound8 & (GENERATION_DELTA - 1))); // Refresh
+
+ return found = bool(tte[i].depth8), &tte[i];
+ }
+
+ // Find an entry to be replaced according to the replacement strategy
+ TTEntry* replace = tte;
+ for (int i = 1; i < ClusterSize; ++i)
+ // Due to our packed storage format for generation and its cyclic
+ // nature we add GENERATION_CYCLE (256 is the modulus, plus what
+ // is needed to keep the unrelated lowest n bits from affecting
+ // the result) to calculate the entry age correctly even after
+ // generation8 overflows into the next cycle.
+ if (replace->depth8
+ - ((GENERATION_CYCLE + generation8 - replace->genBound8) & GENERATION_MASK)
+ > tte[i].depth8
+ - ((GENERATION_CYCLE + generation8 - tte[i].genBound8) & GENERATION_MASK))
+ replace = &tte[i];
+
+ return found = false, replace;