1#![forbid(unsafe_code)]
2
3use std::collections::hash_map::DefaultHasher;
61use std::hash::{Hash, Hasher};
62
63#[derive(Debug, Clone)]
65pub struct QuotientFilter {
66 q: u32,
68 r: u32,
70 slots: Vec<Option<(u32, u64)>>,
72 count: usize,
74 capacity: usize,
76}
77
78#[derive(Debug, Clone, Copy)]
80pub struct QuotientFilterConfig {
81 pub q: u32,
83 pub r: u32,
85}
86
87impl QuotientFilterConfig {
88 #[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 let r = (-fp_rate.log2()).ceil() as u32;
102 let r = r.clamp(2, 32);
103
104 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 } }
117}
118
119impl QuotientFilter {
120 #[must_use]
122 pub fn new(config: QuotientFilterConfig) -> Self {
123 let q = config.q.min(28); 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 #[must_use]
138 pub fn with_defaults() -> Self {
139 Self::new(QuotientFilterConfig::default())
140 }
141
142 #[must_use]
144 pub fn len(&self) -> usize {
145 self.count
146 }
147
148 #[must_use]
150 pub fn is_empty(&self) -> bool {
151 self.count == 0
152 }
153
154 #[must_use]
156 pub fn load_factor(&self) -> f64 {
157 self.count as f64 / self.capacity as f64
158 }
159
160 #[must_use]
162 pub fn capacity(&self) -> usize {
163 self.capacity
164 }
165
166 #[must_use]
168 pub fn theoretical_fp_rate(&self) -> f64 {
169 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 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 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 let mut pos = quotient as usize;
198 for _ in 0..self.capacity {
199 match self.slots[pos] {
200 None => {
201 self.slots[pos] = Some((quotient, remainder));
203 self.count += 1;
204 return true;
205 }
206 Some((q, r)) if q == quotient && r == remainder => {
207 return false;
209 }
210 _ => {
211 pos = (pos + 1) % self.capacity;
213 }
214 }
215 }
216
217 false }
219
220 #[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, Some((q, r)) if q == quotient && r == remainder => return true,
234 _ => pos = (pos + 1) % self.capacity,
235 }
236 }
237
238 false
239 }
240
241 pub fn remove<T: Hash>(&mut self, item: &T) -> bool {
245 let (quotient, remainder) = self.fingerprint(item);
246
247 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 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, Some((q, _r)) => {
276 let canonical = q as usize;
277 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 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 pub fn clear(&mut self) {
310 self.slots.fill(None);
311 self.count = 0;
312 }
313
314 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 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 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#[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 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 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 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 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 for i in 0u64..500 {
460 qf.insert(&i);
461 }
462
463 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 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 for i in (0u64..20).step_by(2) {
505 qf.remove(&i);
506 }
507
508 for i in (1u64..20).step_by(2) {
510 assert!(qf.contains(&i), "odd {i} should survive removal");
511 }
512 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 }); 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 let mut dirty = QuotientFilter::new(QuotientFilterConfig { q: 12, r: 8 });
581
582 let dirty_rows = [5u32, 42, 100, 255, 1000];
584 for &row in &dirty_rows {
585 dirty.insert(&row);
586 }
587
588 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 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 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 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 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 let mut qf = QuotientFilter::new(QuotientFilterConfig { q: 10, r: 20 }); 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 for i in 0u64..target as u64 {
697 assert!(qf.contains(&i), "element {i} missing at high load");
698 }
699 }
700}