Copyright	(c) Chris Coffey 2018
License	MIT
Maintainer	chris@foldl.io
Stability	experimental
Safe Haskell	None
Language	Haskell2010

Data.CuckooFilter.Internal

Contents

Constructing a Cuckoo Filter
Fingerprints
Working with indices
- Bucket Cells,

Description

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
data Filter a = F {
- buckets :: IntMap Bucket
- numBuckets :: !Natural
- size :: !Size
}
empty :: Size -> Filter a
newtype FingerPrint = FP Word8
emptyFP :: FingerPrint
makeFingerprint :: Hashable a => a -> FingerPrint
newtype Bucket = B Word32
emptyBucket :: Bucket
class Index a where
- toIndex :: Natural -> a -> Int
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

newtype Size Source #

A non-zero natural number. Generally this is a power of two, although there's no hard requirement for that given the current implementation.

Constructors

Size Natural

Instances

Eq Size Source #
Instance details Defined in Data.CuckooFilter.Internal Methods (==) :: Size -> Size -> Bool # (/=) :: Size -> Size -> Bool #
Ord Size Source #
Instance details Defined in Data.CuckooFilter.Internal Methods compare :: Size -> Size -> Ordering # (<) :: Size -> Size -> Bool # (<=) :: Size -> Size -> Bool # (>) :: Size -> Size -> Bool # (>=) :: Size -> Size -> Bool # max :: Size -> Size -> Size # min :: Size -> Size -> Size #
Show Size Source #
Instance details Defined in Data.CuckooFilter.Internal Methods showsPrec :: Int -> Size -> ShowS # show :: Size -> String # showList :: [Size] -> ShowS #
Generic Size Source #
Instance details Defined in Data.CuckooFilter.Internal Associated Types type Rep Size :: Type -> Type # Methods from :: Size -> Rep Size x # to :: Rep Size x -> Size #
ToJSON Size Source #
Instance details Defined in Data.CuckooFilter.Internal Methods toJSON :: Size -> Value # toEncoding :: Size -> Encoding # toJSONList :: [Size] -> Value # toEncodingList :: [Size] -> Encoding #
FromJSON Size Source #
Instance details Defined in Data.CuckooFilter.Internal Methods parseJSON :: Value -> Parser Size # parseJSONList :: Value -> Parser [Size] #
Serialize Size Source #
Instance details Defined in Data.CuckooFilter.Internal Methods put :: Putter Size # get :: Get Size #
type Rep Size Source #
Instance details Defined in Data.CuckooFilter.Internal type Rep Size = D1 (MetaData "Size" "Data.CuckooFilter.Internal" "cuckoo-filter-0.1.0.2-8NKAT7gypEH8pARQbiuTP3" True) (C1 (MetaCons "Size" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Natural)))

makeSize :: Natural -> Maybe Size Source #

Safely make a Size or fail if a 0 is provided.

data Filter a Source #

A Cuckoo Filter with a fixed size. The current implementation uses 8 bit fingerprints and 4 element buckets.

Constructors

F
Fields buckets :: IntMap Bucket numBuckets :: !Natural size :: !Size

Instances

Eq (Filter a) Source #
Instance details Defined in Data.CuckooFilter.Internal Methods (==) :: Filter a -> Filter a -> Bool # (/=) :: Filter a -> Filter a -> Bool #
Show (Filter a) Source #
Instance details Defined in Data.CuckooFilter.Internal Methods showsPrec :: Int -> Filter a -> ShowS # show :: Filter a -> String # showList :: [Filter a] -> ShowS #
Generic (Filter a) Source #
Instance details Defined in Data.CuckooFilter.Internal Associated Types type Rep (Filter a) :: Type -> Type # Methods from :: Filter a -> Rep (Filter a) x # to :: Rep (Filter a) x -> Filter a #
ToJSON (Filter a) Source #
Instance details Defined in Data.CuckooFilter.Internal Methods toJSON :: Filter a -> Value # toEncoding :: Filter a -> Encoding # toJSONList :: [Filter a] -> Value # toEncodingList :: [Filter a] -> Encoding #
FromJSON (Filter a) Source #
Instance details Defined in Data.CuckooFilter.Internal Methods parseJSON :: Value -> Parser (Filter a) # parseJSONList :: Value -> Parser [Filter a] #
Serialize (Filter a) Source #
Instance details Defined in Data.CuckooFilter.Internal Methods put :: Putter (Filter a) # get :: Get (Filter a) #
type Rep (Filter a) Source #
Instance details Defined in Data.CuckooFilter.Internal type Rep (Filter a) = D1 (MetaData "Filter" "Data.CuckooFilter.Internal" "cuckoo-filter-0.1.0.2-8NKAT7gypEH8pARQbiuTP3" False) (C1 (MetaCons "F" PrefixI True) (S1 (MetaSel (Just "buckets") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (IntMap Bucket)) :: (S1 (MetaSel (Just "numBuckets") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Natural) :: S1 (MetaSel (Just "size") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Size))))

