{-# OPTIONS_HADDOCK prune #-}
-- | Note that what is referred to as a \"nonce\" in this library may be
-- referred to by some as a \"salt\".
module Data.PerfectHash.Lookup (
LookupTable (LookupTable)
, nonces
, values
, size
, encodeDirectEntry
, lookupPerfect
) where
import Data.Vector.Unboxed (Vector, (!))
import qualified Data.Vector.Unboxed as Vector
import qualified Data.PerfectHash.Hashing as Hashing
-- | Inputs for the lookup function.
--
-- There are two arrays used in successive stages of the lookup.
-- In this implementation, both arrays are the same length.
data LookupTable a = LookupTable {
nonces :: Vector Int
-- ^ This is the intermediate lookup table.
--
-- In the lookup process, the key's hash is computed first with a nonce of
-- zero to obtain an index into this array.
--
-- If the value at this index is negative, it is (after negating and
-- subtracting one) a direct index into the 'values' array.
-- Otherwise, the value shall be used as a nonce in a second application of
-- the hashing function to compute the index into the 'values' array.
--
-- See the documentation of 'lookupPerfect' for details.
, values :: Vector a
-- ^ An array of values of arbitrary type.
--
-- The objective of the perfect hash is to efficiently obtain an index into
-- this array, given the associated key for the value at that index.
}
size :: Vector.Unbox a => LookupTable a -> Int
size = Vector.length . values
encodeDirectEntry = subtract 1 . negate
-- | For embedded applications, this function would usually be re-implemented
-- in C code.
--
-- == Algorithm description
-- The lookup procedure is three steps:
--
-- 1. Compute the 'Hashing.hash' (with a nonce of zero) of the "key", modulo
-- the length of the 'values' array.
-- 2. Use the resulting value as an index into the 'nonces' array. The value
-- found there represents either a direct index into the 'values' array
-- or a nonce for a second round of hashing.
--
-- * If negative, it is the former. Negate it (to obtain a positive
-- value) and subtract one to obtain the actual index.
-- * Otherwise, re-compute the hash of the key, using this
-- value instead of zero as the nonce. Again, compute the modulus with
-- respect to the length of the 'values' array.
--
-- 3. Use the result of (2) as the index into the 'values' array.
lookupPerfect :: (Foldable f, Hashing.ToNumeric a, Vector.Unbox b) =>
LookupTable b
-> f a
-> b
lookupPerfect lookup_table key =
values lookup_table ! v_key
where
table_size = size lookup_table
nonce_index = Hashing.hashToSlot 0 key table_size
nonce = nonces lookup_table ! nonce_index
-- Negative value indicates that we don't need extra lookup layer
v_key = if nonce < 0
then encodeDirectEntry nonce
else Hashing.hashToSlot nonce key table_size