idr_ebr/
config.rs

1use std::{fmt::Debug, marker::PhantomData};
2
3/// Configuration parameters to tune the behavior of an IDR.
4///
5/// The capacity of an IDR is determined by the configuration parameters:
6/// ```text
7///     (2**MAX_PAGES - 1) * INITIAL_PAGE_SIZE
8/// ```
9///
10/// [`Idr::new()`] checks that the configuration is valid at compile time.
11/// These checks are triggered by `cargo build` or `cargo test`, but not
12/// by `cargo check`.
13///
14/// [`Idr::new()`]: crate::Idr::new
15pub trait Config: Sized {
16    /// The capacity of the first page.
17    ///
18    /// When a page in an underlying slab has been filled with values, a new
19    /// page will be allocated that is twice as large as the previous page.
20    /// Thus, the second page will be twice this size, and the third will be
21    /// four times this size, and so on.
22    ///
23    /// **Must** be a power of two.
24    const INITIAL_PAGE_SIZE: u32 = DefaultConfig::INITIAL_PAGE_SIZE;
25
26    /// The maximum number of pages in an underlying slab of an IDR.
27    ///
28    /// This value, in combination with `INITIAL_PAGE_SIZE`, determines how many
29    /// bits of each key are used to represent slot indices.
30    ///
31    /// **Must** be positive.
32    const MAX_PAGES: u32 = DefaultConfig::MAX_PAGES;
33
34    /// A number of **high-order** bits which are reserved from user code.
35    ///
36    /// Note: these bits are taken from the generation counter; reserving
37    /// additional bits will decrease the period of the generation counter.
38    /// These should thus be used relatively sparingly, to ensure that
39    /// generation counters are able to effectively prevent the ABA problem.
40    ///
41    /// **Must** be less than or equal to 32.
42    const RESERVED_BITS: u32 = DefaultConfig::RESERVED_BITS;
43
44    /// Returns a debug representation of the configuration, which includes all
45    /// internally calculated values and limits.
46    #[must_use]
47    fn debug() -> impl Debug {
48        DebugConfig::<Self>(PhantomData)
49    }
50}
51
52/// A default configuration:
53/// * No bits reserved for user code.
54/// * A capacity is 4,294,967,264.
55/// * A generation counter with a period of 4,294,967,296.
56#[allow(missing_debug_implementations)] // `Config::debug()` instead
57pub struct DefaultConfig;
58
59impl Config for DefaultConfig {
60    const INITIAL_PAGE_SIZE: u32 = 32;
61    const MAX_PAGES: u32 = 27;
62    const RESERVED_BITS: u32 = 0;
63}
64
65pub(crate) trait ConfigPrivate: Config {
66    const USED_BITS: u32 = 64 - Self::RESERVED_BITS;
67    const SLOT_BITS: u32 = Self::MAX_PAGES + Self::INITIAL_PAGE_SIZE.trailing_zeros();
68    const SLOT_MASK: u32 = ((1u64 << Self::SLOT_BITS) - 1) as u32;
69    const GENERATION_BITS: u32 = Self::USED_BITS - Self::SLOT_BITS;
70    const GENERATION_MASK: u32 = ((1u64 << Self::GENERATION_BITS) - 1) as u32;
71
72    // For debugging and tests, both values are `<= u32::MAX + 1`.
73    const MAX_SLOTS: u64 = ((1u64 << Self::MAX_PAGES) - 1) * Self::INITIAL_PAGE_SIZE as u64;
74    const MAX_GENERATIONS: u64 = 1u64 << Self::GENERATION_BITS;
75
76    // Compile-time (only test/build, not check) postmono constraints.
77    // https://t.me/terriblerust/38
78    const ENSURE_VALID: bool = {
79        assert!(Self::INITIAL_PAGE_SIZE.is_power_of_two());
80        assert!(Self::MAX_PAGES > 0);
81        assert!(Self::RESERVED_BITS <= 32);
82        assert!(Self::SLOT_BITS <= 32);
83        assert!(Self::GENERATION_BITS <= 32);
84        true
85    };
86}
87
88impl<C: Config> ConfigPrivate for C {}
89
90struct DebugConfig<C>(PhantomData<C>);
91
92impl<C: Config> Debug for DebugConfig<C> {
93    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
94        f.debug_struct(std::any::type_name::<C>())
95            .field("INITIAL_PAGE_SIZE", &C::INITIAL_PAGE_SIZE)
96            .field("MAX_PAGES", &C::MAX_PAGES)
97            .field("RESERVED_BITS", &C::RESERVED_BITS)
98            .field("USED_BITS", &C::USED_BITS)
99            .field("SLOT_BITS", &C::SLOT_BITS)
100            .field("GENERATION_BITS", &C::GENERATION_BITS)
101            .field("MAX_SLOTS", &C::MAX_SLOTS)
102            .field("MAX_GENERATIONS", &C::MAX_GENERATIONS)
103            .finish()
104    }
105}
106
107#[test]
108fn test_default_config() {
109    assert_eq!(DefaultConfig::USED_BITS, 64);
110    assert_eq!(DefaultConfig::SLOT_BITS, 32);
111    assert_eq!(DefaultConfig::SLOT_MASK, u32::MAX);
112    assert_eq!(DefaultConfig::GENERATION_BITS, 32);
113    assert_eq!(DefaultConfig::GENERATION_MASK, u32::MAX);
114    assert_eq!(DefaultConfig::MAX_SLOTS, 4_294_967_264);
115    assert_eq!(DefaultConfig::MAX_GENERATIONS, 4_294_967_296);
116}
idr_ebr/config.rs

idr_ebr/
config.rs
