triangularProbeFromIndexIncludingHoles

Search for a key in haystack matching hit predicate hitPred and hole predicate holePred starting at index in steps of triangular numbers, 0,1,3,6,10,15,21, ... .

If assumeNonFullHaystack is true it is assumed that at least one element in haystack matches pred, thereby enabling sentinel-based probing. Such probing doesn't require in-loop range checking via `indexIncrement != haystack.length` and can be made faster.

size_t
triangularProbeFromIndexIncludingHoles
(
alias hitPred
alias holePred
bool assumeNonFullHaystack = false
T
)
(
const scope T[] haystack
,
size_t index
,
ref size_t holeIndex
)
if (
(
is(typeof(unaryFun!hitPred(T.init))) ||
is(typeof(binaryFun!hitPred(size_t.init, T.init)))
)
||
(
is(typeof(unaryFun!holePred(T.init))) ||
is(typeof(binaryFun!holePred(size_t.init, T.init)))
)
)

Return Value

Type: size_t

index into haystack upon hit, haystack.length upon miss.

Note: haystack.length must be a power of two (or 1 or zero).

See Also

Meta