Skip to main content

CountingBloomFilter

subms_bloom_filter::features::counting

Struct CountingBloomFilter 

Source 
pub struct CountingBloomFilter { /* private fields */ }

Implementations§

Source§

impl CountingBloomFilter

Source

pub fn new(expected_entries: usize) -> Self

Build an empty counting filter sized for expected_entries.

Examples found in repository?
examples/sample_app.rs (line 112)
109fn counting_session_set() {
110    use subms_bloom_filter::CountingBloomFilter;
111    println!("\n== counting: active sessions with logout ==");
112    let mut sessions = CountingBloomFilter::new(1_000);
113    for s in ["sess-alice", "sess-bob", "sess-carol"] {
114        sessions.add(s);
115    }
116    println!("  bob active?   {}", sessions.might_contain("sess-bob"));
117    sessions.remove("sess-bob"); // logout
118    println!("  bob after logout? {}", sessions.might_contain("sess-bob"));
119    assert!(
120        sessions.might_contain("sess-alice"),
121        "other sessions untouched"
122    );
123}
More examples
Hide additional examples
examples/perf_features.rs (line 92)
70fn main() -> io::Result<()> {
71    let ks = keys();
72    let canon = SIZES[SIZES.len() - 1];
73
74    let path = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
75        .join("..")
76        .join(".subms")
77        .join("features")
78        .join("rust.json");
79    let existing = std::fs::read_to_string(&path).unwrap_or_default();
80    let mut manifest = SubMsFeatureManifest::load_str("rust", &existing);
81    // Stamp the box these numbers came from. The bench runs wherever it is
82    // invoked, so an unstamped manifest is indistinguishable from a fleet
83    // capture; the renderer will not publish one it cannot attribute.
84    let (source, instance) = SubMsP99Source::from_env();
85    manifest.set_p99_source(source, instance.as_deref());
86
87    // ---------- counting: adds remove() over 4-bit counters ----------
88    #[cfg(feature = "counting")]
89    {
90        use subms_bloom_filter::CountingBloomFilter;
91        let fill = |n: usize| {
92            let mut c = CountingBloomFilter::new(n);
93            for k in &ks[..n] {
94                c.add(k);
95            }
96            c
97        };
98        let sweep: Vec<(usize, u64)> = SIZES
99            .iter()
100            .map(|&n| {
101                (
102                    n,
103                    probe_p99(n, || fill(n), |c, k| _ = c.might_contain(k), &ks),
104                )
105            })
106            .collect();
107        let (cat, reason) = classify_feature(&sweep, None, None);
108        let mut p99 = BTreeMap::new();
109        p99.insert("contains".to_string(), sweep.last().unwrap().1);
110        p99.insert(
111            "add".to_string(),
112            mutate_p99(
113                canon,
114                || CountingBloomFilter::new(canon),
115                |c, k| c.add(k),
116                &ks,
117            ),
118        );
119        p99.insert(
120            "remove".to_string(),
121            mutate_p99(canon, || fill(canon), |c, k| c.remove(k), &ks),
122        );
123        manifest.set_feature("counting", cat, &p99, &reason);
124    }
125
126    // ---------- scalable: layered add, hit walks layers ----------
127    #[cfg(feature = "scalable")]
128    {
129        use subms_bloom_filter::ScalableBloomFilter;
130        let fill = |n: usize| {
131            let mut s = ScalableBloomFilter::new(1_000);
132            for k in &ks[..n] {
133                s.add(k);
134            }
135            s
136        };
137        let sweep: Vec<(usize, u64)> = SIZES
138            .iter()
139            .map(|&n| {
140                (
141                    n,
142                    probe_p99(n, || fill(n), |s, k| _ = s.might_contain(k), &ks),
143                )
144            })
145            .collect();
146        let (cat, reason) = classify_feature(&sweep, None, None);
147        let mut p99 = BTreeMap::new();
148        p99.insert("contains".to_string(), sweep.last().unwrap().1);
149        p99.insert(
150            "add".to_string(),
151            mutate_p99(
152                canon,
153                || ScalableBloomFilter::new(1_000),
154                |s, k| s.add(k),
155                &ks,
156            ),
157        );
158        manifest.set_feature("scalable", cat, &p99, &reason);
159    }
160
161    // ---------- partitioned: k independent slices ----------
162    #[cfg(feature = "partitioned")]
163    {
164        use subms_bloom_filter::PartitionedBloomFilter;
165        let fill = |n: usize| {
166            let mut p = PartitionedBloomFilter::new(n);
167            for k in &ks[..n] {
168                p.add(k);
169            }
170            p
171        };
172        let sweep: Vec<(usize, u64)> = SIZES
173            .iter()
174            .map(|&n| {
175                (
176                    n,
177                    probe_p99(n, || fill(n), |p, k| _ = p.might_contain(k), &ks),
178                )
179            })
180            .collect();
181        let (cat, reason) = classify_feature(&sweep, None, None);
182        let mut p99 = BTreeMap::new();
183        p99.insert("contains".to_string(), sweep.last().unwrap().1);
184        p99.insert(
185            "add".to_string(),
186            mutate_p99(
187                canon,
188                || PartitionedBloomFilter::new(canon),
189                |p, k| p.add(k),
190                &ks,
191            ),
192        );
193        manifest.set_feature("partitioned", cat, &p99, &reason);
194    }
195
196    // ---------- serde: derive only, no hot-path workload -> auxiliary ----------
197    #[cfg(feature = "serde")]
198    {
199        let (cat, reason) = classify_feature(&[], None, None);
200        manifest.set_feature("serde", cat, &BTreeMap::new(), &reason);
201    }
202
203    std::fs::create_dir_all(path.parent().unwrap())?;
204    std::fs::write(&path, manifest.to_json())?;
205    io::stdout().write_all(manifest.to_json().as_bytes())?;
206    Ok(())
207}
Source

