bufferring 0.0.2

//! Bufferring: Ring buffers for Rust
//!
//! **WARNING**: This crate is not ready for use.  It contains a significant
//! amount of `unsafe` code, but is currently completely untested.
//!
//! ## Usage
//!
//! ```rust
//! use core::num::NonZeroUsize;
//! use bufferring::{
//!     RingBuffer, MaskingBuffer,
//!     storage::{Storage, HeapStorage},
//! };
//! 
//! // Create a masking-based ring buffer using heap-allocated storage.
//! let capacity = NonZeroUsize::new(8).unwrap();
//! let storage = HeapStorage::with_capacity(capacity);
//! let mut buffer = MaskingBuffer::new(storage).unwrap();
//! 
//! // Push some elements into the buffer.
//! for item in 0 .. 14 {
//!     // Drop removed items immediately.
//!     let _ = buffer.enqueue(item);
//! }
//! 
//! // See what elements are in the buffer.
//! println!("{:?}", buffer);
//! assert!(buffer.is_full());
//! assert!(buffer.iter().copied().eq(6 .. 14));
//! 
//! // Remove those elements from the buffer.
//! for item in 6 .. 14 {
//!     assert_eq!(buffer.dequeue(), Some(item));
//! }
//! assert!(buffer.is_empty());
//! ```

#![cfg_attr(not(any(test, feature = "proptest")), no_std)]

pub mod storage;
pub use storage::Storage;

pub mod masking;
pub use masking::MaskingBuffer;

pub mod iter;
use iter::{Iter, IterMut, Drain};

pub mod prop;

mod tests;

/// A ring buffer.
///
/// Ring buffers are double-ended fixed-capacity queues.  New items can be added
/// and the oldest-added items can be retrieved.  Ring buffers have a _capacity_
/// that determines the maximum number of items they can hold at any time; once
/// they hit this limit, adding a new item will remove the oldest-added item.
/// They can be seen as [`VecDeque`]s with a maximum size.
///
/// [`VecDeque`]: https://doc.rust-lang.org/std/collections/struct.VecDeque.html
///
/// This trait is object-safe; it can be used even when the implementing type is
/// not known at compile-time (as `&dyn RingBuffer`).
pub trait RingBuffer {
    /// The type of the items stored by the buffer.
    type Item;

    /// The capacity of the buffer.
    ///
    /// This returns the maximum number of items the ring buffer can hold at any
    /// time.  The capacity of a ring buffer cannot be changed, and it is at
    /// least one (as a zero-capacity ring buffer can never hold items).
    fn cap(&self) -> usize;

    /// The length of the buffer.
    ///
    /// This returns the number of items the ring buffer is currently holding
    /// (this is less than or equal to the capacity of the buffer).
    fn len(&self) -> usize;

    /// Whether the buffer is empty.
    fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Whether the buffer is full.
    ///
    /// The buffer is full if its length is equal to its capacity; in this case,
    /// adding a new item will drop the oldest item.
    fn is_full(&self) -> bool {
        self.len() == self.cap()
    }

    /// Get a shared reference to the item at the given offset.
    ///
    /// Considering the buffer from the oldest-added to newest-added item, the
    /// item at the given index/offset is selected, if it exists, and a shared
    /// reference to it is returned; [`None`] is returned if the offset was too
    /// large and no item could be found.
    fn get(&self, off: usize) -> Option<&Self::Item>;

    /// Get a unique reference to the item at the given offset.
    ///
    /// Considering the buffer from the oldest-added to newest-added item, the
    /// item at the given index/offset is selected, if it exists, and a unique
    /// reference to it is returned; [`None`] is returned if the offset was too
    /// large and no item could be found.
    ///
    /// By default, this is implemented in terms of [`get_disjoint_mut()`]; but
    /// if it is re-implemented without, its body will likely be fairly similar
    /// to that of [`get()`].
    ///
    /// [`get_disjoint_mut()`]: Self::get_disjoint_mut()
    /// [`get()`]: Self::get()
    fn get_mut(&mut self, off: usize) -> Option<&mut Self::Item> {
        if off < self.len() {
            // SAFETY:
            // - The given offset is valid.
            // - The lifetime is unchanged, so the ring buffer is borrowed for
            //   its entire duration, and it will not change or be used in any
            //   other way for this time.
            Some(unsafe { self.get_disjoint_mut(off) })
        } else { None }
    }

