idr_ebr/
key.rs

1use std::{marker::PhantomData, num::NonZeroU64};
2
3use crate::config::{Config, ConfigPrivate};
4
5// === Key ===
6
7/// Represents a key in the IDR.
8///
9/// Properties:
10/// * non-zero.
11/// * always 64bit, even on 32bit platforms.
12/// * contains reserved bits, generation, page and slot indexes.
13///
14/// See [`Config`] for more details.
15#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
16#[repr(transparent)]
17pub struct Key(NonZeroU64);
18
19impl Key {
20    /// # Safety
21    ///
22    /// Both parameters cannot be zero.
23    pub(crate) unsafe fn new_unchecked<C: Config>(slot_id: u32, generation: Generation<C>) -> Self {
24        debug_assert!(0 < slot_id && slot_id <= C::SLOT_MASK);
25        let raw = u64::from(generation.to_u32()) << C::SLOT_BITS | u64::from(slot_id);
26        // SAFETY: `raw` is non-zero because both parameters are non-zero.
27        Self(unsafe { NonZeroU64::new_unchecked(raw) })
28    }
29
30    pub(crate) fn page_no<C: Config>(self) -> PageNo<C> {
31        let slot_id = self.slot_id::<C>();
32
33        // Let's assume (for example):
34        // * width = 8bits
35        // * ips (initial page size) = 4
36        //
37        //   repr    page  index    slot
38        // +--------+----+-------+--------+
39        //  000001xx  0    0..=3   0..=3
40        //  00001xxx  1    0..=7   4..=11
41        //  0001xxxx  2    0..=15  12..=27
42        //  001xxxxx  3    0..=31  28..=59
43        //  01xxxxxx  4    0..=63  60..=123
44        //  1xxxxxxx  5    0..=127 124..=251
45        //
46        // Pros:
47        // * less operations on read by key than in sharded-slab
48        // * repr != 0 => key is non-zero
49        //
50        // Cons:
51        // * total capacity is less (by ips) compared to sharded-slab
52        //
53        // page = width - lz(repr >> log2(ips))
54        //      = (width - tz(ips) - 1) - lz(repr)   [2ops]
55        //        '-------------------'
56        //              constant
57        //
58        // index = repr - (1 << (tz(ips) + page))    [1op]
59        //                '---------------------'
60        //                         cached
61
62        let base = 32 - C::INITIAL_PAGE_SIZE.trailing_zeros() - 1;
63        let lz_repr = slot_id.leading_zeros();
64
65        // For valid keys, `base - lz_repr` is enough.
66        // However, keys can be created from `u64`, so the page bit can be unset.
67        let page_no = base.wrapping_sub(lz_repr);
68
69        PageNo::new(page_no)
70    }
71
72    pub(crate) fn slot_id<C: Config>(self) -> u32 {
73        self.0.get() as u32 & C::SLOT_MASK
74    }
75
76    pub(crate) fn generation<C: Config>(self) -> Generation<C> {
77        let generation = (self.0.get() >> C::SLOT_BITS) as u32 & C::GENERATION_MASK;
78        Generation::new(generation)
79    }
80}
81
82impl From<NonZeroU64> for Key {
83    fn from(raw: NonZeroU64) -> Self {
84        Self(raw)
85    }
86}
87
88impl From<Key> for NonZeroU64 {
89    fn from(key: Key) -> NonZeroU64 {
90        key.0
91    }
92}
93
94impl TryFrom<u64> for Key {
95    type Error = std::num::TryFromIntError;
96
97    fn try_from(raw: u64) -> Result<Self, Self::Error> {
98        NonZeroU64::try_from(raw).map(Into::into)
99    }
100}
101
102impl From<Key> for u64 {
103    fn from(key: Key) -> u64 {
104        key.0.get()
105    }
106}
107
108// === PageNo ===
109
110#[repr(transparent)]
111pub(crate) struct PageNo<C> {
112    value: u32,
113    _config: PhantomData<C>,
114}
115
116impl<C> Copy for PageNo<C> {}
117
118impl<C> Clone for PageNo<C> {
119    fn clone(&self) -> Self {
120        *self
121    }
122}
123
124impl<C: Config> PageNo<C> {
125    pub(crate) fn new(value: u32) -> Self {
126        Self {
127            value,
128            _config: PhantomData,
129        }
130    }
131
132    pub(crate) fn to_usize(self) -> usize {
133        self.value as usize
134    }
135
136    pub(crate) fn start_slot_id(self) -> u32 {
137        let shift = C::INITIAL_PAGE_SIZE.trailing_zeros() + self.value;
138        1 << shift
139    }
140
141    pub(crate) fn capacity(self) -> u32 {
142        C::INITIAL_PAGE_SIZE * 2u32.pow(self.value)
143    }
144}
145
146impl<C> PartialEq for PageNo<C> {
147    fn eq(&self, other: &Self) -> bool {
148        self.value == other.value
149    }
150}
151
152// === Generation ===
153
154#[repr(transparent)]
155pub(crate) struct Generation<C> {
156    value: u32,
157    _config: PhantomData<C>,
158}
159
160impl<C> Copy for Generation<C> {}
161
162impl<C> Clone for Generation<C> {
163    fn clone(&self) -> Self {
164        *self
165    }
166}
167
168impl<C: Config> Generation<C> {
169    pub(crate) fn new(value: u32) -> Self {
170        Self {
171            value,
172            _config: PhantomData,
173        }
174    }
175
176    pub(crate) fn to_u32(self) -> u32 {
177        self.value
178    }
179
180    pub(crate) fn inc(self) -> Self {
181        Self {
182            value: (self.value + 1) & C::GENERATION_MASK,
183            _config: PhantomData,
184        }
185    }
186}
187
188impl<C> PartialEq for Generation<C> {
189    fn eq(&self, other: &Self) -> bool {
190        self.value == other.value
191    }
192}
193
194#[test]
195#[allow(clippy::clone_on_copy)]
196fn test_roundtrip() {
197    let nz = NonZeroU64::new(42).unwrap();
198    assert_eq!(NonZeroU64::from(Key::from(nz)), nz);
199
200    let pn = PageNo::<crate::DefaultConfig>::new(42);
201    assert!(pn.clone() == pn);
202
203    let gn = Generation::<crate::DefaultConfig>::new(42);
204    assert!(gn.clone() == gn);
205}
idr_ebr/key.rs

idr_ebr/
key.rs
