bytes_deque 0.2.1

// BytesDeque Rust crate, a growable deque container storing bytes.
// Copyright (C) 2025  Nikolaos Chatzikonstantinou
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.

//! This crate implements [`BytesDeque`], a growable deque of `u8` bytes.
//!
//! The use of [`BytesDeque`] is similar to
//! [`std::collections::VecDeque`], but its contents are always
//! available as a slice. Other similar projects are
//! [`linear-deque`](https://docs.rs/crate/linear-deque/latest),
//! [`vmap`](https://docs.rs/crate/vmap/latest),
//! [`slice_ring_buf`](https://docs.rs/crate/slice_ring_buf/latest),
//! [`slice-ring-buffer`](https://docs.rs/crate/slice-ring-buffer/latest). Our
//! reason for writing yet another implementation is that we wanted to
//! provide the user of the crate a means by which they can modify the
//! raw memory themselves (and adjust the offset and length to
//! match). Our implementation is more bare-bones compared to the
//! other crates but it fits our needs.
mod buffer;
use crate::buffer::Buffer;
use std::fmt;
use std::mem::MaybeUninit;
use std::ops::{Deref, DerefMut};
use std::ptr;
use std::slice;

/// [`BytesDeque`]
///
/// The [`BytesDeque`] struct is a growing contiguous buffer with
/// three regions, _front_, _active_, and _back_.
///
/// - A [`BytesDeque`] is constructed with
/// [`with_capacity()`][BytesDeque::with_capacity()]. The `capacity`
/// argument will determine the initial size of the buffer and all
/// resizes will be certain multiples of this initial size.
///
/// - The user may prepend to the active region with
/// [`extend_front()`][BytesDeque::extend_front()] and append with
/// [`extend()`][BytesDeque::extend()]. The buffer will grow if there
/// is not sufficient space for the data being placed.
///
/// - Slices to these regions may be obtained via
/// [`front_slice()`][BytesDeque::front_slice()],
/// [`slice()`][BytesDeque::slice()],
/// [`back_slice()`][BytesDeque::back_slice()], and their mutable
/// variants.
///
/// - The active region can be shrunk via
/// [`remove_front()`][BytesDeque::remove_front()] and
/// [`remove_back()`][BytesDeque::remove_back()], and it can be moved
/// around the buffer, altering its offset from the beginning, via
/// [`move_active()`][BytesDeque::move_active()].
///
/// - Raw access is offered to the underlying pointer via
/// [`as_ptr()`][BytesDeque::as_ptr()] and
/// [`as_mut_ptr()`][BytesDeque::as_mut_ptr()]; once the user has made
/// modifications to the contents, they may call
/// [`set_len()`][BytesDeque::set_len()] and
/// [`set_offset()`][BytesDeque::set_offset()] as appropriate to bring
/// the active region to its proper state.
pub struct BytesDeque {
    buffer: Buffer<u8>,
    len: usize,
    offset: usize,
}

/// # Constructor.
impl BytesDeque {
    /// Create a new [`BytesDeque`] with allocated capacity given by
    /// `capacity`.
    ///
    /// The active region will be empty, placed in the middle at
    /// offset `capacity / 2`. This means that both front and back
    /// regions will have length at least `capacity / 2`.
    ///
    /// The `capacity` argument will determine the initial size of the
    /// buffer and all resizes (whether explicitly via
    /// [`realloc()`][BytesDeque::realloc()] or implicitly when
    /// extending or pushing) will be certain multiples of this
    /// initial size. If the `capacity` is `0`, then the
    /// [`BytesDeque`] will initially be dangling and will allocate on
    /// first use `8192` bytes, or a multiple thereof if more are
    /// needed. A dangling [`BytesDeque`] may be desired if immediate
    /// allocation is not desired.
    pub fn with_capacity(capacity: usize) -> BytesDeque {
        let mut buffer = Buffer::new();
        if capacity != 0 {
            buffer.realloc(capacity);
        }
        BytesDeque {
            buffer,
            len: 0,
            offset: capacity / 2,
        }
    }
    /// The capacity of the buffer.
    ///
    /// Note that this is equal to the sum `self.front_slice.len() +
    /// self.slice.len() + self.back_slice.len()` of the lengths of
    /// the three regions.
    pub fn capacity(&self) -> usize {
        self.buffer.cap
    }
    /// True if [`BytesDeque`] is dangling; i.e. if it has zero
    /// capacity.
    pub fn is_dangling(&self) -> bool {
        self.capacity() == 0
    }
}