empty Source #

Arguments

:: Size	The initial size of the filter
-> Filter a

Creates a new & empty Filter of size s

Fingerprints

newtype FingerPrint Source #

A FingerPrint is an 8 bit hash of a value

Constructors

FP Word8

Instances

Eq FingerPrint Source #
Instance details Defined in Data.CuckooFilter.Internal Methods (==) :: FingerPrint -> FingerPrint -> Bool # (/=) :: FingerPrint -> FingerPrint -> Bool #
Ord FingerPrint Source #
Instance details Defined in Data.CuckooFilter.Internal Methods compare :: FingerPrint -> FingerPrint -> Ordering # (<) :: FingerPrint -> FingerPrint -> Bool # (<=) :: FingerPrint -> FingerPrint -> Bool # (>) :: FingerPrint -> FingerPrint -> Bool # (>=) :: FingerPrint -> FingerPrint -> Bool # max :: FingerPrint -> FingerPrint -> FingerPrint # min :: FingerPrint -> FingerPrint -> FingerPrint #
Show FingerPrint Source #
Instance details Defined in Data.CuckooFilter.Internal Methods showsPrec :: Int -> FingerPrint -> ShowS # show :: FingerPrint -> String # showList :: [FingerPrint] -> ShowS #
Generic FingerPrint Source #
Instance details Defined in Data.CuckooFilter.Internal Associated Types type Rep FingerPrint :: Type -> Type # Methods from :: FingerPrint -> Rep FingerPrint x # to :: Rep FingerPrint x -> FingerPrint #
Hashable FingerPrint Source #
Instance details Defined in Data.CuckooFilter.Internal Methods hashWithSalt :: Int -> FingerPrint -> Int # hash :: FingerPrint -> Int #
ToJSON FingerPrint Source #
Instance details Defined in Data.CuckooFilter.Internal Methods toJSON :: FingerPrint -> Value # toEncoding :: FingerPrint -> Encoding # toJSONList :: [FingerPrint] -> Value # toEncodingList :: [FingerPrint] -> Encoding #
FromJSON FingerPrint Source #
Instance details Defined in Data.CuckooFilter.Internal Methods parseJSON :: Value -> Parser FingerPrint # parseJSONList :: Value -> Parser [FingerPrint] #
Serialize FingerPrint Source #
Instance details Defined in Data.CuckooFilter.Internal Methods put :: Putter FingerPrint # get :: Get FingerPrint #
type Rep FingerPrint Source #
Instance details Defined in Data.CuckooFilter.Internal type Rep FingerPrint = D1 (MetaData "FingerPrint" "Data.CuckooFilter.Internal" "cuckoo-filter-0.1.0.2-8NKAT7gypEH8pARQbiuTP3" True) (C1 (MetaCons "FP" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word8)))

emptyFP :: FingerPrint Source #

makeFingerprint :: Hashable a => a -> FingerPrint Source #

hash a % 255. Fingerprints are 8 bits each, and completely opaque to the lookup algorithm.

Working with indices

newtype Bucket Source #

A Bucket is a statically sized list of four FingerPrints.

Constructors

B Word32

Instances

