Salt for hash computations.

Choosing good hash functions is imperative for a good performance of a cuckoo filter. The hash functions must be

• independent and
• provide good uniformity on the lower bits of the output.

The default implementations use sip hash for cuckooHash and fnv1a (64 bit) for cuckooFingerprint and require an instance of Storable.

>>> instance CuckooFilterHash Int

The following example uses the hash functions that are provided in this module to define an instance for ByteString:

>>> import qualified Data.ByteString as B
>>> :{
instance CuckooFilterHash B.ByteString where
    cuckooHash (Salt s) a = fnv1a_bytes s a
    cuckooFingerprint (Salt s) a = sip_bytes s a
    {-# INLINE cuckooHash #-}
    {-# INLINE cuckooFingerprint #-}
:}

Computes a Sip hash for a value that has an Storable instance.

The first argument is a salt value that is used to derive the key for the hash computation.

Computes a Sip hash for a value that is an instance of ByteArrayAccess.

The first argument is a salt value that is used to derive the key for the hash computation.

Computes a 64 bit Fnv1a hash for a value that has an Storable instance.

The first argument is use as a salt.

Computes a 64 bit Fnv1a hash for a value that is an instance of ByteArrayAccess.

The first argument is use as a salt.

Cuckoo Filter with

• State token s :: Type,
• bucket size b :: Nat,
• fingerprint size f :: Nat, and
• content type a :: Type.

The following constraints apply

• \(0 < f \leq 32\)
• \(0 < b\)

The implementation is not thread safe. For concurrent use the filter must be wrapped in a read-write lock.

Cuckoo filter that can be used in the IO monad.

Create a new Cuckoo filter that has at least the given capacity.

Enabling the TypeApplications language extension provides a convenient way for passing the type parameters to the function.

>>> :set -XTypeApplications -XDataKinds -XTypeFamilies
>>> newCuckooFilter @4 @10 @Int 0 1000

The type parameters are

• bucket size b :: Nat,
• fingerprint size f :: Nat,
• content type a :: Type, and
• Monad m :: Type -> Type,

The following constraints apply:

• \(0 < f \leq 32\),
• \(0 < b\), and
• \(64 \leq n\), where \(n\) is the requested size.

The false positive rate depends mostly on the value of f. It is bounded from above by \(\frac{2b}{2^f}\). In most cases 4 is a good choice for b.

Actual performance depends on the choice of good hash functions that provide high uniformity on the lower bits.

The actual capacity may be much larger than what is requested, because the actual bucket count is a power of two.

>>> f <- newCuckooFilter @4 @10 @Int 0 600
>>> capacityInItems f
1024
>>> sizeInAllocatedBytes f
1284

Insert an item into the filter and return whether the operation was successful. If insertion fails, the filter is unchanged. An item can be inserted more than once. The return value indicates whether insertion was successful. The operation can fail when the filter doesn't have enough space for the item.

This function is not thread safe. No concurrent writes or reads should occur while this function is executed. If this is needed a lock must be used.

This function is not exception safe. The filter must not be used any more after an asynchronous exception has been thrown during the computation of this function. If this function is used in the presence of asynchronous exceptions it should be apprioriately masked.

>>> f <- newCuckooFilter @4 @10 @Int 0 1000
>>> insert f 0
True
>>> insert f 0
True
>>> itemCount f
2

Test whether an item is in the set that is represented by the Cuckoo filter.

A negative result means that the item is definitively not in the set. A positive result means that the item is most likely in the set. The rate of false positives is bounded from above by \(\frac{2b}{2^f}\) where b is the number of items per bucket and f is the size of a fingerprint in bits.

>>> f <- newCuckooFilter @4 @10 @Int 0 1000
>>> insert f 0
True
>>> member f 0
True
>>> member f 1
False

Delete an items from the filter. An item that was inserted more than once can also be deleted more than once.

IMPORTANT An item must only be deleted if it was successfully added to the filter before (and hasn't been deleted since then).

Deleting an item that isn't in the filter can result in the filter returning false negative results.

This function is not thread safe. No concurrent writes must occur while this function is executed. If this is needed a lock must be used. Concurrent reads are fine.

>>> f <- newCuckooFilter @4 @10 @Int 0 1000
>>> insert f 0
True
>>> insert f 0
True
>>> itemCount f
2
>>> delete f 0
True
>>> itemCount f
1
>>> member f 0
True
>>> delete f 0
True
>>> itemCount f
0
>>> member f 0
False

The total number of bytes allocated for storing items in the filter.

Total number of items that the filter can hold. In practice a load factor of ~95% of this number can be reached.

Number of items currently stored in the filter.

Note that computing this number is expensive \(\mathcal{O}(n)\).

The current load factor of the filter in percent.

loadFactor f = 100 * itemCount f / capacityInItems

Note that computing this number is expensive \(\mathcal{O}(n)\).

Show the contents of the filter as a list of buckets with values show in hex. Used for debugging purposes.

Returns the different hashes that are associated with an item in the filter. Used for debugging purposes.