dgrambuf 0.2.0

//! A fixed size ring buffer for datagrams of various sizes.
//!
//! Implementation uses [std::collections::VecDeque] for metadata storage and a fixed size backing buffer for storage of datagram data.
//! # Examples
//!
//! Generic usage.
//!
//! ```
//! use dgrambuf::DatagramBuf;
//! use std::io::Write;
//!
//! // allocate backing buffer
//! let mut dgram_buf = Vec::new();
//! dgram_buf.resize(128, 0);
//!
//! // crate `DatagramBuf` based on preallocated buffer for datagram storage
//! let mut dgram_buf = DatagramBuf::from_slice(&mut dgram_buf);
//!
//! // allocate new datagram slice within the backing store
//! let mut dgram = dgram_buf.alloc_front(50).unwrap();
//!
//! // write to the buffer
//! write!(dgram, "hello world");
//! // truncate the buffer to the size of data written
//! dgram_buf.truncate_front("hello world".len());
//!
//! // write another datagram
//! let mut dgram = dgram_buf.alloc_front(50).unwrap();
//! write!(dgram, "foo bar");
//! write!(dgram, " baz");
//! dgram_buf.truncate_front("foo bar baz".len());
//!
//! // take oldest datagram form the buffer
//! let dgram = dgram_buf.pop_back().unwrap();
//! assert_eq!(dgram, b"hello world");
//!
//! let dgram = dgram_buf.pop_back().unwrap();
//! assert_eq!(dgram, b"foo bar baz");
//! ```
//!
//! Usage as store and forward buffer for UNIX datagram socket.
//!
//! ```no_run
//! use dgrambuf::DatagramBuf;
//! use std::os::unix::net::UnixDatagram;
//!
//! fn main() -> std::io::Result<()> {
//!     let socket = UnixDatagram::bind("/path/to/my/socket")?;
//!
//!     // allocate backing buffer
//!     let mut dgram_buf = Vec::new();
//!     dgram_buf.resize(512, 0);
//!
//!     let mut dgram_buf = DatagramBuf::from_slice(&mut dgram_buf);
//!
//!     // receive 10 datagrams up to 128 bytes in length each
//!     for _ in 0..10 {
//!         // drop old datagrams if there is not enough space left in the backing buffer (512)
//!         let mut buf = dgram_buf.alloc_front_drop(128).unwrap();
//!
//!         let count = socket.recv(&mut buf)?;
//!         // reduce the size of the allocation to fit the datagram received
//!         dgram_buf.truncate_front(count);
//!     }
//!
//!     // send back the received datagrams in order
//!     while let Some(mut buf) = dgram_buf.pop_back() {
//!         socket.send(&mut buf)?;
//!     }
//!     Ok(())
//! }
//! ```
//!
use std::collections::VecDeque;

/// A fixed size ring buffer for datagrams of various sizes.
#[derive(Debug)]
pub struct DatagramBuf<B> {
    buf: B,
    index: VecDeque<(usize, usize)>,
    used: usize,
}

/// Types that can be used as data buffer.
pub trait Buf: AsMut<[u8]> + AsRef<[u8]> {}
impl<T> Buf for T where T: AsMut<[u8]> + AsRef<[u8]> {}

impl<'b> DatagramBuf<&'b mut [u8]> {
    /// Creates [DatagramBuf] using given slice as backing buffer.
    pub fn from_slice(slice: &'b mut [u8]) -> DatagramBuf<&'b mut [u8]> {
        Self::new(slice)
    }
}

impl DatagramBuf<Box<[u8]>> {
    /// Creates [DatagramBuf] using internal heap allocated backing buffer of given size.
    pub fn with_capacity(size: usize) -> DatagramBuf<Box<[u8]>> {
        let mut buf = Vec::new();
        buf.resize(size, 0);
        Self::new(buf.into_boxed_slice())
    }
}

impl<B: Buf> DatagramBuf<B> {
    /// Creates [DatagramBuf] using provided backing buffer.
    pub fn new(buf: B) -> DatagramBuf<B> {
        DatagramBuf {
            buf,
            index: VecDeque::new(),
            used: 0,
        }
    }

