1mod bucket;
20mod util;
21
22use crate::bucket::{Fingerprint, BUCKET_SIZE, EMPTY_FINGERPRINT};
23use crate::util::{get_alt_index, get_fai};
24
25pub use crate::util::ItemHash;
26
27use std::collections::hash_map::DefaultHasher;
28use std::error::Error as StdError;
29use std::fmt;
30use std::hash::{Hash, Hasher};
31use std::marker::PhantomData;
32use std::mem;
33
34use rand::Rng;
35#[cfg(feature = "serde_support")]
36use serde_derive::{Deserialize, Serialize};
37
38pub const MAX_REBUCKET: u32 = 500;
40
41pub const DEFAULT_CAPACITY: usize = (1 << 20) - 1;
43
44#[derive(Debug)]
45pub enum CuckooError {
46 NotEnoughSpace,
47 InvalidConfiguration,
48 InvalidExport,
49}
50
51impl fmt::Display for CuckooError {
52 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
53 write!(f, "{:?}", self)
54 }
55}
56
57impl StdError for CuckooError {
58 fn description(&self) -> &str {
59 "Not enough space to store this item, rebucketing failed."
60 }
61}
62
63#[derive(Debug, Clone)]
117pub struct CuckooFilter<H, R = rand::rngs::ThreadRng> {
118 buckets: Box<[u8]>,
119 bucket_size: usize,
120 max_kicks: u32,
121 len: usize,
122 rng: R,
123 _hasher: std::marker::PhantomData<H>,
124}
125
126impl Default for CuckooFilter<DefaultHasher> {
127 fn default() -> Self {
128 Self::new()
129 }
130}
131
132impl CuckooFilter<DefaultHasher> {
133 pub fn new() -> Self {
135 Self::with_capacity(DEFAULT_CAPACITY)
136 }
137}
138
139impl<R: rand::RngCore> CuckooFilter<DefaultHasher, R> {
140 pub fn with_rng(capacity: usize, rng: R) -> Self {
154 Self::with_hasher_and_rng(capacity, DefaultHasher::default(), rng)
155 }
156}
157
158impl<H: Hasher + Default, R: rand::RngCore> CuckooFilter<H, R> {
159 pub fn with_hasher_and_rng(capacity: usize, _hasher: H, rng: R) -> Self {
178 Self::with_config_and_rng(capacity, BUCKET_SIZE, MAX_REBUCKET, rng)
179 .expect("invalid filter capacity")
180 }
181
182 pub fn with_config_and_rng(
184 capacity: usize,
185 bucket_size: usize,
186 max_kicks: u32,
187 rng: R,
188 ) -> Result<Self, CuckooError> {
189 let slots = Self::allocation_size(capacity, bucket_size)?;
190 if max_kicks == 0 {
191 return Err(CuckooError::InvalidConfiguration);
192 }
193 Ok(Self {
194 buckets: vec![EMPTY_FINGERPRINT; slots].into_boxed_slice(),
195 bucket_size,
196 max_kicks,
197 len: 0,
198 rng,
199 _hasher: PhantomData,
200 })
201 }
202
203 pub fn allocation_size(capacity: usize, bucket_size: usize) -> Result<usize, CuckooError> {
205 if !(1..=255).contains(&bucket_size) {
206 return Err(CuckooError::InvalidConfiguration);
207 }
208 let count = capacity
209 .max(1)
210 .checked_add(bucket_size - 1)
211 .and_then(|n| (n / bucket_size).checked_next_power_of_two())
212 .and_then(|n| n.checked_mul(bucket_size))
213 .filter(|n| *n <= isize::MAX as usize)
214 .ok_or(CuckooError::InvalidConfiguration)?;
215 Ok(count)
216 }
217
218 pub fn from_export_with_rng(
220 exported: ExportedCuckooFilter,
221 bucket_size: usize,
222 max_kicks: u32,
223 rng: R,
224 ) -> Result<Self, CuckooError> {
225 Self::from_bytes_with_rng(
226 exported.values.into_boxed_slice(),
227 exported.length,
228 bucket_size,
229 max_kicks,
230 rng,
231 )
232 }
233
234 pub fn from_bytes_with_rng(
241 values: Box<[u8]>,
242 length: usize,
243 bucket_size: usize,
244 max_kicks: u32,
245 rng: R,
246 ) -> Result<Self, CuckooError> {
247 if !(1..=255).contains(&bucket_size)
248 || max_kicks == 0
249 || values.is_empty()
250 || !values.len().is_multiple_of(bucket_size)
251 || !(values.len() / bucket_size).is_power_of_two()
252 || values.iter().filter(|&&fp| fp != EMPTY_FINGERPRINT).count() != length
253 {
254 return Err(CuckooError::InvalidExport);
255 }
256 Ok(Self {
257 buckets: values,
258 bucket_size,
259 max_kicks,
260 len: length,
261 rng,
262 _hasher: PhantomData,
263 })
264 }
265
266 pub fn as_bytes(&self) -> &[u8] {
269 &self.buckets
270 }
271
272 pub fn realloc_buckets(&mut self, f: impl FnOnce(Box<[u8]>) -> Box<[u8]>) {
282 struct RestoreOnPanic<'a> {
285 buckets: &'a mut Box<[u8]>,
286 len: &'a mut usize,
287 slots: usize,
288 }
289 impl Drop for RestoreOnPanic<'_> {
290 fn drop(&mut self) {
291 if self.buckets.is_empty() {
292 *self.buckets = vec![EMPTY_FINGERPRINT; self.slots].into_boxed_slice();
293 *self.len = 0;
294 }
295 }
296 }
297 let slots = self.buckets.len();
298 let guard = RestoreOnPanic {
299 buckets: &mut self.buckets,
300 len: &mut self.len,
301 slots,
302 };
303 let buckets = f(mem::take(guard.buckets));
304 assert_eq!(buckets.len(), slots, "bucket allocation length changed");
305 *guard.buckets = buckets;
306 }
307
308 pub fn rng(&self) -> &R {
310 &self.rng
311 }
312
313 pub fn bucket_count(&self) -> usize {
315 self.buckets.len() / self.bucket_size
316 }
317
318 fn bucket(&self, index: usize) -> &[u8] {
319 let start = (index % self.bucket_count()) * self.bucket_size;
320 &self.buckets[start..start + self.bucket_size]
321 }
322
323 pub fn hash_item<T: ?Sized + Hash>(data: &T) -> ItemHash {
327 get_fai::<T, H>(data)
328 }
329
330 pub fn contains<T: ?Sized + Hash>(&self, data: &T) -> bool {
332 self.contains_hashed(&Self::hash_item(data))
333 }
334
335 pub fn contains_hashed(&self, h: &ItemHash) -> bool {
337 self.bucket(h.i1).contains(&h.fp.data[0]) || self.bucket(h.i2).contains(&h.fp.data[0])
338 }
339
340 pub fn count_hashed(&self, h: &ItemHash) -> usize {
346 let count = |index| {
347 self.bucket(index)
348 .iter()
349 .filter(|&&fp| fp == h.fp.data[0])
350 .count()
351 };
352 let first = count(h.i1);
353 if h.i1 % self.bucket_count() == h.i2 % self.bucket_count() {
354 first
355 } else {
356 first + count(h.i2)
357 }
358 }
359
360 pub fn try_add_no_evict_hashed(&mut self, h: &ItemHash) -> bool {
367 self.put(h.fp.data[0], h.i1) || self.put(h.fp.data[0], h.i2)
368 }
369
370 pub fn add<T: ?Sized + Hash>(&mut self, data: &T) -> Result<(), CuckooError> {
382 self.insert(&Self::hash_item(data), false)
383 }
384
385 pub fn try_add<T: ?Sized + Hash>(&mut self, data: &T) -> Result<(), CuckooError>
388 where
389 R: Clone,
390 {
391 self.try_add_hashed(&Self::hash_item(data))
392 }
393
394 pub fn try_add_hashed(&mut self, h: &ItemHash) -> Result<(), CuckooError>
400 where
401 R: Clone,
402 {
403 let previous_rng = self.rng.clone();
404 let result = self.insert(h, true);
405 if result.is_err() {
406 self.rng = previous_rng;
407 }
408 result
409 }
410
411 fn insert(&mut self, h: &ItemHash, rollback: bool) -> Result<(), CuckooError> {
412 if self.try_add_no_evict_hashed(h) {
413 return Ok(());
414 }
415 let mut index = h.random_index(&mut self.rng);
416 let mut fp = h.fp.data[0];
417 let mut changes = Vec::new();
418 for _ in 0..self.max_kicks {
419 let slot = (index % self.bucket_count()) * self.bucket_size
420 + self.rng.gen_range(0..self.bucket_size);
421 let displaced = self.buckets[slot];
422 if rollback {
423 changes.push((slot, displaced));
424 }
425 self.buckets[slot] = fp;
426 index = get_alt_index::<H>(Fingerprint { data: [displaced] }, index);
427 if self.put(displaced, index) {
428 return Ok(());
429 }
430 fp = displaced;
431 }
432 if rollback {
433 for (slot, previous) in changes.into_iter().rev() {
434 self.buckets[slot] = previous;
435 }
436 }
437 Err(CuckooError::NotEnoughSpace)
438 }
439
440 pub fn test_and_add<T: ?Sized + Hash>(&mut self, data: &T) -> Result<bool, CuckooError> {
444 let h = Self::hash_item(data);
445 if self.contains_hashed(&h) {
446 Ok(false)
447 } else {
448 self.insert(&h, false).map(|_| true)
449 }
450 }
451
452 pub fn len(&self) -> usize {
454 self.len
455 }
456
457 pub fn export(&self) -> ExportedCuckooFilter {
462 self.into()
463 }
464
465 pub fn memory_usage(&self) -> usize {
467 mem::size_of_val(self) + self.buckets.len()
468 }
469
470 pub fn is_empty(&self) -> bool {
472 self.len == 0
473 }
474
475 pub fn delete<T: ?Sized + Hash>(&mut self, data: &T) -> bool {
478 self.delete_hashed(&Self::hash_item(data))
479 }
480
481 pub fn delete_hashed(&mut self, h: &ItemHash) -> bool {
486 self.remove(h.fp.data[0], h.i1) || self.remove(h.fp.data[0], h.i2)
487 }
488
489 pub fn clear(&mut self) {
491 if self.is_empty() {
492 return;
493 }
494
495 self.buckets.fill(EMPTY_FINGERPRINT);
496 self.len = 0;
497 }
498
499 fn values(&self) -> Vec<u8> {
501 self.as_bytes().to_vec()
502 }
503
504 fn remove(&mut self, fp: u8, index: usize) -> bool {
505 let start = (index % self.bucket_count()) * self.bucket_size;
506 if let Some(slot) = self.buckets[start..start + self.bucket_size]
507 .iter_mut()
508 .find(|f| **f == fp)
509 {
510 *slot = EMPTY_FINGERPRINT;
511 self.len -= 1;
512 return true;
513 }
514 false
515 }
516
517 fn put(&mut self, fp: u8, index: usize) -> bool {
518 let start = (index % self.bucket_count()) * self.bucket_size;
519 if let Some(slot) = self.buckets[start..start + self.bucket_size]
520 .iter_mut()
521 .find(|f| **f == EMPTY_FINGERPRINT)
522 {
523 *slot = fp;
524 self.len += 1;
525 return true;
526 }
527 false
528 }
529}
530
531impl<H: Hasher + Default> CuckooFilter<H> {
532 pub fn with_capacity(capacity: usize) -> Self {
534 Self::with_config_and_rng(capacity, BUCKET_SIZE, MAX_REBUCKET, rand::thread_rng())
535 .expect("invalid filter capacity")
536 }
537}
538
539#[derive(Debug, Clone, Default)]
541#[cfg_attr(feature = "serde_support", derive(Deserialize, Serialize))]
542pub struct ExportedCuckooFilter {
543 #[cfg_attr(feature = "serde_support", serde(with = "serde_bytes"))]
544 pub values: Vec<u8>,
545 pub length: usize,
546}
547
548impl<H: Hasher + Default> From<ExportedCuckooFilter> for CuckooFilter<H> {
549 fn from(exported: ExportedCuckooFilter) -> Self {
550 Self::from_export_with_rng(exported, BUCKET_SIZE, MAX_REBUCKET, rand::thread_rng())
551 .expect("invalid exported filter")
552 }
553}
554
555impl<H, R> From<&CuckooFilter<H, R>> for ExportedCuckooFilter
556where
557 H: Hasher + Default,
558 R: rand::RngCore,
559{
560 fn from(cuckoo: &CuckooFilter<H, R>) -> Self {
563 Self {
564 values: cuckoo.values(),
565 length: cuckoo.len(),
566 }
567 }
568}
569
570#[cfg(test)]
571mod tests {
572 use super::*;
573 use rand::SeedableRng;
574 use rand_chacha::ChaCha8Rng;
575
576 #[test]
577 fn test_deterministic_eviction() {
578 let mut filter1 = CuckooFilter::with_rng(100, ChaCha8Rng::seed_from_u64(42));
579 let mut filter2 = CuckooFilter::with_rng(100, ChaCha8Rng::seed_from_u64(42));
580 let mut failures = 0;
581
582 for item in 0..150_u64 {
585 let result1 = filter1.add(&item);
586 let result2 = filter2.add(&item);
587 assert_eq!(result1.is_ok(), result2.is_ok(), "item {item}");
588 if result1.is_err() {
589 failures += 1;
590 }
591
592 let state1 = filter1.export();
593 let state2 = filter2.export();
594 assert_eq!(state1.values, state2.values, "item {item}");
595 assert_eq!(state1.length, state2.length, "item {item}");
596 }
597
598 assert!(failures > 0);
599 assert!(filter1.rng.get_word_pos() > 0);
601 assert_eq!(filter1.rng.get_word_pos(), filter2.rng.get_word_pos());
602 }
603 #[test]
604 fn transactional_insert_and_snapshot_resume() {
605 let mut filter = CuckooFilter::<DefaultHasher, _>::with_config_and_rng(
606 32,
607 2,
608 3,
609 ChaCha8Rng::seed_from_u64(42),
610 )
611 .unwrap();
612 let mut successes = Vec::new();
613 let mut failures = 0;
614 for item in 0..100_u64 {
615 let before = filter.export();
616 let position = filter.rng().get_word_pos();
617 if filter.try_add(&item).is_ok() {
618 successes.push(item);
619 } else {
620 failures += 1;
621 assert_eq!(filter.export().values, before.values);
622 assert_eq!(filter.len(), before.length);
623 assert_eq!(filter.rng().get_word_pos(), position);
624 }
625 for value in &successes {
626 assert!(filter.contains(value));
627 }
628 }
629 assert!(failures > 0);
630 let mut restored = CuckooFilter::<DefaultHasher, _>::from_export_with_rng(
631 filter.export(),
632 2,
633 3,
634 filter.rng().clone(),
635 )
636 .unwrap();
637 for item in 100..200_u64 {
638 assert_eq!(
639 filter.try_add(&item).is_ok(),
640 restored.try_add(&item).is_ok()
641 );
642 assert_eq!(filter.export().values, restored.export().values);
643 assert_eq!(filter.rng().get_word_pos(), restored.rng().get_word_pos());
644 }
645 }
646
647 #[test]
648 fn configurable_buckets_and_invalid_snapshots() {
649 for size in [1, 2, 4, 8, 255] {
650 let filter = CuckooFilter::<DefaultHasher, _>::with_config_and_rng(
651 100,
652 size,
653 10,
654 ChaCha8Rng::seed_from_u64(42),
655 )
656 .unwrap();
657 assert!(filter.bucket_count().is_power_of_two());
658 assert_eq!(filter.export().values.len(), filter.bucket_count() * size);
659 assert!(filter.export().values.len() >= 100);
660 let mut invalid = filter.export();
661 invalid.length = 1;
662 assert!(CuckooFilter::<DefaultHasher, _>::from_export_with_rng(
663 invalid,
664 size,
665 10,
666 ChaCha8Rng::seed_from_u64(42),
667 )
668 .is_err());
669 }
670 assert!(CuckooFilter::<DefaultHasher>::allocation_size(usize::MAX, 4).is_err());
671 }
672}