Data.CuckooFilter.Internal

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.

Constructing a Cuckoo Filter

newtype Size

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

Defined in Data.CuckooFilter.Internal

Methods

(==) :: Size -> Size -> Bool

(/=) :: Size -> Size -> Bool

Ord Size

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

Defined in Data.CuckooFilter.Internal

Methods

showsPrec :: Int -> Size -> ShowS

show :: Size -> String

showList :: [Size] -> ShowS

Generic Size

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

Defined in Data.CuckooFilter.Internal

Methods

toJSON :: Size -> Value

toEncoding :: Size -> Encoding

toJSONList :: [Size] -> Value

toEncodingList :: [Size] -> Encoding

FromJSON Size

Defined in Data.CuckooFilter.Internal

Methods

parseJSON :: Value -> Parser Size

parseJSONList :: Value -> Parser [Size]

Serialize Size

Defined in Data.CuckooFilter.Internal

Methods

put :: Putter Size

get :: Get Size

type Rep Size

Defined in Data.CuckooFilter.Internal

type Rep Size = D1 (MetaData "Size" "Data.CuckooFilter.Internal" "cuckoo-filter-0.2.0.2-B7QL3ZxFbHGZXnXJGf4MU" True) (C1 (MetaCons "Size" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Natural)))

makeSize :: Natural -> Maybe Size

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

class Monad m => CuckooFilter filt m where

A low-level interface for working with cuckoo filter storage.

Methods

initialize :: Size -> m (filt a)

Create a new cuckoo filter of the specified size

bucketCount :: filt a -> m Natural

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)

Write the new contents of a bucket to the storage

readBucket :: Int -> filt a -> m Bucket

Read the contents of a bucket from the storage

Instances

CuckooFilter MFilter IO

Defined in Data.CuckooFilter.Mutable

Methods

initialize :: Size -> IO (MFilter a)

bucketCount :: MFilter a -> IO Natural

writeBucket :: Int -> Bucket -> MFilter a -> IO (MFilter a)

readBucket :: Int -> MFilter a -> IO Bucket

Monad m => CuckooFilter Filter m

Defined in Data.CuckooFilter.Pure

Methods

initialize :: Size -> m (Filter a)

bucketCount :: Filter a -> m Natural

writeBucket :: Int -> Bucket -> Filter a -> m (Filter a)

readBucket :: Int -> Filter a -> m Bucket

Fingerprints

newtype FingerPrint

A FingerPrint is an 8 bit hash of a value

Constructors

FP Word8

Instances

Eq FingerPrint

Defined in Data.CuckooFilter.Internal

Methods

(==) :: FingerPrint -> FingerPrint -> Bool

(/=) :: FingerPrint -> FingerPrint -> Bool

Ord FingerPrint

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

Defined in Data.CuckooFilter.Internal

Methods

showsPrec :: Int -> FingerPrint -> ShowS

show :: FingerPrint -> String

showList :: [FingerPrint] -> ShowS

Generic FingerPrint

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

Defined in Data.CuckooFilter.Internal

Methods

hashWithSalt :: Int -> FingerPrint -> Int

hash :: FingerPrint -> Int

ToJSON FingerPrint

Defined in Data.CuckooFilter.Internal

Methods

toJSON :: FingerPrint -> Value

toEncoding :: FingerPrint -> Encoding

toJSONList :: [FingerPrint] -> Value

toEncodingList :: [FingerPrint] -> Encoding

FromJSON FingerPrint

Defined in Data.CuckooFilter.Internal

Methods

parseJSON :: Value -> Parser FingerPrint

parseJSONList :: Value -> Parser [FingerPrint]

Serialize FingerPrint

Defined in Data.CuckooFilter.Internal

Methods

put :: Putter FingerPrint

get :: Get FingerPrint

type Rep FingerPrint

Defined in Data.CuckooFilter.Internal

type Rep FingerPrint = D1 (MetaData "FingerPrint" "Data.CuckooFilter.Internal" "cuckoo-filter-0.2.0.2-B7QL3ZxFbHGZXnXJGf4MU" True) (C1 (MetaCons "FP" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word8)))

emptyFP :: FingerPrint

makeFingerprint :: Hashable a => a -> FingerPrint

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

Working with indices

newtype Bucket

A Bucket is a statically sized list of four FingerPrints.

Constructors

B Word32

Instances

Eq Bucket

Defined in Data.CuckooFilter.Internal

Methods

(==) :: Bucket -> Bucket -> Bool

(/=) :: Bucket -> Bucket -> Bool

Ord Bucket

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

Defined in Data.CuckooFilter.Internal

Methods

showsPrec :: Int -> Bucket -> ShowS

show :: Bucket -> String

showList :: [Bucket] -> ShowS

Generic Bucket

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

Defined in Data.CuckooFilter.Internal

Methods

toJSON :: Bucket -> Value

toEncoding :: Bucket -> Encoding

toJSONList :: [Bucket] -> Value