    fn write_offset(&self) -> usize {
        let (offset, size) = self.index.front().unwrap_or(&(0,0));
        offset + size
    }

    fn read_offset(&self) -> usize {
        let (offset, _size) = self.index.back().unwrap_or(&(0,0));
        *offset
    }

    fn find_write_offset(&self, size: usize) -> Option<usize> {
        let write_offset = self.write_offset();
        let read_offset = self.read_offset();

        if write_offset >= read_offset {
            if size <= self.buf.as_ref().len() - write_offset  {
                Some(write_offset)
            } else if size <= read_offset {
                Some(0)
            } else {
                None
            }
        } else {
            if size <= read_offset - write_offset {
                Some(write_offset)
            } else {
                None
            }
        }
    }

    fn alloc(&mut self, size: usize, drop: bool) -> Option<&mut [u8]> {
        let offset = if !drop {
            self.find_write_offset(size)?
        } else {
            loop {
                if let Some(offset) = self.find_write_offset(size) {
                    break offset
                } else {
                    self.pop_back()?;
                }
            }
        };

        let ret = &mut self.buf.as_mut()[offset..offset + size];
        self.index.push_front((offset, size));
        self.used += size;
        Some(ret)
    }

    /// Allocates datagram buffer of given size.
    ///
    /// Returns `None` if there is not enough continuous space available in the backing buffer.
    pub fn alloc_front(&mut self, size: usize) -> Option<&mut [u8]> {
        self.alloc(size, false)
    }

    /// Allocates datagram buffer of given size dropping oldest buffer to free up space.
    ///
    /// Returns `None` if requested size is bigger than the backing buffer. Datagrams in the buffer
    /// would have been dropped.
    pub fn alloc_front_drop(&mut self, size: usize) -> Option<&mut [u8]> {
        self.alloc(size, true)
    }

    /// Changes the length of last allocated datagram buffer.
    ///
    /// Returns truncated datagram slice.
    ///
    /// # Panics
    ///
    /// * Panics if there are no datagrams allocated.
    /// * Panics if new size is larger than old size.
    pub fn truncate_front(&mut self, new_size: usize) -> &mut [u8] {
        let meta = self.index.front_mut().expect("truncate_front: no datagram allocated in datagram buffer");
        if new_size > meta.1 {
            panic!("truncate_front: new size is bigger than current size")
        }

        self.used -= meta.1 - new_size;
        meta.1 = new_size;

        let (offset, size) = *meta;
        &mut self.buf.as_mut()[offset..offset + size]
    }

    /// Gets the last allocated datagram buffer, or `None` if it is empty.
    pub fn front(&mut self) -> Option<&mut [u8]> {
        let (offset, size) = self.index.front()?;
        Some(&mut self.buf.as_mut()[*offset..*offset + size])
    }

    /// Pops the last allocated datagram buffer freeing space, or `None` if it is empty.
    pub fn pop_front(&mut self) -> Option<&mut [u8]> {
        let (offset, size) = self.index.pop_front()?;
        self.used -= size;
        Some(&mut self.buf.as_mut()[offset..offset + size])
    }

    /// Gets the oldest datagram buffer, or `None` if it is empty.
    pub fn back(&mut self) -> Option<&mut [u8]> {
        let (offset, size) = self.index.back()?;
        Some(&mut self.buf.as_mut()[*offset..*offset + size])
    }

    /// Pops the oldest datagram buffer freeing space, or `None` if it is empty.
    pub fn pop_back(&mut self) -> Option<&mut [u8]> {
        let (offset, size) = self.index.pop_back()?;
        self.used -= size;
        Some(&mut self.buf.as_mut()[offset..offset + size])
    }

    /// Removes all datagram buffers stored.
    pub fn clear(&mut self) {
        self.used = 0;
        self.index.clear()
    }

    // Returns `true` if there are no datagrams stored.
    pub fn is_empty(&self) -> bool {
        self.index.is_empty()
    }

    // Returns number of datagrams stored.
    pub fn len(&self) -> usize {
        self.index.len()
    }

    // Returns backing buffer size in bytes.
    pub fn size(&self) -> usize {
        self.buf.as_ref().len()
    }

