Merge #456

456: Cancel/reschedule support for monotonics r=AfoHT a=korken89

Design document: https://hackmd.io/lhUCzrKBS-66aadO4KsSzw?view

Co-authored-by: Emil Fresk <emil.fresk@gmail.com>

4 files changed, 652 insertions, 242 deletions

diff --git a/src/cyccnt.rs b/src/cyccnt.rs
deleted file mode 100644
index 8e07b00..0000000
--- a/src/cyccnt.rs
+++ /dev/null
@@ -1,221 +0,0 @@
-//! Data Watchpoint Trace (DWT) unit's CYCle CouNTer (CYCCNT)
-
-use core::{
-    cmp::Ordering,
-    convert::{Infallible, TryInto},
-    fmt, ops,
-};
-
-use cortex_m::peripheral::DWT;
-
-use crate::Fraction;
-
-/// A measurement of the CYCCNT. Opaque and useful only with `Duration`
-///
-/// This data type is only available on ARMv7-M
-///
-/// # Correctness
-///
-/// Adding or subtracting a `Duration` of more than `(1 << 31)` cycles to an `Instant` effectively
-/// makes it "wrap around" and creates an incorrect value. This is also true if the operation is
-/// done in steps, e.g. `(instant + dur) + dur` where `dur` is `(1 << 30)` ticks.
-#[derive(Clone, Copy, Eq, PartialEq)]
-pub struct Instant {
-    inner: i32,
-}
-
-impl Instant {
-    /// Returns an instant corresponding to "now"
-    ///
-    /// *HEADS UP* this function can, and will, return nonsensical values if called within `init`.
-    /// Only use it in `idle` and tasks. In `init`, use the `init::Context.start` field, or the
-    /// `CYCCNT::zero` function, instead of this function
-    pub fn now() -> Self {
-        Instant {
-            inner: DWT::get_cycle_count() as i32,
-        }
-    }
-
-    /// Returns the amount of time elapsed since this instant was created.
-    pub fn elapsed(&self) -> Duration {
-        let diff = Instant::now().inner.wrapping_sub(self.inner);
-        assert!(diff >= 0, "instant now is earlier than self");
-        Duration { inner: diff as u32 }
-    }
-
-    /// Returns the amount of time elapsed from another instant to this one.
-    pub fn duration_since(&self, earlier: Instant) -> Duration {
-        let diff = self.inner.wrapping_sub(earlier.inner);
-        assert!(diff >= 0, "second instant is later than self");
-        Duration { inner: diff as u32 }
-    }
-}
-
-impl fmt::Debug for Instant {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_tuple("Instant")
-            .field(&(self.inner as u32))
-            .finish()
-    }
-}
-
-impl ops::AddAssign<Duration> for Instant {
-    fn add_assign(&mut self, dur: Duration) {
-        // NOTE this is a debug assertion because there's no foolproof way to detect a wrap around;
-        // the user may write `(instant + dur) + dur` where `dur` is `(1<<31)-1` ticks.
-        debug_assert!(dur.inner < (1 << 31));
-        self.inner = self.inner.wrapping_add(dur.inner as i32);
-    }
-}
-
-impl ops::Add<Duration> for Instant {
-    type Output = Self;
-
-    fn add(mut self, dur: Duration) -> Self {
-        self += dur;
-        self
-    }
-}
-
-impl ops::SubAssign<Duration> for Instant {
-    fn sub_assign(&mut self, dur: Duration) {
-        // NOTE see the NOTE in `<Instant as AddAssign<Duration>>::add_assign`
-        debug_assert!(dur.inner < (1 << 31));
-        self.inner = self.inner.wrapping_sub(dur.inner as i32);
-    }
-}
-
-impl ops::Sub<Duration> for Instant {
-    type Output = Self;
-
-    fn sub(mut self, dur: Duration) -> Self {
-        self -= dur;
-        self
-    }
-}
-
-impl ops::Sub<Instant> for Instant {
-    type Output = Duration;
-
-    fn sub(self, other: Instant) -> Duration {
-        self.duration_since(other)
-    }
-}
-
-impl Ord for Instant {
-    fn cmp(&self, rhs: &Self) -> Ordering {
-        self.inner.wrapping_sub(rhs.inner).cmp(&0)
-    }
-}
-
-impl PartialOrd for Instant {
-    fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
-        Some(self.cmp(rhs))
-    }
-}
-
-/// A `Duration` type to represent a span of time.
-///
-/// This data type is only available on ARMv7-M
-///
-/// # Correctness
-///
-/// This type is *not* appropriate for representing time spans in the order of, or larger than,
-/// seconds because it can hold a maximum of `(1 << 31)` "ticks" where each tick is the inverse of
-/// the CPU frequency, which usually is dozens of MHz.
-#[derive(Clone, Copy, Default, Eq, Ord, PartialEq, PartialOrd)]
-pub struct Duration {
-    inner: u32,
-}
-
-impl Duration {
-    /// Creates a new `Duration` from the specified number of clock cycles
-    pub fn from_cycles(cycles: u32) -> Self {
-        Duration { inner: cycles }
-    }
-
-    /// Returns the total number of clock cycles contained by this `Duration`
-    pub fn as_cycles(&self) -> u32 {
-        self.inner
-    }
-}
-
-impl TryInto<u32> for Duration {
-    type Error = Infallible;
-
-    fn try_into(self) -> Result<u32, Infallible> {
-        Ok(self.as_cycles())
-    }
-}
-
-impl ops::AddAssign for Duration {
-    fn add_assign(&mut self, dur: Duration) {
-        self.inner += dur.inner;
-    }
-}
-
-impl ops::Add<Duration> for Duration {
-    type Output = Self;
-
-    fn add(self, other: Self) -> Self {
-        Duration {
-            inner: self.inner + other.inner,
-        }
-    }
-}
-
-impl ops::SubAssign for Duration {
-    fn sub_assign(&mut self, rhs: Duration) {
-        self.inner -= rhs.inner;
-    }
-}
-
-impl ops::Sub<Duration> for Duration {
-    type Output = Self;
-
-    fn sub(self, rhs: Self) -> Self {
-        Duration {
-            inner: self.inner - rhs.inner,
-        }
-    }
-}
-
-/// Adds the `cycles` method to the `u32` type
-///
-/// This trait is only available on ARMv7-M
-pub trait U32Ext {
-    /// Converts the `u32` value into clock cycles
-    fn cycles(self) -> Duration;
-}
-
-impl U32Ext for u32 {
-    fn cycles(self) -> Duration {
-        Duration { inner: self }
-    }
-}
-
-/// Implementation of the `Monotonic` trait based on CYCle CouNTer
-pub struct CYCCNT;
-
-impl crate::Monotonic for CYCCNT {
-    type Instant = Instant;
-
-    fn ratio() -> Fraction {
-        Fraction {
-            numerator: 1,
-            denominator: 1,
-        }
-    }
-
-    unsafe fn reset() {
-        (0xE0001004 as *mut u32).write_volatile(0)
-    }
-
-    fn now() -> Instant {
-        Instant::now()
-    }
-
-    fn zero() -> Instant {
-        Instant { inner: 0 }
-    }
-}
diff --git a/src/lib.rs b/src/lib.rs
index 8220739..a4abc4c 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -43,6 +43,8 @@ pub use rtic_monotonic::{self, embedded_time as time, Monotonic};
 #[doc(hidden)]
 pub mod export;
 #[doc(hidden)]