Eq Bucket Source #
Instance details Defined in Data.CuckooFilter.Internal Methods (==) :: Bucket -> Bucket -> Bool # (/=) :: Bucket -> Bucket -> Bool #
Ord Bucket Source #
Instance details Defined in Data.CuckooFilter.Internal Methods compare :: Bucket -> Bucket -> Ordering # (<) :: Bucket -> Bucket -> Bool # (<=) :: Bucket -> Bucket -> Bool # (>) :: Bucket -> Bucket -> Bool # (>=) :: Bucket -> Bucket -> Bool # max :: Bucket -> Bucket -> Bucket # min :: Bucket -> Bucket -> Bucket #
Show Bucket Source #
Instance details Defined in Data.CuckooFilter.Internal Methods showsPrec :: Int -> Bucket -> ShowS # show :: Bucket -> String # showList :: [Bucket] -> ShowS #
Generic Bucket Source #
Instance details Defined in Data.CuckooFilter.Internal Associated Types type Rep Bucket :: Type -> Type # Methods from :: Bucket -> Rep Bucket x # to :: Rep Bucket x -> Bucket #
ToJSON Bucket Source #
Instance details Defined in Data.CuckooFilter.Internal Methods toJSON :: Bucket -> Value # toEncoding :: Bucket -> Encoding # toJSONList :: [Bucket] -> Value # toEncodingList :: [Bucket] -> Encoding #
FromJSON Bucket Source #
Instance details Defined in Data.CuckooFilter.Internal Methods parseJSON :: Value -> Parser Bucket # parseJSONList :: Value -> Parser [Bucket] #
Serialize Bucket Source #
Instance details Defined in Data.CuckooFilter.Internal Methods put :: Putter Bucket # get :: Get Bucket #
type Rep Bucket Source #
Instance details Defined in Data.CuckooFilter.Internal type Rep Bucket = D1 (MetaData "Bucket" "Data.CuckooFilter.Internal" "cuckoo-filter-0.1.0.2-8NKAT7gypEH8pARQbiuTP3" True) (C1 (MetaCons "B" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word32)))

emptyBucket :: Bucket Source #

class Index a where Source #

Methods

toIndex :: Natural -> a -> Int Source #

Instances

Index IndexB Source #
Instance details Defined in Data.CuckooFilter.Internal Methods toIndex :: Natural -> IndexB -> Int Source #
Index IndexA Source #
Instance details Defined in Data.CuckooFilter.Internal Methods toIndex :: Natural -> IndexA -> Int Source #

newtype IndexA Source #

An Index represents the keys into buckets

Constructors

IA Word32

Instances

Eq IndexA Source #
Instance details Defined in Data.CuckooFilter.Internal Methods (==) :: IndexA -> IndexA -> Bool # (/=) :: IndexA -> IndexA -> Bool #
Ord IndexA Source #
Instance details Defined in Data.CuckooFilter.Internal Methods compare :: IndexA -> IndexA -> Ordering # (<) :: IndexA -> IndexA -> Bool # (<=) :: IndexA -> IndexA -> Bool # (>) :: IndexA -> IndexA -> Bool # (>=) :: IndexA -> IndexA -> Bool # max :: IndexA -> IndexA -> IndexA # min :: IndexA -> IndexA -> IndexA #
Show IndexA Source #
Instance details Defined in Data.CuckooFilter.Internal Methods showsPrec :: Int -> IndexA -> ShowS # show :: IndexA -> String # showList :: [IndexA] -> ShowS #
Generic IndexA Source #
Instance details Defined in Data.CuckooFilter.Internal Associated Types type Rep IndexA :: Type -> Type # Methods from :: IndexA -> Rep IndexA x # to :: Rep IndexA x -> IndexA #
Hashable IndexA Source #
Instance details Defined in Data.CuckooFilter.Internal Methods hashWithSalt :: Int -> IndexA -> Int # hash :: IndexA -> Int #
ToJSON IndexA Source #
Instance details Defined in Data.CuckooFilter.Internal Methods toJSON :: IndexA -> Value # toEncoding :: IndexA -> Encoding # toJSONList :: [IndexA] -> Value # toEncodingList :: [IndexA] -> Encoding #
FromJSON IndexA Source #
Instance details Defined in Data.CuckooFilter.Internal Methods parseJSON :: Value -> Parser IndexA # parseJSONList :: Value -> Parser [IndexA] #
Serialize IndexA Source #
Instance details Defined in Data.CuckooFilter.Internal Methods put :: Putter IndexA # get :: Get IndexA #
Index IndexA Source #
Instance details Defined in Data.CuckooFilter.Internal Methods toIndex :: Natural -> IndexA -> Int Source #
type Rep IndexA Source #
Instance details Defined in Data.CuckooFilter.Internal type Rep IndexA = D1 (MetaData "IndexA" "Data.CuckooFilter.Internal" "cuckoo-filter-0.1.0.2-8NKAT7gypEH8pARQbiuTP3" True) (C1 (MetaCons "IA" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word32)))

