subms_bloom_filter/features/
counting.rs

1//! Counting bloom filter: supports `remove()` by storing 4-bit
2//! counters per cell instead of 1-bit flags. Cost: 4x memory vs the
3//! base filter; gain: a real `remove()` operation that the base can't
4//! support (since clearing a base bit can disturb other keys).
5//!
6//! Sized for ~1% FPR at 10 bits per key, k=7 (same defaults as the
7//! base `BloomFilter`). Counter saturates at 15 to bound memory; on
8//! saturation a `remove()` won't reduce the counter for that cell
9//! (false-positive risk shifts slightly but no false negatives).
10
11use crate::{FNV_OFFSET, FNV_PRIME, fnv1a64};
12
13#[cfg(feature = "serde")]
14use serde::{Deserialize, Serialize};
15
16#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
17pub struct CountingBloomFilter {
18    bit_count: u32,
19    k: u32,
20    /// 4 bits per cell - two cells per byte. Counter saturates at 15.
21    cells: Vec<u8>,
22}
23
24impl CountingBloomFilter {
25    /// Build an empty counting filter sized for `expected_entries`.
26    pub fn new(expected_entries: usize) -> Self {
27        let bit_count = expected_entries.saturating_mul(10).max(64) as u32;
28        // 4 bits per cell -> bytes = (bit_count + 1) / 2 (round up).
29        let bytes = (bit_count as usize).div_ceil(2);
30        Self {
31            bit_count,
32            k: 7,
33            cells: vec![0u8; bytes],
34        }
35    }
36
37    pub fn bit_count(&self) -> u32 {
38        self.bit_count
39    }
40    pub fn k(&self) -> u32 {
41        self.k
42    }
43
44    /// Add a key. Increments the per-cell 4-bit counter at each of the
45    /// `k` positions, saturating at 15.
46    pub fn add(&mut self, key: &str) {
47        let (h1, h2) = self.hash_pair(key);
48        for i in 0..self.k {
49            let idx = h1.wrapping_add(i.wrapping_mul(h2)) % self.bit_count;
50            self.incr(idx);
51        }
52    }
53
54    /// Probabilistic membership query. No false negatives - if the
55    /// key was added (and never removed enough to clear all `k`
56    /// counters), this returns `true`. False positives still occur at
57    /// the configured rate.
58    pub fn might_contain(&self, key: &str) -> bool {
59        let (h1, h2) = self.hash_pair(key);
60        for i in 0..self.k {
61            let idx = h1.wrapping_add(i.wrapping_mul(h2)) % self.bit_count;
62            if self.read(idx) == 0 {
63                return false;
64            }
65        }
66        true
67    }
68
69    /// Remove a key. Decrements each of the `k` counters. Cells that
70    /// were saturated (counter == 15) stay at 15 - they cannot be
71    /// decremented without risking false negatives for OTHER keys
72    /// that incremented them past the saturation point.
73    pub fn remove(&mut self, key: &str) {
74        let (h1, h2) = self.hash_pair(key);
75        for i in 0..self.k {
76            let idx = h1.wrapping_add(i.wrapping_mul(h2)) % self.bit_count;
77            self.decr(idx);
78        }
79    }
80
81    /// Zero every counter, keeping the allocation.
82    pub fn clear(&mut self) {
83        self.cells.fill(0);
84    }
85
86    fn hash_pair(&self, key: &str) -> (u32, u32) {
87        let h = fnv1a64(key);
88        let h1 = h as u32;
89        let h2 = ((h >> 32) as u32) | 1;
90        (h1, h2)
91    }
92
93    fn read(&self, idx: u32) -> u8 {
94        let byte = self.cells[(idx / 2) as usize];
95        if idx % 2 == 0 {
96            byte & 0x0f
97        } else {
98            (byte >> 4) & 0x0f
99        }
100    }
101
102    fn write_cell(&mut self, idx: u32, value: u8) {
103        let i = (idx / 2) as usize;
104        let v = value & 0x0f;
105        if idx % 2 == 0 {
106            self.cells[i] = (self.cells[i] & 0xf0) | v;
107        } else {
108            self.cells[i] = (self.cells[i] & 0x0f) | (v << 4);
109        }
110    }
111
112    fn incr(&mut self, idx: u32) {
113        let cur = self.read(idx);
114        if cur < 15 {
115            self.write_cell(idx, cur + 1);
116        }
117    }
118
119    fn decr(&mut self, idx: u32) {
120        let cur = self.read(idx);
121        // Don't decrement saturated cells - they may have been bumped
122        // past 15 by other keys; we can't tell, so we hold them.
123        if cur > 0 && cur < 15 {
124            self.write_cell(idx, cur - 1);
125        }
126    }
127}
128
129// Keep the imports used by the file (silences unused-import warnings
130// in builds where only one of the related items is referenced).
131const _: u64 = FNV_PRIME;
132const _: u64 = FNV_OFFSET;
133
134#[cfg(test)]
135#[path = "counting_tests.rs"]
136mod tests;
subms_bloom_filter/features/counting.rs

subms_bloom_filter/features/
counting.rs
