Skip to main content

cuckoofilter/
lib.rs

1//! Cuckoo filter probabilistic data structure for membership testing and cardinality counting.
2//!
3//! # Usage
4//!
5//! This fork is [on crates.io](https://crates.io/crates/valkey-cuckoo) and can be
6//! used under the `cuckoofilter` dependency name in your project's `Cargo.toml`.
7//!
8//! ```toml
9//! [dependencies]
10//! cuckoofilter = { package = "valkey-cuckoo", version = "0.2.0" }
11//! ```
12//!
13//! And this in your crate root:
14//!
15//! ```rust
16//! extern crate cuckoofilter;
17//! ```
18
19mod 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
38/// If insertion fails, we will retry this many times.
39pub const MAX_REBUCKET: u32 = 500;
40
41/// The default number of buckets.
42pub 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/// A cuckoo filter class exposes a Bloomier filter interface,
64/// providing methods of add, delete, contains.
65///
66/// The default RNG is `ThreadRng`, which makes the filter neither `Send` nor
67/// `Sync`. Use a custom RNG with the required traits when sharing filters
68/// between threads.
69///
70/// # Examples
71///
72/// ```
73/// extern crate cuckoofilter;
74///
75/// let words = vec!["foo", "bar", "xylophone", "milagro"];
76/// let mut cf = cuckoofilter::CuckooFilter::new();
77///
78/// let mut insertions = 0;
79/// for s in &words {
80///     if cf.test_and_add(s).unwrap() {
81///         insertions += 1;
82///     }
83/// }
84///
85/// assert_eq!(insertions, words.len());
86/// assert_eq!(cf.len(), words.len());
87///
88/// // Re-add the first element.
89/// cf.add(words[0]);
90///
91/// assert_eq!(cf.len(), words.len() + 1);
92///
93/// for s in &words {
94///     cf.delete(s);
95/// }
96///
97/// assert_eq!(cf.len(), 1);
98/// assert!(!cf.is_empty());
99///
100/// cf.delete(words[0]);
101///
102/// assert_eq!(cf.len(), 0);
103/// assert!(cf.is_empty());
104///
105/// for s in &words {
106///     if cf.test_and_add(s).unwrap() {
107///         insertions += 1;
108///     }
109/// }
110///
111/// cf.clear();
112///
113/// assert!(cf.is_empty());
114///
115/// ```
116#[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    /// Construct a CuckooFilter with default capacity and hasher.
134    pub fn new() -> Self {
135        Self::with_capacity(DEFAULT_CAPACITY)
136    }
137}
138
139impl<R: rand::RngCore> CuckooFilter<DefaultHasher, R> {
140    /// Constructs a filter with the given capacity and RNG, using `DefaultHasher`.
141    ///
142    /// Identical RNG states and insertion sequences produce identical evictions
143    /// when hashing produces identical results. Cross-platform or cross-version
144    /// replication also requires stable hashing of the input values.
145    ///
146    /// ```
147    /// use cuckoofilter::CuckooFilter;
148    /// use rand::SeedableRng;
149    /// use rand_chacha::ChaCha8Rng;
150    ///
151    /// let filter = CuckooFilter::with_rng(100, ChaCha8Rng::seed_from_u64(42));
152    /// ```
153    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    /// Constructs a filter with the given capacity, hasher type, and RNG.
160    ///
161    /// The supplied hasher selects the type `H`; its state is not retained.
162    /// The filter creates `H::default()` for each hash operation.
163    /// The RNG is stored without consuming any random values.
164    ///
165    /// ```
166    /// use cuckoofilter::CuckooFilter;
167    /// use fnv::FnvHasher;
168    /// use rand::SeedableRng;
169    /// use rand_chacha::ChaCha8Rng;
170    ///
171    /// let filter = CuckooFilter::with_hasher_and_rng(
172    ///     100,
173    ///     FnvHasher::default(),
174    ///     ChaCha8Rng::seed_from_u64(42),
175    /// );
176    /// ```
177    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    /// Construct a filter with a runtime bucket size and eviction limit.
183    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    /// Number of fingerprint bytes allocated for these parameters.
204    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    /// Restore raw buckets with an explicitly supplied RNG state and configuration.
219    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    /// Restore an owned fingerprint buffer without copying it.
235    ///
236    /// Validates the configuration, buffer size, and number of occupied slots.
237    /// Byte 100 marks an empty slot; all other values are fingerprints.
238    /// The caller must supply the original hasher type, bucket size, eviction
239    /// limit, and RNG state to continue the same insertion sequence.
240    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    /// Borrow the raw fingerprint bytes without copying, one byte per slot.
267    /// Byte 100 marks an empty slot; the layout matches [`Self::export`].
268    pub fn as_bytes(&self) -> &[u8] {
269        &self.buckets
270    }
271
272    /// Transfer the bucket allocation to `f` and install the returned allocation.
273    ///
274    /// The callback must preserve every byte and the allocation's length. This
275    /// supports relocating storage during defragmentation without copying here.
276    ///
277    /// # Panics
278    ///
279    /// Panics if the returned length changes. If this happens or `f` panics,
280    /// the filter is cleared, retaining its capacity and RNG state.
281    pub fn realloc_buckets(&mut self, f: impl FnOnce(Box<[u8]>) -> Box<[u8]>) {
282        // Ownership cannot be recovered if the callback unwinds. Keep the filter
283        // usable if the caller catches that panic; allocate only on this path.
284        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    /// Access the RNG for saving its state alongside exported fingerprints.
309    pub fn rng(&self) -> &R {
310        &self.rng
311    }
312
313    /// Number of allocated buckets.
314    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    /// Hash an item once for use with the `*_hashed` methods.
324    /// The result can be reused across filters with the same hasher, regardless
325    /// of capacity, bucket size, or eviction limit.
326    pub fn hash_item<T: ?Sized + Hash>(data: &T) -> ItemHash {
327        get_fai::<T, H>(data)
328    }
329
330    /// Checks if `data` is in the filter. False positives are possible.
331    pub fn contains<T: ?Sized + Hash>(&self, data: &T) -> bool {
332        self.contains_hashed(&Self::hash_item(data))
333    }
334
335    /// Check membership using a hash produced with this filter's hasher.
336    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    /// Count matching fingerprints in the two candidate buckets.
341    ///
342    /// Counts duplicate insertions, but collisions can overestimate the number
343    /// of copies of an item. A bucket shared by both indices is counted once.
344    /// The hash must have been produced with this filter's hasher.
345    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    /// Insert into a free slot in either candidate bucket, without evictions.
361    ///
362    /// Inserts another fingerprint even if one already matches. Returns false
363    /// without changing buckets, length, or RNG when neither bucket has room.
364    /// Takes O(bucket_size) time and does not consume randomness or allocate.
365    /// The hash must have been produced with this filter's hasher.
366    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    /// Adds `data` to the filter. Returns `Ok` if the insertion was successful,
371    /// but could fail with a `NotEnoughSpace` error, especially when the filter
372    /// is nearing its capacity.
373    /// Note that while you can put any hashable type in the same filter, beware
374    /// for side effects like that the same number can have diferent hashes
375    /// depending on the type.
376    /// So for the filter, 4711i64 isn't the same as 4711u64.
377    ///
378    /// **Note:** When this returns `NotEnoughSpace`, the element given was
379    /// actually added to the filter, but some random *other* element was
380    /// removed. This might improve in the future.
381    pub fn add<T: ?Sized + Hash>(&mut self, data: &T) -> Result<(), CuckooError> {
382        self.insert(&Self::hash_item(data), false)
383    }
384
385    /// Insert without dropping existing fingerprints on failure.
386    /// The RNG must clone into an independent state to roll back its stream too.
387    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    /// Insert a precomputed hash, including another copy of a matching fingerprint.
395    ///
396    /// On failure restores buckets, length, and RNG state. The hash must have
397    /// been produced with this filter's hasher, and the RNG's clone must have
398    /// independent state for its stream to be rolled back.
399    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    /// Adds `data` to the filter if it does not exist in the filter yet.
441    /// Returns `Ok(true)` if `data` was not yet present in the filter and added
442    /// successfully.
443    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    /// Number of items in the filter.
453    pub fn len(&self) -> usize {
454        self.len
455    }
456
457    /// Exports fingerprints in all buckets, along with the filter's length for storage.
458    /// The filter can be recovered by passing the `ExportedCuckooFilter` struct to the
459    /// `from` method of `CuckooFilter`.
460    /// RNG state is not exported; importing a filter initializes a new `ThreadRng`.
461    pub fn export(&self) -> ExportedCuckooFilter {
462        self.into()
463    }
464
465    /// Number of bytes the filter occupies in memory
466    pub fn memory_usage(&self) -> usize {
467        mem::size_of_val(self) + self.buckets.len()
468    }
469
470    /// Check if filter is empty
471    pub fn is_empty(&self) -> bool {
472        self.len == 0
473    }
474
475    /// Deletes `data` from the filter. Returns true if `data` existed in the
476    /// filter before.
477    pub fn delete<T: ?Sized + Hash>(&mut self, data: &T) -> bool {
478        self.delete_hashed(&Self::hash_item(data))
479    }
480
481    /// Remove one matching fingerprint using a precomputed hash.
482    ///
483    /// Only delete items known to have been inserted: false positives can cause
484    /// deletion of a different item. The hash must use this filter's hasher.
485    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    /// Empty all the buckets in a filter and reset the number of items.
490    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    /// Extracts fingerprint values from all buckets, used for exporting the filters data.
500    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    /// Construct a filter with default bucket size, eviction limit, and thread RNG.
533    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/// A minimal representation of the CuckooFilter which can be transfered or stored, then recovered at a later stage.
540#[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    /// Converts a `CuckooFilter` into a simplified version which can be serialized and stored
561    /// for later use.
562    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        // Capacity rounds up to 128 slots, so 150 insertions force eviction
583        // and exercise the failure path after the filter fills up.
584        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        // Check that eviction actually consumed the injected RNG.
600        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}