Copyright | (c) Chris Coffey 2018 |
---|---|
License | MIT |
Maintainer | chris@foldl.io |
Stability | experimental |
Safe Haskell | None |
Language | Haskell2010 |
This is the internal API and implemntation of CuckooFilter
. It is subject to
change at any time and should not be used. Instead, use the exports from CuckooFilter
.
Synopsis
- newtype Size = Size Natural
- makeSize :: Natural -> Maybe Size
- class Monad m => CuckooFilter filt m where
- initialize :: Size -> m (filt a)
- bucketCount :: filt a -> m Natural
- writeBucket :: Int -> Bucket -> filt a -> m (filt a)
- readBucket :: Int -> filt a -> m Bucket
- newtype FingerPrint = FP Word8
- emptyFP :: FingerPrint
- makeFingerprint :: Hashable a => a -> FingerPrint
- newtype Bucket = B Word32
- emptyBucket :: Bucket
- class Index a where
- newtype IndexA = IA Word32
- newtype IndexB = IB Word32
- replaceInBucket :: FingerPrint -> (FingerPrint -> Bucket -> (Bool, Bool, Bool, Bool)) -> Bucket -> (FingerPrint, Bucket)
- insertBucket :: FingerPrint -> Bucket -> Maybe Bucket
- primaryIndex :: Hashable a => a -> Natural -> IndexA
- secondaryIndex :: FingerPrint -> Natural -> IndexA -> IndexB
- kickedSecondaryIndex :: FingerPrint -> Natural -> IndexB -> IndexB
- getCell :: Bucket -> Natural -> FingerPrint
- setCell :: Bucket -> Natural -> FingerPrint -> Bucket
Constructing a Cuckoo Filter
A non-zero natural number. Generally this is a power of two, although there's no hard requirement for that given the current implementation.
class Monad m => CuckooFilter filt m where Source #
A low-level interface for working with cuckoo filter storage.
initialize :: Size -> m (filt a) Source #
Create a new cuckoo filter of the specified size
bucketCount :: filt a -> m Natural Source #
Return the number of buckets contained in the filter. This is distinct from the total size of the filter (size /4)
writeBucket :: Int -> Bucket -> filt a -> m (filt a) Source #
Write the new contents of a bucket to the storage
readBucket :: Int -> filt a -> m Bucket Source #
Read the contents of a bucket from the storage
Instances
CuckooFilter MFilter IO Source # | |
Monad m => CuckooFilter Filter m Source # | |
Defined in Data.CuckooFilter.Pure |
Fingerprints
newtype FingerPrint Source #
A FingerPrint is an 8 bit hash of a value
Instances
makeFingerprint :: Hashable a => a -> FingerPrint Source #
hash a % 255. Fingerprints are 8 bits each, and completely opaque to the lookup algorithm.
Working with indices
A Bucket is a statically sized list of four FingerPrints.
emptyBucket :: Bucket Source #
An Index represents the keys into buckets
Instances
Eq IndexA Source # | |
Ord IndexA Source # | |
Show IndexA Source # | |
Generic IndexA Source # | |
Hashable IndexA Source # | |
Defined in Data.CuckooFilter.Internal | |
ToJSON IndexA Source # | |
Defined in Data.CuckooFilter.Internal | |
FromJSON IndexA Source # | |
Serialize IndexA Source # | |
Index IndexA Source # | |
type Rep IndexA Source # | |
Defined in Data.CuckooFilter.Internal |
Instances
Eq IndexB Source # | |
Ord IndexB Source # | |
Show IndexB Source # | |
Generic IndexB Source # | |
Hashable IndexB Source # | |
Defined in Data.CuckooFilter.Internal | |
ToJSON IndexB Source # | |
Defined in Data.CuckooFilter.Internal | |
FromJSON IndexB Source # | |
Serialize IndexB Source # | |
Index IndexB Source # | |
type Rep IndexB Source # | |
Defined in Data.CuckooFilter.Internal |
:: FingerPrint | |
-> (FingerPrint -> Bucket -> (Bool, Bool, Bool, Bool)) | Bucket predicate |
-> Bucket | |
-> (FingerPrint, Bucket) |
insertBucket :: FingerPrint -> Bucket -> Maybe Bucket Source #
secondaryIndex :: FingerPrint -> Natural -> IndexA -> IndexB Source #
(indexA xor
hash fp) % numBuckets
kickedSecondaryIndex :: FingerPrint -> Natural -> IndexB -> IndexB Source #