    // Returns total size of datagrams stored.
    //
    // Note: It may not be possible to fully use the backing buffer space.
    pub fn used(&self) -> usize {
        self.used
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::io::Write;

    #[test]
    fn test_fill() {
        let mut slice = Vec::new();
        slice.resize(10, 0);
        let mut db = DatagramBuf::from_slice(slice.as_mut());

        let dgrams = vec![vec![1, 2, 3], vec![4, 5], vec![6, 7, 8, 9, 10]];

        for dgram in &dgrams {
            let mut s = db.alloc_front(dgram.len()).unwrap();
            s.write_all(&dgram).unwrap();
        }
        assert_eq!(db.used(), 10);

        for dgram in &dgrams {
            let s = db.pop_back().unwrap();
            assert_eq!(s, dgram.as_slice());
        }
        assert_eq!(db.used(), 0);
    }

    #[test]
    fn test_clear() {
        let mut slice = Vec::new();
        slice.resize(10, 0);
        let mut db = DatagramBuf::from_slice(slice.as_mut());

        let dgrams = vec![vec![1, 2, 3], vec![4, 5], vec![6, 7, 8, 9, 10]];

        for dgram in &dgrams {
            let mut s = db.alloc_front(dgram.len()).unwrap();
            s.write_all(&dgram).unwrap();
        }
        assert_eq!(db.used(), 10);

        db.clear();
        assert_eq!(db.used(), 0);
        assert!(db.pop_front().is_none());
        assert!(db.pop_back().is_none());
    }

    #[test]
    fn test_overflow() {
        let mut slice = Vec::new();
        slice.resize(6, 0);
        let mut db = DatagramBuf::from_slice(slice.as_mut());

        let dgrams = vec![vec![1, 2, 3], vec![4, 5], vec![6, 7, 8, 9, 10]];

        let mut dgram_iter = dgrams.iter();

        assert_eq!(db.used(), 0);
        {
            let dgram = dgram_iter.next().unwrap();
            let mut s = db.alloc_front(dgram.len()).unwrap();
            s.write_all(&dgram).unwrap();
        }

        assert_eq!(db.used(), 3);
        {
            let dgram = dgram_iter.next().unwrap();
            let mut s = db.alloc_front(dgram.len()).unwrap();
            s.write_all(&dgram).unwrap();
        }

        assert_eq!(db.used(), 5);
        {
            let dgram = dgram_iter.next().unwrap();
            assert!(db.alloc_front(dgram.len()).is_none()); // out of space
        }

        assert_eq!(db.used(), 5);
        let mut dgram_iter = dgrams.iter();
        {
            let dgram = dgram_iter.next().unwrap();
            let s = db.pop_back().unwrap();
            assert_eq!(s, dgram.as_slice());
        }

        assert_eq!(db.used(), 2);
        {
            let dgram = dgram_iter.next().unwrap();
            let s = db.pop_back().unwrap();
            assert_eq!(s, dgram.as_slice());
        }

        assert_eq!(db.used(), 0);
        {
            assert!(db.pop_back().is_none());
        }
    }

    #[test]
    fn test_reuse() {
        let mut slice = Vec::new();
        slice.resize(7, 0);
        let mut db = DatagramBuf::from_slice(slice.as_mut());

        let dgrams = vec![vec![1, 2, 3], vec![4, 5], vec![6, 7, 8, 9, 10]];

        for dgram in &dgrams {
            let mut s = db.alloc_front_drop(dgram.len()).unwrap();
            s.write_all(&dgram).unwrap();
        }

        let s = db.back().unwrap();
        assert_eq!(s, dgrams[2]);

        {
            let mut s = db.alloc_front_drop(dgrams[1].len()).unwrap();
            s.write_all(&dgrams[1]).unwrap();
        }

        let s = db.pop_back().unwrap();
        assert_eq!(s, dgrams[2]);
    }

    #[test]
    fn test_reuse2() {
        let mut slice = Vec::new();
        slice.resize(10, 0);
        let mut db = DatagramBuf::from_slice(slice.as_mut());

        let dgrams = vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9], vec![10, 11]];

        for dgram in &dgrams {
            let mut s = db.alloc_front_drop(dgram.len()).unwrap();
            s.write_all(&dgram).unwrap();
        }

