packages feed

cuckoo-filter (empty) → 0.1.0.0

raw patch · 10 files changed

+749/−0 lines, 10 filesdep +QuickCheckdep +aesondep +basesetup-changed

Dependencies added: QuickCheck, aeson, base, cereal, containers, criterion, cuckoo-filter, hashable, random, tasty, tasty-hunit, tasty-quickcheck

Files

+ ChangeLog.md view
@@ -0,0 +1,3 @@+# Changelog for cuckoo-filter++## Unreleased changes
+ LICENSE view
@@ -0,0 +1,30 @@+Copyright Author name here (c) 2018++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Author name here nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,27 @@+# cuckoo-filter++[![Build Status](https://travis-ci.org/ChrisCoffey/cuckoo-filter.svg?branch=master)](https://travis-ci.org/ChrisCoffey/cuckoo-filter)++Cuckoo filters are a probabilistic data structure used to answer questions like "Have I already seen this user" or "Is this word in the English language?". They're _probabilistic_ because each membership operation has a false positive probability. It guarnatees that there will never be a false negative, but may have a low chance of false positives.++Bloom filters are the cannonical probabilistic filter structure, and cuckoo filters are a simlar but different tool. As a bloom filter's load factor increases, the chance of false positive trends towards 100%, but the inserts will never fail. On the other hand, a Cuckoo filter retains a relatively stable false positive probability under load, but as load approahes 95% inserts will begin to fail. In either case you probably want to resize your filter...++This implementation has the following properties:+- Buckets of 4 elements+- 8 bit fingerprints+- Cycle termination during item kicking occurs after (0.1 * size) buckets have been checked.+- Size may be any non-zero natural number (not limited to powers of 2)++For more details about how Cuckoo filters work, I recommend you read Fan et. al.'s 2016 paper https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf.++### Usage+Cuckoo filters support three operations: `insert`, `member`, and `delete`. See the [haddocks]() for details.++### Performance+As you'll find in the criterion results, the pure version of the filter can handle ~1.6 million insertions/s. From memory profiles, the vast majority of the memory is taken up by the underlying implementation of `Filter`, so this is an obvious area for improvement.++The current implementation avoids pre-allocating memory for the filter, so the heap usage will incrase linearly with `insert` calls. This obviously helps keep heap usage low for sparse filters, but also means inserts are slower than they would be in a mutable implementation.++### TODO+- [ ] Benchmark against a Bloom filter implementation+- [ ] Introduce a mutable version of `Filter` and a typeclass for the storage interactions
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ benchmarks/Benchmarks.hs view
@@ -0,0 +1,10 @@+import Benchmarks.Simple++import Criterion.Main+++main = defaultMain [+    tenPctPacked,+    fiftyPctPacked,+    ninetyPctPacked+    ]
+ benchmarks/Benchmarks/Simple.hs view
@@ -0,0 +1,78 @@+module Benchmarks.Simple (+    stdInBenchmark,+    tenPctPacked,+    fiftyPctPacked,+    ninetyPctPacked+) where++import Criterion+import Control.Monad (foldM)+import Data.CuckooFilter+import Data.Ratio (Ratio)+import Numeric.Natural (Natural)+import System.Environment+import System.Random++stdInBenchmark :: IO ()+stdInBenchmark = do+    [n, m] <- fmap read <$> getArgs+    let (Just s) = makeSize n+        filt = empty s+    print s+    filt' <- pure $ foldM (\ f a -> f `insert` a) filt [1..m]+    print $ member 1 <$> filt'++tenPctPacked :: Benchmark+tenPctPacked = bgroup "10% packed" [+    bench "Store 100k, 1% dupes" $ whnf (doTest oneMM (LF 10)) (D 1),+    bench "Store 100k, 10% dupes" $ whnf (doTest oneMM (LF 10)) (D 10),+    bench "Store 100k, 50% dupes" $ whnf (doTest oneMM (LF 10)) (D 50),+    bench "Store 10MM, 1% dupes" $ whnf (doTest oneHundredMM (LF 10)) (D 1),+    bench "Store 10MM, 10% dupes" $ whnf (doTest oneHundredMM (LF 10)) (D 10),+    bench "Store 10MM, 50% dupes" $ whnf (doTest oneHundredMM (LF 10)) (D 50)+    ]++fiftyPctPacked :: Benchmark+fiftyPctPacked = bgroup "50% packed" [+    bench "Store 500k, 1% dupes" $ whnf (doTest oneMM (LF 50)) (D 1),+    bench "Store 500k, 10% dupes" $ whnf (doTest oneMM (LF 50)) (D 10),+    bench "Store 500k, 50% dupes" $ whnf (doTest oneMM (LF 50)) (D 50),+    bench "Store 50MM, 1% dupes" $ whnf (doTest oneHundredMM (LF 50)) (D 1),+    bench "Store 50MM, 10% dupes" $ whnf (doTest oneHundredMM (LF 50)) (D 10),+    bench "Store 50MM, 50% dupes" $ whnf (doTest oneHundredMM (LF 50)) (D 50)+    ]++ninetyPctPacked :: Benchmark+ninetyPctPacked = bgroup "90% packed" [+    bench "Store 900k, 1% dupes" $ whnf (doTest oneMM (LF 90)) (D 1),+    bench "Store 900k, 10% dupes" $ whnf (doTest oneMM (LF 90)) (D 10),+    bench "Store 900k, 50% dupes" $ whnf (doTest oneMM (LF 90)) (D 50),+    bench "Store 90MM, 1% dupes" $ whnf (doTest oneHundredMM (LF 10)) (D 1),+    bench "Store 90MM, 10% dupes" $ whnf (doTest oneHundredMM (LF 10)) (D 10),+    bench "Store 90MM, 50% dupes" $ whnf (doTest oneHundredMM (LF 10)) (D 50)+    ]++oneMM :: Natural+oneMM = 1000000+oneHundredMM :: Natural+oneHundredMM = oneMM * 100+newtype DupePct = D Natural+newtype LoadFactor = LF Natural++doTest ::+    Natural+    -> LoadFactor+    -> DupePct+    -> Maybe (Filter Int)+doTest size (LF lf) (D d) =+    foldM insert (empty s) vals+    where+        valCount :: Int+        valCount = floor $ (fromIntegral size) * (realToFrac lf / 100.0)+        dupeCount :: Int+        dupeCount = floor $ (fromIntegral valCount) * (realToFrac d / 100.0)+        dupes = if d > 0+                then [1.. dupeCount]+                else []+        vals = dupes <> [1..(valCount - dupeCount)]+        Just s = makeSize size
+ cuckoo-filter.cabal view
@@ -0,0 +1,86 @@+cabal-version: 1.12++-- This file has been generated from package.yaml by hpack version 0.31.0.+--+-- see: https://github.com/sol/hpack+--+-- hash: 39f661e082b0630ac91c43d1adf7e2cfb00d6a9e2983e9223a63e7ea8433c78f++name:           cuckoo-filter+version:        0.1.0.0+synopsis:       Pure and impure Cuckoo Filter+description:    Please see the README on Github at <https://github.com/ChrisCoffey/cuckoo-filter#readme>+category:       Data+homepage:       https://github.com/ChrisCoffey/cuckoo-filter#readme+bug-reports:    https://github.com/ChrisCoffey/cuckoo-filter/issues+author:         Chris Coffey+maintainer:     chris@foldl.io+copyright:      2018 Chris Coffey+license:        MIT+license-file:   LICENSE+build-type:     Simple+extra-source-files:+    README.md+    ChangeLog.md++source-repository head+  type: git+  location: https://github.com/ChrisCoffey/cuckoo-filter++library+  exposed-modules:+      Data.CuckooFilter+      Data.CuckooFilter.Internal+  other-modules:+      Paths_cuckoo_filter+  hs-source-dirs:+      src+  default-extensions: NamedFieldPuns DerivingStrategies ScopedTypeVariables DeriveGeneric+  ghc-options: -O2+  build-depends:+      aeson+    , base >=4.7 && <5+    , cereal+    , containers+    , hashable+  default-language: Haskell2010++executable benchmarks+  main-is: Benchmarks.hs+  other-modules:+      Benchmarks.Simple+  hs-source-dirs:+      benchmarks+  ghc-options: -threaded -rtsopts -with-rtsopts=-N -O2+  build-depends:+      aeson+    , base >=4.7 && <5+    , cereal+    , containers+    , criterion+    , cuckoo-filter+    , hashable+    , random+  default-language: Haskell2010++test-suite cuckoo-filter-test+  type: exitcode-stdio-1.0+  main-is: Spec.hs+  other-modules:+      Paths_cuckoo_filter+  hs-source-dirs:+      test+  default-extensions: NamedFieldPuns DerivingStrategies ScopedTypeVariables DeriveGeneric+  ghc-options: -threaded -rtsopts -with-rtsopts=-N+  build-depends:+      QuickCheck+    , aeson+    , base >=4.7 && <5+    , cereal+    , containers+    , cuckoo-filter+    , hashable+    , tasty+    , tasty-hunit+    , tasty-quickcheck+  default-language: Haskell2010
+ src/Data/CuckooFilter.hs view
@@ -0,0 +1,155 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE DeriveAnyClass #-}++{-|+Module      : Data.CuckooFilter+Copyright   : (c) Chris Coffey, 2018+License     : MIT+Maintainer  : chris@foldl.io+Stability   : experimental++Cuckoo filters are an alternative data structure to Bloom filters. They use a different+approach to hashing items into the filter, which provides different behavior under load.++Inserting an item in to a Bloom filter always succeeds, although as the load factor on+the filter increases the false positive probability trends towards /%100/. Cuckoo filters+on the other hand hold the false positive probability constant under load, but will+begin to fail inserts.++Cuckoo filters also support deletion natively, which allows reclaiming some used space+from the filter to ward off insertion failures.++For more details see: Fan, . Cuckoo Filter: Practically Better Than Bloom. Retrieved August 22, 2016, from https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf+-}++module Data.CuckooFilter+    (+    -- * The Cuckoo Filter+    Size,+    makeSize,+    Filter,+    empty,++    -- * Working with a Cuckoo Filter+    insert,+    member,+    delete+    ) where++import Data.Hashable (Hashable)+import qualified Data.IntMap.Strict as IM+import Data.Maybe (fromMaybe)++import Data.CuckooFilter.Internal+++-- | In exchange for the stable false-positive probability, insertion into a cuckoo filter+-- may fail as the load factor increases.+--+-- Amoritized /O(1)/+--+-- Note, because of how cuckoo hashing works, inserts will fail when there's a set of items /s/+-- that hash to the same fingerprint and share either IndexA or IndexB with probability /(2/numBuckets * 1/256)^ (|s|-1)/.+-- Alternatively, inserting the same item /2b+1/ times will trigger the failure as well.+--+insert :: (Hashable a) =>+    Filter a -- ^ Current filter state+    -> a -- ^ Item to hash and store in the filter+    -> Maybe (Filter a)+insert cfilt@(F {numBuckets}) val = let+    idxA = primaryIndex val numBuckets+    fp = makeFingerprint val+    bkts = buckets cfilt+    bucketA = fromMaybe emptyBucket $ toIndex numBuckets idxA `IM.lookup` bkts+    in case insertBucket fp bucketA of+        Just bucketA' -> Just $ cfilt {buckets = IM.insert (toIndex numBuckets idxA) bucketA' bkts}+        Nothing -> let+            idxB = secondaryIndex fp numBuckets idxA+            in bumpHash maxNumKicks cfilt idxB fp+    where+        (Size s) = size cfilt+        maxNumKicks = floor $ 0.1 * fromIntegral s++        -- The details of this algorithm can be found in https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf+        -- If the kick count is exhausted, the insert fails+        bumpHash 0 _ _ _ = Nothing+        bumpHash remaingKicks cfilt' idxB fp = let+            bkts = buckets cfilt'+            bucketB = fromMaybe emptyBucket $ toIndex numBuckets idxB `IM.lookup` bkts+            in case insertBucket fp bucketB of+                Just bb' -> Just $ cfilt' {buckets = IM.insert (toIndex numBuckets idxB) bb' bkts }+                Nothing -> let+                    (bumpedFP, bucketB') = replaceInBucket fp isBucketMinimum bucketB+                    nextStepFilter = cfilt' {buckets = IM.insert (toIndex numBuckets idxB) bucketB' bkts }+                    kickedIndex = kickedSecondaryIndex bumpedFP numBuckets idxB+                    in bumpHash (remaingKicks - 1) nextStepFilter kickedIndex bumpedFP++        isBucketMinimum _ bkt = let+            a = getCell bkt 0+            b = getCell bkt 1+            c = getCell bkt 2+            d = getCell bkt 3+            m = min a . min b $ min c d+            in (a == m, b == m, c == m, d == m)++-- | Checks whether a given item is within the filter.+--+-- /O(1)/+member :: (Hashable a) =>+    a -- ^ Check if this element is in the filter+    -> Filter a -- ^ The filter+    -> Bool+member a cFilter =+    inBucket fp bA || inBucket fp bB+    where+        bktCount = numBuckets cFilter+        fp = makeFingerprint a+        idxA = primaryIndex a bktCount+        idxB = secondaryIndex fp bktCount idxA+        bkts = buckets cFilter++        -- TODO Try to make this typesafe+        bA = fromMaybe emptyBucket $ toIndex bktCount idxA `IM.lookup` bkts+        bB = fromMaybe emptyBucket $ toIndex bktCount idxB `IM.lookup` bkts++        -- fp `elem` [a,b,c,d] is simpler, but it allocates an additional list unnecessarily+        inBucket fp bucket =+            fp == getCell bucket 0 ||+            fp == getCell bucket 1 ||+            fp == getCell bucket 2 ||+            fp == getCell bucket 3++++-- | Deletes a single occurance of 'a' from the 'Filter'. It first checks for a value+-- in the primary index, then in the secondary index.+--+-- Deleting an element not in the Cuckoo Filter is a noop and returns the filter unchanged.+--+-- /O(1)/+delete :: (Hashable a) =>+    Filter a+    -> a+    -> Filter a+delete cFilt@(F {numBuckets, buckets}) a+    | not $ member a cFilt = cFilt+    | otherwise = let+        bucketA = fromMaybe emptyBucket $ toIndex numBuckets idxA `IM.lookup` buckets+        bucketB = fromMaybe emptyBucket $ toIndex numBuckets idxB `IM.lookup` buckets+        (removedFromA, bucketA') = removeFromBucket bucketA+        (_, bucketB') = removeFromBucket bucketB+        in if removedFromA+           then cFilt {buckets = IM.insert (toIndex numBuckets idxA) bucketA' buckets}+           else cFilt {buckets = IM.insert (toIndex numBuckets idxB) bucketB' buckets}+    where+        fp = makeFingerprint a+        idxA = primaryIndex a numBuckets+        idxB = secondaryIndex fp numBuckets idxA+        -- TODO just use Control.Arrow+        matchesFP _ bucket = (fp == getCell bucket 0,+                              fp == getCell bucket 1,+                              fp == getCell bucket 2,+                              fp == getCell bucket 3)+        removeFromBucket bucket = let+            (_, bucket') = replaceInBucket (FP 0) matchesFP bucket+            in (bucket /= bucket', bucket')
+ src/Data/CuckooFilter/Internal.hs view
@@ -0,0 +1,221 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE DeriveAnyClass #-}++{-|+Module      : Data.CuckooFilter.Internal+Description : Internal functions and data types for Data.CuckooFilter+Copyright   : (c) Chris Coffey, 2018+License     : MIT+Maintainer  : chris@foldl.io+Stability   : experimental++This is the internal API and implemntation of 'Data.CuckooFilter'. It is subject to+change at any time and should not be used. Instead, use the exports from 'Data.CuckooFilter'.+-}++module Data.CuckooFilter.Internal (+    -- * Constructing a Cuckoo Filter+    Size(..),+    makeSize,+    Filter(..),+    empty,++    -- * Fingerprints+    FingerPrint(..),+    emptyFP,+    makeFingerprint,++    -- * Working with indices+    Bucket(..),+    emptyBucket,+    Index(..),+    IndexA(..),+    IndexB(..),+    replaceInBucket,+    insertBucket,+    primaryIndex,+    secondaryIndex,+    kickedSecondaryIndex,++    -- ** Bucket Cells,+    getCell,+    setCell+) where++import Data.Aeson (ToJSON, FromJSON)+import Data.Bits (xor, (.&.), (.|.), shiftR, shiftL)+import Data.Foldable (foldl')+import qualified Data.IntMap.Strict as IM+import Data.Hashable (Hashable, hash)+import Data.Serialize (Serialize)+import Data.Word (Word32, Word8)+import GHC.Generics (Generic)+import Numeric.Natural (Natural)++-- | A non-zero natural number. Generally this is a power of two, although there's no hard requirement+-- for that given the current implementation.+newtype Size = Size Natural+    deriving (Show, Eq, Ord)+    deriving stock Generic+    deriving newtype (Serialize, ToJSON, FromJSON)+-- | Safely make a 'Size' or fail if a 0 is provided.+makeSize :: Natural -> Maybe Size+makeSize n+    | n == 0 = Nothing+    | otherwise = Just . Size $ fromIntegral n++class Index a where+    toIndex :: Natural -> a -> Int++-- | An Index represents the keys into buckets+newtype IndexA = IA Word32+    deriving (Show, Eq, Ord, Generic)+    deriving newtype (ToJSON, FromJSON, Hashable)+    deriving anyclass Serialize+instance Index IndexA where+    toIndex numBuckets (IA n) = fromIntegral n `mod` fromIntegral numBuckets++newtype IndexB = IB Word32+    deriving (Show, Eq, Ord, Generic)+    deriving newtype (ToJSON, FromJSON, Hashable)+    deriving anyclass Serialize+instance Index IndexB where+    toIndex numBuckets (IB n) = fromIntegral n `mod` fromIntegral numBuckets++-- | A FingerPrint is an 8 bit hash of a value+newtype FingerPrint = FP Word8+    deriving (Show, Eq, Ord, Generic)+    deriving newtype (ToJSON, FromJSON, Hashable)+    deriving anyclass Serialize+emptyFP :: FingerPrint+emptyFP = FP 0+-- | A Bucket is a statically sized list of four FingerPrints.+--+newtype Bucket = B Word32+    deriving (Show, Ord)+    deriving stock Generic+    deriving newtype (ToJSON, FromJSON, Eq)+    deriving anyclass Serialize+emptyBucket :: Bucket+emptyBucket = B 0++getCell ::+    Bucket+    -> Natural -- Really just 0-3. Is it worth creating a custom datatype for this?+    -> FingerPrint+getCell (B bucket) cellNumber =+    FP . fromIntegral $ (bucket .&. mask) `shiftR` offset+    where+        offset = (fromIntegral cellNumber) * 8+        mask = (255 :: Word32) `shiftL` offset++setCell ::+    Bucket+    -> Natural+    -> FingerPrint+    -> Bucket+setCell (B bucket) cellNumber (FP fp) =+    B $ zeroed .|. mask+    where+        offset = (fromIntegral cellNumber) * 8+        zeroed = (bucket .|. zeroMask) `xor` zeroMask+        zeroMask = (255 :: Word32) `shiftL` offset+        mask = (fromIntegral fp :: Word32) `shiftL` offset++-- | A Cuckoo Filter with a fixed size. The current implementation uses 8 bit fingerprints+-- and 4 element buckets.+data Filter a = F {+    buckets :: IM.IntMap Bucket, -- size / 4.+    numBuckets :: !Natural, -- Track the number of buckets to avoid a length lookup+    size :: !Size -- The number of buckets+    }+    deriving (Show, Eq, Generic, Serialize, ToJSON, FromJSON)++-- | Creates a new & empty 'Filter' of size s+empty ::+    Size -- ^ The initial size of the filter+    -> Filter a+empty (Size s) = F {+    -- By using an empty map, we're able to avoid allocating any memory for elements that aren't stored.+    -- If the filter is packed densely the additional memory for the IntMap hurts quite a bit, but at load+    -- factors+    buckets = IM.empty,+    numBuckets = numBuckets,+    size = Size s+    }+    where+        addBucket rawFilt n = IM.insert (fromIntegral n) emptyBucket  rawFilt+        numBuckets = s `div` 4++--+-- Working with Buckets+--+insertBucket ::+    FingerPrint+    -> Bucket+    -> Maybe Bucket+insertBucket fp bucket =+    case (a,b,c,d) of+        (True, _, _, _) -> Just $ setCell bucket 0 fp+        (_, True, _, _) -> Just $ setCell bucket 1 fp+        (_, _, True, _) -> Just $ setCell bucket 2 fp+        (_, _, _, True) -> Just $ setCell bucket 3 fp+        _ -> Nothing+    where+        -- TODO factor out all of this duplicated code+        a = emptyFP == getCell bucket 0+        b = emptyFP == getCell bucket 1+        c = emptyFP == getCell bucket 2+        d = emptyFP == getCell bucket 3++replaceInBucket ::+    FingerPrint+    -> (FingerPrint -> Bucket -> (Bool, Bool, Bool, Bool)) -- ^ Bucket predicate+    -> Bucket -- existing bucket+    -> (FingerPrint, Bucket) -- Removed fingerprint and latest bucket state+replaceInBucket fp predicate bucket = let+    results = predicate fp bucket+    in case results of+        (True, _, _, _) -> (getCell bucket 0, setCell bucket 0 fp)+        (_, True, _, _) -> (getCell bucket 1, setCell bucket 1 fp)+        (_, _, True, _) -> (getCell bucket 2, setCell bucket 2 fp)+        (_, _, _, True) -> (getCell bucket 3, setCell bucket 3 fp)+        _ -> (fp, bucket)++--+-- Index and hashes+--++-- | hash a % 255. Fingerprints are 8 bits each, and completely opaque to the+-- lookup algorithm.+makeFingerprint :: Hashable a =>+    a+    -> FingerPrint+makeFingerprint a = FP . max 1 $  fromIntegral (abs $ hash a) `mod` 255++-- | (hash a) % numBuckets+primaryIndex :: Hashable a =>+    a+    -> Natural+    -> IndexA+primaryIndex a numBuckets =+    IA . fromIntegral $ hash a++-- | (indexA `xor` hash fp) % numBuckets+secondaryIndex ::+    FingerPrint+    -> Natural+    -> IndexA+    -> IndexB+secondaryIndex fp numBuckets (IA primary) =+    IB (primary `xor` fpHash)+    where+        fpHash = fromIntegral $ hash fp++kickedSecondaryIndex ::+    FingerPrint+    -> Natural+    -> IndexB+    -> IndexB+kickedSecondaryIndex fp numBuckets (IB alt) =+    secondaryIndex fp numBuckets (IA alt)
+ test/Spec.hs view
@@ -0,0 +1,137 @@+import Test.Tasty+import Test.Tasty.HUnit+import Test.Tasty.QuickCheck+import Test.QuickCheck++import Control.Monad (foldM, replicateM)+import Data.Hashable (Hashable)+import Data.Maybe (isJust, isNothing)+import Data.Word+import Numeric.Natural (Natural)++import Data.CuckooFilter+import Data.CuckooFilter.Internal++main :: IO ()+main = defaultMain tests++tests :: TestTree+tests = testGroup "Data.CuckooFilter" [+    -- testProperty "insert x increases load factor" undefined,+    testProperty "insert x >> delete x is idempotent" $ \s -> let+        Just f = insert defaultFilter s+        f' = delete f s+        in defaultFilter == f'++    ,testProperty "inserts into a full filter will fail" $ \s n -> let+        f = insertNTimes (100000 + abs n) s defaultFilter+        in isNothing f++    ,testCase "delete x on empty == empty" $ let+        (Just s) = makeSize 10+        in delete (empty s) "Foobar" @=? empty s++    ,testProperty "Looking up a non existent value is False" $ \s ->+        not (member s defaultFilter)++    -- the bucket size is hardcoded to 4 based on the recommendations from the paper, hence 8 below+    ,testCase "More than 2b deletes is a noop" $ do+        let Just f' = insertNTimes 8 "Foobar" defaultFilter+            g = deleteNTimes 7 "Foobar" f'+            h = deleteNTimes 8 "Foobar" f'+            i = deleteNTimes 90 "Foobar" f'+        member "Foobar" f' @=? True+        member "Foobar" g @=? True+        member "Foobar" h @=? False+        member "Foobar" i @=? False++    --+    ,testProperty "insert x >> member x == True" $ \ s -> let+        Just f = insert defaultFilter s+        in member s f++    , indexTests+    , bucketTests+    ]++indexTests :: TestTree+indexTests = testGroup "Indices" [+    testProperty "primaryIndex == kickedSecondaryIndex" $ \(s::String) n -> let+        fp = makeFingerprint s+        pi = primaryIndex s n+        IA piv = pi+        si = secondaryIndex fp n pi+        in (IB piv) == kickedSecondaryIndex fp n si+    ]++bucketTests :: TestTree+bucketTests = testGroup "Buckets" [+    testCase "getCell i on an empty bucket == 0" $ do+        getCell emptyBucket 0 @=? emptyFP+        getCell emptyBucket 1 @=? emptyFP+        getCell emptyBucket 2 @=? emptyFP+        getCell emptyBucket 3 @=? emptyFP++    ,testProperty "(`getCell` n) $ setCell b n fp) == fp" $ \(IC n, fp) -> let+        b = setCell emptyBucket n fp+        in getCell b n == fp++    ,testProperty "insertBucket fails on a full bucket" $ \(FB b, fp) ->+        maybe True (const False) $ insertBucket fp b++    ]+++--+-- Utilities+--++defaultFilter :: Filter String+defaultFilter = empty s+    where+        (Just s) = makeSize 100000++insertNTimes :: Hashable a =>+    Int+    -> a+    -> Filter a+    -> Maybe (Filter a)+insertNTimes n a filt =+    foldM (const . (`insert` a )) filt [1..n]+++deleteNTimes :: Hashable a =>+    Int+    -> a+    -> Filter a+    -> Filter a+deleteNTimes n a filt = foldl (const . (`delete` a )) filt [1..n]++--+-- Instances+--+instance Arbitrary FingerPrint where+    arbitrary = FP <$> arbitrary++instance Arbitrary Bucket where+    arbitrary = B <$> arbitrary++newtype IndexCell = IC Natural+    deriving Show+instance Arbitrary IndexCell where+    arbitrary = IC <$> elements [0..3]++instance Arbitrary Natural where+    arbitrary = ((+ 1) . fromIntegral . abs) <$> (arbitrary :: Gen Int)++newtype FullBucket = FB Bucket+    deriving Show+instance Arbitrary FullBucket where+    arbitrary = do+        [a,b,c,d] <- replicateM 4 $ choose (1,255)+        let a' = setCell emptyBucket 0 (FP a)+            b' = setCell a' 1 (FP b)+            c' = setCell b' 2 (FP c)+            d' = setCell c' 3 (FP d)+        pure (FB d')+