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