tokio_timerd/
delay_queue.rs1use crate::timer::Timer;
2use futures_core::{ready, Stream};
3use slab::Slab;
4use std::cmp::{Ordering, Reverse};
5use std::collections::BinaryHeap;
6use std::io;
7use std::pin::Pin;
8use std::task::{Context, Poll};
9use std::time::{Duration, Instant};
10
11#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
13pub struct Key {
14 index: usize,
15 sequence: u64,
16}
17
18struct Slot<T> {
19 sequence: u64,
20 value: Option<Box<T>>,
21}
22
23struct Entry {
24 deadline: Instant,
25 index: usize,
26 sequence: u64,
27}
28
29impl PartialOrd for Entry {
30 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
31 Some(self.cmp(other))
32 }
33}
34
35impl Ord for Entry {
36 fn cmp(&self, other: &Self) -> Ordering {
37 self.deadline
38 .cmp(&other.deadline)
39 .then_with(|| self.sequence.cmp(&other.sequence))
40 }
41}
42
43impl PartialEq for Entry {
44 fn eq(&self, other: &Self) -> bool {
45 self.deadline == other.deadline && self.sequence == other.sequence
46 }
47}
48
49impl Eq for Entry {}
50
51pub struct DelayQueue<T> {
57 timer: Timer,
58 slots: Slab<Slot<T>>,
59 heap: BinaryHeap<Reverse<Entry>>,
60 next_sequence: u64,
61 active: usize,
62}
63
64impl<T> DelayQueue<T> {
65 pub fn new() -> io::Result<Self> {
67 Ok(Self {
68 timer: Timer::new()?,
69 slots: Slab::new(),
70 heap: BinaryHeap::new(),
71 next_sequence: 0,
72 active: 0,
73 })
74 }
75
76 pub fn insert_at(&mut self, value: T, deadline: Instant) -> Key {
78 let sequence = self.next_sequence;
79 self.next_sequence = self
80 .next_sequence
81 .checked_add(1)
82 .expect("DelayQueue sequence exhausted");
83
84 let index = self.slots.insert(Slot {
85 sequence,
86 value: Some(Box::new(value)),
87 });
88 self.heap.push(Reverse(Entry {
89 deadline,
90 index,
91 sequence,
92 }));
93 self.active += 1;
94
95 Key { index, sequence }
96 }
97
98 pub fn try_insert(&mut self, value: T, timeout: Duration) -> io::Result<Key> {
100 let deadline = Instant::now().checked_add(timeout).ok_or_else(|| {
101 io::Error::new(
102 io::ErrorKind::InvalidInput,
103 "delay exceeds the supported clock range",
104 )
105 })?;
106 Ok(self.insert_at(value, deadline))
107 }
108
109 pub fn insert(&mut self, value: T, timeout: Duration) -> Key {
115 self.try_insert(value, timeout)
116 .expect("delay exceeds the supported clock range")
117 }
118
119 pub fn remove(&mut self, key: Key) -> Option<T> {
121 let value = self
122 .slots
123 .get_mut(key.index)
124 .filter(|slot| slot.sequence == key.sequence)
125 .and_then(|slot| slot.value.take())
126 .map(|value| *value);
127
128 if value.is_some() {
129 self.active -= 1;
130 let removed_earliest = self.heap.peek().is_some_and(|entry| {
131 entry.0.index == key.index && entry.0.sequence == key.sequence
132 });
133 if removed_earliest {
134 self.timer.disarm();
135 }
136 }
137 value
138 }
139
140 pub fn clear(&mut self) {
142 self.heap.clear();
143 self.slots.clear();
144 self.active = 0;
145 self.timer.disarm();
146 }
147
148 pub fn len(&self) -> usize {
150 self.active
151 }
152
153 pub fn is_empty(&self) -> bool {
155 self.active == 0
156 }
157
158 fn is_stale(&self, entry: &Entry) -> bool {
159 self.slots.get(entry.index).map_or(true, |slot| {
160 slot.sequence != entry.sequence || slot.value.is_none()
161 })
162 }
163
164 fn next_deadline(&mut self) -> Option<Instant> {
165 loop {
166 let entry = self.heap.peek().map(|entry| &entry.0)?;
167 if self.is_stale(entry) {
168 self.heap.pop();
169 } else {
170 return Some(entry.deadline);
171 }
172 }
173 }
174
175 fn pop_expired(&mut self, deadline: Instant) -> Option<Expired<T>> {
176 while let Some(entry) = self.heap.pop() {
177 let entry = entry.0;
178 if entry.deadline > deadline {
179 self.heap.push(Reverse(entry));
180 return None;
181 }
182
183 let Some(slot) = self.slots.get_mut(entry.index) else {
184 continue;
185 };
186 if slot.sequence != entry.sequence {
187 continue;
188 }
189 let Some(value) = slot.value.take() else {
190 continue;
191 };
192
193 self.active -= 1;
194 return Some(Expired {
195 value,
196 deadline: entry.deadline,
197 key: Key {
198 index: entry.index,
199 sequence: entry.sequence,
200 },
201 });
202 }
203 None
204 }
205}
206
207pub struct Expired<T> {
209 value: Box<T>,
210 deadline: Instant,
211 key: Key,
212}
213
214impl<T> Expired<T> {
215 pub fn deadline(&self) -> Instant {
217 self.deadline
218 }
219
220 pub fn key(&self) -> Key {
222 self.key
223 }
224
225 pub fn into_inner(self) -> T {
227 *self.value
228 }
229}
230
231impl<T> Stream for DelayQueue<T> {
232 type Item = Result<Expired<T>, io::Error>;
233
234 fn size_hint(&self) -> (usize, Option<usize>) {
235 (self.active, Some(self.active))
236 }
237
238 fn poll_next(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Option<Self::Item>> {
239 loop {
240 let Some(deadline) = self.next_deadline() else {
241 self.timer.disarm();
242 return Poll::Pending;
243 };
244
245 if Instant::now() >= deadline {
246 if let Some(expired) = self.pop_expired(deadline) {
247 return Poll::Ready(Some(Ok(expired)));
248 }
249 continue;
250 }
251
252 self.timer.arm(deadline)?;
253 ready!(self.timer.poll_expired(cx))?;
254 }
255 }
256}
257
258#[cfg(test)]
259mod tests {
260 use super::*;
261 use futures::stream::StreamExt;
262
263 #[tokio::test]
264 async fn entries_expire_in_deadline_order() {
265 let mut queue = DelayQueue::new().unwrap();
266 queue.insert(3_u32, Duration::from_millis(30));
267 queue.insert(1_u32, Duration::from_millis(10));
268 queue.insert(2_u32, Duration::from_millis(20));
269
270 for expected in 1..=3 {
271 let expired = queue.next().await.unwrap().unwrap();
272 assert_eq!(expired.into_inner(), expected);
273 }
274 }
275
276 #[tokio::test]
277 async fn removing_earliest_entry_uses_next_deadline() {
278 let mut queue = DelayQueue::new().unwrap();
279 let first = queue.insert(1_u32, Duration::from_millis(10));
280 queue.insert(2_u32, Duration::from_millis(20));
281
282 assert_eq!(queue.remove(first), Some(1));
283 let expired = queue.next().await.unwrap().unwrap();
284 assert_eq!(expired.into_inner(), 2);
285 }
286
287 #[tokio::test]
288 async fn old_key_does_not_remove_reused_slot() {
289 let mut queue = DelayQueue::new().unwrap();
290 let old = queue.insert(1_u32, Duration::from_millis(10));
291 assert_eq!(queue.remove(old), Some(1));
292
293 queue.insert(2_u32, Duration::from_millis(10));
294 assert_eq!(queue.remove(old), None);
295 assert_eq!(queue.next().await.unwrap().unwrap().into_inner(), 2);
296 }
297
298 #[tokio::test]
299 async fn equal_deadlines_are_fifo() {
300 let mut queue = DelayQueue::new().unwrap();
301 let deadline = Instant::now() + Duration::from_millis(10);
302 queue.insert_at(1_u32, deadline);
303 queue.insert_at(2_u32, deadline);
304
305 assert_eq!(queue.next().await.unwrap().unwrap().into_inner(), 1);
306 assert_eq!(queue.next().await.unwrap().unwrap().into_inner(), 2);
307 }
308
309 #[tokio::test]
310 async fn overflow_is_rejected() {
311 let mut queue = DelayQueue::new().unwrap();
312 assert!(queue.try_insert(1_u32, Duration::MAX).is_err());
313 }
314
315 #[tokio::test]
316 async fn many_entries_share_one_timer() {
317 let mut queue = DelayQueue::new().unwrap();
318 for value in 0..64_u32 {
319 queue.insert(value, Duration::from_millis(1 + u64::from(value % 4)));
320 }
321
322 let mut received = Vec::new();
323 for _ in 0..64 {
324 received.push(queue.next().await.unwrap().unwrap().into_inner());
325 }
326 received.sort_unstable();
327 assert_eq!(received, (0..64).collect::<Vec<_>>());
328 }
329
330 #[tokio::test]
331 async fn clear_removes_entries() {
332 let mut queue = DelayQueue::new().unwrap();
333 queue.insert(1_u32, Duration::from_secs(1));
334 assert_eq!(queue.len(), 1);
335 queue.clear();
336 assert!(queue.is_empty());
337 }
338}