bloomfilter 1.1.0 → 1.2.0

raw patch · 3 files changed

+128/−10 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/BloomFilter.hs +103/−7
• Data/BloomFilter/Array.hs +22/−0
• bloomfilter.cabal +3/−3

@@ -1,4 +1,5 @@ {-# LANGUAGE Rank2Types, TypeOperators #-}+{-# OPTIONS_GHC -fglasgow-exts #-}  -- | -- Module: Data.BloomFilter@@ -43,15 +44,25 @@     -- * Immutable Bloom filters     -- ** Creation     , unfoldB+     , fromListB-    , createB+    , emptyB+    , singletonB      -- ** Accessors     , lengthB     , elemB     , notElemB +    -- ** Mutators+    , insertB+    , insertListB+     -- * Mutable Bloom filters+    -- ** Immutability wrappers+    , createB+    , modifyB+     -- ** Creation     , newMB     , unsafeFreezeMB@@ -79,9 +90,10 @@ import Control.Monad (liftM, forM_) import Control.Monad.ST (ST, runST) import Data.Array.Base (unsafeAt, unsafeRead, unsafeWrite)-import Data.Array.ST (STUArray, newArray, thaw, unsafeFreeze)+import Data.Array.ST (STUArray, thaw, unsafeFreeze) import Data.Array.Unboxed (UArray) import Data.Bits ((.&.), (.|.))+import Data.BloomFilter.Array (newArray) import Data.BloomFilter.Util (FastShift(..), (:*)(..), nextPowerOfTwo) import Data.Word (Word32) import qualified Data.ByteString as SB@@ -134,11 +146,12 @@ newMB :: (a -> [Hash])          -- ^ family of hash functions to use       -> Int                    -- ^ number of bits in filter       -> ST s (MBloom s a)-newMB hash numBits = MB hash shift mask `liftM` newArray (0, numElems - 1) 0+newMB hash numBits = MB hash shift mask `liftM` newArray numElems numBytes   where twoBits | numBits < 1 = 1                 | isPowerOfTwo numBits = numBits                 | otherwise = nextPowerOfTwo numBits         numElems = max 2 (twoBits `shiftR` logBitsInHash)+        numBytes = numElems `shiftL` logBytesInHash         trueBits = numElems `shiftL` logBitsInHash         shift = logPower2 trueBits         mask = trueBits - 1@@ -147,6 +160,9 @@ logBitsInHash :: Int logBitsInHash = 5 -- logPower2 bitsInHash +logBytesInHash :: Int+logBytesInHash = 2 -- logPower2 (sizeOf (undefined :: Hash))+ -- | Create an immutable Bloom filter, using the given setup function -- which executes in the 'ST' monad. --@@ -171,6 +187,27 @@   body mb   unsafeFreezeMB mb +-- | Create an empty Bloom filter.+--+-- This function is subject to fusion with 'insertB'+-- and 'insertListB'.+emptyB :: (a -> [Hash])         -- ^ family of hash functions to use+       -> Int                   -- ^ number of bits in filter+       -> Bloom a+{-# INLINE [1] emptyB #-}+emptyB hash numBits = createB hash numBits (\_ -> return ())++-- | Create a Bloom filter with a single element.+--+-- This function is subject to fusion with 'insertB'+-- and 'insertListB'.+singletonB :: (a -> [Hash])     -- ^ family of hash functions to use+           -> Int               -- ^ number of bits in filter+           -> a                 -- ^ element to insert+           -> Bloom a+{-# INLINE [1] singletonB #-}+singletonB hash numBits elt = createB hash numBits (\mb -> insertMB mb elt)+ -- | Given a filter's mask and a hash value, compute an offset into -- a word array and a bit offset within that word. hashIdx :: Int -> Word32 -> (Int :* Int)@@ -220,6 +257,63 @@ elemB elt ub = all test (hashesU ub elt)   where test (off :* bit) = (bitArrayB ub `unsafeAt` off) .&. (1 `shiftL` bit) /= 0           +modifyB :: (forall s. (MBloom s a -> ST s z))  -- ^ mutation function (result is discarded)+        -> Bloom a+        -> Bloom a+{-# INLINE modifyB #-}+modifyB body ub = runST $ do+  mb <- thawMB ub+  body mb+  unsafeFreezeMB mb++-- | Create a new Bloom filter from an existing one, with the given+-- member added.+--+-- This function may be expensive, as it is likely to cause the+-- underlying bit array to be copied.+--+-- Repeated applications of this function with itself are subject to+-- fusion.+insertB :: a -> Bloom a -> Bloom a+{-# NOINLINE insertB #-}+insertB elt = modifyB (flip insertMB elt)++-- | Create a new Bloom filter from an existing one, with the given+-- members added.+--+-- This function may be expensive, as it is likely to cause the+-- underlying bit array to be copied.+--+-- Repeated applications of this function with itself are subject to+-- fusion.+insertListB :: [a] -> Bloom a -> Bloom a+{-# NOINLINE insertListB #-}+insertListB elts = modifyB $ \mb -> mapM_ (insertMB mb) elts++{-# RULES "Bloom insertB . insertB" forall a b u.+    insertB b (insertB a u) = insertListB [a,b] u+  #-}++{-# RULES "Bloom insertListB . insertB" forall x xs u.+    insertListB xs (insertB x u) = insertListB (x:xs) u+  #-}++{-# RULES "Bloom insertB . insertListB" forall x xs u.+    insertB x (insertListB xs u) = insertListB (x:xs) u+  #-}++{-# RULES "Bloom insertListB . insertListB" forall xs ys u.+    insertListB xs (insertListB ys u) = insertListB (xs++ys) u+  #-}++{-# RULES "Bloom insertListB . emptyB" forall h n xs.+    insertListB xs (emptyB h n) = fromListB h n xs+  #-}++{-# RULES "Bloom insertListB . singletonB" forall h n x xs.+    insertListB xs (singletonB h n x) = fromListB h n (x:xs)+  #-}+ -- | Query an immutable Bloom filter for non-membership.  If the value -- /is/ present, return @False@.  If the value is not present, there -- is /still/ some possibility that @False@ will be returned.@@ -285,10 +379,12 @@           -> Int                -- ^ number of bits in filter           -> [a]                -- ^ values to populate with           -> Bloom a-{-# INLINE fromListB #-}-fromListB hashes numBits list = createB hashes numBits (loop list)-  where loop (x:xs) mb = insertMB mb x >> loop xs mb-        loop _ _       = return ()+{-# INLINE [1] fromListB #-}+fromListB hashes numBits list = createB hashes numBits $ forM_ list . insertMB++{-# RULES "Bloom insertListB . fromListB" forall h n xs ys.+    insertListB xs (fromListB h n ys) = fromListB h n (xs ++ ys)+  #-}  {- -- This is a simpler definition, but GHC doesn't inline the unfold

@@ -0,0 +1,22 @@+{-# LANGUAGE FlexibleContexts, ForeignFunctionInterface, MagicHash,+             Rank2Types #-}+{-# OPTIONS_GHC -fglasgow-exts #-}++module Data.BloomFilter.Array (newArray) where++import Control.Monad.ST (ST, unsafeIOToST)+import Data.Array.Base (MArray, STUArray(..), unsafeNewArray_)+import Foreign.C.Types (CInt, CSize)+import Foreign.Ptr (Ptr)+import GHC.Base (MutableByteArray#)++newArray :: forall e s. (MArray (STUArray s) e (ST s)) =>+            Int -> Int -> ST s (STUArray s Int e)+{-# INLINE newArray #-}+newArray numElems numBytes = do+  ary@(STUArray _ _ _ marr#) <- unsafeNewArray_ (0, numElems - 1)+  unsafeIOToST (memset marr# 0 (fromIntegral numBytes))+  return ary++foreign import ccall unsafe "memset"+    memset :: MutableByteArray# s -> CInt -> CSize -> IO (Ptr a)

@@ -1,5 +1,5 @@ name:            bloomfilter-version:         1.1.0+version:         1.2.0 license:         BSD3 license-file:    LICENSE author:          Bryan O'Sullivan <bos@serpentine.com>@@ -35,8 +35,8 @@   exposed-modules: Data.BloomFilter                    Data.BloomFilter.Easy                    Data.BloomFilter.Hash-  other-modules:   Data.BloomFilter.Util+  other-modules:   Data.BloomFilter.Array+                   Data.BloomFilter.Util   c-sources:       cbits/lookup3.c   ghc-options:     -O2 -Wall -fliberate-case-threshold=1000-   cc-options:      -O3