    /// Get a unique reference to the item at the given offset, assuming that no
    /// other reference to this item does or will exist.
    ///
    /// This function is `unsafe`; it can only be called if its invariants are
    /// satisfied, as otherwise undefined behaviour will occur.  Specifically,
    /// while the given lifetime exists:
    ///
    /// - The given offset must be valid (in the range `0 .. len`).
    /// - The ring buffer must exist, at the same location, without moving.
    /// - No new items can be enqueued or dequeued.
    /// - This method cannot be called with the same index again.
    ///
    /// If these conditions are satisfied, a unique reference to the item at the
    /// given offset is returned, as in [`get_mut()`][Self::get_mut()], but for
    /// a shared reference to `self`.  This can be used to hold multiple unique
    /// references to different items at once, but it must be handled very
    /// carefully.
    unsafe fn get_disjoint_mut(&self, off: usize) -> &mut Self::Item;

    /// Iterate over shared references to the items in the queue.
    ///
    /// The referenced items are not modified or removed from the queue; this is
    /// simply an inspection of the items, akin to calling [`get()`] for
    /// each item.  For unique references, see [`iter_mut()`].
    ///
    /// [`get()`]: Self::get()
    /// [`iter_mut()`]: Self::iter_mut()
    fn iter(&self) -> Iter<'_, Self> {
        Iter::new(self)
    }

    /// Iterate over unique references to the items in the queue.
    ///
    /// The referenced items are not modified or removed from the queue; this is
    /// simply an inspection of the items, akin to calling [`get_mut()`] for
    /// each item.  For shared references, see [`iter()`].
    ///
    /// [`get_mut()`]: Self::get_mut()
    /// [`iter()`]: Self::iter()
    fn iter_mut(&mut self) -> IterMut<'_, Self> {
        IterMut::new(self)
    }

    /// Enqueue an item.
    ///
    /// If the buffer is full, the oldest item in the buffer will be removed and
    /// returned.  Otherwise, [`None`] is returned.
    fn enqueue(&mut self, item: Self::Item) -> Option<Self::Item>;

    /// Dequeue an item.
    ///
    /// The oldest-added item in the buffer will be removed and returned.  If
    /// the buffer is empty, [`None`] is returned.
    fn dequeue(&mut self) -> Option<Self::Item>;

    /// Skip the next item.
    ///
    /// The oldest-added item in the buffer, if any, will be removed.  This is
    /// akin to dequeueing the item and dropping it immediately.
    fn skip_one(&mut self) {
        let _ = self.dequeue();
    }

    /// Skip the given number of item.
    ///
    /// This is equivalent to dequeueing this number of items (if they exist)
    /// and dropping them immediately.  If the buffer contains fewer items, they
    /// are all dropped, and the buffer is cleared.
    fn skip(&mut self, num: usize) {
        for _ in 0 .. core::cmp::min(num, self.len()) {
            self.skip_one();
        }
    }

    /// Clear the buffer.
    ///
    /// All the items in the buffer will be removed and dropped.
    fn clear(&mut self) {
        for _ in 0 .. self.len() {
            self.skip_one();
        }
    }

    /// Drain the items of the iterator.
    ///
    /// An iterator is returned which removes and returns individual items from
    /// this ring buffer.  Once the iterator is dropped, any remaining items can
    /// be accessed from the ring buffer; no items are lost outright.  This is
    /// akin to calling [`dequeue()`][Self::dequeue()] on the buffer repeatedly.
    fn drain(&mut self) -> Drain<'_, Self> {
        Drain::new(self)
    }
}

impl<RB: RingBuffer> RingBuffer for &mut RB {
    type Item = RB::Item;

    fn cap(&self) -> usize {
        RB::cap(*self)
    }

    fn len(&self) -> usize {
        RB::len(*self)
    }

    fn get(&self, off: usize) -> Option<&Self::Item> {
        RB::get(*self, off)
    }

    fn get_mut(&mut self, off: usize) -> Option<&mut Self::Item> {
        RB::get_mut(*self, off)
    }

    unsafe fn get_disjoint_mut(&self, off: usize) -> &mut Self::Item {
        RB::get_disjoint_mut(*self, off)
    }

    fn enqueue(&mut self, item: Self::Item) -> Option<Self::Item> {
        RB::enqueue(*self, item)
    }

    fn dequeue(&mut self) -> Option<Self::Item> {
        RB::dequeue(*self)
    }

    fn skip(&mut self, num: usize) {
        RB::skip(*self, num)
    }

    fn clear(&mut self) {
        RB::clear(*self)
    }
}