7 files changed, 396 insertions, 0 deletions

diff --git a/embassy-time-queue-utils/CHANGELOG.md b/embassy-time-queue-utils/CHANGELOG.md
new file mode 100644
index 000000000..03d89f9a7
--- /dev/null
+++ b/embassy-time-queue-utils/CHANGELOG.md
@@ -0,0 +1,23 @@
+# Changelog for embassy-time-queue-utils
+
+All notable changes to this project will be documented in this file.
+
+The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/),
+and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).
+
+<!-- next-header -->
+## Unreleased - ReleaseDate
+
+## 0.3.0 - 2025-08-26
+
+## 0.2.1 - 2025-08-26
+
+- Removed the embassy-executor dependency
+
+## 0.2.0 - 2025-08-04
+
+Bumped embassy-executor
+
+## 0.1.0 - 2024-01-11
+
+Initial release
diff --git a/embassy-time-queue-utils/Cargo.toml b/embassy-time-queue-utils/Cargo.toml
new file mode 100644
index 000000000..8da30c544
--- /dev/null
+++ b/embassy-time-queue-utils/Cargo.toml
@@ -0,0 +1,67 @@
+[package]
+name = "embassy-time-queue-utils"
+version = "0.3.0"
+edition = "2024"
+description = "Timer queue driver trait for embassy-time"
+repository = "https://github.com/embassy-rs/embassy"
+documentation = "https://docs.embassy.dev/embassy-time-queue-utils"
+readme = "README.md"
+license = "MIT OR Apache-2.0"
+categories = [
+    "embedded",
+    "no-std",
+    "concurrency",
+    "asynchronous",
+]
+
+# Prevent multiple copies of this crate in the same binary.
+# Needed because different copies might get different tick rates, causing
+# wrong delays if the time driver is using one copy and user code is using another.
+# This is especially common when mixing crates from crates.io and git.
+links = "embassy-time-queue"
+
+[dependencies]
+heapless = "0.8"
+embassy-executor-timer-queue = { version = "0.1", path = "../embassy-executor-timer-queue", features = ["timer-item-size-6-words"] }
+
+[features]
+#! ### Generic Queue
+
+#! By default this crate uses a timer queue implementation that is faster but depends on `embassy-executor`.
+#! It will panic if you try to await any timer when using another executor.
+#! 
+#! Alternatively, you can choose to use a "generic" timer queue implementation that works on any executor.
+#! To enable it, enable any of the features below.
+#! 
+#! The features also set how many timers are used for the generic queue. At most one
+#! `generic-queue-*` feature can be enabled. If none is enabled, a default of 64 timers is used.
+#!
+#! When using embassy-time-queue-driver from libraries, you should *not* enable any `generic-queue-*` feature, to allow the
+#! end user to pick.
+
+## Generic Queue with 8 timers
+generic-queue-8 = ["_generic-queue"]
+## Generic Queue with 16 timers
+generic-queue-16 = ["_generic-queue"]
+## Generic Queue with 32 timers
+generic-queue-32 = ["_generic-queue"]
+## Generic Queue with 64 timers
+generic-queue-64 = ["_generic-queue"]
+## Generic Queue with 128 timers
+generic-queue-128 = ["_generic-queue"]
+
+_generic-queue = []
+
+[package.metadata.embassy]
+build = [
+    {target = "thumbv6m-none-eabi", features = []},
+    {target = "thumbv6m-none-eabi", features = ["generic-queue-8"]},
+    # Xtensa builds
+    {group = "xtensa", build-std = ["core", "alloc"],  target = "xtensa-esp32s2-none-elf", features = []},
+    {group = "xtensa", build-std = ["core", "alloc"],  target = "xtensa-esp32s2-none-elf", features = ["generic-queue-8"]},
+]
+
+[package.metadata.embassy_docs]
+src_base = "https://github.com/embassy-rs/embassy/blob/embassy-time-queue-utils-v$VERSION/embassy-time-queue-utils/src/"
+src_base_git = "https://github.com/embassy-rs/embassy/blob/$COMMIT/embassy-time-queue-utils/src/"
+target = "x86_64-unknown-linux-gnu"
diff --git a/embassy-time-queue-utils/README.md b/embassy-time-queue-utils/README.md
new file mode 100644
index 000000000..36461f1cb
--- /dev/null
+++ b/embassy-time-queue-utils/README.md
@@ -0,0 +1,8 @@
+# embassy-time-queue-utils
+
+This crate contains timer queues to help implementing an [`embassy-time-driver`](https://crates.io/crates/embassy-time-driver).
+
+As a HAL user, you should not need to depend on this crate.
+
+As a HAL implementer, you need to depend on this crate if you want to implement a time driver,
+but how you should do so is documented in `embassy-time-driver`.
diff --git a/embassy-time-queue-utils/build.rs b/embassy-time-queue-utils/build.rs
new file mode 100644
index 000000000..f328e4d9d
--- /dev/null
+++ b/embassy-time-queue-utils/build.rs
@@ -0,0 +1 @@
+fn main() {}
diff --git a/embassy-time-queue-utils/src/lib.rs b/embassy-time-queue-utils/src/lib.rs
new file mode 100644
index 000000000..a6f66913f
--- /dev/null
+++ b/embassy-time-queue-utils/src/lib.rs
@@ -0,0 +1,13 @@
+#![no_std]
+#![doc = include_str!("../README.md")]
+#![warn(missing_docs)]
+
+#[cfg(feature = "_generic-queue")]
+pub mod queue_generic;
+#[cfg(not(feature = "_generic-queue"))]
+pub mod queue_integrated;
+
+#[cfg(feature = "_generic-queue")]
+pub use queue_generic::Queue;
+#[cfg(not(feature = "_generic-queue"))]
+pub use queue_integrated::Queue;
diff --git a/embassy-time-queue-utils/src/queue_generic.rs b/embassy-time-queue-utils/src/queue_generic.rs
new file mode 100644
index 000000000..88986953d
--- /dev/null
+++ b/embassy-time-queue-utils/src/queue_generic.rs
@@ -0,0 +1,148 @@
+//! Generic timer queue implementations.
+//!
+//! Time queue drivers may use this to simplify their implementation.
+
+use core::cmp::{Ordering, min};
+use core::task::Waker;
+
+use heapless::Vec;
+
+#[derive(Debug)]
+struct Timer {
+    at: u64,
+    waker: Waker,
+}
+
+impl PartialEq for Timer {
+    fn eq(&self, other: &Self) -> bool {
+        self.at == other.at
+    }
+}
+
+impl Eq for Timer {}
+
+impl PartialOrd for Timer {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        self.at.partial_cmp(&other.at)
+    }
+}
+
+impl Ord for Timer {
+    fn cmp(&self, other: &Self) -> Ordering {
+        self.at.cmp(&other.at)
+    }
+}
+
+/// A timer queue with a pre-determined capacity.
+#[derive(Debug)]
+pub struct ConstGenericQueue<const QUEUE_SIZE: usize> {
+    queue: Vec<Timer, QUEUE_SIZE>,
+}
+
+impl<const QUEUE_SIZE: usize> ConstGenericQueue<QUEUE_SIZE> {
+    /// Creates a new timer queue.
+    pub const fn new() -> Self {
+        Self { queue: Vec::new() }
+    }
+
+    /// Schedules a task to run at a specific time, and returns whether any changes were made.
+    ///
+    /// If this function returns `true`, the called should find the next expiration time and set
+    /// a new alarm for that time.
+    pub fn schedule_wake(&mut self, at: u64, waker: &Waker) -> bool {
+        self.queue
+            .iter_mut()
+            .find(|timer| timer.waker.will_wake(waker))
+            .map(|timer| {
+                if timer.at > at {
+                    timer.at = at;
+                    true
+                } else {
+                    false
+                }
+            })
+            .unwrap_or_else(|| {
+                let mut timer = Timer {
+                    waker: waker.clone(),
+                    at,
+                };
+
+                loop {
+                    match self.queue.push(timer) {
+                        Ok(()) => break,
+                        Err(e) => timer = e,
+                    }
+
+                    self.queue.pop().unwrap().waker.wake();
+                }
+
+                true
+            })
+    }
+
+    /// Dequeues expired timers and returns the next alarm time.
+    pub fn next_expiration(&mut self, now: u64) -> u64 {
+        let mut next_alarm = u64::MAX;
+
+        let mut i = 0;
+        while i < self.queue.len() {
+            let timer = &self.queue[i];
+            if timer.at <= now {
+                let timer = self.queue.swap_remove(i);
+                timer.waker.wake();
+            } else {
+                next_alarm = min(next_alarm, timer.at);
+                i += 1;
+            }
+        }
+
+        next_alarm
+    }
+}
+
+#[cfg(feature = "generic-queue-8")]
+const QUEUE_SIZE: usize = 8;
+#[cfg(feature = "generic-queue-16")]
+const QUEUE_SIZE: usize = 16;
+#[cfg(feature = "generic-queue-32")]
+const QUEUE_SIZE: usize = 32;
+#[cfg(feature = "generic-queue-64")]
+const QUEUE_SIZE: usize = 64;
+#[cfg(feature = "generic-queue-128")]
+const QUEUE_SIZE: usize = 128;
+#[cfg(not(any(
+    feature = "generic-queue-8",
+    feature = "generic-queue-16",
+    feature = "generic-queue-32",
+    feature = "generic-queue-64",
+    feature = "generic-queue-128"
+)))]
+const QUEUE_SIZE: usize = 64;
+
+/// A timer queue with a pre-determined capacity.
+#[derive(Debug)]
+pub struct Queue {
+    queue: ConstGenericQueue<QUEUE_SIZE>,
+}
+
+impl Queue {
+    /// Creates a new timer queue.
+    pub const fn new() -> Self {
+        Self {
+            queue: ConstGenericQueue::new(),
+        }
+    }
+
+    /// Schedules a task to run at a specific time, and returns whether any changes were made.
+    ///
+    /// If this function returns `true`, the called should find the next expiration time and set
+    /// a new alarm for that time.
+    pub fn schedule_wake(&mut self, at: u64, waker: &Waker) -> bool {
+        self.queue.schedule_wake(at, waker)
+    }
+
+    /// Dequeues expired timers and returns the next alarm time.
+    pub fn next_expiration(&mut self, now: u64) -> u64 {
+        self.queue.next_expiration(now)
+    }
+}
diff --git a/embassy-time-queue-utils/src/queue_integrated.rs b/embassy-time-queue-utils/src/queue_integrated.rs
new file mode 100644
index 000000000..2731d1ac6
--- /dev/null
+++ b/embassy-time-queue-utils/src/queue_integrated.rs
@@ -0,0 +1,136 @@
+//! Timer queue operations.
+use core::cell::Cell;
+use core::cmp::min;
+use core::ptr::NonNull;
+use core::task::Waker;
+
+use embassy_executor_timer_queue::TimerQueueItem;
+
+/// An item in the timer queue.
+#[derive(Default)]
+struct QueueItem {
+    /// The next item in the queue.
+    ///
+    /// If this field contains `Some`, the item is in the queue. The last item in the queue has a
+    /// value of `Some(dangling_pointer)`
+    pub next: Cell<Option<NonNull<QueueItem>>>,
+
+    /// The time at which this item expires.
+    pub expires_at: u64,
+
+    /// The registered waker. If Some, the item is enqueued in the timer queue.
+    pub waker: Option<Waker>,
+}
+
+unsafe impl Sync for QueueItem {}
+
+/// A timer queue, with items integrated into tasks.
+///
+/// # Safety
+///
+/// **This Queue is only safe when there is a single integrated queue in the system.**
+///
+/// If there are multiple integrated queues, additional checks are necessary to ensure that a Waker
+/// is not attempted to be enqueued in multiple queues.
+pub struct Queue {
+    head: Cell<Option<NonNull<QueueItem>>>,
+}
+
+impl core::fmt::Debug for Queue {
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        f.debug_struct("Queue").finish()
+    }
+}
+
+unsafe impl Send for Queue {}
+unsafe impl Sync for Queue {}
+
+impl Queue {
+    /// Creates a new timer queue.
+    pub const fn new() -> Self {
+        Self { head: Cell::new(None) }
+    }
+
+    /// Schedules a task to run at a specific time.
+    ///
+    /// If this function returns `true`, the called should find the next expiration time and set
+    /// a new alarm for that time.
+    pub fn schedule_wake(&mut self, at: u64, waker: &Waker) -> bool {
+        let item = unsafe {
+            // Safety: the `&mut self`, along with the Safety note of the Queue, are sufficient to
+            // ensure that this function creates the only mutable reference to the queue item.
+            TimerQueueItem::from_embassy_waker(waker)
+        };
+        let item = unsafe { item.as_mut::<QueueItem>() };
+        match item.waker.as_ref() {
+            Some(_) if at <= item.expires_at => {
+                // If expiration is sooner than previously set, update.
+                item.expires_at = at;
+                // The waker is always stored in its own queue item, so we don't need to update it.
+
+                // Trigger a queue update in case this item can be immediately dequeued.
+                true
+            }
+            Some(_) => {
+                // Queue item does not need to be updated, the task will be scheduled to be woken
+                // before the new expiration.
+                false
+            }
+            None => {
+                // If not in the queue, add it and update.
+                let mut item_ptr = NonNull::from(item);
+                let prev = self.head.replace(Some(item_ptr));
+
+                let item = unsafe { item_ptr.as_mut() };
+
+                item.expires_at = at;
+                item.waker = Some(waker.clone());
+                item.next.set(prev);
+                // The default implementation doesn't care about the
+                // opaque payload, leave it unchanged.
+
+                true
+            }
+        }
+    }
+
+    /// Dequeues expired timers and returns the next alarm time.
+    ///
+    /// The provided callback will be called for each expired task. Tasks that never expire
+    /// will be removed, but the callback will not be called.
+    pub fn next_expiration(&mut self, now: u64) -> u64 {
+        let mut next_expiration = u64::MAX;
+
+        self.retain(|item| {
+            if item.expires_at <= now {
+                // Timer expired, process task.
+                if let Some(waker) = item.waker.take() {
+                    waker.wake();
+                }
+                false
+            } else {
+                // Timer didn't yet expire, or never expires.
+                next_expiration = min(next_expiration, item.expires_at);
+                item.expires_at != u64::MAX
+            }
+        });
+
+        next_expiration
+    }
+
+    fn retain(&mut self, mut f: impl FnMut(&mut QueueItem) -> bool) {
+        let mut prev = &self.head;
+        while let Some(mut p) = prev.get() {
+            let mut item = unsafe { p.as_mut() };
+
+            if f(&mut item) {
+                // Skip to next
+                prev = &item.next;
+            } else {
+                // Remove it
+                prev.set(item.next.get());
+                item.next.set(None);
+            }
+        }
+    }
+}