        let s = db.back().unwrap();
        assert_eq!(s, dgrams[1]);

        let s = db.front().unwrap();
        assert_eq!(s, dgrams[3]);

        assert_eq!(db.used(), 8);

        {
            let mut s = db.alloc_front_drop(dgrams[3].len()).unwrap();
            s.write_all(&dgrams[3]).unwrap();
        }

        assert_eq!(db.used(), 7);

        let s = db.pop_back().unwrap();
        assert_eq!(s, dgrams[2]);
    }

    #[test]
    fn test_reuse2_with_capacity() {
        let mut db = DatagramBuf::with_capacity(10);

        let dgrams = vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9], vec![10, 11]];

        for dgram in &dgrams {
            let mut s = db.alloc_front_drop(dgram.len()).unwrap();
            s.write_all(&dgram).unwrap();
        }

        let s = db.back().unwrap();
        assert_eq!(s, dgrams[1]);

        let s = db.front().unwrap();
        assert_eq!(s, dgrams[3]);

        assert_eq!(db.used(), 8);

        {
            let mut s = db.alloc_front_drop(dgrams[3].len()).unwrap();
            s.write_all(&dgrams[3]).unwrap();
        }

        assert_eq!(db.used(), 7);

        let s = db.pop_back().unwrap();
        assert_eq!(s, dgrams[2]);
    }

    #[test]
    fn test_too_big() {
        let mut slice = Vec::new();
        slice.resize(6, 0);
        let mut db = DatagramBuf::from_slice(slice.as_mut());
        assert!(db.alloc_front(7).is_none());
    }

    #[test]
    fn test_front() {
        let mut slice = Vec::new();
        slice.resize(10, 0);
        let mut db = DatagramBuf::from_slice(slice.as_mut());

        let dgrams = vec![vec![1, 2, 3], vec![4, 5], vec![6, 7, 8, 9, 10]];

        for dgram in &dgrams {
            let mut s = db.alloc_front(dgram.len()).unwrap();
            s.write_all(&dgram).unwrap();
        }

        assert_eq!(db.front().as_deref(), Some(dgrams[2].as_slice()));
    }

    #[test]
    fn test_pop_front() {
        let mut slice = Vec::new();
        slice.resize(10, 0);
        let mut db = DatagramBuf::from_slice(slice.as_mut());

        let dgrams = vec![vec![1, 2, 3], vec![4, 5], vec![6, 7, 8, 9, 10]];

        for dgram in &dgrams {
            let mut s = db.alloc_front(dgram.len()).unwrap();
            s.write_all(&dgram).unwrap();
        }

        assert_eq!(db.used(), 10);
        for dgram in dgrams.iter().rev() {
            let s = db.pop_front().unwrap();
            assert_eq!(s, dgram.as_slice());
        }
        assert_eq!(db.used(), 0);
    }

    #[test]
    fn test_truncate_front() {
        let mut slice = Vec::new();
        slice.resize(10, 0);
        let mut db = DatagramBuf::from_slice(slice.as_mut());

        let dgrams = vec![vec![1, 2, 3], vec![4, 5], vec![6, 7, 8, 9, 10]];

        for dgram in &dgrams {
            let mut s = db.alloc_front(dgram.len()).unwrap();
            s.write_all(&dgram).unwrap();
        }

        assert_eq!(db.used(), 10);
        assert_eq!(db.truncate_front(5), &dgrams[2]);
        assert_eq!(db.used(), 10);
        assert_eq!(db.truncate_front(2), &dgrams[2][..2]);
        assert_eq!(db.used(), 7);
        assert_eq!(db.front().unwrap(), &dgrams[2][..2]);
    }

    #[test]
    #[should_panic(expected = "truncate_front: new size is bigger than current size")]
    fn test_truncate_front_bad_size() {
        let mut slice = Vec::new();
        slice.resize(10, 0);
        let mut db = DatagramBuf::from_slice(slice.as_mut());

        let dgrams = vec![vec![1, 2, 3], vec![4, 5], vec![6, 7, 8, 9, 10]];

        for dgram in &dgrams {
            let mut s = db.alloc_front(dgram.len()).unwrap();
            s.write_all(&dgram).unwrap();
        }

        db.truncate_front(6);
    }
}