pub fn bit_count(&self) -> u32

Source

pub fn k(&self) -> u32

Source

pub fn add(&mut self, key: &str)

Add a key. Increments the per-cell 4-bit counter at each of the k positions, saturating at 15.

Examples found in repository?
examples/sample_app.rs (line 114)
109fn counting_session_set() {
110    use subms_bloom_filter::CountingBloomFilter;
111    println!("\n== counting: active sessions with logout ==");
112    let mut sessions = CountingBloomFilter::new(1_000);
113    for s in ["sess-alice", "sess-bob", "sess-carol"] {
114        sessions.add(s);
115    }
116    println!("  bob active?   {}", sessions.might_contain("sess-bob"));
117    sessions.remove("sess-bob"); // logout
118    println!("  bob after logout? {}", sessions.might_contain("sess-bob"));
119    assert!(
120        sessions.might_contain("sess-alice"),
121        "other sessions untouched"
122    );
123}
More examples
Hide additional examples
examples/perf_features.rs (line 94)
70fn main() -> io::Result<()> {
71    let ks = keys();
72    let canon = SIZES[SIZES.len() - 1];
73
74    let path = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
75        .join("..")
76        .join(".subms")
77        .join("features")
78        .join("rust.json");
79    let existing = std::fs::read_to_string(&path).unwrap_or_default();
80    let mut manifest = SubMsFeatureManifest::load_str("rust", &existing);
81    // Stamp the box these numbers came from. The bench runs wherever it is
82    // invoked, so an unstamped manifest is indistinguishable from a fleet
83    // capture; the renderer will not publish one it cannot attribute.
84    let (source, instance) = SubMsP99Source::from_env();
85    manifest.set_p99_source(source, instance.as_deref());
86
87    // ---------- counting: adds remove() over 4-bit counters ----------
88    #[cfg(feature = "counting")]
89    {
90        use subms_bloom_filter::CountingBloomFilter;
91        let fill = |n: usize| {
92            let mut c = CountingBloomFilter::new(n);
93            for k in &ks[..n] {
94                c.add(k);
95            }
96            c
97        };
98        let sweep: Vec<(usize, u64)> = SIZES
99            .iter()
100            .map(|&n| {
101                (
102                    n,
103                    probe_p99(n, || fill(n), |c, k| _ = c.might_contain(k), &ks),
104                )
105            })
106            .collect();
107        let (cat, reason) = classify_feature(&sweep, None, None);
108        let mut p99 = BTreeMap::new();
109        p99.insert("contains".to_string(), sweep.last().unwrap().1);
110        p99.insert(
111            "add".to_string(),
112            mutate_p99(
113                canon,
114                || CountingBloomFilter::new(canon),
115                |c, k| c.add(k),
116                &ks,
117            ),
118        );
119        p99.insert(
120            "remove".to_string(),
121            mutate_p99(canon, || fill(canon), |c, k| c.remove(k), &ks),
122        );
123        manifest.set_feature("counting", cat, &p99, &reason);
124    }
125
126    // ---------- scalable: layered add, hit walks layers ----------
127    #[cfg(feature = "scalable")]
128    {
129        use subms_bloom_filter::ScalableBloomFilter;
130        let fill = |n: usize| {
131            let mut s = ScalableBloomFilter::new(1_000);
132            for k in &ks[..n] {
133                s.add(k);
134            }
135            s
136        };
137        let sweep: Vec<(usize, u64)> = SIZES
138            .iter()
139            .map(|&n| {
140                (
141                    n,
142                    probe_p99(n, || fill(n), |s, k| _ = s.might_contain(k), &ks),
143                )
144            })
145            .collect();
146        let (cat, reason) = classify_feature(&sweep, None, None);
147        let mut p99 = BTreeMap::new();
148        p99.insert("contains".to_string(), sweep.last().unwrap().1);
149        p99.insert(
150            "add".to_string(),
151            mutate_p99(
152                canon,
153                || ScalableBloomFilter::new(1_000),
154                |s, k| s.add(k),
155                &ks,
156            ),
157        );
158        manifest.set_feature("scalable", cat, &p99, &reason);
159    }
160
161    // ---------- partitioned: k independent slices ----------
162    #[cfg(feature = "partitioned")]
163    {
164        use subms_bloom_filter::PartitionedBloomFilter;
165        let fill = |n: usize| {
166            let mut p = PartitionedBloomFilter::new(n);
167            for k in &ks[..n] {
168                p.add(k);
169            }
170            p
171        };
172        let sweep: Vec<(usize, u64)> = SIZES
173            .iter()
174            .map(|&n| {
175                (
176                    n,
177                    probe_p99(n, || fill(n), |p, k| _ = p.might_contain(k), &ks),
178                )
179            })
180            .collect();
181        let (cat, reason) = classify_feature(&sweep, None, None);
182        let mut p99 = BTreeMap::new();
183        p99.insert("contains".to_string(), sweep.last().unwrap().1);
184        p99.insert(
185            "add".to_string(),
186            mutate_p99(
187                canon,
188                || PartitionedBloomFilter::new(canon),
189                |p, k| p.add(k),
190                &ks,
191            ),
192        );
193        manifest.set_feature("partitioned", cat, &p99, &reason);
194    }
195
196    // ---------- serde: derive only, no hot-path workload -> auxiliary ----------
197    #[cfg(feature = "serde")]
198    {
199        let (cat, reason) = classify_feature(&[], None, None);
200        manifest.set_feature("serde", cat, &BTreeMap::new(), &reason);
201    }
202
203    std::fs::create_dir_all(path.parent().unwrap())?;
204    std::fs::write(&path, manifest.to_json())?;
205    io::stdout().write_all(manifest.to_json().as_bytes())?;
206    Ok(())
207}
Source

