Safe Haskell	None
Language	Haskell2010

DataFrame.Internal.HashTable

Description

A flat, unboxed, open-addressing (linear-probe) hash table mapping a row's key-hash to a dense group id, re-verifying the real key on every hash hit to reject collisions. Runs in any PrimMonad (ST for grouping, IO per worker).

Synopsis

data HashTable s = HashTable {
- htHash :: !(MVector s Int)
- htGroup :: !(MVector s Int)
- htRep :: !(MVector s Int)
- htMask :: !Int
}
newHashTable :: PrimMonad m => Int -> m (HashTable (PrimState m))
htInsert :: PrimMonad m => HashTable (PrimState m) -> (Int -> Int -> Bool) -> Int -> Int -> Int -> m (Int, Bool)
nextPow2Above :: Int -> Int

Documentation

data HashTable s Source #

An open-addressing linear-probe table. htMask is capacity - 1 (capacity is a power of two) and maps a hash to its home slot.

Constructors

HashTable
Fields htHash :: !(MVector s Int) htGroup :: !(MVector s Int) htRep :: !(MVector s Int) htMask :: !Int

newHashTable :: PrimMonad m => Int -> m (HashTable (PrimState m)) Source #

Allocate an empty table able to hold up to n distinct groups while keeping the load factor under ~0.5 (capacity = nextPow2Above (2*n)). All group slots start empty (-1).

htInsert Source #

Arguments

:: PrimMonad m
=> HashTable (PrimState m)
-> (Int -> Int -> Bool)	`eqRow a b`: do rows `a` and `b` have equal key columns?
-> Int	Next dense group id to assign if this row starts a new group.
-> Int	Row index being inserted.
-> Int	Precomputed hash of the row's key.
-> m (Int, Bool)

Look up row (with precomputed hash) and return its dense group id: an empty slot starts a new group via nextGroup, a stored-hash match is re-verified with eqRow before reuse. The Bool is True when a new group was created.

nextPow2Above :: Int -> Int Source #

Smallest power of two strictly greater than n, at least 2. Sizes the table so the load factor stays below ~0.5 even when every row is a distinct group.