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

idr_ebr/
key.rs