+mod linked_list;
+#[doc(hidden)]
 mod tq;
 
 /// Sets the given `interrupt` as pending
diff --git a/src/linked_list.rs b/src/linked_list.rs
new file mode 100644
index 0000000..6a9836e
--- /dev/null
+++ b/src/linked_list.rs
@@ -0,0 +1,599 @@
+use core::fmt;
+use core::marker::PhantomData;
+use core::mem::MaybeUninit;
+use core::ops::{Deref, DerefMut};
+use core::ptr;
+pub use generic_array::ArrayLength;
+use generic_array::GenericArray;
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
+struct LinkedIndex(u16);
+
+impl LinkedIndex {
+    #[inline]
+    const unsafe fn new_unchecked(value: u16) -> Self {
+        LinkedIndex(value)
+    }
+
+    #[inline]
+    const fn none() -> Self {
+        LinkedIndex(u16::MAX)
+    }
+
+    #[inline]
+    const fn option(self) -> Option<u16> {
+        if self.0 == u16::MAX {
+            None
+        } else {
+            Some(self.0)
+        }
+    }
+}
+
+/// A node in the linked list.
+pub struct Node<T> {
+    val: MaybeUninit<T>,
+    next: LinkedIndex,
+}
+
+/// Iterator for the linked list.
+pub struct Iter<'a, T, Kind, N>
+where
+    T: PartialEq + PartialOrd,
+    Kind: kind::Kind,
+    N: ArrayLength<Node<T>>,
+{
+    list: &'a LinkedList<T, Kind, N>,
+    index: LinkedIndex,
+}
+
+impl<'a, T, Kind, N> Iterator for Iter<'a, T, Kind, N>
+where
+    T: PartialEq + PartialOrd,
+    Kind: kind::Kind,
+    N: ArrayLength<Node<T>>,
+{
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let index = self.index.option()?;
+
+        let node = self.list.node_at(index as usize);
+        self.index = node.next;
+
+        Some(self.list.read_data_in_node_at(index as usize))
+    }
+}
+
+/// Comes from [`LinkedList::find_mut`].
+pub struct FindMut<'a, T, Kind, N>
+where
+    T: PartialEq + PartialOrd,
+    Kind: kind::Kind,
+    N: ArrayLength<Node<T>>,
+{
+    list: &'a mut LinkedList<T, Kind, N>,
+    is_head: bool,
+    prev_index: LinkedIndex,
+    index: LinkedIndex,
+    maybe_changed: bool,
+}
+
+impl<'a, T, Kind, N> FindMut<'a, T, Kind, N>
+where
+    T: PartialEq + PartialOrd,
+    Kind: kind::Kind,
+    N: ArrayLength<Node<T>>,
+{
+    fn pop_internal(&mut self) -> T {
+        if self.is_head {
+            // If it is the head element, we can do a normal pop
+            unsafe { self.list.pop_unchecked() }
+        } else {
+            // Somewhere in the list
+
+            // Re-point the previous index
+            self.list.node_at_mut(self.prev_index.0 as usize).next =
+                self.list.node_at_mut(self.index.0 as usize).next;
+
+            // Release the index into the free queue
+            self.list.node_at_mut(self.index.0 as usize).next = self.list.free;
+            self.list.free = self.index;
+
+            self.list.extract_data_in_node_at(self.index.0 as usize)
+        }
+    }
+
+    /// This will pop the element from the list.
+    ///
+    /// Complexity is O(1).
+    #[inline]
+    pub fn pop(mut self) -> T {
+        self.pop_internal()
+    }
+
+    /// This will resort the element into the correct position in the list in needed.
+    /// Same as calling `drop`.
+    ///
+    /// Complexity is worst-case O(N).
+    #[inline]
+    pub fn finish(self) {
+        drop(self)
+    }
+}
+
+impl<T, Kind, N> Drop for FindMut<'_, T, Kind, N>
+where
+    T: PartialEq + PartialOrd,
+    Kind: kind::Kind,
+    N: ArrayLength<Node<T>>,
+{
+    fn drop(&mut self) {
+        // Only resort the list if the element has changed
+        if self.maybe_changed {
+            let val = self.pop_internal();
+            unsafe { self.list.push_unchecked(val) };
+        }
+    }
+}
+
+impl<T, Kind, N> Deref for FindMut<'_, T, Kind, N>
+where
+    T: PartialEq + PartialOrd,
+    Kind: kind::Kind,
+    N: ArrayLength<Node<T>>,
+{
+    type Target = T;
+
+    fn deref(&self) -> &Self::Target {
+        self.list.read_data_in_node_at(self.index.0 as usize)
+    }
+}
+
+impl<T, Kind, N> DerefMut for FindMut<'_, T, Kind, N>
+where
+    T: PartialEq + PartialOrd,
+    Kind: kind::Kind,
+    N: ArrayLength<Node<T>>,
+{
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        self.maybe_changed = true;
+        self.list.read_mut_data_in_node_at(self.index.0 as usize)
+    }
+}
+
+impl<T, Kind, N> fmt::Debug for FindMut<'_, T, Kind, N>
+where
+    T: PartialEq + PartialOrd + core::fmt::Debug,
+    Kind: kind::Kind,
+    N: ArrayLength<Node<T>>,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_struct("FindMut")
+            .field("prev_index", &self.prev_index)
+            .field("index", &self.index)
+            .field(
+                "prev_value",
+                &self
+                    .list
+                    .read_data_in_node_at(self.prev_index.option().unwrap() as usize),
+            )
+            .field(
+                "value",
+                &self
+                    .list
+                    .read_data_in_node_at(self.index.option().unwrap() as usize),
+            )
+            .finish()
+    }
+}
+
+/// The linked list.
+pub struct LinkedList<T, Kind, N>
+where
+    T: PartialEq + PartialOrd,
+    Kind: kind::Kind,
+    N: ArrayLength<Node<T>>,
+{
+    list: MaybeUninit<GenericArray<Node<T>, N>>,
+    head: LinkedIndex,
+    free: LinkedIndex,
+    _kind: PhantomData<Kind>,
+}
+
+impl<T, Kind, N> LinkedList<T, Kind, N>
+where
+    T: PartialEq + PartialOrd,
+    Kind: kind::Kind,
+    N: ArrayLength<Node<T>>,
+{
+    /// Internal helper to not do pointer arithmetic all over the place.
+    #[inline]
+    fn node_at(&self, index: usize) -> &Node<T> {
+        // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
+        unsafe { &*(self.list.as_ptr() as *const Node<T>).add(index) }
+    }
+
+    /// Internal helper to not do pointer arithmetic all over the place.
+    #[inline]
+    fn node_at_mut(&mut self, index: usize) -> &mut Node<T> {
+        // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
+        unsafe { &mut *(self.list.as_mut_ptr() as *mut Node<T>).add(index) }
+    }
+
+    /// Internal helper to not do pointer arithmetic all over the place.
+    #[inline]
+    fn write_data_in_node_at(&mut self, index: usize, data: T) {
+        unsafe {
+            self.node_at_mut(index).val.as_mut_ptr().write(data);
+        }
+    }
+
+    /// Internal helper to not do pointer arithmetic all over the place.
+    #[inline]
+    fn read_data_in_node_at(&self, index: usize) -> &T {
+        unsafe { &*self.node_at(index).val.as_ptr() }
+    }
+
+    /// Internal helper to not do pointer arithmetic all over the place.
+    #[inline]
+    fn read_mut_data_in_node_at(&mut self, index: usize) -> &mut T {
+        unsafe { &mut *self.node_at_mut(index).val.as_mut_ptr() }
+    }
+
+    /// Internal helper to not do pointer arithmetic all over the place.
+    #[inline]
+    fn extract_data_in_node_at(&mut self, index: usize) -> T {
+        unsafe { self.node_at(index).val.as_ptr().read() }
+    }
+
+    /// Internal helper to not do pointer arithmetic all over the place.
+    /// Safety: This can overwrite existing allocated nodes if used improperly, meaning their
+    /// `Drop` methods won't run.
+    #[inline]
+    unsafe fn write_node_at(&mut self, index: usize, node: Node<T>) {
+        (self.list.as_mut_ptr() as *mut Node<T>)
+            .add(index)
+            .write(node)
+    }
+
+    /// Create a new linked list.
+    pub fn new() -> Self {
+        let mut list = LinkedList {
+            list: MaybeUninit::uninit(),
+            head: LinkedIndex::none(),
+            free: unsafe { LinkedIndex::new_unchecked(0) },
+            _kind: PhantomData,
+        };
+
+        let len = N::U16;
+        let mut free = 0;
+
+        // Initialize indexes
+        while free < len - 1 {
+            unsafe {
+                list.write_node_at(
+                    free as usize,
+                    Node {
+                        val: MaybeUninit::uninit(),
+                        next: LinkedIndex::new_unchecked(free + 1),
+                    },
+                );
+            }
+            free += 1;
+        }
+
+        // Initialize final index
+        unsafe {
+            list.write_node_at(
+                free as usize,
+                Node {
+                    val: MaybeUninit::uninit(),
+                    next: LinkedIndex::none(),
+                },
+            );
+        }
+
+        list
+    }
+
+    /// Push unchecked
+    ///
+    /// Complexity is O(N).
+    ///
+    /// # Safety
+    ///
+    /// Assumes that the list is not full.
+    pub unsafe fn push_unchecked(&mut self, value: T) {
+        let new = self.free.0;
+        // Store the data and update the next free spot
+        self.write_data_in_node_at(new as usize, value);
+        self.free = self.node_at(new as usize).next;
+
+        if let Some(head) = self.head.option() {
+            // Check if we need to replace head
+            if self
+                .read_data_in_node_at(head as usize)
+                .partial_cmp(self.read_data_in_node_at(new as usize))
+                != Kind::ordering()
+            {
+                self.node_at_mut(new as usize).next = self.head;
+                self.head = LinkedIndex::new_unchecked(new);
+            } else {
+                // It's not head, search the list for the correct placement
+                let mut current = head;
+
+                while let Some(next) = self.node_at(current as usize).next.option() {
+                    if self
+                        .read_data_in_node_at(next as usize)
+                        .partial_cmp(self.read_data_in_node_at(new as usize))
+                        != Kind::ordering()
+                    {
+                        break;
+                    }
+
+                    current = next;
+                }
+
+                self.node_at_mut(new as usize).next = self.node_at(current as usize).next;
+                self.node_at_mut(current as usize).next = LinkedIndex::new_unchecked(new);
+            }
+        } else {
+            self.node_at_mut(new as usize).next = self.head;
+            self.head = LinkedIndex::new_unchecked(new);
+        }
+    }
+
+    /// Pushes an element to the linked list and sorts it into place.
+    ///
+    /// Complexity is O(N).
+    pub fn push(&mut self, value: T) -> Result<(), T> {
+        if !self.is_full() {
+            Ok(unsafe { self.push_unchecked(value) })
+        } else {
+            Err(value)
+        }
+    }
+
+    /// Get an iterator over the sorted list.
+    pub fn iter(&self) -> Iter<'_, T, Kind, N> {
+        Iter {
+            list: self,
+            index: self.head,
+        }
+    }
+
+    /// Find an element in the list.
+    pub fn find_mut<F>(&mut self, mut f: F) -> Option<FindMut<'_, T, Kind, N>>
+    where
+        F: FnMut(&T) -> bool,
+    {
+        let head = self.head.option()?;
+
+        // Special-case, first element
+        if f(self.read_data_in_node_at(head as usize)) {
+            return Some(FindMut {
+                is_head: true,
+                prev_index: LinkedIndex::none(),
+                index: self.head,
+                list: self,
+                maybe_changed: false,
+            });
+        }
+
+        let mut current = head;
+
+        while let Some(next) = self.node_at(current as usize).next.option() {
+            if f(self.read_data_in_node_at(next as usize)) {
+                return Some(FindMut {
+                    is_head: false,
+                    prev_index: unsafe { LinkedIndex::new_unchecked(current) },
+                    index: unsafe { LinkedIndex::new_unchecked(next) },
+                    list: self,
+                    maybe_changed: false,
+                });
+            }
+
+            current = next;
+        }
+
+        None
+    }
+
+    /// Peek at the first element.
+    pub fn peek(&self) -> Option<&T> {
+        self.head
+            .option()
+            .map(|head| self.read_data_in_node_at(head as usize))
+    }
+
+    /// Pop unchecked
+    ///
+    /// # Safety
+    ///
+    /// Assumes that the list is not empty.
+    pub unsafe fn pop_unchecked(&mut self) -> T {
+        let head = self.head.0;
+        let current = head;
+        self.head = self.node_at(head as usize).next;
+        self.node_at_mut(current as usize).next = self.free;
+        self.free = LinkedIndex::new_unchecked(current);
+
+        self.extract_data_in_node_at(current as usize)
+    }
+
+    /// Pops the first element in the list.
+    ///
+    /// Complexity is O(1).
+    pub fn pop(&mut self) -> Result<T, ()> {
+        if !self.is_empty() {
+            Ok(unsafe { self.pop_unchecked() })
+        } else {
+            Err(())
+        }
+    }
+
+    /// Checks if the linked list is full.
+    #[inline]
+    pub fn is_full(&self) -> bool {
+        self.free.option().is_none()
+    }
+
+    /// Checks if the linked list is empty.
+    #[inline]
+    pub fn is_empty(&self) -> bool {
+        self.head.option().is_none()
+    }
+}
+
+impl<T, Kind, N> Drop for LinkedList<T, Kind, N>
+where
+    T: PartialEq + PartialOrd,
+    Kind: kind::Kind,
+    N: ArrayLength<Node<T>>,
+{
+    fn drop(&mut self) {
+        let mut index = self.head;
+
+        while let Some(i) = index.option() {
+            let node = self.node_at_mut(i as usize);
+            index = node.next;
+
+            unsafe {
+                ptr::drop_in_place(node.val.as_mut_ptr());
+            }
+        }
+    }
+}
+
+impl<T, Kind, N> fmt::Debug for LinkedList<T, Kind, N>
+where
+    T: PartialEq + PartialOrd + core::fmt::Debug,
+    Kind: kind::Kind,
+    N: ArrayLength<Node<T>>,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_list().entries(self.iter()).finish()
+    }
+}
+
+/// Min sorted linked list.
+pub struct Min;
+
+/// Max sorted linked list.
+pub struct Max;
+
+/// Sealed traits and implementations for `linked_list`
+pub mod kind {
+    use super::{Max, Min};
+    use core::cmp::Ordering;
+
+    /// The linked list kind: min first or max first
+    pub unsafe trait Kind {
+        #[doc(hidden)]
+        fn ordering() -> Option<Ordering>;
+    }
+
+    unsafe impl Kind for Min {
+        #[inline]
+        fn ordering() -> Option<Ordering> {
+            Some(Ordering::Less)
+        }
+    }
+
+    unsafe impl Kind for Max {
+        #[inline]
+        fn ordering() -> Option<Ordering> {
+            Some(Ordering::Greater)
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    // Note this useful idiom: importing names from outer (for mod tests) scope.
+    use super::*;
+    use generic_array::typenum::consts::*;
+
+    #[test]
+    fn test_peek() {
+        let mut ll: LinkedList<u32, Max, U3> = LinkedList::new();
+
+        ll.push(1).unwrap();
+        assert_eq!(ll.peek().unwrap(), &1);
+
+        ll.push(2).unwrap();
+        assert_eq!(ll.peek().unwrap(), &2);
+
+        ll.push(3).unwrap();
+        assert_eq!(ll.peek().unwrap(), &3);
+
+        let mut ll: LinkedList<u32, Min, U3> = LinkedList::new();
+
+        ll.push(2).unwrap();
+        assert_eq!(ll.peek().unwrap(), &2);
+
+        ll.push(1).unwrap();
+        assert_eq!(ll.peek().unwrap(), &1);
+
+        ll.push(3).unwrap();
+        assert_eq!(ll.peek().unwrap(), &1);
+    }
+
+    #[test]
+    fn test_full() {
+        let mut ll: LinkedList<u32, Max, U3> = LinkedList::new();
+        ll.push(1).unwrap();
+        ll.push(2).unwrap();
+        ll.push(3).unwrap();
+
+        assert!(ll.is_full())
+    }
+
+    #[test]
+    fn test_empty() {
+        let ll: LinkedList<u32, Max, U3> = LinkedList::new();
+
+        assert!(ll.is_empty())
+    }
+
+    #[test]
+    fn test_rejected_push() {
+        let mut ll: LinkedList<u32, Max, U3> = LinkedList::new();
+        ll.push(1).unwrap();
+        ll.push(2).unwrap();
+        ll.push(3).unwrap();
+
+        // This won't fit
+        let r = ll.push(4);
+
+        assert_eq!(r, Err(4));
+    }
+
+    #[test]
+    fn test_updating() {
+        let mut ll: LinkedList<u32, Max, U3> = LinkedList::new();
+        ll.push(1).unwrap();
+        ll.push(2).unwrap();
+        ll.push(3).unwrap();
+
+        let mut find = ll.find_mut(|v| *v == 2).unwrap();
+
+        *find += 1000;
+        find.finish();
+
+        assert_eq!(ll.peek().unwrap(), &1002);
+
+        let mut find = ll.find_mut(|v| *v == 3).unwrap();
+
+        *find += 1000;
+        find.finish();
+
+        assert_eq!(ll.peek().unwrap(), &1003);
+
+        // Remove largest element
+        ll.find_mut(|v| *v == 1003).unwrap().pop();
+
+        assert_eq!(ll.peek().unwrap(), &1002);
+    }
+}
diff --git a/src/tq.rs b/src/tq.rs
index 063bbd8..3864025 100644
--- a/src/tq.rs
+++ b/src/tq.rs
@@ -1,22 +1,35 @@
 use crate::{
+    linked_list::{ArrayLength, LinkedList, Min, Node},
     time::{Clock, Instant},
     Monotonic,
 };
 use core::cmp::Ordering;
-use heapless::{binary_heap::Min, ArrayLength, BinaryHeap};
 
-pub struct TimerQueue<Mono, Task, N>(pub BinaryHeap<NotReady<Mono, Task>, N, Min>)
+#[inline(always)]
+fn unwrapper<T, E>(val: Result<T, E>) -> T {
+    if let Ok(v) = val {
+        v
+    } else {
+        unreachable!("Your monotonic is not infallible")
+    }
+}
+
+pub struct TimerQueue<Mono, Task, N>(pub LinkedList<NotReady<Mono, Task>, Min, N>)
 where
     Mono: Monotonic,
-    N: ArrayLength<NotReady<Mono, Task>>,
+    N: ArrayLength<Node<NotReady<Mono, Task>>>,
     Task: Copy;
 
 impl<Mono, Task, N> TimerQueue<Mono, Task, N>
 where
     Mono: Monotonic,
-    N: ArrayLength<NotReady<Mono, Task>>,
+    N: ArrayLength<Node<NotReady<Mono, Task>>>,
     Task: Copy,
 {
+    pub fn new() -> Self {
+        TimerQueue(LinkedList::new())
+    }
+
     /// # Safety
     ///
     /// Writing to memory with a transmute in order to enable
@@ -34,26 +47,20 @@ where
         F1: FnOnce(),
         F2: FnOnce(),
     {
-        let mut is_empty = true;
         // Check if the top contains a non-empty element and if that element is
         // greater than nr
         let if_heap_max_greater_than_nr = self
             .0
             .peek()
-            .map(|head| {
-                is_empty = false;
-                nr.instant < head.instant
-            })
+            .map(|head| nr.instant < head.instant)
             .unwrap_or(true);
+
         if if_heap_max_greater_than_nr {
-            if Mono::DISABLE_INTERRUPT_ON_EMPTY_QUEUE && is_empty {
-                // mem::transmute::<_, SYST>(()).enable_interrupt();A
+            if Mono::DISABLE_INTERRUPT_ON_EMPTY_QUEUE && self.0.is_empty() {
                 mono.enable_timer();
                 enable_interrupt();
             }
 
-            // Set SysTick pending
-            // SCB::set_pendst();
             pend_handler();
         }
 
@@ -66,17 +73,39 @@ where
         self.0.is_empty()
     }
 
-    #[inline]
-    fn unwrapper<T, E>(val: Result<T, E>) -> T {
-        if let Ok(v) = val {
-            v
+    /// Cancel the marker value
+    pub fn cancel_marker(&mut self, marker: u32) -> Option<(Task, u8)> {
+        if let Some(val) = self.0.find_mut(|nr| nr.marker == marker) {
+            let nr = val.pop();
+
+            Some((nr.task, nr.index))
         } else {
-            unreachable!("Your monotonic is not infallible")
+            None
+        }
+    }
+
+    /// Update the instant at an marker value to a new instant
+    pub fn update_marker<F: FnOnce()>(
+        &mut self,
+        marker: u32,
+        new_marker: u32,
+        instant: Instant<Mono>,
+        pend_handler: F,
+    ) -> Result<(), ()> {
+        if let Some(mut val) = self.0.find_mut(|nr| nr.marker == marker) {
+            val.instant = instant;
+            val.marker = new_marker;
+
+            // On update pend the handler to reconfigure the next compare match
+            pend_handler();
+
+            Ok(())
+        } else {
+            Err(())
         }
     }
 
     /// Dequeue a task from the TimerQueue
-    #[inline]
     pub fn dequeue<F>(&mut self, disable_interrupt: F, mono: &mut Mono) -> Option<(Task, u8)>
     where
         F: FnOnce(),
@@ -84,7 +113,7 @@ where
         mono.clear_compare_flag();
 
         if let Some(instant) = self.0.peek().map(|p| p.instant) {
-            if instant <= Self::unwrapper(Clock::try_now(mono)) {
+            if instant <= unwrapper(Clock::try_now(mono)) {
                 // task became ready
                 let nr = unsafe { self.0.pop_unchecked() };
 
@@ -97,7 +126,7 @@ where
                 // dequeue. If the monotonic is fast enough it can happen that from the
                 // read of now to the set of the compare, the time can overflow. This is to
                 // guard against this.
-                if instant <= Self::unwrapper(Clock::try_now(mono)) {
+                if instant <= unwrapper(Clock::try_now(mono)) {
                     let nr = unsafe { self.0.pop_unchecked() };
 
                     Some((nr.task, nr.index))
@@ -125,6 +154,7 @@ where
     pub index: u8,
     pub instant: Instant<Mono>,
     pub task: Task,
+    pub marker: u32,
 }
 
 impl<Mono, Task> Eq for NotReady<Mono, Task>