pub fn might_contain(&self, key: &str) -> bool

Probabilistic membership query. No false negatives - if the key was added (and never removed enough to clear all k counters), this returns true. False positives still occur at the configured rate.

Examples found in repository?
examples/sample_app.rs (line 116)
109fn counting_session_set() {
110    use subms_bloom_filter::CountingBloomFilter;
111    println!("\n== counting: active sessions with logout ==");
112    let mut sessions = CountingBloomFilter::new(1_000);
113    for s in ["sess-alice", "sess-bob", "sess-carol"] {
114        sessions.add(s);
115    }
116    println!("  bob active?   {}", sessions.might_contain("sess-bob"));
117    sessions.remove("sess-bob"); // logout
118    println!("  bob after logout? {}", sessions.might_contain("sess-bob"));
119    assert!(
120        sessions.might_contain("sess-alice"),
121        "other sessions untouched"
122    );
123}
More examples
Hide additional examples
examples/perf_features.rs (line 103)
70fn main() -> io::Result<()> {
71    let ks = keys();
72    let canon = SIZES[SIZES.len() - 1];
73
74    let path = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
75        .join("..")
76        .join(".subms")
77        .join("features")
78        .join("rust.json");
79    let existing = std::fs::read_to_string(&path).unwrap_or_default();
80    let mut manifest = SubMsFeatureManifest::load_str("rust", &existing);
81    // Stamp the box these numbers came from. The bench runs wherever it is
82    // invoked, so an unstamped manifest is indistinguishable from a fleet
83    // capture; the renderer will not publish one it cannot attribute.
84    let (source, instance) = SubMsP99Source::from_env();
85    manifest.set_p99_source(source, instance.as_deref());
86
87    // ---------- counting: adds remove() over 4-bit counters ----------
88    #[cfg(feature = "counting")]
89    {
90        use subms_bloom_filter::CountingBloomFilter;
91        let fill = |n: usize| {
92            let mut c = CountingBloomFilter::new(n);
93            for k in &ks[..n] {
94                c.add(k);
95            }
96            c
97        };
98        let sweep: Vec<(usize, u64)> = SIZES
99            .iter()
100            .map(|&n| {
101                (
102                    n,
103                    probe_p99(n, || fill(n), |c, k| _ = c.might_contain(k), &ks),
104                )
105            })
106            .collect();
107        let (cat, reason) = classify_feature(&sweep, None, None);
108        let mut p99 = BTreeMap::new();
109        p99.insert("contains".to_string(), sweep.last().unwrap().1);
110        p99.insert(
111            "add".to_string(),
112            mutate_p99(
113                canon,
114                || CountingBloomFilter::new(canon),
115                |c, k| c.add(k),
116                &ks,
117            ),
118        );
119        p99.insert(
120            "remove".to_string(),
121            mutate_p99(canon, || fill(canon), |c, k| c.remove(k), &ks),
122        );
123        manifest.set_feature("counting", cat, &p99, &reason);
124    }
125
126    // ---------- scalable: layered add, hit walks layers ----------
127    #[cfg(feature = "scalable")]
128    {
129        use subms_bloom_filter::ScalableBloomFilter;
130        let fill = |n: usize| {
131            let mut s = ScalableBloomFilter::new(1_000);
132            for k in &ks[..n] {
133                s.add(k);
134            }
135            s
136        };
137        let sweep: Vec<(usize, u64)> = SIZES
138            .iter()
139            .map(|&n| {
140                (
141                    n,
142                    probe_p99(n, || fill(n), |s, k| _ = s.might_contain(k), &ks),
143                )
144            })
145            .collect();
146        let (cat, reason) = classify_feature(&sweep, None, None);
147        let mut p99 = BTreeMap::new();
148        p99.insert("contains".to_string(), sweep.last().unwrap().1);
149        p99.insert(
150            "add".to_string(),
151            mutate_p99(
152                canon,
153                || ScalableBloomFilter::new(1_000),
154                |s, k| s.add(k),
155                &ks,
156            ),
157        );
158        manifest.set_feature("scalable", cat, &p99, &reason);
159    }
160
161    // ---------- partitioned: k independent slices ----------
162    #[cfg(feature = "partitioned")]
163    {
164        use subms_bloom_filter::PartitionedBloomFilter;
165        let fill = |n: usize| {
166            let mut p = PartitionedBloomFilter::new(n);
167            for k in &ks[..n] {
168                p.add(k);
169            }
170            p
171        };
172        let sweep: Vec<(usize, u64)> = SIZES
173            .iter()
174            .map(|&n| {
175                (
176                    n,
177                    probe_p99(n, || fill(n), |p, k| _ = p.might_contain(k), &ks),
178                )
179            })
180            .collect();
181        let (cat, reason) = classify_feature(&sweep, None, None);
182        let mut p99 = BTreeMap::new();
183        p99.insert("contains".to_string(), sweep.last().unwrap().1);
184        p99.insert(
185            "add".to_string(),
186            mutate_p99(
187                canon,
188                || PartitionedBloomFilter::new(canon),
189                |p, k| p.add(k),
190                &ks,
191            ),
192        );
193        manifest.set_feature("partitioned", cat, &p99, &reason);
194    }
195
196    // ---------- serde: derive only, no hot-path workload -> auxiliary ----------
197    #[cfg(feature = "serde")]
198    {
199        let (cat, reason) = classify_feature(&[], None, None);
200        manifest.set_feature("serde", cat, &BTreeMap::new(), &reason);
201    }
202
203    std::fs::create_dir_all(path.parent().unwrap())?;
204    std::fs::write(&path, manifest.to_json())?;
205    io::stdout().write_all(manifest.to_json().as_bytes())?;
206    Ok(())
207}
Source

