cuckoo_clock/
config.rs

1//! This module provides configuration types for [`crate::CuckooFilter`].
2
3use std::{
4    fmt::Display,
5    hash::RandomState,
6    num::{NonZeroU32, NonZeroUsize},
7    ops::{Add, Deref, DerefMut},
8};
9
10use crate::{CuckooFilter, data_block::DataBlockFieldConfiguration};
11
12/// Error type for all configuration options.
13#[derive(Debug)]
14pub enum ConfigError {
15    /// Error due to requesting buckets that are too big to represent (requiring over [`usize::MAX`]
16    /// bytes).
17    BucketTooBig,
18    /// Error due to requesting more than 32 bits for any of the fields (fingerprint or associated
19    /// field).
20    BitCountTooHigh,
21    /// Error due to requesting 0 bits for a field. If a field is enabled, it should take up at
22    /// least 1 bit.
23    BitCountTooLow,
24}
25
26impl Display for ConfigError {
27    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
28        match self {
29            ConfigError::BucketTooBig => {
30                f.write_str("Filter configuration requires buckets that are too big!")
31            }
32            ConfigError::BitCountTooHigh => f.write_str(&format!(
33                "Bit count is too high! Max is {}.",
34                BitCount::MAX.0
35            )),
36            ConfigError::BitCountTooLow => {
37                f.write_str(&format!("Bit count too low! Min is {}.", BitCount::MIN.0))
38            }
39        }
40    }
41}
42
43impl std::error::Error for ConfigError {
44    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
45        None
46    }
47}
48
49/// Builder for [`CuckooConfiguration`].
50///
51/// New instance can be created using [`CuckooConfiguration::builder`].
52///
53/// # Examples
54///
55/// ```
56/// use cuckoo_clock::config::CuckooConfiguration;
57/// let builder = CuckooConfiguration::builder(100_000);
58/// ```
59pub struct CuckooConfigurationBuilder {
60    pub(crate) fingerprint_bits: BitCount,
61    pub(crate) bucket_size: NonZeroUsize,
62    pub(crate) max_entries: usize,
63    pub(crate) max_kicks: usize,
64    pub(crate) lru: Option<LruConfig>,
65    pub(crate) ttl: Option<TtlConfig>,
66    pub(crate) counter: Option<CounterConfig>,
67}
68
69impl CuckooConfigurationBuilder {
70    /// Sets the number of bits used for fingerprint. Higher number of bits should result in less
71    /// collisions, which should result in a lower false positive rate, at the cost of increased
72    /// memory usage.
73    #[must_use]
74    pub const fn fingerprint_bits(mut self, bits: BitCount) -> Self {
75        self.fingerprint_bits = bits;
76        self
77    }
78
79    /// Sets the number of buckets to hold in a bucket. Larger buckets improve filter occupancy
80    /// (space utilization), but they also require larger fingerprints to retain the same false
81    /// positive rate.
82    ///
83    /// 5.1. Optimal bucket size in [the original paper] describes this relation.
84    ///
85    /// [the original paper]: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
86    #[must_use]
87    pub const fn bucket_size(mut self, size: NonZeroUsize) -> Self {
88        self.bucket_size = size;
89        self
90    }
91
92    /// Maximum number of kicks to perform if all requested slots are occupied when inserting new
93    /// items. Items will be evicted and moved to their alternate slots until no more evictions are
94    /// required or maximum number of kicks is reached.
95    ///
96    /// If the maximum number of kicks is reached, one item will be lost from the filter.
97    ///
98    /// Increasing this number will increase filter occupancy at the cost of insertion speed.
99    #[must_use]
100    pub const fn max_kicks(mut self, kicks: usize) -> Self {
101        self.max_kicks = kicks;
102        self
103    }
104
105    /// Enables LRU eviction for the filter. Kicks will no longer be performed randomly and will
106    /// always target least recently used items, until either no more evictions are required, max
107    /// number of kicks was reached or the kicked item is to be moved in a bucket with all slots
108    /// occupied by more used items.
109    ///
110    /// When LRU is used, [`crate::CuckooFilter::scan_and_update_full`] should be called
111    /// periodically, to age LRU for all items. It is up to the caller to schedule this process.
112    /// More frequent scans will result in faster aging LRU for all items, requiring item to be
113    /// used more frequently to outlive other items.
114    #[must_use]
115    pub const fn with_lru(mut self, lru: LruConfig) -> Self {
116        self.lru = Some(lru);
117        self
118    }
119
120    /// Enables TTL for items in the filter. TTL will be used to expire items from the filter when
121    /// [`crate::CuckooFilter::scan_and_update_full`] is called.
122    ///
123    /// When TTL is used, [`crate::CuckooFilter::scan_and_update_full`] should be called
124    /// periodically, to age TTL for all items. It is up to the caller to schedule this process.
125    /// More frequent scans will result in lower TTL for all items.
126    #[must_use]
127    pub const fn with_ttl(mut self, ttl: TtlConfig) -> Self {
128        self.ttl = Some(ttl);
129        self
130    }
131
132    /// Enables counter for items in the filter. Counter is just provided as a value that can be
133    /// read when accessing items. It is increased on every access (and can be controlled
134    /// directly).
135    #[must_use]
136    pub const fn with_counter(mut self, counter: CounterConfig) -> Self {
137        self.counter = Some(counter);
138        self
139    }
140
141    /// Validates and builds the configuration.
142    ///
143    /// # Errors
144    ///
145    /// [`ConfigError::BucketTooBig`] if requests buckets are too big to represent with [`usize::MAX`].
146    /// Bucket size is defined as [`Self::bucket_size`] * item bits (sum of all fields bits,
147    /// rounded to byte).
148    pub fn build(&self) -> Result<CuckooConfiguration, ConfigError> {
149        let required_bucket_count = self.max_entries.div_ceil(self.bucket_size.get());
150        let bucket_count = required_bucket_count.next_power_of_two();
151        let ttl_start = *self.fingerprint_bits
152            + if let Some(LruConfig { counter_bits, .. }) = self.lru {
153                *counter_bits
154            } else {
155                0
156            };
157        let counter_start = ttl_start
158            + if let Some(TtlConfig { ttl_bits, .. }) = self.ttl {
159                *ttl_bits
160            } else {
161                0
162            };
163
164        // Sum of bits will never reach the size of `usize`, so no need to do checked adds
165        let mut data_block_size = *self.fingerprint_bits;
166        if let Some(LruConfig { counter_bits, .. }) = self.lru {
167            data_block_size += *counter_bits;
168        }
169        if let Some(TtlConfig { ttl_bits, .. }) = self.ttl {
170            data_block_size += *ttl_bits;
171        }
172        if let Some(CounterConfig { counter_bits, .. }) = self.counter {
173            data_block_size += *counter_bits;
174        }
175        data_block_size = data_block_size.div_ceil(8);
176        Ok(CuckooConfiguration {
177            bucket_size: self.bucket_size.get(),
178            max_kicks: self.max_kicks,
179
180            fingerprint_field_config: DataBlockFieldConfiguration::new(0..*self.fingerprint_bits),
181            lru_field_config: self.lru.clone().map(|lru| {
182                (
183                    lru,
184                    DataBlockFieldConfiguration::new(
185                        *self.fingerprint_bits
186                            ..*self.fingerprint_bits
187                                + self
188                                    .lru
189                                    .as_ref()
190                                    .map(|l| l.counter_bits)
191                                    .unwrap_or(BitCount(0)),
192                    ),
193                )
194            }),
195            ttl_field_config: self.ttl.clone().map(|ttl| {
196                (
197                    ttl,
198                    DataBlockFieldConfiguration::new(
199                        ttl_start
200                            ..ttl_start
201                                + *self.ttl.as_ref().map(|t| t.ttl_bits).unwrap_or(BitCount(0)),
202                    ),
203                )
204            }),
205            counter_field_config: self.counter.clone().map(|counter| {
206                (
207                    counter,
208                    DataBlockFieldConfiguration::new(
209                        counter_start
210                            ..counter_start
211                                + *self
212                                    .counter
213                                    .as_ref()
214                                    .map(|c| c.counter_bits)
215                                    .unwrap_or(BitCount(0)),
216                    ),
217                )
218            }),
219            data_block_size,
220            bucket_byte_size: self
221                .bucket_size
222                .get()
223                .checked_mul(data_block_size)
224                .ok_or(ConfigError::BucketTooBig)?,
225            bucket_count,
226            #[expect(clippy::cast_possible_truncation)]
227            buckets_mask: (bucket_count - 1) as u32,
228        })
229    }
230}
231
232/// Configuration for the LRU field.
233///
234/// Used to define memory used by the LRU field, also affecting its maximum value.
235///
236/// # Examples
237///
238/// ```
239/// use cuckoo_clock::config::LruConfig;
240///
241/// let ttl_config = LruConfig {
242///     counter_bits: 5.try_into()?
243/// };
244/// # Ok::<(), Box<dyn std::error::Error>>(())
245/// ```
246#[derive(Clone, Debug, PartialEq, Eq)]
247pub struct LruConfig {
248    /// Number of bits used to represent the LRU counter.
249    /// Larger bit counts allow more values to be represented, allowing items to "accumulate"
250    /// higher use counts, which will take longer to age.
251    pub counter_bits: BitCount,
252}
253
254impl Default for LruConfig {
255    fn default() -> Self {
256        Self {
257            counter_bits: BitCount(8),
258        }
259    }
260}
261
262/// Configuration for the TTL field.
263///
264/// Used to define memory used by the TTL field and the default value.
265///
266/// # Examples
267///
268/// ```
269/// use cuckoo_clock::config::TtlConfig;
270///
271/// let ttl_config = TtlConfig {
272///     ttl: 100.try_into()?,
273///     ttl_bits: 7.try_into()?
274/// };
275/// # Ok::<(), Box<dyn std::error::Error>>(())
276/// ```
277#[derive(Clone, Debug, PartialEq, Eq)]
278pub struct TtlConfig {
279    /// The default TTL counter value for newly inserted items. The actual lifetime duration will
280    /// be defined by this value combined with the frequency of calls to
281    /// [`crate::CuckooFilter::scan_and_update_full`]. Each call to
282    /// [`crate::CuckooFilter::scan_and_update_full`] will reduce the counter by 1, until it
283    /// reaches 0, when the item is removed.
284    pub ttl: NonZeroU32,
285    /// Number of bits used to represent the TTL counter.
286    /// Larget bit counts allow higher TTL to be represented.
287    pub ttl_bits: BitCount,
288}
289
290/// Configuration for the generic counter field.
291///
292/// Used to define memory used by the generic counter field, also affecting its maximum value.
293///
294/// # Examples
295///
296/// ```
297/// use cuckoo_clock::config::CounterConfig;
298///
299/// let ttl_config = CounterConfig {
300///     counter_bits: 5.try_into()?,
301///     ..Default::default()
302/// };
303/// # Ok::<(), Box<dyn std::error::Error>>(())
304/// ```
305#[derive(Clone, Debug, PartialEq, Eq)]
306pub struct CounterConfig {
307    /// How many bits are used to represent the generic counter.
308    /// Larget bit counts allow higher counter values to be represented.
309    pub counter_bits: BitCount,
310    /// Diff to apply to counter on each insert.
311    pub change_on_insert: i32,
312    /// Diff to apply to counter on each lookup.
313    pub change_on_lookup: i32,
314}
315
316impl Default for CounterConfig {
317    fn default() -> Self {
318        Self {
319            counter_bits: BitCount(4),
320            change_on_insert: 1,
321            change_on_lookup: 1,
322        }
323    }
324}
325
326/// Configuration for the [`crate::CuckooFilter`].
327///
328/// Used to define main cuckoo filter parameters (capacity, bucket size, fingeprint size,
329/// max kicks), as well as additional features (TTL, LRU, generic counter).
330///
331/// Create a new instance using [`CuckooConfiguration::builder`].
332///
333/// # Examples
334///
335/// ```
336/// use cuckoo_clock::config::CuckooConfiguration;
337///
338/// let config = CuckooConfiguration::builder(100_000)
339///     .fingerprint_bits(14.try_into()?)
340///     .bucket_size(4.try_into()?)
341///     .max_kicks(8)
342///     .build()?;
343/// # Ok::<(), Box<dyn std::error::Error>>(())
344/// ```
345///
346/// ```
347/// use cuckoo_clock::config::{CuckooConfiguration, TtlConfig, LruConfig};
348///
349/// let config = CuckooConfiguration::builder(100_000)
350///     .fingerprint_bits(14.try_into()?)
351///     .with_ttl(TtlConfig {
352///         ttl: 10.try_into()?,
353///         ttl_bits: 4.try_into()?
354///     })
355///     .with_lru(LruConfig {
356///         counter_bits: 6.try_into()?
357///     })
358///     .bucket_size(4.try_into()?)
359///     .max_kicks(8)
360///     .build()?;
361/// # Ok::<(), Box<dyn std::error::Error>>(())
362/// ```
363#[derive(Clone, Debug, PartialEq, Eq)]
364pub struct CuckooConfiguration {
365    pub(crate) bucket_size: usize,
366    pub(crate) max_kicks: usize,
367
368    pub(crate) fingerprint_field_config: DataBlockFieldConfiguration,
369    pub(crate) lru_field_config: Option<(LruConfig, DataBlockFieldConfiguration)>,
370    pub(crate) counter_field_config: Option<(CounterConfig, DataBlockFieldConfiguration)>,
371    pub(crate) ttl_field_config: Option<(TtlConfig, DataBlockFieldConfiguration)>,
372    pub(crate) data_block_size: usize,
373    pub(crate) bucket_byte_size: usize,
374    pub(crate) bucket_count: usize,
375    pub(crate) buckets_mask: u32,
376}
377
378impl CuckooConfiguration {
379    /// Creates a new instance of [`CuckooConfigurationBuilder`] with provided maximum number of
380    /// entries.
381    #[must_use]
382    pub const fn builder(max_entries: usize) -> CuckooConfigurationBuilder {
383        CuckooConfigurationBuilder {
384            fingerprint_bits: BitCount(8),
385            #[expect(clippy::expect_used)]
386            bucket_size: NonZeroUsize::new(4).expect("4 != 0"),
387            max_entries,
388            max_kicks: 500,
389            lru: None,
390            ttl: None,
391            counter: None,
392        }
393    }
394
395    /// Returns the memory usage of filter that would be created from this configuration in bytes.
396    #[must_use]
397    pub const fn get_configured_memory_usage(&self) -> usize {
398        CuckooFilter::<RandomState>::get_expected_memory_usage(
399            self.bucket_byte_size,
400            self.bucket_count,
401        )
402    }
403}
404
405/// Number of bits. Used to define sizes of the fields.
406///
407/// This value is limited by [`BitCount::MIN`] and [`BitCount::MAX`] and can only be created using
408/// the [`TryFrom`] trait, to ensure the bit count is validated.
409///
410/// # Examples
411///
412/// ```
413/// use cuckoo_clock::config::BitCount;
414///
415/// let bit_count: BitCount = 8.try_into().unwrap();
416/// let bit_count_max: BitCount = 32.try_into().unwrap();
417/// let bit_count_min: BitCount = 1.try_into().unwrap();
418/// ```
419///
420/// ```should_panic
421/// use cuckoo_clock::config::BitCount;
422///
423/// let bit_count: BitCount = 0.try_into().unwrap();
424/// ```
425///
426/// ```should_panic
427/// use cuckoo_clock::config::BitCount;
428///
429/// let bit_count: BitCount = 40.try_into().unwrap();
430/// ```
431#[derive(Debug, Clone, Copy, PartialEq, Eq)]
432pub struct BitCount(usize);
433
434impl BitCount {
435    /// Maximum allowed value for [`BitCount`]
436    pub const MAX: BitCount = BitCount(32);
437    /// Minimum allowed value for [`BitCount`]
438    pub const MIN: BitCount = BitCount(1);
439}
440
441impl Deref for BitCount {
442    type Target = usize;
443
444    fn deref(&self) -> &Self::Target {
445        &self.0
446    }
447}
448
449impl DerefMut for BitCount {
450    fn deref_mut(&mut self) -> &mut Self::Target {
451        &mut self.0
452    }
453}
454
455impl TryFrom<usize> for BitCount {
456    type Error = ConfigError;
457
458    fn try_from(value: usize) -> Result<Self, Self::Error> {
459        if value > Self::MAX.0 {
460            return Err(ConfigError::BitCountTooHigh);
461        }
462        if value < Self::MIN.0 {
463            return Err(ConfigError::BitCountTooLow);
464        }
465        Ok(Self(value))
466    }
467}
468
469impl From<BitCount> for usize {
470    fn from(value: BitCount) -> Self {
471        value.0
472    }
473}
474
475// Since bit count can't be higher than 32
476// Conversion into any integer is fine
477impl From<BitCount> for u64 {
478    fn from(value: BitCount) -> Self {
479        value.0 as u64
480    }
481}
482
483impl From<BitCount> for u32 {
484    #[expect(clippy::cast_possible_truncation)]
485    fn from(value: BitCount) -> Self {
486        value.0 as u32
487    }
488}
489
490impl From<BitCount> for u16 {
491    #[expect(clippy::cast_possible_truncation)]
492    fn from(value: BitCount) -> Self {
493        value.0 as u16
494    }
495}
496
497impl From<BitCount> for u8 {
498    #[expect(clippy::cast_possible_truncation)]
499    fn from(value: BitCount) -> Self {
500        value.0 as u8
501    }
502}
503
504impl Add<usize> for BitCount {
505    type Output = usize;
506
507    fn add(self, rhs: usize) -> Self::Output {
508        self.0 + rhs
509    }
510}
511
512impl Add<BitCount> for usize {
513    type Output = usize;
514
515    fn add(self, rhs: BitCount) -> Self::Output {
516        self + rhs.0
517    }
518}
cuckoo_clock/config.rs

cuckoo_clock/
config.rs
