Skip to main content

tokio_timerd/
delay_queue.rs

1use 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/// Identifies an entry stored in a [`DelayQueue`].
12#[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
51/// A queue of values that become available after their deadlines elapse.
52///
53/// The queue owns one operating-system timer and multiplexes all entries
54/// through a min-heap, so adding many timers does not consume one native
55/// timer handle per entry.
56pub 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    /// Creates a new, empty queue.
66    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    /// Inserts `value` and returns a key that can remove it before expiration.
77    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    /// Tries to insert `value` to expire after `timeout`.
99    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    /// Inserts `value` to expire after `timeout`.
110    ///
111    /// # Panics
112    ///
113    /// Panics if the timeout exceeds the supported clock range.
114    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    /// Removes an entry if it has not expired.
120    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    /// Removes all entries and disarms the underlying timer.
141    pub fn clear(&mut self) {
142        self.heap.clear();
143        self.slots.clear();
144        self.active = 0;
145        self.timer.disarm();
146    }
147
148    /// Returns the number of unexpired entries.
149    pub fn len(&self) -> usize {
150        self.active
151    }
152
153    /// Returns `true` when the queue contains no unexpired entries.
154    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
207/// An entry returned after its deadline has elapsed.
208pub struct Expired<T> {
209    value: Box<T>,
210    deadline: Instant,
211    key: Key,
212}
213
214impl<T> Expired<T> {
215    /// Returns the deadline that expired.
216    pub fn deadline(&self) -> Instant {
217        self.deadline
218    }
219
220    /// Returns the key associated with the expired entry.
221    pub fn key(&self) -> Key {
222        self.key
223    }
224
225    /// Consumes the entry and returns its value.
226    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}