/// # The three slices.
///
/// The functions below deal with obtaining slices on the front,
/// active, and back regions.
impl BytesDeque {
    /// A raw pointer to the beginning of the front region.
    pub fn as_ptr(&self) -> *const u8 {
        self.buffer.ptr.as_ptr()
    }
    /// A mutable raw pointer to the beginning of the front region.
    pub fn as_mut_ptr(&mut self) -> *mut u8 {
        self.buffer.ptr.as_ptr()
    }
    /// The entire active region in a slice.
    pub fn slice(&self) -> &[u8] {
        unsafe { std::slice::from_raw_parts(self.as_ptr().add(self.offset), self.len) }
    }
    /// The entire active region in a mutable slice.
    pub fn slice_mut(&mut self) -> &mut [u8] {
        unsafe { std::slice::from_raw_parts_mut(self.as_mut_ptr().add(self.offset), self.len) }
    }
    /// The entire front region in a slice.
    pub fn front_slice(&self) -> &[MaybeUninit<u8>] {
        unsafe { slice::from_raw_parts(self.as_ptr() as *const MaybeUninit<u8>, self.offset) }
    }
    /// The entire front region in a mutable slice.
    pub fn front_slice_mut(&mut self) -> &mut [MaybeUninit<u8>] {
        unsafe { slice::from_raw_parts_mut(self.as_mut_ptr() as *mut MaybeUninit<u8>, self.offset) }
    }
    /// The entire back region in a slice.
    pub fn back_slice(&self) -> &[MaybeUninit<u8>] {
        unsafe {
            slice::from_raw_parts(
                self.as_ptr().add(self.offset + self.len) as *const MaybeUninit<u8>,
                self.capacity() - self.offset - self.len,
            )
        }
    }
    /// The entire back region in a mutable slice.
    pub fn back_slice_mut(&mut self) -> &mut [MaybeUninit<u8>] {
        unsafe {
            slice::from_raw_parts_mut(
                self.as_mut_ptr().add(self.offset + self.len) as *mut MaybeUninit<u8>,
                self.capacity() - self.offset - self.len,
            )
        }
    }
}