toEncodingList :: [Bucket] -> Encoding

FromJSON Bucket

Defined in Data.CuckooFilter.Internal

Methods

parseJSON :: Value -> Parser Bucket

parseJSONList :: Value -> Parser [Bucket]

Serialize Bucket

Defined in Data.CuckooFilter.Internal

Methods

put :: Putter Bucket

get :: Get Bucket

type Rep Bucket

Defined in Data.CuckooFilter.Internal

type Rep Bucket = D1 (MetaData "Bucket" "Data.CuckooFilter.Internal" "cuckoo-filter-0.2.0.2-B7QL3ZxFbHGZXnXJGf4MU" True) (C1 (MetaCons "B" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word32)))

emptyBucket :: Bucket

class Index a where

Methods

toIndex :: Natural -> a -> Int

Instances

Index IndexB

Defined in Data.CuckooFilter.Internal

Methods

toIndex :: Natural -> IndexB -> Int

Index IndexA

Defined in Data.CuckooFilter.Internal

Methods

toIndex :: Natural -> IndexA -> Int

newtype IndexA

An Index represents the keys into buckets

Constructors

IA Word32

Instances

Eq IndexA

Defined in Data.CuckooFilter.Internal

Methods

(==) :: IndexA -> IndexA -> Bool

(/=) :: IndexA -> IndexA -> Bool

Ord IndexA

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

Defined in Data.CuckooFilter.Internal

Methods

showsPrec :: Int -> IndexA -> ShowS

show :: IndexA -> String

showList :: [IndexA] -> ShowS

Generic IndexA

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

Defined in Data.CuckooFilter.Internal

Methods

hashWithSalt :: Int -> IndexA -> Int

hash :: IndexA -> Int

ToJSON IndexA

Defined in Data.CuckooFilter.Internal

Methods

toJSON :: IndexA -> Value

toEncoding :: IndexA -> Encoding

toJSONList :: [IndexA] -> Value

toEncodingList :: [IndexA] -> Encoding

FromJSON IndexA

Defined in Data.CuckooFilter.Internal

Methods

parseJSON :: Value -> Parser IndexA

parseJSONList :: Value -> Parser [IndexA]

Serialize IndexA

Defined in Data.CuckooFilter.Internal

Methods

put :: Putter IndexA

get :: Get IndexA

Index IndexA

Defined in Data.CuckooFilter.Internal

Methods

toIndex :: Natural -> IndexA -> Int

type Rep IndexA

Defined in Data.CuckooFilter.Internal

type Rep IndexA = D1 (MetaData "IndexA" "Data.CuckooFilter.Internal" "cuckoo-filter-0.2.0.2-B7QL3ZxFbHGZXnXJGf4MU" True) (C1 (MetaCons "IA" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word32)))

newtype IndexB

Constructors

IB Word32

Instances

Eq IndexB

Defined in Data.CuckooFilter.Internal

Methods

(==) :: IndexB -> IndexB -> Bool

(/=) :: IndexB -> IndexB -> Bool

Ord IndexB

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

Defined in Data.CuckooFilter.Internal

Methods

showsPrec :: Int -> IndexB -> ShowS

show :: IndexB -> String

showList :: [IndexB] -> ShowS

Generic IndexB

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

Defined in Data.CuckooFilter.Internal

Methods

hashWithSalt :: Int -> IndexB -> Int

hash :: IndexB -> Int

ToJSON IndexB

Defined in Data.CuckooFilter.Internal

Methods

toJSON :: IndexB -> Value

toEncoding :: IndexB -> Encoding

toJSONList :: [IndexB] -> Value

toEncodingList :: [IndexB] -> Encoding

FromJSON IndexB

Defined in Data.CuckooFilter.Internal

Methods

parseJSON :: Value -> Parser IndexB

parseJSONList :: Value -> Parser [IndexB]

Serialize IndexB

Defined in Data.CuckooFilter.Internal

Methods

put :: Putter IndexB

get :: Get IndexB

Index IndexB

Defined in Data.CuckooFilter.Internal

Methods

toIndex :: Natural -> IndexB -> Int

type Rep IndexB

Defined in Data.CuckooFilter.Internal

type Rep IndexB = D1 (MetaData "IndexB" "Data.CuckooFilter.Internal" "cuckoo-filter-0.2.0.2-B7QL3ZxFbHGZXnXJGf4MU" True) (C1 (MetaCons "IB" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word32)))

replaceInBucket

Arguments

:: FingerPrint

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

Bucket predicate

-> Bucket

-> (FingerPrint, Bucket)

insertBucket :: FingerPrint -> Bucket -> Maybe Bucket

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

(hash a) % numBuckets

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

(indexA xor hash fp) % numBuckets

kickedSecondaryIndex :: FingerPrint -> Natural -> IndexB -> IndexB

Bucket Cells,

getCell :: Bucket -> Natural -> FingerPrint

setCell :: Bucket -> Natural -> FingerPrint -> Bucket