avr-oxide 0.0.5

/* ringq.rs
 *
 * Developed by Tim Walls <tim.walls@snowgoons.com>
 * Copyright (c) All Rights Reserved, Tim Walls
 */
//! A simple ring queue implementation for internal use within Oxide.


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

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

/**
 * A simple ring-queue implementation.  We make the maximum size 255 (i.e.
 * represented as a u8) so we can be sure that reading/writing that value
 * will be atomic without needing a lock.
 *
 * Note that in this implementation we can store 1-less than the size (we
 * need a buffer between start and end of queue so we can tell the difference
 * between full and empty.  An alternative is to maintain a separate length
 * counter, but then I have to make that atomic, whereas in this implementation
 * I can be sure tail is only ever written by the consumer, and head is only
 * ever written by the producer, and both are atomic.
 */
pub struct RingQ<E, const SIZE: usize>
  where
    E: Clone + Coalesce
{
  pub queue: [Option<E>; SIZE],
  pub head: u8,
  pub tail: u8
}

/**
 * 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 Coalesce : Sized {
  /**
   * Mutate myself so that I represent the result of coalescing with the
   * provided element.
   */
  fn coalesce(&mut self, with: &Self) -> Result<(),QueueError>;
}

/**
 * Marker trait that allows a default implementation for Coalesce for types
 * that don't want the functionality.
 */
pub trait DoesNotCoalesce {}

/**
 * Errors which can be generated by our Ring Queue.
 */
#[derive(Debug)]
pub enum QueueError {
  /// There is no more space in the queue to append an item
  QueueFull,

  /// An attempt to coalesce objects that cannot be combined was made
  CannotCoalesce
}


pub trait BoundedMaths<T> {
  fn binc<const BOUND: usize>(&mut self);

  fn bdec<const BOUND: usize>(&mut self);

  fn bsub<const BOUND: usize>(&self, val: T) -> Self;
}

impl BoundedMaths<u8> for u8
{
  #[inline(always)]
  fn binc<const BOUND: usize>(&mut self) {
    *self = (*self + 1) % BOUND as u8;
  }
  #[inline(always)]
  fn bdec<const BOUND: usize>(&mut self) {
   if *self > 0 {
     *self -= 1;
   } else {
     *self = (BOUND-1) as u8;
   }
  }
  #[inline(always)]
  fn bsub<const BOUND: usize>(&self, val: u8) -> Self{
    if *self >= val {
      *self - val
    } else {
      (BOUND as u8-(val%BOUND as u8))+*self
    }
  }
}


// Code ======================================================================
impl DoesNotCoalesce for u8 {}

impl<T: DoesNotCoalesce> Coalesce for T {
  fn coalesce(&mut self, _with: &Self) -> Result<(), QueueError> {
    Err(QueueError::CannotCoalesce)
  }
}

impl<E, const SIZE: usize> RingQ<E,SIZE>
where
  E: Clone + Coalesce
{
  pub fn new() -> Self {
    Self {
      queue: [None; SIZE],
      head: 0,
      tail: 0
    }
  }

  /**
   * Return the number of elements in the queue
   */
  pub fn len(&self) -> u8 {
    self.head.bsub::<SIZE>(self.tail)
  }

  /**
   * Consume an entry from the ring queue (if there is one :).)  This is
   * the single-consumer version of the method, that does no locking at all -
   * it will only be safe to use if no other thread is also reading.
   */
  pub fn consume_nolock(&mut self) -> Option<E> {
    let tail = self.tail;

    if self.head == tail {
      None
    } else {
      // Extract the current value *before* we modify the tail pointer
      let consumed = core::mem::replace(&mut self.queue[tail as usize], None);
      self.tail.binc::<SIZE>();
      consumed
    }
  }
  /**
   * Insert an entry into the ring queue, if possible.  This method is a
   * single-producer version that does no locking - it will only be safe
   * if no other thread is also writing.
   */
  pub fn append_nolock(&mut self, element: E) -> Result<(), QueueError> {
    let head = self.head;


    if head != self.tail { // Queue is not empty
      let prev = head.bsub::<SIZE>(1);

      // OK, attempt coalescing
      match &mut self.queue[prev as usize] {
        None => {}
        Some(queued_event) => {
          if let Ok(()) = queued_event.coalesce(&element) {
            return Ok(());
          }
        }
      }
    }

    if head != (self.tail.bsub::<SIZE>(1)) { // There is space
      self.queue[head as usize] = Some(element.clone());
      self.head.binc::<SIZE>();
      Ok(())
    } else {
      Err(QueueError::QueueFull)
    }
  }

  /**
   * Insert an entry into the ring queue.  If the queue is full, block until
   * there is space.
   */
  pub fn append_blocking_nolock(&mut self, element: E) {
    while let Err(_) = self.append_nolock(element.clone()) {
    }
  }
}