/// # Resizing or otherwise modifying the slice boundaries.
impl BytesDeque {
    /// Sets the length of the front region.
    ///
    /// The length of the active region is retained as-is. That means
    /// the user may end up with uninitialized bytes in the active
    /// region; it is **their responsibility** to ensure that they do
    /// not read those values before initializing them. It is further
    /// **their responsibility** to ensure that `new_offset +
    /// self.slice().len() <= self.capacity()`.
    ///
    /// For example if the three regions appear like this:
    ///
    /// ```plain
    /// *123**
    /// faaabb
    ///     |
    ///     uninitialized byte in back region
    /// ```
    ///
    /// and the user decides to increase the length of the front
    /// region by one unit, the buffer will now appear like so:
    ///
    /// ```plain
    /// *123**
    /// ffaaab
    ///     |
    ///     uninitialized byte in active region!
    /// ```
    ///
    /// Typically this methow would be used together with
    /// [`as_mut_ptr()`][BytesDeque::as_mut_ptr()].
    pub unsafe fn set_offset(&mut self, new_offset: usize) {
        self.offset = new_offset;
    }
    /// Sets the length of the active region.
    ///
    /// The user may end up with uninitialized bytes in the active
    /// region if they increase the length of the active region; it is
    /// **their responsibility** to ensure that they do not read those
    /// values before initializing them.  It is further **their
    /// responsibility** to ensure that `new_offset +
    /// self.slice().len() <= self.capacity()`.
    ///
    /// Typically this methow would be used together with
    /// [`as_mut_ptr()`][BytesDeque::as_mut_ptr()].
    pub unsafe fn set_len(&mut self, new_len: usize) {
        self.len = new_len;
    }
    /// Reallocates the buffer to a different capacity.
    ///
    /// This function may be used to increase the buffer size to
    /// provide more room for the regions, or to decrease it.
    ///
    /// # Increasing the buffer
    ///
    /// When increasing the buffer, only the back region becomes
    /// larger. If the user wishes to then move the active region,
    /// they may use [`move_active()`][BytesDeque::move_active].
    ///
    /// # Decreasing the buffer
    ///
    /// - If `new_capacity <= self.front_slice().len()`, then the
    /// active and back regions are truncated to zero size, the front
    /// region will lose the difference `self.front_slice().len() -
    /// new_capacity` from its end, and the offset is set to the end
    /// of the buffer.
    ///
    /// - If `new_capacity < self.front_slice().len() +
    /// self.slice().len()`, then the back region is truncated to zero
    /// size and the active region will lose the difference
    /// `self.front_slice().len() + self.slice().len() - new_capacity`
    /// from its back.
    pub fn realloc(&mut self, new_capacity: usize) {
        if new_capacity <= self.offset {
            self.offset = new_capacity;
            self.len = 0;
        } else if new_capacity < self.offset + self.len {
            self.len -= self.offset + self.len - new_capacity;
        }
        self.buffer.realloc(new_capacity);
    }
    /// Ensures that there's at least `requested` bytes available in
    /// the back region.
    ///
    /// Reallocates if necessary.
    pub fn ensure_back_capacity(&mut self, requested: usize) {
        if self.capacity() == 0 {
            self.realloc(8192);
            self.offset = 8192 / 2;
        }
        if requested > self.back_slice().len() {
            let n = 2 + requested / self.capacity();
            self.realloc(n * self.capacity());
        }
    }
    /// Ensures that there's at least `requested` bytes available in
    /// the front region.
    ///
    /// Reallocates if necessary.
    pub fn ensure_front_capacity(&mut self, requested: usize) {
        if self.capacity() == 0 {
            self.realloc(8192);
            self.offset = 8192 / 2;
        }
        if requested > self.front_slice().len() {
            let old_capacity = self.capacity();
            let n = 2 + requested / old_capacity;
            self.realloc(n * old_capacity);
            unsafe {
                self.move_active_nonoverlapping(self.offset + (n - 1) * old_capacity);
            }
        }
    }
    /// Move the active region elsewhere.
    ///
    /// The user must ensure that the new active region does not land
    /// out of bounds, by verifying that `new_offset + self.len() <=
    /// self.capacity()`.
    pub fn move_active(&mut self, new_offset: usize) {
        unsafe {
            ptr::copy(
                self.slice().as_ptr(),
                self.as_mut_ptr().add(new_offset),
                self.len,
            );
        }
        self.offset = new_offset;
    }
    /// Move the active region elsewhere, nonoverlapping.
    ///
    /// The user must guarantee that moving the active region to the
    /// new offset will not overlap with the old active region. If
    /// this guarantee does not hold, use
    /// [`move_active()`][BytesDeque::move_active()] instead, which is
    /// less optimized.
    pub unsafe fn move_active_nonoverlapping(&mut self, new_offset: usize) {
        unsafe {
            ptr::copy_nonoverlapping(
                self.slice().as_ptr(),
                self.as_mut_ptr().add(new_offset),
                self.len,
            );
        }
        self.offset = new_offset;
    }
}

