timer_kit/wheel/
level.rs

1use super::Stack;
2
3use std::fmt;
4
5/// Wheel for a single level in the timer. This wheel contains 64 slots.
6pub(crate) struct Level<T> {
7    level: usize,
8
9    /// Bit field tracking which slots currently contain entries.
10    ///
11    /// Using a bit field to track slots that contain entries allows avoiding a
12    /// scan to find entries. This field is updated when entries are added or
13    /// removed from a slot.
14    ///
15    /// The least-significant bit represents slot zero.
16    occupied: u64,
17
18    /// Slots
19    slot: [T; LEVEL_MULT],
20}
21
22/// Indicates when a slot must be processed next.
23#[derive(Debug)]
24pub(crate) struct Expiration {
25    /// The level containing the slot.
26    pub(crate) level: usize,
27
28    /// The slot index.
29    pub(crate) slot: usize,
30
31    /// The instant at which the slot needs to be processed.
32    pub(crate) deadline: u64,
33}
34
35/// Level multiplier.
36///
37/// Being a power of 2 is very important.
38const LEVEL_MULT: usize = 64;
39
40impl<T: Stack> Level<T> {
41    pub(crate) fn new(level: usize) -> Level<T> {
42        // Rust's derived implementations for arrays require that the value
43        // contained by the array be `Copy`. So, here we have to manually
44        // initialize every single slot.
45        macro_rules! s {
46            () => {
47                T::default()
48            };
49        }
50
51        Level {
52            level,
53            occupied: 0,
54            slot: [
55                // It does not look like the necessary traits are
56                // derived for [T; 64].
57                s!(),
58                s!(),
59                s!(),
60                s!(),
61                s!(),
62                s!(),
63                s!(),
64                s!(),
65                s!(),
66                s!(),
67                s!(),
68                s!(),
69                s!(),
70                s!(),
71                s!(),
72                s!(),
73                s!(),
74                s!(),
75                s!(),
76                s!(),
77                s!(),
78                s!(),
79                s!(),
80                s!(),
81                s!(),
82                s!(),
83                s!(),
84                s!(),
85                s!(),
86                s!(),
87                s!(),
88                s!(),
89                s!(),
90                s!(),
91                s!(),
92                s!(),
93                s!(),
94                s!(),
95                s!(),
96                s!(),
97                s!(),
98                s!(),
99                s!(),
100                s!(),
101                s!(),
102                s!(),
103                s!(),
104                s!(),
105                s!(),
106                s!(),
107                s!(),
108                s!(),
109                s!(),
110                s!(),
111                s!(),
112                s!(),
113                s!(),
114                s!(),
115                s!(),
116                s!(),
117                s!(),
118                s!(),
119                s!(),
120                s!(),
121            ],
122        }
123    }
124
125    /// Finds the slot that needs to be processed next and returns the slot and
126    /// `Instant` at which this slot must be processed.
127    pub(crate) fn next_expiration(&self, now: u64) -> Option<Expiration> {
128        // Use the `occupied` bit field to get the index of the next slot that
129        // needs to be processed.
130        let slot = match self.next_occupied_slot(now) {
131            Some(slot) => slot,
132            None => return None,
133        };
134
135        // From the slot index, calculate the `Instant` at which it needs to be
136        // processed. This value *must* be in the future with respect to `now`.
137
138        let level_range = level_range(self.level);
139        let slot_range = slot_range(self.level);
140
141        // TODO: This can probably be simplified w/ power of 2 math
142        let level_start = now - (now % level_range);
143        let deadline = level_start + slot as u64 * slot_range;
144
145        debug_assert!(
146            deadline >= now,
147            "deadline={}; now={}; level={}; slot={}; occupied={:b}",
148            deadline,
149            now,
150            self.level,
151            slot,
152            self.occupied
153        );
154
155        Some(Expiration {
156            level: self.level,
157            slot,
158            deadline,
159        })
160    }
161
162    fn next_occupied_slot(&self, now: u64) -> Option<usize> {
163        if self.occupied == 0 {
164            return None;
165        }
166
167        // Get the slot for now using Maths
168        let now_slot = (now / slot_range(self.level)) as usize;
169        let occupied = self.occupied.rotate_right(now_slot as u32);
170        let zeros = occupied.trailing_zeros() as usize;
171        let slot = (zeros + now_slot) % 64;
172
173        Some(slot)
174    }
175
176    pub(crate) fn add_entry(&mut self, when: u64, item: T::Owned, store: &mut T::Store) {
177        let slot = slot_for(when, self.level);
178
179        self.slot[slot].push(item, store);
180        self.occupied |= occupied_bit(slot);
181    }
182
183    pub(crate) fn remove_entry(&mut self, when: u64, item: &T::Borrowed, store: &mut T::Store) {
184        let slot = slot_for(when, self.level);
185
186        self.slot[slot].remove(item, store);
187
188        if self.slot[slot].is_empty() {
189            // The bit is currently set
190            debug_assert!(self.occupied & occupied_bit(slot) != 0);
191
192            // Unset the bit
193            self.occupied ^= occupied_bit(slot);
194        }
195    }
196
197    pub(crate) fn pop_entry_slot(&mut self, slot: usize, store: &mut T::Store) -> Option<T::Owned> {
198        let ret = self.slot[slot].pop(store);
199
200        if ret.is_some() && self.slot[slot].is_empty() {
201            // The bit is currently set
202            debug_assert!(self.occupied & occupied_bit(slot) != 0);
203
204            self.occupied ^= occupied_bit(slot);
205        }
206
207        ret
208    }
209}
210
211impl<T> fmt::Debug for Level<T> {
212    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
213        fmt.debug_struct("Level")
214            .field("occupied", &self.occupied)
215            .finish()
216    }
217}
218
219fn occupied_bit(slot: usize) -> u64 {
220    1 << slot
221}
222
223fn slot_range(level: usize) -> u64 {
224    LEVEL_MULT.pow(level as u32) as u64
225}
226
227fn level_range(level: usize) -> u64 {
228    LEVEL_MULT as u64 * slot_range(level)
229}
230
231/// Convert a duration (milliseconds) and a level to a slot position
232fn slot_for(duration: u64, level: usize) -> usize {
233    ((duration >> (level * 6)) % LEVEL_MULT as u64) as usize
234}
235
236#[cfg(all(test, not(loom)))]
237mod test {
238    use super::*;
239
240    #[test]
241    fn test_slot_for() {
242        for pos in 0..64 {
243            assert_eq!(pos as usize, slot_for(pos, 0));
244        }
245
246        for level in 1..5 {
247            for pos in level..64 {
248                let a = pos * 64_usize.pow(level as u32);
249                assert_eq!(pos as usize, slot_for(a as u64, level));
250            }
251        }
252    }
253}
timer_kit/wheel/level.rs

timer_kit/wheel/
level.rs
