prob/bloom
Bloom
(defstruct Bloom [bits : (Vec int) m : int k : int])
a Bloom filter: bit array of m bits, k hash functions.
Since: probabilistic-spice-plan C1
bloom-m
(bloom-m [^borrow bf : Bloom] :)
the bit count.
| bf | the filter |
m, the number of bits in the bit array.
Since: probabilistic-spice-plan C1
bloom-k
(bloom-k [^borrow bf : Bloom] :)
the hash function count.
| bf | the filter |
k, the number of hash functions.
Since: probabilistic-spice-plan C1
bloom-new
(bloom-new [m : int k : int] :)
create a Bloom filter with m bits and k hash functions.
| m | number of bits (should be a power of two for fast mod) | |
| k | number of hash functions |
A new Bloom filter with all bits clear.
(let [bf (bloom-new 1024 7)] ...)
Since: probabilistic-spice-plan C1
bloom-free
(bloom-free [bf : Bloom] :)
release the bit array.
| bf | the filter to free |
Since: probabilistic-spice-plan C1
bloom-insert!
(bloom-insert! [^borrow bf : Bloom key : int] :)
add an element to the filter.
| bf | the filter (mutated in place via the shared bit array) | |
| key | the integer key to insert |
nil
(bloom-insert! bf 42)
Since: probabilistic-spice-plan C1
bloom-maybe?
(bloom-maybe? [^borrow bf : Bloom key : int] :)
is the element possibly in the filter?
| bf | the filter | |
| key | the integer key to check |
true if all k bits are set (element may be present, or a false positive). false if any bit is clear (element is definitely not present).
(bloom-maybe? bf 42)
Since: probabilistic-spice-plan C1
bloom-count
(bloom-count [^borrow bf : Bloom] :)
the number of set bits (popcount).
| bf | the filter |
The popcount of the bit array.
Since: probabilistic-spice-plan C1
bloom-merge
(bloom-merge [^borrow a : Bloom ^borrow b : Bloom] :)
bit-OR two filters into a new one.
| a | first filter | |
| b | second filter (must have the same m and k) |
A new Bloom filter whose bits are the OR of a's and b's. Both inputs remain valid.
Since: probabilistic-spice-plan C1
Internal definitions
__bloom-init-- internal: push m zeros into the bit Vec.__bloom-set-loop-- internal: set k bits at the double-hash positions.__bloom-check-loop-- internal: are all k bits set?__bloom-count-loop-- internal: count set bits.__bloom-or-loop-- internal: OR src bits into dst.__bloom-eq-loop-- internal: are all bits equal?Eq[Bloom]-- same m, k, and all bits equal.default-bloom-m-- default bit count for bottom.default-bloom-k-- default hash count for bottom.JoinSemilattice[Bloom]-- join is bit-OR.BoundedJoin[Bloom]-- the all-zero filter of default size is bottom.