Bryan O'Sullivan avatar Bryan O'Sullivan committed c566073

Beginnings of a scalable module

Comments (0)

Files changed (2)

Data/BloomFilter/Scalable/Mutable.hs

+-- |
+-- Module: Data.BloomFilter.Scalable.Mutable
+-- Copyright: Bryan O'Sullivan
+-- License: BSD3
+--
+-- Maintainer: Bryan O'Sullivan <bos@serpentine.com>
+-- Stability: unstable
+-- Portability: portable
+
+module Data.BloomFilter.Scalable.Mutable
+    (
+      MSBloom
+    , new
+    ) where
+
+import qualified Data.BloomFilter.Mutable as MB
+import Data.BloomFilter.Mutable.Internal
+import Data.BloomFilter.Easy
+import Data.BloomFilter.Hash
+import Data.STRef
+import Control.Monad.ST (ST)
+import Data.Word (Word32)
+
+data MSBState s a = MSBState {
+      mbs :: [MBloom s a]
+    , capacity :: !Int
+    , hashFunc :: a -> [Hash]
+    , errRates :: [Double]
+    }
+
+data MSBloom s a = MSBloom {
+      state :: STRef s (MSBState s a)
+    , size :: STRef s Int
+    }
+
+hasher :: (Hashable a) => a -> [Word32]
+hasher v = go 0xb9c53ef3
+    where go s = let s' = hashSalt32 s v
+                 in s' : go s'
+
+grow hasher cap errRate tightening = do
+  let newCap = cap * 2
+      newErrRate = errRate * tightening
+      (numBits, numHashes) = case safeSuggestSizing newCap newErrRate of
+                               Left _   -> suggestSizing cap errRate
+                               Right bh -> bh
+  MB.new (take numHashes . hasher) numBits
+
+new :: (a -> [Hash])
+    -> Double
+    -> Double
+    -> ST s (MSBloom s a)
+new hasher errRate tightening
+    | tightening <= 0 || tightening >= 1 = error "invalid tightening"
+    | otherwise = do
+  let initCap = 1024
+  let (numBits, numHashes) = suggestSizing initCap errRate
+  mb <- MB.new (take numHashes . hasher) numBits
+  state <- newSTRef MSBState {
+             mbs = [mb]
+           , capacity = initCap
+           , hashFunc = hasher
+           , errRates = tail $ iterate (* tightening) errRate
+           }
+  size <- newSTRef 0
+  return $ MSBloom state size

bloomfilter.cabal

   exposed-modules:  Data.BloomFilter
                     Data.BloomFilter.Easy
                     Data.BloomFilter.Mutable
+                    Data.BloomFilter.Scalable.Mutable
                     Data.BloomFilter.Hash
   other-modules:    Data.BloomFilter.Array
                     Data.BloomFilter.Mutable.Internal
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.