/// # Adding and removing bytes.
impl BytesDeque {
    /// Copies `src` into the back of the active region, extending it.
    ///
    /// Reallocates if necessary.
    pub fn extend(&mut self, src: &[u8]) {
        self.ensure_back_capacity(src.len());
        unsafe {
            ptr::copy_nonoverlapping(
                src.as_ptr(),
                self.as_mut_ptr().add(self.offset + self.len),
                src.len(),
            );
        }
        self.len += src.len();
    }
    /// Copies `byte` into the back of the active region, extending
    /// it.
    ///
    /// Reallocates if necessary.
    pub fn push_back(&mut self, byte: u8) {
        self.ensure_back_capacity(1);
        unsafe {
            *self.as_mut_ptr().add(self.offset + self.len) = byte;
        }
        self.len += 1;
    }
    /// Copies `src` into the front of the active region, extending
    /// it.
    ///
    /// Reallocates if necessary.
    pub fn extend_front(&mut self, src: &[u8]) {
        self.ensure_front_capacity(src.len());
        unsafe {
            ptr::copy_nonoverlapping(
                src.as_ptr(),
                self.as_mut_ptr().add(self.offset - src.len()),
                src.len(),
            );
        }
        self.offset -= src.len();
        self.len += src.len();
    }
    /// Copies `byte` into the front of the active region, extending
    /// it.
    ///
    /// Reallocates if necessary.
    pub fn push_front(&mut self, byte: u8) {
        self.ensure_front_capacity(1);
        unsafe {
            *self.as_mut_ptr().add(self.offset - 1) = byte;
        }
        self.offset -= 1;
        self.len += 1;
    }
    /// Remove `n` bytes from the back of the active region.
    pub fn remove_back(&mut self, n: usize) {
        if self.len >= n {
            self.len -= n;
        } else {
            self.len = 0;
        }
    }
    /// Remove `n` bytes from the front of the active region.
    pub fn remove_front(&mut self, n: usize) {
        if self.len >= n {
            self.offset += n;
            self.len -= n;
        } else {
            self.offset += self.len;
            self.len = 0;
        }
    }
}

impl Deref for BytesDeque {
    type Target = [u8];
    fn deref(&self) -> &Self::Target {
        self.slice()
    }
}

impl DerefMut for BytesDeque {
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.slice_mut()
    }
}

impl PartialEq<&[u8]> for BytesDeque {
    fn eq(&self, other: &&[u8]) -> bool {
        self.slice() == *other
    }
}

impl fmt::Debug for BytesDeque {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(
            f,
            "BytesDeque {{ active: {:?} len: {:?}, offset: {:?} }}",
            self.slice(),
            self.len,
            self.offset
        )
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_with_capacity() {
        let d = BytesDeque::with_capacity(10);
        assert_eq!(d.capacity(), 10);
    }
    #[test]
    fn test_with_capacity_dangling() {
        let d = BytesDeque::with_capacity(0);
        assert!(d.is_dangling());
        assert_eq!(d, b"");
    }
    #[test]
    fn test_extend_empty() {
        let mut d = BytesDeque::with_capacity(0);
        assert_eq!(d.is_dangling(), true);
        d.extend(b"world");
        assert_eq!(d.is_dangling(), false);
        d.push_front(b' ');
        d.extend_front(b"Hello");
        d.push_back(b'!');
        assert_eq!(d, b"Hello world!");
        d.remove_back(2);
        assert_eq!(d, b"Hello worl");
        d.remove_front(2);
        assert_eq!(d, b"llo worl");
        d.remove_front(100);
        assert_eq!(d, b"");
    }
    #[test]
    fn test_extend_nonempty_01() {
        let mut d = BytesDeque::with_capacity(1);
        assert_eq!(d.is_dangling(), false);
        d.extend(b"world");
        d.push_front(b' ');
        d.extend_front(b"Hello");
        d.push_back(b'!');
        assert_eq!(d, b"Hello world!");
        d.remove_back(2);
        assert_eq!(d, b"Hello worl");
        d.remove_front(2);
        assert_eq!(d, b"llo worl");
        d.remove_back(100);
        assert_eq!(d, b"");
    }
    #[test]
    fn test_extend_nonempty_02() {
        let mut d = BytesDeque::with_capacity(10);
        assert_eq!(d.is_dangling(), false);
        d.extend_front(b"son");
        assert_eq!(d, b"son");
        d.extend_front(b"hello ");
        assert_eq!(d, b"hello son");
    }
}