1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
//! A variant of [Cuckoo Filter][cuckoo filter] whose size automatically scales as necessary. //! //! # Examples //! //! Basic usage: //! //! ``` //! use scalable_cuckoo_filter::ScalableCuckooFilter; //! //! let mut filter = ScalableCuckooFilter::new(100, 0.001); //! assert!(!filter.contains("foo")); //! filter.insert("foo"); //! assert!(filter.contains("foo")); //! ``` //! //! Filter grows automatically: //! //! ``` //! use scalable_cuckoo_filter::ScalableCuckooFilter; //! //! let mut filter = ScalableCuckooFilter::new(100, 0.001); //! assert_eq!(filter.capacity(), 128); //! //! for i in 0..1000 { //! filter.insert(&i); //! } //! assert_eq!(filter.capacity(), 1923); //! ``` //! //! Filter shrinking: //! //! ``` //! use scalable_cuckoo_filter::ScalableCuckooFilter; //! //! let mut filter = ScalableCuckooFilter::new(1000, 0.001); //! for i in 0..100 { //! filter.insert(&i); //! } //! assert_eq!(filter.capacity(), 1024); //! assert_eq!(filter.bits(), 14336); //! //! filter.shrink_to_fit(); //! for i in 0..100 { //! assert!(filter.contains(&i)); //! } //! assert_eq!(filter.capacity(), 128); //! assert_eq!(filter.bits(), 1792); //! ``` //! //! # References //! //! - [Cuckoo Filter: Practically Better Than Bloom][cuckoo filter] //! - [Scalable Bloom Filters][scalable bloom filters] //! //! [cuckoo filter]: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf //! [scalable bloom filters]: http://haslab.uminho.pt/cbm/files/dbloom.pdf #![warn(missing_docs)] extern crate rand; extern crate siphasher; pub use scalable_cuckoo_filter::{DefaultHasher, DefaultRng, ScalableCuckooFilter, ScalableCuckooFilterBuilder}; mod bits; mod buckets; mod cuckoo_filter; mod scalable_cuckoo_filter; #[inline] fn hash<T: ?Sized + std::hash::Hash, H: std::hash::Hasher + Clone>(hasher: &H, item: &T) -> u64 { let mut hasher = hasher.clone(); item.hash(&mut hasher); hasher.finish() }