pub fn remove(&mut self, key: &str)

Remove a key. Decrements each of the k counters. Cells that were saturated (counter == 15) stay at 15 - they cannot be decremented without risking false negatives for OTHER keys that incremented them past the saturation point.

Examples found in repository?
examples/sample_app.rs (line 117)
109fn counting_session_set() {
110    use subms_bloom_filter::CountingBloomFilter;
111    println!("\n== counting: active sessions with logout ==");
112    let mut sessions = CountingBloomFilter::new(1_000);
113    for s in ["sess-alice", "sess-bob", "sess-carol"] {
114        sessions.add(s);
115    }
116    println!("  bob active?   {}", sessions.might_contain("sess-bob"));
117    sessions.remove("sess-bob"); // logout
118    println!("  bob after logout? {}", sessions.might_contain("sess-bob"));
119    assert!(
120        sessions.might_contain("sess-alice"),
121        "other sessions untouched"
122    );
123}
More examples
Hide additional examples
examples/perf_features.rs (line 121)
70fn main() -> io::Result<()> {
71    let ks = keys();
72    let canon = SIZES[SIZES.len() - 1];
73
74    let path = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
75        .join("..")
76        .join(".subms")
77        .join("features")
78        .join("rust.json");
79    let existing = std::fs::read_to_string(&path).unwrap_or_default();
80    let mut manifest = SubMsFeatureManifest::load_str("rust", &existing);
81    // Stamp the box these numbers came from. The bench runs wherever it is
82    // invoked, so an unstamped manifest is indistinguishable from a fleet
83    // capture; the renderer will not publish one it cannot attribute.
84    let (source, instance) = SubMsP99Source::from_env();
85    manifest.set_p99_source(source, instance.as_deref());
86
87    // ---------- counting: adds remove() over 4-bit counters ----------
88    #[cfg(feature = "counting")]
89    {
90        use subms_bloom_filter::CountingBloomFilter;
91        let fill = |n: usize| {
92            let mut c = CountingBloomFilter::new(n);
93            for k in &ks[..n] {
94                c.add(k);
95            }
96            c
97        };
98        let sweep: Vec<(usize, u64)> = SIZES
99            .iter()
100            .map(|&n| {
101                (
102                    n,
103                    probe_p99(n, || fill(n), |c, k| _ = c.might_contain(k), &ks),
104                )
105            })
106            .collect();
107        let (cat, reason) = classify_feature(&sweep, None, None);
108        let mut p99 = BTreeMap::new();
109        p99.insert("contains".to_string(), sweep.last().unwrap().1);
110        p99.insert(
111            "add".to_string(),
112            mutate_p99(
113                canon,
114                || CountingBloomFilter::new(canon),
115                |c, k| c.add(k),
116                &ks,
117            ),
118        );
119        p99.insert(
120            "remove".to_string(),
121            mutate_p99(canon, || fill(canon), |c, k| c.remove(k), &ks),
122        );
123        manifest.set_feature("counting", cat, &p99, &reason);
124    }
125
126    // ---------- scalable: layered add, hit walks layers ----------
127    #[cfg(feature = "scalable")]
128    {
129        use subms_bloom_filter::ScalableBloomFilter;
130        let fill = |n: usize| {
131            let mut s = ScalableBloomFilter::new(1_000);
132            for k in &ks[..n] {
133                s.add(k);
134            }
135            s
136        };
137        let sweep: Vec<(usize, u64)> = SIZES
138            .iter()
139            .map(|&n| {
140                (
141                    n,
142                    probe_p99(n, || fill(n), |s, k| _ = s.might_contain(k), &ks),
143                )
144            })
145            .collect();
146        let (cat, reason) = classify_feature(&sweep, None, None);
147        let mut p99 = BTreeMap::new();
148        p99.insert("contains".to_string(), sweep.last().unwrap().1);
149        p99.insert(
150            "add".to_string(),
151            mutate_p99(
152                canon,
153                || ScalableBloomFilter::new(1_000),
154                |s, k| s.add(k),
155                &ks,
156            ),
157        );
158        manifest.set_feature("scalable", cat, &p99, &reason);
159    }
160
161    // ---------- partitioned: k independent slices ----------
162    #[cfg(feature = "partitioned")]
163    {
164        use subms_bloom_filter::PartitionedBloomFilter;
165        let fill = |n: usize| {
166            let mut p = PartitionedBloomFilter::new(n);
167            for k in &ks[..n] {
168                p.add(k);
169            }
170            p
171        };
172        let sweep: Vec<(usize, u64)> = SIZES
173            .iter()
174            .map(|&n| {
175                (
176                    n,
177                    probe_p99(n, || fill(n), |p, k| _ = p.might_contain(k), &ks),
178                )
179            })
180            .collect();
181        let (cat, reason) = classify_feature(&sweep, None, None);
182        let mut p99 = BTreeMap::new();
183        p99.insert("contains".to_string(), sweep.last().unwrap().1);
184        p99.insert(
185            "add".to_string(),
186            mutate_p99(
187                canon,
188                || PartitionedBloomFilter::new(canon),
189                |p, k| p.add(k),
190                &ks,
191            ),
192        );
193        manifest.set_feature("partitioned", cat, &p99, &reason);
194    }
195
196    // ---------- serde: derive only, no hot-path workload -> auxiliary ----------
197    #[cfg(feature = "serde")]
198    {
199        let (cat, reason) = classify_feature(&[], None, None);
200        manifest.set_feature("serde", cat, &BTreeMap::new(), &reason);
201    }
202
203    std::fs::create_dir_all(path.parent().unwrap())?;
204    std::fs::write(&path, manifest.to_json())?;
205    io::stdout().write_all(manifest.to_json().as_bytes())?;
206    Ok(())
207}
Source

pub fn clear(&mut self)

Zero every counter, keeping the allocation.

Trait Implementations§

Source§

impl<'de> Deserialize<'de> for CountingBloomFilter

Source§

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>
where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer. Read more
Source§

impl Serialize for CountingBloomFilter

Source§

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>
where __S: Serializer,

Serialize this value into the given Serde serializer. Read more

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> DeserializeOwned for T
where T: for<'de> Deserialize<'de>,

Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.