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/// Strategy to use when aging LRU counter on scans.
233#[derive(Clone, Default, Debug, PartialEq, Eq)]
234#[repr(u8)]
235pub enum LruAgingStrategy {
236 /// Halving the counter value each scan. Useful to age the items more quickly.
237 #[default]
238 Halving,
239 /// Reduces the counter by a fixed amount each scan.
240 Decrement(u32),
241}
242
243impl LruAgingStrategy {
244 pub(crate) const fn age_value(&self, value: u32) -> u32 {
245 match self {
246 LruAgingStrategy::Halving => value >> 1,
247 LruAgingStrategy::Decrement(dec) => value.saturating_sub(*dec),
248 }
249 }
250}
251
252/// Configuration for the LRU field.
253///
254/// Used to define memory used by the LRU field, also affecting its maximum value.
255///
256/// # Examples
257///
258/// ```
259/// use cuckoo_clock::config::LruConfig;
260///
261/// let ttl_config = LruConfig {
262/// counter_bits: 5.try_into()?,
263/// ..Default::default()
264/// };
265/// # Ok::<(), Box<dyn std::error::Error>>(())
266/// ```
267#[derive(Clone, Debug, PartialEq, Eq)]
268pub struct LruConfig {
269 /// Number of bits used to represent the LRU counter.
270 /// Larger bit counts allow more values to be represented, allowing items to "accumulate"
271 /// higher use counts, which will take longer to age.
272 pub counter_bits: BitCount,
273 /// The strategy to use when aging LRU counters.
274 pub aging_strategy: LruAgingStrategy,
275 /// The starting value for LRU counter to use.
276 pub starting_value: u32,
277 /// If set to true, items that already have a 0 counter value will be removed at scan time.
278 pub remove_on_zero: bool,
279 /// Increment to add to LRU counter on each insert and lookup.
280 pub increment: u32,
281}
282
283impl Default for LruConfig {
284 fn default() -> Self {
285 Self {
286 counter_bits: BitCount(8),
287 aging_strategy: LruAgingStrategy::default(),
288 starting_value: 1,
289 remove_on_zero: false,
290 increment: 1,
291 }
292 }
293}
294
295/// Configuration for the TTL field.
296///
297/// Used to define memory used by the TTL field and the default value.
298///
299/// # Examples
300///
301/// ```
302/// use cuckoo_clock::config::TtlConfig;
303///
304/// let ttl_config = TtlConfig {
305/// ttl: 100.try_into()?,
306/// ttl_bits: 7.try_into()?
307/// };
308/// # Ok::<(), Box<dyn std::error::Error>>(())
309/// ```
310#[derive(Clone, Debug, PartialEq, Eq)]
311pub struct TtlConfig {
312 /// The default TTL counter value for newly inserted items. The actual lifetime duration will
313 /// be defined by this value combined with the frequency of calls to
314 /// [`crate::CuckooFilter::scan_and_update_full`]. Each call to
315 /// [`crate::CuckooFilter::scan_and_update_full`] will reduce the counter by 1, until it
316 /// reaches 0, when the item is removed.
317 pub ttl: NonZeroU32,
318 /// Number of bits used to represent the TTL counter.
319 /// Larget bit counts allow higher TTL to be represented.
320 pub ttl_bits: BitCount,
321}
322
323/// Configuration for the generic counter field.
324///
325/// Used to define memory used by the generic counter field, also affecting its maximum value.
326///
327/// # Examples
328///
329/// ```
330/// use cuckoo_clock::config::CounterConfig;
331///
332/// let ttl_config = CounterConfig {
333/// counter_bits: 5.try_into()?,
334/// ..Default::default()
335/// };
336/// # Ok::<(), Box<dyn std::error::Error>>(())
337/// ```
338#[derive(Clone, Debug, PartialEq, Eq)]
339pub struct CounterConfig {
340 /// How many bits are used to represent the generic counter.
341 /// Larget bit counts allow higher counter values to be represented.
342 pub counter_bits: BitCount,
343 /// Diff to apply to counter on each insert.
344 pub change_on_insert: i32,
345 /// Diff to apply to counter on each lookup.
346 pub change_on_lookup: i32,
347}
348
349impl Default for CounterConfig {
350 fn default() -> Self {
351 Self {
352 counter_bits: BitCount(4),
353 change_on_insert: 1,
354 change_on_lookup: 1,
355 }
356 }
357}
358
359/// Configuration for the [`crate::CuckooFilter`].
360///
361/// Used to define main cuckoo filter parameters (capacity, bucket size, fingeprint size,
362/// max kicks), as well as additional features (TTL, LRU, generic counter).
363///
364/// Create a new instance using [`CuckooConfiguration::builder`].
365///
366/// # Examples
367///
368/// ```
369/// use cuckoo_clock::config::CuckooConfiguration;
370///
371/// let config = CuckooConfiguration::builder(100_000)
372/// .fingerprint_bits(14.try_into()?)
373/// .bucket_size(4.try_into()?)
374/// .max_kicks(8)
375/// .build()?;
376/// # Ok::<(), Box<dyn std::error::Error>>(())
377/// ```
378///
379/// ```
380/// use cuckoo_clock::config::{CuckooConfiguration, TtlConfig, LruConfig};
381///
382/// let config = CuckooConfiguration::builder(100_000)
383/// .fingerprint_bits(14.try_into()?)
384/// .with_ttl(TtlConfig {
385/// ttl: 10.try_into()?,
386/// ttl_bits: 4.try_into()?
387/// })
388/// .with_lru(LruConfig {
389/// counter_bits: 6.try_into()?,
390/// ..Default::default()
391/// })
392/// .bucket_size(4.try_into()?)
393/// .max_kicks(8)
394/// .build()?;
395/// # Ok::<(), Box<dyn std::error::Error>>(())
396/// ```
397#[derive(Clone, Debug, PartialEq, Eq)]
398pub struct CuckooConfiguration {
399 pub(crate) bucket_size: usize,
400 pub(crate) max_kicks: usize,
401
402 pub(crate) fingerprint_field_config: DataBlockFieldConfiguration,
403 pub(crate) lru_field_config: Option<(LruConfig, DataBlockFieldConfiguration)>,
404 pub(crate) counter_field_config: Option<(CounterConfig, DataBlockFieldConfiguration)>,
405 pub(crate) ttl_field_config: Option<(TtlConfig, DataBlockFieldConfiguration)>,
406 pub(crate) data_block_size: usize,
407 pub(crate) bucket_byte_size: usize,
408 pub(crate) bucket_count: usize,
409 pub(crate) buckets_mask: u32,
410}
411
412impl CuckooConfiguration {
413 /// Creates a new instance of [`CuckooConfigurationBuilder`] with provided maximum number of
414 /// entries.
415 #[must_use]
416 pub const fn builder(max_entries: usize) -> CuckooConfigurationBuilder {
417 CuckooConfigurationBuilder {
418 fingerprint_bits: BitCount(8),
419 #[expect(clippy::expect_used)]
420 bucket_size: NonZeroUsize::new(4).expect("4 != 0"),
421 max_entries,
422 max_kicks: 500,
423 lru: None,
424 ttl: None,
425 counter: None,
426 }
427 }
428
429 /// Returns the memory usage of filter that would be created from this configuration in bytes.
430 #[must_use]
431 pub const fn get_configured_memory_usage(&self) -> usize {
432 CuckooFilter::<RandomState>::get_expected_memory_usage(
433 self.bucket_byte_size,
434 self.bucket_count,
435 )
436 }
437
438 /// Checks whether this and other configuration have a compatible layout.
439 ///
440 /// If this is true, filter exported by the other configuration can be imported and used with this
441 /// configuration. The only compatible configuration changes are generally ones that don't
442 /// affect size or count of the buckets and items.
443 #[must_use]
444 pub fn compatible_layout(&self, other: Self) -> bool {
445 if self.bucket_size != other.bucket_size {
446 return false;
447 }
448 if self.bucket_count != other.bucket_count {
449 return false;
450 }
451 if self.buckets_mask != other.buckets_mask {
452 return false;
453 }
454 if self.bucket_byte_size != other.bucket_byte_size {
455 return false;
456 }
457 if self.data_block_size != other.data_block_size {
458 return false;
459 }
460 if self.fingerprint_field_config != other.fingerprint_field_config {
461 return false;
462 }
463 if !Self::field_compatible(&self.lru_field_config, &other.lru_field_config) {
464 return false;
465 }
466 if !Self::field_compatible(&self.counter_field_config, &other.counter_field_config) {
467 return false;
468 }
469 if !Self::field_compatible(&self.ttl_field_config, &other.ttl_field_config) {
470 return false;
471 }
472 true
473 }
474
475 fn field_compatible<T>(
476 self_field: &Option<(T, DataBlockFieldConfiguration)>,
477 other_field: &Option<(T, DataBlockFieldConfiguration)>,
478 ) -> bool {
479 match (self_field, other_field) {
480 (None, Some(_)) | (Some(_), None) => false,
481 (None, None) => true,
482 (Some((_, self_field_config)), Some((_, other_field_config))) => {
483 self_field_config == other_field_config
484 }
485 }
486 }
487}
488
489/// Number of bits. Used to define sizes of the fields.
490///
491/// This value is limited by [`BitCount::MIN`] and [`BitCount::MAX`] and can only be created using
492/// the [`TryFrom`] trait, to ensure the bit count is validated.
493///
494/// # Examples
495///
496/// ```
497/// use cuckoo_clock::config::BitCount;
498///
499/// let bit_count: BitCount = 8.try_into().unwrap();
500/// let bit_count_max: BitCount = 32.try_into().unwrap();
501/// let bit_count_min: BitCount = 1.try_into().unwrap();
502/// ```
503///
504/// ```should_panic
505/// use cuckoo_clock::config::BitCount;
506///
507/// let bit_count: BitCount = 0.try_into().unwrap();
508/// ```
509///
510/// ```should_panic
511/// use cuckoo_clock::config::BitCount;
512///
513/// let bit_count: BitCount = 40.try_into().unwrap();
514/// ```
515#[derive(Debug, Clone, Copy, PartialEq, Eq)]
516pub struct BitCount(usize);
517
518impl BitCount {
519 /// Maximum allowed value for [`BitCount`]
520 pub const MAX: BitCount = BitCount(32);
521 /// Minimum allowed value for [`BitCount`]
522 pub const MIN: BitCount = BitCount(1);
523}
524
525impl Deref for BitCount {
526 type Target = usize;
527
528 fn deref(&self) -> &Self::Target {
529 &self.0
530 }
531}
532
533impl DerefMut for BitCount {
534 fn deref_mut(&mut self) -> &mut Self::Target {
535 &mut self.0
536 }
537}
538
539impl TryFrom<usize> for BitCount {
540 type Error = ConfigError;
541
542 fn try_from(value: usize) -> Result<Self, Self::Error> {
543 if value > Self::MAX.0 {
544 return Err(ConfigError::BitCountTooHigh);
545 }
546 if value < Self::MIN.0 {
547 return Err(ConfigError::BitCountTooLow);
548 }
549 Ok(Self(value))
550 }
551}
552
553impl From<BitCount> for usize {
554 fn from(value: BitCount) -> Self {
555 value.0
556 }
557}
558
559// Since bit count can't be higher than 32
560// Conversion into any integer is fine
561impl From<BitCount> for u64 {
562 fn from(value: BitCount) -> Self {
563 value.0 as u64
564 }
565}
566
567impl From<BitCount> for u32 {
568 #[expect(clippy::cast_possible_truncation)]
569 fn from(value: BitCount) -> Self {
570 value.0 as u32
571 }
572}
573
574impl From<BitCount> for u16 {
575 #[expect(clippy::cast_possible_truncation)]
576 fn from(value: BitCount) -> Self {
577 value.0 as u16
578 }
579}
580
581impl From<BitCount> for u8 {
582 #[expect(clippy::cast_possible_truncation)]
583 fn from(value: BitCount) -> Self {
584 value.0 as u8
585 }
586}
587
588impl Add<usize> for BitCount {
589 type Output = usize;
590
591 fn add(self, rhs: usize) -> Self::Output {
592 self.0 + rhs
593 }
594}
595
596impl Add<BitCount> for usize {
597 type Output = usize;
598
599 fn add(self, rhs: BitCount) -> Self::Output {
600 self + rhs.0
601 }
602}