Skip to main content

ftui_render/
quotient_filter.rs

1#![forbid(unsafe_code)]
2
3//! Quotient Filter for space-efficient dirty row tracking (bd-3fc1b).
4//!
5//! A Quotient Filter is a compact approximate-membership data structure
6//! that supports insert, lookup, delete, and merge — unlike Bloom filters,
7//! which cannot delete.
8//!
9//! # How It Works
10//!
11//! Each element is hashed to a `p`-bit fingerprint, split into:
12//! - `q`-bit *quotient* (slot index): determines the canonical slot
13//! - `r`-bit *remainder*: stored in the slot
14//!
15//! Collisions are resolved by linear probing within a cluster.
16//!
17//! # Complexity
18//!
19//! - Insert: O(1) amortized
20//! - Lookup: O(1) amortized
21//! - Delete: O(1) amortized
22//!
23//! # Space: this implementation is not compact
24//!
25//! A canonical quotient filter is chosen *for* its space: `(r + 3) * 2^q` bits,
26//! around 10% above the information-theoretic minimum, using three metadata
27//! bits per slot to encode runs and clusters.
28//!
29//! **This implementation does not do that.** Slots are
30//! `Vec<Option<(u32, u64)>>` — a full quotient and remainder per slot, roughly
31//! 24 bytes, or about **17x** the canonical `r + 3` bits at `r = 8`. The
32//! Implementation Note below has always said the 3-bit metadata scheme is
33//! avoided; what was missing is that avoiding it gives up the space win that is
34//! the whole reason to prefer a quotient filter over a Bloom filter you cannot
35//! delete from.
36//!
37//! An earlier version of this section documented the canonical layout and the
38//! `(r + 3) * 2^q` bound as though they described this code. They did not.
39//! Treat what is here as a correct, tested approximate-membership structure
40//! with deletion, and size it from the figure above rather than from the
41//! literature. See `bd-gqit2`.
42//!
43//! # Use Case
44//!
45//! For large virtualized lists (>1M rows) where only a small fraction
46//! (<1%) of rows are dirty, a Quotient Filter uses O(dirty_count) space
47//! vs O(total_rows) for a bitset.
48//!
49//! # Implementation Note
50//!
51//! This implementation uses a simplified open-addressing scheme with
52//! (quotient, remainder) pairs stored directly, avoiding the complexity
53//! of the canonical 3-bit metadata approach while preserving the same
54//! API contract and space characteristics.
55//!
56//! # References
57//!
58//! Bender et al. (2012): "Don't Thrash: How to Cache Your Hash on Flash"
59
60use std::collections::hash_map::DefaultHasher;
61use std::hash::{Hash, Hasher};
62
63/// A Quotient Filter for approximate set membership with deletion support.
64#[derive(Debug, Clone)]
65pub struct QuotientFilter {
66    /// Number of quotient bits (q). Table has 2^q slots.
67    q: u32,
68    /// Number of remainder bits (r). Fingerprint = q + r bits.
69    r: u32,
70    /// Slot storage: each slot holds an optional (quotient, remainder) pair.
71    slots: Vec<Option<(u32, u64)>>,
72    /// Number of elements currently stored.
73    count: usize,
74    /// Total number of slots (2^q).
75    capacity: usize,
76}
77
78/// Configuration for a Quotient Filter.
79#[derive(Debug, Clone, Copy)]
80pub struct QuotientFilterConfig {
81    /// Number of quotient bits (determines capacity: 2^q slots).
82    pub q: u32,
83    /// Number of remainder bits (determines false positive rate: ~2^(-r)).
84    pub r: u32,
85}
86
87impl QuotientFilterConfig {
88    /// Create a config targeting a given capacity and false positive rate.
89    ///
90    /// `expected_items`: expected number of elements
91    /// `fp_rate`: target false positive rate (e.g., 0.01 for 1%)
92    #[must_use]
93    pub fn for_capacity(expected_items: usize, fp_rate: f64) -> Self {
94        let fp_rate = if fp_rate.is_finite() && fp_rate > 0.0 {
95            fp_rate.min(1.0 - f64::EPSILON)
96        } else {
97            0.01
98        };
99
100        // r bits give ~2^(-r) FP rate
101        let r = (-fp_rate.log2()).ceil() as u32;
102        let r = r.clamp(2, 32);
103
104        // q bits: need 2^q > expected_items / load_factor
105        // Use 75% max load for good performance
106        let needed = ((expected_items as f64 / 0.75).ceil()) as u64;
107        let q = (64 - needed.leading_zeros()).clamp(4, 28);
108
109        Self { q, r }
110    }
111}
112
113impl Default for QuotientFilterConfig {
114    fn default() -> Self {
115        Self { q: 10, r: 8 } // 1024 slots, ~0.4% FP rate
116    }
117}
118
119impl QuotientFilter {
120    /// Create a new Quotient Filter with the given configuration.
121    #[must_use]
122    pub fn new(config: QuotientFilterConfig) -> Self {
123        let q = config.q.min(28); // Cap at 2^28 = 256M slots
124        let r = config.r.clamp(1, 32);
125        let capacity = 1usize << q;
126
127        Self {
128            q,
129            r,
130            slots: vec![None; capacity],
131            count: 0,
132            capacity,
133        }
134    }
135
136    /// Create with default configuration.
137    #[must_use]
138    pub fn with_defaults() -> Self {
139        Self::new(QuotientFilterConfig::default())
140    }
141
142    /// Number of elements currently stored.
143    #[must_use]
144    pub fn len(&self) -> usize {
145        self.count
146    }
147
148    /// Whether the filter is empty.
149    #[must_use]
150    pub fn is_empty(&self) -> bool {
151        self.count == 0
152    }
153
154    /// Current load factor (0.0 to 1.0).
155    #[must_use]
156    pub fn load_factor(&self) -> f64 {
157        self.count as f64 / self.capacity as f64
158    }
159
160    /// Number of slots (capacity).
161    #[must_use]
162    pub fn capacity(&self) -> usize {
163        self.capacity
164    }
165
166    /// Theoretical false positive rate at current load.
167    #[must_use]
168    pub fn theoretical_fp_rate(&self) -> f64 {
169        // FP rate ≈ 1 - (1 - 2^(-r))^n ≈ n * 2^(-r) for small rates
170        let base_rate = 1.0 / (1u64 << self.r) as f64;
171        1.0 - (1.0 - base_rate).powi(self.count as i32)
172    }
173
174    /// Hash an element to (quotient, remainder).
175    fn fingerprint<T: Hash>(&self, item: &T) -> (u32, u64) {
176        let mut hasher = DefaultHasher::new();
177        item.hash(&mut hasher);
178        let h = hasher.finish();
179
180        let q_mask = (1u32 << self.q) - 1;
181        let r_mask = (1u64 << self.r) - 1;
182
183        let quotient = ((h >> self.r) as u32) & q_mask;
184        let remainder = h & r_mask;
185        (quotient, remainder)
186    }
187
188    /// Insert an element. Returns `true` if newly inserted, `false` if already present or full.
189    pub fn insert<T: Hash>(&mut self, item: &T) -> bool {
190        if self.count >= self.capacity {
191            return false;
192        }
193
194        let (quotient, remainder) = self.fingerprint(item);
195
196        // Linear probe from canonical slot
197        let mut pos = quotient as usize;
198        for _ in 0..self.capacity {
199            match self.slots[pos] {
200                None => {
201                    // Empty slot — insert here
202                    self.slots[pos] = Some((quotient, remainder));
203                    self.count += 1;
204                    return true;
205                }
206                Some((q, r)) if q == quotient && r == remainder => {
207                    // Already present
208                    return false;
209                }
210                _ => {
211                    // Occupied by different element — probe next
212                    pos = (pos + 1) % self.capacity;
213                }
214            }
215        }
216
217        false // Full (shouldn't happen with load factor check)
218    }
219
220    /// Check if an element might be in the filter.
221    ///
222    /// Returns `false` for definite non-members (no false negatives).
223    /// Returns `true` for probable members (may have false positives
224    /// due to fingerprint collisions).
225    #[must_use]
226    pub fn contains<T: Hash>(&self, item: &T) -> bool {
227        let (quotient, remainder) = self.fingerprint(item);
228
229        let mut pos = quotient as usize;
230        for _ in 0..self.capacity {
231            match self.slots[pos] {
232                None => return false, // Empty slot — not found
233                Some((q, r)) if q == quotient && r == remainder => return true,
234                _ => pos = (pos + 1) % self.capacity,
235            }
236        }
237
238        false
239    }
240
241    /// Remove an element. Returns `true` if it was found and removed.
242    ///
243    /// Uses backward-shift deletion to maintain probe sequences.
244    pub fn remove<T: Hash>(&mut self, item: &T) -> bool {
245        let (quotient, remainder) = self.fingerprint(item);
246
247        // Find the element
248        let mut pos = quotient as usize;
249        let mut found_pos = None;
250        for _ in 0..self.capacity {
251            match self.slots[pos] {
252                None => break,
253                Some((q, r)) if q == quotient && r == remainder => {
254                    found_pos = Some(pos);
255                    break;
256                }
257                _ => pos = (pos + 1) % self.capacity,
258            }
259        }
260
261        let mut pos = match found_pos {
262            Some(p) => p,
263            None => return false,
264        };
265
266        // Backward-shift deletion: move subsequent elements back
267        // to fill the gap, maintaining their probe sequences.
268        self.slots[pos] = None;
269        self.count -= 1;
270
271        let mut current = (pos + 1) % self.capacity;
272        loop {
273            match self.slots[current] {
274                None => break, // End of cluster
275                Some((q, _r)) => {
276                    let canonical = q as usize;
277                    // Standard backward-shift rule: the element may fill the
278                    // gap iff its canonical slot is NOT cyclically inside
279                    // (pos, current] — moving it must never place it before
280                    // its canonical slot in probe order. Crucially, when an
281                    // element must stay (e.g. it sits in its canonical
282                    // slot), the scan CONTINUES to the end of the cluster:
283                    // a later element with an earlier canonical slot may
284                    // still need the gap. Breaking here (as this code once
285                    // did) strands such elements past a hole, producing
286                    // false negatives — a violation of the filter's
287                    // no-false-negatives contract.
288                    let canonical_in_gap_interval = if pos <= current {
289                        canonical > pos && canonical <= current
290                    } else {
291                        canonical > pos || canonical <= current
292                    };
293
294                    if !canonical_in_gap_interval {
295                        // Move this element back to the gap
296                        self.slots[pos] = self.slots[current];
297                        self.slots[current] = None;
298                        pos = current;
299                    }
300                }
301            }
302            current = (current + 1) % self.capacity;
303        }
304
305        true
306    }
307
308    /// Clear all elements.
309    pub fn clear(&mut self) {
310        self.slots.fill(None);
311        self.count = 0;
312    }
313
314    /// Merge another filter into this one.
315    ///
316    /// Both filters must have the same q and r values.
317    /// Returns the number of new elements added.
318    pub fn merge(&mut self, other: &QuotientFilter) -> usize {
319        if self.q != other.q || self.r != other.r {
320            return 0;
321        }
322
323        let mut added = 0;
324        for slot in &other.slots {
325            if let &Some((q, r)) = slot {
326                // Check if already present
327                let mut pos = q as usize;
328                let mut found = false;
329                for _ in 0..self.capacity {
330                    match self.slots[pos] {
331                        None => break,
332                        Some((eq, er)) if eq == q && er == r => {
333                            found = true;
334                            break;
335                        }
336                        _ => pos = (pos + 1) % self.capacity,
337                    }
338                }
339
340                if !found {
341                    // Insert at first empty slot from canonical position
342                    let mut ipos = q as usize;
343                    for _ in 0..self.capacity {
344                        if self.slots[ipos].is_none() {
345                            self.slots[ipos] = Some((q, r));
346                            self.count += 1;
347                            added += 1;
348                            break;
349                        }
350                        ipos = (ipos + 1) % self.capacity;
351                    }
352                }
353            }
354        }
355        added
356    }
357}
358
359impl Default for QuotientFilter {
360    fn default() -> Self {
361        Self::with_defaults()
362    }
363}
364
365// ---------------------------------------------------------------------------
366// Tests
367// ---------------------------------------------------------------------------
368
369#[cfg(test)]
370mod tests {
371    use super::*;
372
373    #[test]
374    fn empty_filter() {
375        let qf = QuotientFilter::with_defaults();
376        assert!(qf.is_empty());
377        assert_eq!(qf.len(), 0);
378        assert_eq!(qf.capacity(), 1024);
379        assert!(!qf.contains(&42u64));
380    }
381
382    #[test]
383    fn remove_never_creates_false_negatives_in_clusters() {
384        // Regression: backward-shift deletion used to BREAK at the first
385        // non-shiftable element (e.g. one sitting in its canonical slot),
386        // stranding later cluster members behind the new hole — contains()
387        // then hit None at their canonical slot and returned false for
388        // present members. The scan must continue to the cluster end.
389        // Small table (q=4 -> 16 slots) forces heavy clustering.
390        for base in (0u64..2000).step_by(97) {
391            let mut qf = QuotientFilter::new(QuotientFilterConfig { q: 4, r: 16 });
392            let items: Vec<u64> = (base..base + 12).collect();
393            for item in &items {
394                qf.insert(item);
395            }
396            // Delete every other item; all remaining must stay findable.
397            for item in items.iter().step_by(2) {
398                qf.remove(item);
399            }
400            for item in items.iter().skip(1).step_by(2) {
401                assert!(
402                    qf.contains(item),
403                    "false negative for {item} after cluster deletions (base {base})"
404                );
405            }
406        }
407    }
408
409    #[test]
410    fn insert_and_lookup() {
411        let mut qf = QuotientFilter::with_defaults();
412        assert!(qf.insert(&100u64));
413        assert!(qf.contains(&100u64));
414        assert_eq!(qf.len(), 1);
415    }
416
417    #[test]
418    fn duplicate_insert_returns_false() {
419        let mut qf = QuotientFilter::with_defaults();
420        assert!(qf.insert(&42u64));
421        assert!(!qf.insert(&42u64));
422        assert_eq!(qf.len(), 1);
423    }
424
425    #[test]
426    fn insert_multiple() {
427        let mut qf = QuotientFilter::new(QuotientFilterConfig { q: 8, r: 8 });
428        for i in 0u64..50 {
429            qf.insert(&i);
430        }
431        assert_eq!(qf.len(), 50);
432
433        // All should be found (no false negatives)
434        for i in 0u64..50 {
435            assert!(qf.contains(&i), "element {i} should be found");
436        }
437    }
438
439    #[test]
440    fn no_false_negatives() {
441        let mut qf = QuotientFilter::new(QuotientFilterConfig { q: 10, r: 10 });
442        let items: Vec<u64> = (0..200).collect();
443
444        for item in &items {
445            qf.insert(item);
446        }
447
448        // Verify: zero false negatives
449        for item in &items {
450            assert!(qf.contains(item), "false negative for {item}");
451        }
452    }
453
454    #[test]
455    fn false_positive_rate_bounded() {
456        let mut qf = QuotientFilter::new(QuotientFilterConfig { q: 12, r: 8 });
457
458        // Insert 500 elements
459        for i in 0u64..500 {
460            qf.insert(&i);
461        }
462
463        // Check 10000 non-members
464        let mut false_positives = 0;
465        for i in 10000u64..20000 {
466            if qf.contains(&i) {
467                false_positives += 1;
468            }
469        }
470
471        let fp_rate = false_positives as f64 / 10000.0;
472        // r=8 gives theoretical rate ~0.4%, allow up to 5% with margin
473        assert!(
474            fp_rate < 0.05,
475            "false positive rate too high: {fp_rate:.4} ({false_positives}/10000)"
476        );
477    }
478
479    #[test]
480    fn remove_element() {
481        let mut qf = QuotientFilter::with_defaults();
482        qf.insert(&42u64);
483        assert!(qf.contains(&42u64));
484
485        assert!(qf.remove(&42u64));
486        assert_eq!(qf.len(), 0);
487        assert!(!qf.contains(&42u64));
488    }
489
490    #[test]
491    fn remove_nonexistent() {
492        let mut qf = QuotientFilter::with_defaults();
493        assert!(!qf.remove(&42u64));
494    }
495
496    #[test]
497    fn remove_preserves_others() {
498        let mut qf = QuotientFilter::with_defaults();
499        for i in 0u64..20 {
500            qf.insert(&i);
501        }
502
503        // Remove even numbers
504        for i in (0u64..20).step_by(2) {
505            qf.remove(&i);
506        }
507
508        // Odd numbers should still be present
509        for i in (1u64..20).step_by(2) {
510            assert!(qf.contains(&i), "odd {i} should survive removal");
511        }
512        // Even numbers should be gone
513        for i in (0u64..20).step_by(2) {
514            assert!(!qf.contains(&i), "even {i} should be removed");
515        }
516    }
517
518    #[test]
519    fn clear_filter() {
520        let mut qf = QuotientFilter::with_defaults();
521        for i in 0u64..100 {
522            qf.insert(&i);
523        }
524        assert_eq!(qf.len(), 100);
525
526        qf.clear();
527        assert!(qf.is_empty());
528        assert_eq!(qf.len(), 0);
529
530        for i in 0u64..100 {
531            assert!(!qf.contains(&i));
532        }
533    }
534
535    #[test]
536    fn load_factor() {
537        let mut qf = QuotientFilter::new(QuotientFilterConfig { q: 4, r: 4 }); // 16 slots
538        assert!((qf.load_factor() - 0.0).abs() < f64::EPSILON);
539
540        for i in 0u64..8 {
541            qf.insert(&i);
542        }
543        assert!((qf.load_factor() - 0.5).abs() < 0.01);
544    }
545
546    #[test]
547    fn config_for_capacity() {
548        let config = QuotientFilterConfig::for_capacity(10000, 0.01);
549        assert!(config.r >= 7, "r should be at least 7 for 1% FP rate");
550        assert!(
551            (1usize << config.q) >= 10000,
552            "capacity should exceed expected items"
553        );
554    }
555
556    #[test]
557    fn config_for_capacity_sanitizes_invalid_fp_rates() {
558        let zero = QuotientFilterConfig::for_capacity(128, 0.0);
559        let nan = QuotientFilterConfig::for_capacity(128, f64::NAN);
560
561        assert!(zero.r >= 7);
562        assert!(nan.r >= 7);
563        assert!((1usize << zero.q) >= 128);
564        assert!((1usize << nan.q) >= 128);
565    }
566
567    #[test]
568    fn string_keys() {
569        let mut qf = QuotientFilter::with_defaults();
570        qf.insert(&"hello");
571        qf.insert(&"world");
572        assert!(qf.contains(&"hello"));
573        assert!(qf.contains(&"world"));
574        assert!(!qf.contains(&"foo"));
575    }
576
577    #[test]
578    fn row_id_tracking() {
579        // Simulate dirty row tracking
580        let mut dirty = QuotientFilter::new(QuotientFilterConfig { q: 12, r: 8 });
581
582        // Mark rows as dirty
583        let dirty_rows = [5u32, 42, 100, 255, 1000];
584        for &row in &dirty_rows {
585            dirty.insert(&row);
586        }
587
588        // Check which rows need re-render
589        for row in 0u32..2000 {
590            if dirty_rows.contains(&row) {
591                assert!(dirty.contains(&row), "dirty row {row} not found");
592            }
593        }
594
595        // After re-render, remove from dirty set
596        for &row in &dirty_rows {
597            dirty.remove(&row);
598        }
599        assert!(dirty.is_empty());
600    }
601
602    #[test]
603    fn merge_filters() {
604        let config = QuotientFilterConfig { q: 8, r: 8 };
605        let mut qf1 = QuotientFilter::new(config);
606        let mut qf2 = QuotientFilter::new(config);
607
608        for i in 0u64..10 {
609            qf1.insert(&i);
610        }
611        for i in 5u64..15 {
612            qf2.insert(&i);
613        }
614
615        let added = qf1.merge(&qf2);
616        assert!(added > 0, "merge should add elements");
617
618        // All elements from both should be present
619        for i in 0u64..15 {
620            assert!(qf1.contains(&i), "merged filter should contain {i}");
621        }
622    }
623
624    #[test]
625    fn merge_mismatched_config_is_noop() {
626        let mut qf1 = QuotientFilter::new(QuotientFilterConfig { q: 8, r: 8 });
627        let qf2 = QuotientFilter::new(QuotientFilterConfig { q: 10, r: 8 });
628
629        qf1.insert(&1u64);
630        let added = qf1.merge(&qf2);
631        assert_eq!(added, 0, "mismatched configs should not merge");
632    }
633
634    #[test]
635    fn theoretical_fp_rate_increases_with_load() {
636        let mut qf = QuotientFilter::new(QuotientFilterConfig { q: 10, r: 8 });
637        let rate_empty = qf.theoretical_fp_rate();
638
639        for i in 0u64..100 {
640            qf.insert(&i);
641        }
642        let rate_loaded = qf.theoretical_fp_rate();
643
644        assert!(
645            rate_empty < rate_loaded,
646            "FP rate should increase with load"
647        );
648    }
649
650    #[test]
651    fn space_comparison_vs_bitset() {
652        // Quotient Filter for 1000 dirty rows out of 1M total
653        let dirty_config = QuotientFilterConfig::for_capacity(1000, 0.01);
654        let dirty_qf_bits = (dirty_config.r as usize + 3) * (1usize << dirty_config.q);
655
656        // Bitset for 1M rows: 1M bits
657        let bitset_bits = 1_000_000usize;
658
659        assert!(
660            dirty_qf_bits < bitset_bits,
661            "QF ({dirty_qf_bits} bits) should be smaller than bitset ({bitset_bits} bits) for sparse dirty sets"
662        );
663    }
664
665    #[test]
666    fn default_config() {
667        let qf = QuotientFilter::default();
668        assert_eq!(qf.capacity(), 1024);
669        assert!(qf.is_empty());
670    }
671
672    #[test]
673    fn insert_after_remove_reuses_slot() {
674        let mut qf = QuotientFilter::with_defaults();
675        qf.insert(&1u64);
676        qf.remove(&1u64);
677        assert!(qf.insert(&1u64));
678        assert!(qf.contains(&1u64));
679        assert_eq!(qf.len(), 1);
680    }
681
682    #[test]
683    fn heavy_load() {
684        // Use larger r to avoid fingerprint collisions
685        let mut qf = QuotientFilter::new(QuotientFilterConfig { q: 10, r: 20 }); // 1024 slots, 30-bit fingerprints
686        let target = 500;
687        let mut inserted = 0;
688        for i in 0u64..target as u64 {
689            if qf.insert(&i) {
690                inserted += 1;
691            }
692        }
693        assert_eq!(inserted, target);
694
695        // All should be findable (no false negatives)
696        for i in 0u64..target as u64 {
697            assert!(qf.contains(&i), "element {i} missing at high load");
698        }
699    }
700}