1//! Timer queue operations.
2use core::cell::Cell;
3use core::cmp::min;
4use core::task::Waker;
5
6use embassy_executor::raw::TaskRef;
7
8/// A timer queue, with items integrated into tasks.
9pub struct Queue {
10 head: Cell<Option<TaskRef>>,
11}
12
13impl Queue {
14 /// Creates a new timer queue.
15 pub const fn new() -> Self {
16 Self { head: Cell::new(None) }
17 }
18
19 /// Schedules a task to run at a specific time.
20 ///
21 /// If this function returns `true`, the called should find the next expiration time and set
22 /// a new alarm for that time.
23 pub fn schedule_wake(&mut self, at: u64, waker: &Waker) -> bool {
24 let task = embassy_executor::raw::task_from_waker(waker);
25 let item = task.timer_queue_item();
26 if item.next.get().is_none() {
27 // If not in the queue, add it and update.
28 let prev = self.head.replace(Some(task));
29 item.next.set(if prev.is_none() {
30 Some(unsafe { TaskRef::dangling() })
31 } else {
32 prev
33 });
34 item.expires_at.set(at);
35 true
36 } else if at <= item.expires_at.get() {
37 // If expiration is sooner than previously set, update.
38 item.expires_at.set(at);
39 true
40 } else {
41 // Task does not need to be updated.
42 false
43 }
44 }
45
46 /// Dequeues expired timers and returns the next alarm time.
47 ///
48 /// The provided callback will be called for each expired task. Tasks that never expire
49 /// will be removed, but the callback will not be called.
50 pub fn next_expiration(&mut self, now: u64) -> u64 {
51 let mut next_expiration = u64::MAX;
52
53 self.retain(|p| {
54 let item = p.timer_queue_item();
55 let expires = item.expires_at.get();
56
57 if expires <= now {
58 // Timer expired, process task.
59 embassy_executor::raw::wake_task(p);
60 false
61 } else {
62 // Timer didn't yet expire, or never expires.
63 next_expiration = min(next_expiration, expires);
64 expires != u64::MAX
65 }
66 });
67
68 next_expiration
69 }
70
71 fn retain(&self, mut f: impl FnMut(TaskRef) -> bool) {
72 let mut prev = &self.head;
73 while let Some(p) = prev.get() {
74 if unsafe { p == TaskRef::dangling() } {
75 // prev was the last item, stop
76 break;
77 }
78 let item = p.timer_queue_item();
79 if f(p) {
80 // Skip to next
81 prev = &item.next;
82 } else {
83 // Remove it
84 prev.set(item.next.get());
85 item.next.set(None);
86 }
87 }
88 }
89}
90