avr-oxide 0.0.1

/* ringq.rs
 *
 * Developed by Tim Walls <tim.walls@snowgoons.com>
 * Copyright (c) All Rights Reserved, Tim Walls
 */
//! A simple ring queue implementation for our hardware to remember events
//! generated by interrupts with.


// Imports ===================================================================

use crate::hal::concurrency::imp::{MutexRc, atomic};


// Declarations ==============================================================

/**
 * A simple ring-queue implementation for our event queue
 */
pub struct RingQ<E, const SIZE: usize>
  where
    E: Clone
{
  inner: MutexRc<RingQProtected<E, SIZE>>
}

struct RingQProtected<E, const SIZE: usize> {
  pub queue: [Option<E>; SIZE],
  pub head: usize,
  pub len: usize
}

/**
 * A ring queue that coalesces its members (i.e. if a new entry can be
 * combined with the last element of the queue, then it will actually replace
 * it with a new combined instance instead of appending.)
 */
pub struct CoalescingRingQ<E, const SIZE: usize>
where
  E: Coalescable + Clone
{
  inner: RingQ<E,SIZE>
}

/**
 * A trait implemented by objects that can be coalesced - i.e. two objects
 * replaced by one that represents the same semantic event/action/whatever.
 */
pub trait Coalescable : Sized {

  /**
  * Return true if and only if this
  */
  fn can_coalesce(&self, with: &Self) -> bool;

  /**
   * Return a new instance of myself that is the combination of self and
   * the passed instance.
   */
  fn coalesce(&self, with: &Self) -> Result<Self,QueueError>;
}

#[derive(Debug)]
pub enum QueueError {
  QueueFull,

  CannotCoalesce
}

// Code ======================================================================
impl<E, const SIZE: usize> RingQ<E,SIZE>
  where
    E: Clone
{
  pub fn new() -> Self {
    unsafe {
      let mut new = RingQProtected {
        #[allow(deprecated)]
        queue: core::mem::uninitialized(),
        head: 0,
        len: 0
      };

      for item in &mut new.queue[..] {
        core::ptr::write(item, None);
      }

      Self {
        inner: MutexRc::new(new)
      }
    }
  }

  pub fn len(&self) -> usize {
    atomic(|cs| {
      let inner = self.inner.borrow(cs);

      inner.len
    })
  }

  /**
   * Consume an entry from the ring queue (if there is one :).)
   */
  pub fn consume(&self) -> Option<E> {
    atomic(|cs| {
      let mut inner = self.inner.borrow_mut(cs);

      if inner.len == 0 {
        None
      } else {
        let tail = (inner.head + (SIZE - inner.len)) % SIZE;
        inner.len -= 1;
        core::mem::replace(&mut inner.queue[tail], None)
      }
    })
  }

  /**
   * Insert an entry into the ring queue, if possible.  If the queue is
   * full, will return an error.
   */
  pub fn append(&self, event: E) -> Result<(), QueueError> {
    atomic(|cs| {
      let inner = &mut *self.inner.borrow_mut(cs);

      if inner.len >= SIZE {
        Err(QueueError::QueueFull)
      } else {
        inner.queue[inner.head] = Some(event.clone());
        inner.head = (inner.head + 1) % SIZE;
        inner.len += 1;
        Ok(())
      }
    })
  }
}

// Tests =====================================================================
#[cfg(test)]
mod tests {
  use crate::ringq::RingQ;

  #[derive(Clone,PartialEq,Eq,Debug)]
  struct TestEvent {
    num: u8
  }

  #[test]
  fn test_ringq() {
    let mut queue : RingQ<TestEvent,10> = RingQ::new();

    println!("Initial queue length: {}", queue.len());
    assert_eq!(queue.len(), 0);

    let test_ev1 = TestEvent { num: 0 };
    queue.append(test_ev1).unwrap();

    println!("Queue length after adding 1 event: {}", queue.len());
    assert_eq!(queue.len(), 1);
  }

  #[test]
  #[should_panic]
  fn test_ringq_bounds() {
    let mut queue: RingQ<TestEvent,10> = RingQ::new();

    for _i in 1..=10 {
      let test_ev1 = TestEvent { num: 0 };
      queue.append(test_ev1).unwrap();
    }

    println!("Queue length: {}", queue.len());
    println!("Succesfully added 10 events; next should panic");
    let test_ev1 = TestEvent { num: 0 };
    queue.append(test_ev1).unwrap();
  }

  #[test]
  fn test_ringq_consume() {
    let mut queue : RingQ<TestEvent,3> = RingQ::new();

    println!("Initial queue length: {}", queue.len());
    assert_eq!(queue.len(), 0);

    let test_ev1 = TestEvent { num: 1 };
    let test_ev2 = TestEvent { num: 2 };
    let test_ev3 = TestEvent { num: 3 };
    queue.append(test_ev1.clone()).unwrap();
    queue.append(test_ev2.clone()).unwrap();
    queue.append(test_ev3.clone()).unwrap();

    println!("Queue length after adding 3 events: {}", queue.len());
    assert_eq!(queue.len(), 3);

    let consumed_ev1 = queue.consume().unwrap();
    let consumed_ev2 = queue.consume().unwrap();

    println!("Queue length after consuming 2 events: {}", queue.len());
    assert_eq!(queue.len(), 1);

    let test_ev4 = TestEvent { num: 4 };
    let test_ev5 = TestEvent { num: 5 };
    queue.append(test_ev4.clone()).unwrap();
    queue.append(test_ev5.clone()).unwrap();

    println!("Queue length after adding 2 more events: {}", queue.len());
    assert_eq!(queue.len(), 3);

    let consumed_ev3 = queue.consume().unwrap();
    let consumed_ev4 = queue.consume().unwrap();
    let consumed_ev5 = queue.consume().unwrap();

    println!("Queue length after consuming 3 more events: {}", queue.len());
    assert_eq!(queue.len(), 0);

    // Check we got the data out in the same order we inserted it
    let inserted = [ test_ev1, test_ev2, test_ev3, test_ev4, test_ev5 ];
    let consumed = [ consumed_ev1, consumed_ev2, consumed_ev3, consumed_ev4, consumed_ev5 ];
    assert_eq!(inserted, consumed);
  }
}