newtype IndexB Source #

Constructors

IB Word32

Instances

Eq IndexB Source #
Instance details Defined in Data.CuckooFilter.Internal Methods (==) :: IndexB -> IndexB -> Bool # (/=) :: IndexB -> IndexB -> Bool #
Ord IndexB Source #
Instance details Defined in Data.CuckooFilter.Internal Methods compare :: IndexB -> IndexB -> Ordering # (<) :: IndexB -> IndexB -> Bool # (<=) :: IndexB -> IndexB -> Bool # (>) :: IndexB -> IndexB -> Bool # (>=) :: IndexB -> IndexB -> Bool # max :: IndexB -> IndexB -> IndexB # min :: IndexB -> IndexB -> IndexB #
Show IndexB Source #
Instance details Defined in Data.CuckooFilter.Internal Methods showsPrec :: Int -> IndexB -> ShowS # show :: IndexB -> String # showList :: [IndexB] -> ShowS #
Generic IndexB Source #
Instance details Defined in Data.CuckooFilter.Internal Associated Types type Rep IndexB :: Type -> Type # Methods from :: IndexB -> Rep IndexB x # to :: Rep IndexB x -> IndexB #
Hashable IndexB Source #
Instance details Defined in Data.CuckooFilter.Internal Methods hashWithSalt :: Int -> IndexB -> Int # hash :: IndexB -> Int #
ToJSON IndexB Source #
Instance details Defined in Data.CuckooFilter.Internal Methods toJSON :: IndexB -> Value # toEncoding :: IndexB -> Encoding # toJSONList :: [IndexB] -> Value # toEncodingList :: [IndexB] -> Encoding #
FromJSON IndexB Source #
Instance details Defined in Data.CuckooFilter.Internal Methods parseJSON :: Value -> Parser IndexB # parseJSONList :: Value -> Parser [IndexB] #
Serialize IndexB Source #
Instance details Defined in Data.CuckooFilter.Internal Methods put :: Putter IndexB # get :: Get IndexB #
Index IndexB Source #
Instance details Defined in Data.CuckooFilter.Internal Methods toIndex :: Natural -> IndexB -> Int Source #
type Rep IndexB Source #
Instance details Defined in Data.CuckooFilter.Internal type Rep IndexB = D1 (MetaData "IndexB" "Data.CuckooFilter.Internal" "cuckoo-filter-0.1.0.2-8NKAT7gypEH8pARQbiuTP3" True) (C1 (MetaCons "IB" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word32)))

replaceInBucket Source #

Arguments

:: FingerPrint
-> (FingerPrint -> Bucket -> (Bool, Bool, Bool, Bool))	Bucket predicate
-> Bucket
-> (FingerPrint, Bucket)

insertBucket :: FingerPrint -> Bucket -> Maybe Bucket Source #

primaryIndex :: Hashable a => a -> Natural -> IndexA Source #

(hash a) % numBuckets

secondaryIndex :: FingerPrint -> Natural -> IndexA -> IndexB Source #

(indexA xor hash fp) % numBuckets

kickedSecondaryIndex :: FingerPrint -> Natural -> IndexB -> IndexB Source #

Bucket Cells,

getCell :: Bucket -> Natural -> FingerPrint Source #

setCell :: Bucket -> Natural -> FingerPrint -> Bucket Source #