embassy_time_queue_utils/
queue_generic.rs

1//! Generic timer queue implementations.
2//!
3//! Time queue drivers may use this to simplify their implementation.
4
5use core::cmp::{Ordering, min};
6use core::task::Waker;
7
8use heapless::Vec;
9
10#[derive(Debug)]
11struct Timer {
12    at: u64,
13    waker: Waker,
14}
15
16impl PartialEq for Timer {
17    fn eq(&self, other: &Self) -> bool {
18        self.at == other.at
19    }
20}
21
22impl Eq for Timer {}
23
24impl PartialOrd for Timer {
25    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
26        self.at.partial_cmp(&other.at)
27    }
28}
29
30impl Ord for Timer {
31    fn cmp(&self, other: &Self) -> Ordering {
32        self.at.cmp(&other.at)
33    }
34}
35
36/// A timer queue with a pre-determined capacity.
37#[derive(Debug)]
38pub struct ConstGenericQueue<const QUEUE_SIZE: usize> {
39    queue: Vec<Timer, QUEUE_SIZE>,
40}
41
42impl<const QUEUE_SIZE: usize> ConstGenericQueue<QUEUE_SIZE> {
43    /// Creates a new timer queue.
44    pub const fn new() -> Self {
45        Self { queue: Vec::new() }
46    }
47
48    /// Schedules a task to run at a specific time, and returns whether any changes were made.
49    ///
50    /// If this function returns `true`, the caller should find the next expiration time and set
51    /// a new alarm for that time.
52    pub fn schedule_wake(&mut self, at: u64, waker: &Waker) -> bool {
53        self.queue
54            .iter_mut()
55            .find(|timer| timer.waker.will_wake(waker))
56            .map(|timer| {
57                if timer.at > at {
58                    timer.at = at;
59                    true
60                } else {
61                    false
62                }
63            })
64            .unwrap_or_else(|| {
65                let mut timer = Timer {
66                    waker: waker.clone(),
67                    at,
68                };
69
70                loop {
71                    match self.queue.push(timer) {
72                        Ok(()) => break,
73                        Err(e) => timer = e,
74                    }
75
76                    self.queue.pop().unwrap().waker.wake();
77                }
78
79                true
80            })
81    }
82
83    /// Dequeues expired timers and returns the next alarm time.
84    pub fn next_expiration(&mut self, now: u64) -> u64 {
85        let mut next_alarm = u64::MAX;
86
87        let mut i = 0;
88        while i < self.queue.len() {
89            let timer = &self.queue[i];
90            if timer.at <= now {
91                let timer = self.queue.swap_remove(i);
92                timer.waker.wake();
93            } else {
94                next_alarm = min(next_alarm, timer.at);
95                i += 1;
96            }
97        }
98
99        next_alarm
100    }
101}
102
103#[cfg(feature = "generic-queue-8")]
104const QUEUE_SIZE: usize = 8;
105#[cfg(feature = "generic-queue-16")]
106const QUEUE_SIZE: usize = 16;
107#[cfg(feature = "generic-queue-32")]
108const QUEUE_SIZE: usize = 32;
109#[cfg(feature = "generic-queue-64")]
110const QUEUE_SIZE: usize = 64;
111#[cfg(feature = "generic-queue-128")]
112const QUEUE_SIZE: usize = 128;
113#[cfg(not(any(
114    feature = "generic-queue-8",
115    feature = "generic-queue-16",
116    feature = "generic-queue-32",
117    feature = "generic-queue-64",
118    feature = "generic-queue-128"
119)))]
120const QUEUE_SIZE: usize = 64;
121
122/// A timer queue with a pre-determined capacity.
123#[derive(Debug)]
124pub struct Queue {
125    queue: ConstGenericQueue<QUEUE_SIZE>,
126}
127
128impl Queue {
129    /// Creates a new timer queue.
130    pub const fn new() -> Self {
131        Self {
132            queue: ConstGenericQueue::new(),
133        }
134    }
135
136    /// Schedules a task to run at a specific time, and returns whether any changes were made.
137    ///
138    /// If this function returns `true`, the caller should find the next expiration time and set
139    /// a new alarm for that time.
140    pub fn schedule_wake(&mut self, at: u64, waker: &Waker) -> bool {
141        self.queue.schedule_wake(at, waker)
142    }
143
144    /// Dequeues expired timers and returns the next alarm time.
145    pub fn next_expiration(&mut self, now: u64) -> u64 {
146        self.queue.next_expiration(now)
147    }
148}
embassy_time_queue_utils/queue_generic.rs

embassy_time_queue_utils/
queue_generic.rs
