~%      !"#$None 3;HM%&&%&Bryan O'SullivanBSD3%Bryan O'Sullivan <bos@serpentine.com>unstableportableNone+A mutable Bloom filter, for use within the ST monad.A hash value is 32 bits wide. This limits the maximum size of a filter to about four billion elements, or 512 megabytes of memory.'()*+'()*'()*+None;JK,This is a workaround for poor optimisation in GHC 6.8.2. It fails to notice constant-width shifts, and adds a test and branch to every shift. This imposes about a 10% performance hit.-A strict pair type..LCompute the nearest power of two greater to or equal than the given number. ,/0-1.2345,/0-1.,/0-1.2345Bryan O'SullivanBSD3%Bryan O'Sullivan <bos@serpentine.com>unstableportableNone3HJKMCreate a new mutable Bloom filter. For efficiency, the number of bits used may be larger than the number requested. It is always rounded up to the nearest higher power of two, but will be clamped at a maximum of 4 gigabits, since hashes are 32 bits in size.6oGiven a filter's mask and a hash value, compute an offset into a word array and a bit offset within that word.7_Hash the given value, returning a list of (word offset, bit offset) pairs, one per hash value.xInsert a value into a mutable Bloom filter. Afterwards, a membership query for the same value is guaranteed to return True.OQuery a mutable Bloom filter for membership. If the value is present, return True*. If the value is not present, there is still some possibility that True will be returned.3Return the size of a mutable Bloom filter, in bits.8XSlow, crummy way of computing the integer log of an integer known to be a power of two. family of hash functions to usenumber of bits in filter9:;678 9:;678Bryan O'SullivanBSD3%Bryan O'Sullivan <bos@serpentine.com>unstableportableNone JK GCompute a 32-bit hash of a value. The salt value perturbs the result. Compute a 64-bit hash of a value. The first salt value perturbs the first element of the result, and the second salt perturbs the second. Compute a 32-bit hash. Compute a salted 32-bit hash. Compute a salted 64-bit hash.rCompute a list of 32-bit hashes. The value to hash may be inspected as many times as there are hashes requested.Compute a list of 32-bit hashes relatively cheaply. The value to hash is inspected at most twice, regardless of the number of hashes requested.We use a variant of Kirsch and Mitzenmacher's technique from "Less Hashing, Same Performance: Building a Better Bloom Filter",  7http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf.Where Kirsch and Mitzenmacher multiply the second hash by a coefficient, we shift right by the coefficient. This offers better performance (as a shift is much cheaper than a multiply), and the low order bits of the final hash stay well mixed.<_A fast unchecked shift. Nasty, but otherwise GHC 6.8.2 does a test and branch on every shift.Compute a 32-bit hash of a = instance.Compute a 64-bit hash of a = instance.#Compute a 32-bit hash of a list of = instances.#Compute a 64-bit hash of a list of = instances.8> value to hashsalt  value to hashsalt?@ABCDEF salt value to hash salt value to hashnumber of hashes to compute value to hashnumber of hashes to compute value to hash<GHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefg    6> ?@ABCDEF <GHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefgBryan O'SullivanBSD3%Bryan O'Sullivan <bos@serpentine.com>unstableportableNoneHJKM@An immutable Bloom filter, suitable for querying from pure code.hXCreate an immutable Bloom filter, using the given setup function which executes in the i monad.Example: import Data.BloomFilter.Hash{ (cheapHashes) filter = create (cheapHashes 3) 1024 $ mf -> do insertMB mf "foo" insertMB mf "bar" 7Note that the result of the setup function is not used.eCreate an immutable Bloom filter from a mutable one. The mutable filter may be modified afterwards.JCreate an immutable Bloom filter from a mutable one. The mutable filter must not] be modified afterwards, or a runtime crash may occur. For a safer creation interface, use  or h.]Copy an immutable Bloom filter to create a mutable one. There is no non-copying equivalent.Create an empty Bloom filter.(This function is subject to fusion with  and .,Create a Bloom filter with a single element.(This function is subject to fusion with  and .joGiven a filter's mask and a hash value, compute an offset into a word array and a bit offset within that word.k_Hash the given value, returning a list of (word offset, bit offset) pairs, one per hash value.l_Hash the given value, returning a list of (word offset, bit offset) pairs, one per hash value.RQuery an immutable Bloom filter for membership. If the value is present, return True*. If the value is not present, there is still some possibility that True will be returned.MCreate 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.JRepeated applications of this function with itself are subject to fusion.NCreate 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.JRepeated applications of this function with itself are subject to fusion.CQuery 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 True will be returned.6Return the size of an immutable Bloom filter, in bits. jBuild an immutable Bloom filter from a seed value. The seeding function populates the filter as follows.If it returns mA, it is finished producing values to insert into the filter.If it returns n (a,b), a! is added to the filter and b is used as a new seed.!GCreate an immutable Bloom filter, populating it from a list of values.!Here is an example that uses the  cheapHashes function from the Data.BloomFilter.Hash= module to create a hash function that returns three hashes. import Data.BloomFilter.HashM (cheapHashes) filt = fromList (cheapHashes 3) 1024 ["foo", "bar", "quux"] oXSlow, crummy way of computing the integer log of an integer known to be a power of two.pqrsthfamily of hash functions to usenumber of bits in filtersetup functionfamily of hash functions to usenumber of bits in filterfamily of hash functions to usenumber of bits in filterelement to insertjklu'mutation function (result is discarded) family of hash functions to usenumber of bits in filterseeding function initial seed!family of hash functions to usenumber of bits in filtervalues to populate withovw ! !pqrsthjklu !ovwBryan O'SullivanBSD3%Bryan O'Sullivan <bos@serpentine.com>unstableportableNoneM"tCreate a Bloom filter with the given false positive rate and members. The hash functions used are computed by the  cheapHashes function from the  module.#Suggest a good combination of filter size and number of hash functions for a Bloom filter, based on its expected maximum capacity and a desired false positive rate.WThe false positive rate is the rate at which queries against the filter should return True when an element is not actually present. It should be a fraction between 0 and 1, so a 1% false positive rate is represented by 0.01.$ Behaves as # , but calls x* if given invalid or out-of-range inputs."!desired false positive rate (0 < e < 1)values to populate with#expected maximum capacity!desired false positive rate (0 < e < 1)$expected maximum capacity!desired false positive rate (0 < e < 1)"#$"#$"#$y       !  "#$%&'()*+,-./01230456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijkl?mn89o?pq?pr:s,-<tuv?wxybloomfilter-2.0.1.0Data.BloomFilter.MutableData.BloomFilter.HashData.BloomFilterData.BloomFilter.EasyData.BloomFilter.Array!Data.BloomFilter.Mutable.InternalData.BloomFilter.UtilHashMBloombitArraynewinsertelemlengthHashablehashIO32hashIO64hash32hash64 hashSalt32 hashSalt64hashes cheapHashes hashOne32 hashOne64 hashList32 hashList64Bloomfreeze unsafeFreezethawempty singleton insertListnotElemunfoldfromListeasyListsafeSuggestSizing suggestSizingmemsetnewArrayMBshiftmask $fShowMBloom FastShift:*nextPowerOfTwoshiftLshiftR$fFastShiftInteger$fFastShiftInt$fFastShiftWord64$fFastShiftWord32hashIdxhashesM logPower2maxHash logBitsInHashlogBytesInHashdiv4baseForeign.StorableStorable HashStatec_endc_stepc_fragc_begin hashLittle2 hashLittle hashWord2hashWord alignedHashwith alignedHash2 doubleHashrechunkunsafeUseAsCStringLenunsafeAdjustCStringLen hashChunks $fHashable[]$fHashable(,,,,)$fHashable(,,,)$fHashable(,,) $fHashable(,)$fHashableEither$fHashableMaybe$fHashableByteString$fHashableByteString0$fHashableWord64$fHashableWord32$fHashableWord16$fHashableWord8$fHashableInt64$fHashableInt32$fHashableInt16$fHashableInt8$fHashableDouble$fHashableFloat $fHashableInt$fHashableChar$fHashableOrdering$fHashableBool$fHashableInteger $fHashable()createGHC.STSThashesU Data.MaybeNothingJustBmodify $fNFDataBloom $fShowBloomGHC.Errerror