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