1 use crate::time::wheel::Stack;
2
3 use std::fmt;
4
5 /// Wheel for a single level in the timer. This wheel contains 64 slots.
6 pub(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)]
24 pub(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.
38 const LEVEL_MULT: usize = 64;
39
40 impl<T: Stack> Level<T> {
new(level: usize) -> 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.
next_expiration(&self, now: u64) -> Option<Expiration>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
next_occupied_slot(&self, now: u64) -> Option<usize>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
add_entry(&mut self, when: u64, item: T::Owned, store: &mut T::Store)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
remove_entry(&mut self, when: u64, item: &T::Borrowed, store: &mut T::Store)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
pop_entry_slot(&mut self, slot: usize, store: &mut T::Store) -> Option<T::Owned>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
211 impl<T> fmt::Debug for Level<T> {
fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result212 fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
213 fmt.debug_struct("Level")
214 .field("occupied", &self.occupied)
215 .finish()
216 }
217 }
218
occupied_bit(slot: usize) -> u64219 fn occupied_bit(slot: usize) -> u64 {
220 1 << slot
221 }
222
slot_range(level: usize) -> u64223 fn slot_range(level: usize) -> u64 {
224 LEVEL_MULT.pow(level as u32) as u64
225 }
226
level_range(level: usize) -> u64227 fn 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
slot_for(duration: u64, level: usize) -> usize232 fn 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)))]
237 mod test {
238 use super::*;
239
240 #[test]
test_slot_for()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 }
254