// Tests =====================================================================
#[cfg(test)]
mod tests {
  use crate::private::ringq::{RingQ, DoesNotCoalesce, Coalesce, QueueError, BoundedMaths};

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

  #[derive(Clone,PartialEq,Eq,Debug)]
  struct CoalescingTestEvent {
    num: u8
  }
  impl Coalesce for CoalescingTestEvent {
    fn coalesce(&mut self, with: &Self) -> Result<(), QueueError> {
      self.num += with.num;

      Ok(())
    }
  }



  #[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_nolock(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..=9 {
      let test_ev1 = TestEvent { num: 0 };
      queue.append_nolock(test_ev1).unwrap();
      println!("Appended element {}", i);
    }

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

  #[test]
  fn test_ringq_consume() {
    let mut queue : RingQ<TestEvent,4> = 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_nolock(test_ev1.clone()).unwrap();
    queue.append_nolock(test_ev2.clone()).unwrap();
    queue.append_nolock(test_ev3.clone()).unwrap();

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

    let consumed_ev1 = queue.consume_nolock().unwrap();
    let consumed_ev2 = queue.consume_nolock().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_nolock(test_ev4.clone()).unwrap();
    queue.append_nolock(test_ev5.clone()).unwrap();

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

    let consumed_ev3 = queue.consume_nolock().unwrap();
    let consumed_ev4 = queue.consume_nolock().unwrap();
    let consumed_ev5 = queue.consume_nolock().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);
  }

  #[test]
  fn test_ringq_coalesce() {
    let mut queue : RingQ<CoalescingTestEvent, 4> = RingQ::new();

    let test_ev1 = CoalescingTestEvent { num: 1 };
    let test_ev2 = CoalescingTestEvent { num: 2 };
    let test_ev3 = CoalescingTestEvent { num: 3 };
    let test_ev4 = CoalescingTestEvent { num: 4 };
    let test_ev5 = CoalescingTestEvent { num: 5 };

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

    queue.append_nolock(test_ev1.clone()).unwrap();
    queue.append_nolock(test_ev2.clone()).unwrap();
    queue.append_nolock(test_ev3.clone()).unwrap();
    queue.append_nolock(test_ev4.clone()).unwrap();
    queue.append_nolock(test_ev5.clone()).unwrap();

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

    let consumed_ev1 = queue.consume_nolock().unwrap();
    println!("Consumed event: {:?}", &consumed_ev1);
    assert_eq!(consumed_ev1.num, 15);
  }

  #[test]
  fn test_bounded_maths() {
    let mut val:u8 = 0;

    assert_eq!(val.bsub::<10>(1u8), 9);
    assert_eq!(val, 0);
    val.binc::<10>();
    assert_eq!(val, 1);
    val.binc::<10>();
    assert_eq!(val, 2);
    val.bdec::<10>();
    assert_eq!(val, 1);
    val.bdec::<10>();
    assert_eq!(val, 0);

    val.bdec::<10>();
    assert_eq!(val, 9);
    val.binc::<10>();
    assert_eq!(val, 0);

    let zero:u8 = 0;
    let one:u8  = 1;
    let five:u8 = 5;
    let four:u8 = 4;

    assert_eq!(five.bsub::<10>(four), 1);
    assert_eq!(four.bsub::<10>(five), 9);
    assert_eq!(zero.bsub::<10>(one), 9);
    assert_eq!(one.bsub::<10>(zero), 1);
  }
}