ring_buffer/

lib.rs

/*!
A queue that also allows direct index addressing.

This queue trades in some features from VecDeque in the std library for the feature of direct
indexing. For more information, see the struct.
*/

use std::alloc::{alloc, dealloc, handle_alloc_error, Layout};
use std::cmp::{max, Ordering};
use std::collections::VecDeque;
use std::fmt::Debug;
use std::hash::{Hash, Hasher};
use std::iter::{FromIterator, FusedIterator, IntoIterator};
use std::marker::PhantomData;
use std::mem::{align_of, size_of};
use std::ops::{Index, IndexMut};
use std::ptr::NonNull;
use std::slice;

#[warn(missing_docs)]
/**
A queue that also allows direct index addressing.

This queue trades some features from VecDeque in the std library for the feature of direct indexing.
Instead of returning `()`, [`push_back`] returns the index of the new element in the buffer. Methods
like [`get_absolute`] can then be used for element access.

The index returned by [`push_back`] or used by [`get_absolute`] may not be the actual index but a
higher number that gets wrapped around internally so the indices are still valid after elements get
moved around by expanding or shrinking the container.

The features not present in `RingBuffer` whereas present in `VecDeque` include:
- Double ended functionality, including `push_front` and `pop_back`
- `append`
- `drain`
- `insert`
- `remove`
- basically anything that messes with the position of elements in the buffer apart from `swap`

[`push_back`]: Self::push_back
[`get_absolute`]: Self::get_absolute
*/
pub struct RingBuffer<T> {
    /// Pointer to the allocated array data.
    data: NonNull<T>,
    /// Tells the compiler the struct owns `T` values.
    _marker: PhantomData<T>,
    /// A bitfield signaling if a value got moved to this position by growing from a wrapped state.
    moved_value: Box<[u64]>,
    /// The count of elements currently saved in the buffer.
    len: usize,
    /// The amount of element that fit into the buffer before reallocation.
    capacity: usize,
    /// The next free element index.
    head: usize,
    /// The last valid element index, is there is one.
    tail: usize,
}

/// A direct index into the buffer.
#[derive(Clone, Copy, Debug)]
pub struct RingBufferIndex {
    /// The index at the time of allocation.
    base_index: usize,
    /// An offset that is applied if the value got moved by growing the buffer.
    wrap_offset: usize,
}

impl<T> RingBuffer<T> {
    /// Creates an empty `RingBuffer`.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let buffer: RingBuffer<usize> = RingBuffer::new();
    /// ```
    pub fn new() -> RingBuffer<T> {
        RingBuffer::<T>::with_capacity(0)
    }

    /// Creates an empty `RingBuffer` with space for at least `capacity` elements.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let buffer: RingBuffer<usize> = RingBuffer::with_capacity(10);
    /// assert!(buffer.capacity() >= 10);
    /// ```
    pub fn with_capacity(capacity: usize) -> RingBuffer<T> {
        if size_of::<T>() > 0 {
            let capacity = max(capacity.next_power_of_two(), 2);

            let layout =
                Layout::from_size_align(capacity * size_of::<T>(), align_of::<T>()).unwrap();
            let ptr = unsafe { alloc(layout) };
            if ptr.is_null() {
                handle_alloc_error(layout);
            }

            RingBuffer {
                data: NonNull::new(ptr).unwrap().cast(),
                _marker: PhantomData::<T>,
                moved_value: vec![0; (capacity + u64::BITS as usize - 1) / u64::BITS as usize]
                    .into(),
                len: 0,
                capacity,
                head: 0,
                tail: 0,
            }
        } else {
            RingBuffer {
                data: NonNull::dangling(),
                _marker: PhantomData::<T>,
                moved_value: vec![0; (capacity + u64::BITS as usize - 1) / u64::BITS as usize]
                    .into(),
                len: 0,
                capacity: usize::MAX,
                head: 0,
                tail: 0,
            }
        }
    }

    /// Returns a pair of slices which contain, in order, the contents of the
    /// `RingBuffer`.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    ///
    /// buffer.push_back(41);
    /// buffer.push_back(42);
    /// buffer.push_back(1);
    /// buffer.push_back(2);
    ///
    /// assert_eq!(buffer.len(), 4);
    /// assert_eq!(buffer.capacity(), 4);
    /// assert_eq!(buffer.front(), Some(&41));
    /// assert_eq!(buffer.as_slices(), (&[41, 42, 1, 2][..], &[][..]));
    ///
    /// buffer.pop_front();
    /// buffer.pop_front();
    /// buffer.push_back(3);
    /// buffer.push_back(4);
    ///
    /// assert_eq!(buffer.as_slices(), (&[1, 2][..], &[3, 4][..]));
    /// ```
    #[inline]
    pub fn as_slices(&self) -> (&[T], &[T]) {
        unsafe {
            if self.wraps_around() {
                (
                    slice::from_raw_parts(
                        self.data.as_ptr().add(self.tail),
                        self.capacity - self.tail,
                    ),
                    slice::from_raw_parts(self.data.as_ptr(), self.head),
                )
            } else {
                let head_or_capacity = if self.head == 0 {
                    self.capacity
                } else {
                    self.head
                };

                (
                    slice::from_raw_parts(
                        self.data.as_ptr().add(self.tail),
                        head_or_capacity - self.tail,
                    ),
                    &[],
                )
            }
        }
    }

    /// Provides a reference to the back element of the queue, or `None` if the `RingBuffer` is
    /// empty.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// assert_eq!(buffer.back(), None);
    ///
    /// buffer.push_back(1);
    /// buffer.push_back(2);
    /// assert_eq!(buffer.back(), Some(&2));
    /// ```
    #[inline]
    pub fn back(&self) -> Option<&T> {
        self.get_relative(self.len.wrapping_sub(1))
    }

    /// Provides a mutable reference to the back element of the queue, or `None` if the
    /// `RingBuffer` is empty.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// assert_eq!(buffer.back(), None);
    ///
    /// buffer.push_back(1);
    /// buffer.push_back(2);
    /// if let Some(x) = buffer.back_mut() {
    ///     *x = 42;
    /// }
    /// assert_eq!(buffer.back(), Some(&42));
    /// ```
    #[inline]
    pub fn back_mut(&mut self) -> Option<&mut T> {
        self.get_relative_mut(self.len.wrapping_sub(1))
    }

    /// Returns the absolute index of the back element of the queue, or `None` if the
    /// `RingBuffer` is empty.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// assert!(buffer.back_absolute_index().is_none());
    ///
    /// buffer.push_back(1);
    /// buffer.push_back(2);
    /// let back_index = buffer.back_absolute_index();
    ///
    /// assert!(back_index.is_some());
    /// assert_eq!(buffer.get_absolute(back_index.unwrap()), buffer.back());
    /// ```
    #[inline]
    pub fn back_absolute_index(&self) -> Option<RingBufferIndex> {
        if self.len > 0 {
            Some(RingBufferIndex {
                base_index: self.head.wrapping_sub(1) & self.mask(),
                wrap_offset: self.capacity * (self.wraps_around() & (self.head != 0)) as usize,
            })
        } else {
            None
        }
    }

    /// Returns the number of elements the `RingBuffer` can hold without reallocating.
    /// For fast wrapping functionality, capacity is always a power of two.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let buffer: RingBuffer<usize> = RingBuffer::with_capacity(10);
    /// assert!(buffer.capacity() >= 16);
    /// ```
    #[inline]
    pub fn capacity(&self) -> usize {
        self.capacity
    }

    /// Clears the `RingBuffer`, removing all values.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// buffer.push_back(1);
    /// buffer.clear();
    /// assert!(buffer.is_empty());
    /// ```
    #[inline]
    pub fn clear(&mut self) {
        while self.len > 0 {
            self.pop_front();
        }
        for field in self.moved_value.iter_mut() {
            *field = 0;
        }
        self.len = 0;
        self.head = 0;
        self.tail = 0;
    }

    /// Returns `true` if the `RingBuffer` contains an element equal to the
    /// given value.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    ///
    /// buffer.push_back(0);
    /// buffer.push_back(1);
    ///
    /// assert_eq!(buffer.contains(&1), true);
    /// assert_eq!(buffer.contains(&42), false);
    /// ```
    #[inline]
    pub fn contains(&self, x: &T) -> bool
    where
        T: PartialEq<T>,
    {
        let (a, b) = self.as_slices();
        a.contains(x) || b.contains(x)
    }

    /// Provides a reference to the front element of the queue, or `None` if the `RingBuffer` is
    /// empty.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// assert_eq!(buffer.front(), None);
    ///
    /// buffer.push_back(1);
    /// buffer.push_back(2);
    /// assert_eq!(buffer.front(), Some(&1));
    /// ```
    #[inline]
    pub fn front(&self) -> Option<&T> {
        self.get_relative(0)
    }

    /// Provides a mutable reference to the front element of the queue, or `None` if the
    /// `RingBuffer` is empty.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// assert_eq!(buffer.front_mut(), None);
    ///
    /// buffer.push_back(1);
    /// buffer.push_back(2);
    /// if let Some(x) = buffer.front_mut() {
    ///     *x = 42;
    /// }
    /// assert_eq!(buffer.front(), Some(&42));
    /// ```
    #[inline]
    pub fn front_mut(&mut self) -> Option<&mut T> {
        self.get_relative_mut(0)
    }

    /// Returns the absolute index of the front element of the queue, or `None` if the
    /// `RingBuffer` is empty.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// assert!(buffer.front_absolute_index().is_none());
    ///
    /// buffer.push_back(1);
    /// buffer.push_back(2);
    ///
    /// let front_index = buffer.front_absolute_index();
    ///
    /// assert!(front_index.is_some());
    /// assert_eq!(buffer.get_absolute(front_index.unwrap()), buffer.front());
    /// ```
    #[inline]
    pub fn front_absolute_index(&self) -> Option<RingBufferIndex> {
        if self.len > 0 {
            Some(RingBufferIndex {
                base_index: self.tail,
                wrap_offset: 0,
            })
        } else {
            None
        }
    }

    /// Retrieves an element in the `RingBuffer` by absolute index.
    ///
    /// The index provided is the index used by the internal container.
    /// This is designed to be used in conjunction with [`push_back`].
    /// This also gets wrapped around, supporting expanding and shrinking the container without
    /// breaking the access with absolute addresses.
    ///
    /// [`push_back`]: Self::push_back
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    ///
    /// let first = buffer.push_back(1);
    /// buffer.push_back(2);
    /// let second = buffer.push_back(42);
    ///
    /// assert_eq!(buffer.get_absolute(first), Some(&1));
    /// assert_eq!(buffer.get_absolute(second), Some(&42));
    /// ```
    #[inline]
    pub fn get_absolute(&self, index: RingBufferIndex) -> Option<&T> {
        if self.is_index_in_range(index) {
            unsafe { Some(&*self.data.as_ptr().add(self.resolve_index(index))) }
        } else {
            None
        }
    }

    /// Retrieves a mutable element in the `RingBuffer` by absolute index.
    ///
    /// The index provided is the index used by the internal container.
    /// This is designed to be used in conjunction with [`push_back`].
    /// This also gets wrapped around, supporting expanding and shrinking the container without
    /// breaking the access with absolute addresses.
    ///
    /// [`push_back`]: Self::push_back
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    ///
    /// buffer.push_back(1);
    /// let the_answer = buffer.push_back(2);
    /// buffer.push_back(3);
    ///
    /// assert_eq!(buffer.get_absolute(the_answer), Some(&2));
    ///
    /// if let Some(x) = buffer.get_absolute_mut(the_answer) {
    ///     *x = 42;
    /// }
    ///
    /// assert_eq!(buffer.get_absolute(the_answer), Some(&42));
    /// ```
    #[inline]
    pub fn get_absolute_mut(&mut self, index: RingBufferIndex) -> Option<&mut T> {
        if self.is_index_in_range(index) {
            unsafe { Some(&mut *self.data.as_ptr().add(self.resolve_index(index))) }
        } else {
            None
        }
    }

    /// Retrieves an element in the `RingBuffer` by absolute index without checking for validity.
    ///
    /// This does the same as [`get_absolute`], but skips any checks. Use this if you really need
    /// the performance and can guarantee the accessed element is valid.
    ///
    /// [`get_absolute`]: Self::get_absolute
    ///
    /// # Safety
    ///
    /// The caller is responsible for maintaining Rusts ownership guarantees.
    /// The validity of a buffer entry also isn't checked, so while being valid memory, the
    /// reference may not point to an object in valid state.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    ///
    /// let first = buffer.push_back(1);
    /// buffer.push_back(2);
    /// let second = buffer.push_back(42);
    ///
    /// unsafe {
    ///     assert_eq!(buffer.get_absolute_unchecked(first), &1);
    ///     assert_eq!(buffer.get_absolute_unchecked(second), &42);
    /// }
    /// ```
    #[inline]
    pub unsafe fn get_absolute_unchecked(&self, index: RingBufferIndex) -> &T {
        &*self.data.as_ptr().add(self.resolve_index(index))
    }

    /// Retrieves a mutable element in the `RingBuffer` by absolute index without checking for
    /// validity.
    ///
    /// This does the same as [`get_absolute_mut`], but skips any checks. Use this if you really need
    /// the performance and can guarantee the accessed element is valid.
    ///
    /// [`get_absolute_mut`]: Self::get_absolute_mut
    ///
    /// # Safety
    ///
    /// The caller is responsible for maintaining Rusts ownership guarantees.
    /// The validity of a buffer entry also isn't checked, so while being valid memory, the
    /// reference may not point to an object in valid state.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    ///
    /// buffer.push_back(1);
    /// let the_answer = buffer.push_back(2);
    /// buffer.push_back(3);
    ///
    /// assert_eq!(buffer.get_absolute(the_answer), Some(&2));
    ///
    /// unsafe {
    ///     *buffer.get_absolute_mut_unchecked(the_answer) = 42;
    /// }
    ///
    /// assert_eq!(buffer.get_absolute(the_answer), Some(&42));
    /// ```
    #[inline]
    pub unsafe fn get_absolute_mut_unchecked(&mut self, index: RingBufferIndex) -> &mut T {
        &mut *self.data.as_ptr().add(self.resolve_index(index))
    }

    /// Retrieves an element in the `RingBuffer` by relative index.
    ///
    /// Element at index 0 is the front of the queue.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// buffer.push_back(3);
    /// buffer.push_back(4);
    /// buffer.push_back(5);
    /// buffer.push_back(6);
    /// assert_eq!(buffer.get_relative(1), Some(&4));
    /// ```
    pub fn get_relative(&self, index: usize) -> Option<&T> {
        if index < self.len {
            unsafe { Some(&*self.get_relative_pointer(index)) }
        } else {
            None
        }
    }

    /// Retrieves an element in the `RingBuffer` mutably by relative index.
    ///
    /// Element at index 0 is the front of the queue.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// buffer.push_back(3);
    /// buffer.push_back(4);
    /// buffer.push_back(5);
    /// buffer.push_back(6);
    /// if let Some(elem) = buffer.get_relative_mut(1) {
    ///     *elem = 7;
    /// }
    ///
    /// assert_eq!(buffer.get_relative(1), Some(&7));
    /// ```
    pub fn get_relative_mut(&mut self, index: usize) -> Option<&mut T> {
        if index < self.len {
            unsafe { Some(&mut *self.get_relative_pointer(index)) }
        } else {
            None
        }
    }

    /// Returns `true` if the `RingBuffer` is empty.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// assert!(buffer.is_empty());
    /// buffer.push_back(1);
    /// assert!(!buffer.is_empty());
    /// ```
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns `true` if the buffer is at full capacity.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::with_capacity(2);
    /// assert_eq!(buffer.capacity(), 2);
    /// assert!(!buffer.is_full());
    /// buffer.push_back(1);
    /// buffer.push_back(2);
    /// assert!(buffer.is_full());
    /// ```
    #[inline]
    pub fn is_full(&self) -> bool {
        self.len == self.capacity
    }

    /// Returns a front-to-back iterator.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// buffer.push_back(3);
    /// buffer.push_back(4);
    /// buffer.push_back(5);
    /// let b: &[_] = &[&3, &4, &5];
    /// let c: Vec<&usize> = buffer.iter().collect();
    /// assert_eq!(buffer.front(), Some(&3));
    /// assert_eq!(&c[..], b);
    /// ```
    #[inline]
    pub fn iter(&self) -> Iter<T> {
        Iter {
            buffer: unsafe { slice::from_raw_parts(self.data.as_ptr(), self.capacity) },
            len: self.len,
            index: self.tail,
        }
    }

    /// Returns a front-to-back iterator that returns mutable references.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// buffer.push_back(3);
    /// buffer.push_back(4);
    /// buffer.push_back(5);
    /// for num in buffer.iter_mut() {
    ///     *num = *num - 2;
    /// }
    /// let b: &[_] = &[&mut 1, &mut 2, &mut 3];
    /// assert_eq!(&buffer.iter_mut().collect::<Vec<&mut usize>>()[..], b);
    /// ```
    #[inline]
    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut {
            buffer: unsafe { slice::from_raw_parts_mut(self.data.as_ptr(), self.capacity) },
            len: self.len,
            index: self.tail,
        }
    }

    /// Returns the number of elements in the `RingBuffer`.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// assert_eq!(buffer.len(), 0);
    /// buffer.push_back(1);
    /// assert_eq!(buffer.len(), 1);
    /// ```
    #[inline]
    pub fn len(&self) -> usize {
        self.len
    }

    /// Removes the first element and returns it, or `None` if the `RingBuffer` is
    /// empty.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// buffer.push_back(1);
    /// buffer.push_back(2);
    ///
    /// assert_eq!(buffer.pop_front(), Some(1));
    /// assert_eq!(buffer.pop_front(), Some(2));
    /// assert_eq!(buffer.pop_front(), None);
    /// ```
    #[inline]
    pub fn pop_front(&mut self) -> Option<T> {
        if !self.is_empty() {
            let return_value = unsafe { Some(self.data.as_ptr().add(self.tail).read()) };

            self.tail = (self.tail + 1) & self.mask();
            self.len -= 1;
            return_value
        } else {
            None
        }
    }

    /// Appends an element to the back of the `RingBuffer`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// buffer.push_back(1);
    /// buffer.push_back(42);
    /// assert_eq!(42, *buffer.back().unwrap());
    /// ```
    #[inline]
    pub fn push_back(&mut self, new_element: T) -> RingBufferIndex {
        if self.is_full() {
            self.grow(self.capacity << 1);
        }

        unsafe {
            self.data.as_ptr().add(self.head).write(new_element);
        }

        let wrap_offset;
        let check_bit = 1 << (self.head & (u64::BITS as usize - 1));
        if self.wraps_around() {
            self.moved_value[self.head / u64::BITS as usize] |= check_bit;
            wrap_offset = self.capacity;
        } else {
            self.moved_value[self.head / u64::BITS as usize] &= u64::MAX ^ check_bit;
            wrap_offset = 0;
        }
        let base_index = self.head;
        self.head = (self.head + 1) & self.mask();
        self.len += 1;

        RingBufferIndex {
            base_index,
            wrap_offset,
        }
    }

    /// Reserves capacity for at least `additional` more elements to be inserted in the given
    /// `RingBuffer`. The collection may reserve more space to avoid frequent reallocations.
    ///
    /// # Panics
    ///
    /// Panics if the new capacity overflows `usize`.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer: RingBuffer<usize> = vec![1].into_iter().collect();
    /// buffer.reserve(10);
    /// assert!(buffer.capacity() >= 11);
    /// ```
    pub fn reserve(&mut self, additional: usize) {
        let new_capacity = self
            .len
            .checked_add(additional)
            .and_then(|cap| cap.checked_next_power_of_two())
            .expect("capacity overflow");
        if new_capacity > self.capacity {
            self.grow(new_capacity);
        }
    }

    /// Shrinks the capacity of the `RingBuffer` with a lower bound.
    ///
    /// The capacity will remain at least as large as the maximum of the length
    /// and the supplied value.
    ///
    /// Does nothing if the current capacity is smaller than the supplied
    /// minimum capacity.
    ///
    /// Also only shrinks if no element position needs to change as to preserve the indices of the
    /// allocated elements.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::with_capacity(15);
    /// buffer.extend(0..4);
    /// assert!(buffer.capacity() >= 15);
    /// assert!(!(buffer.capacity() < 6));
    /// buffer.shrink_to(6);
    /// assert!(buffer.capacity() >= 6);
    /// assert!(!(buffer.capacity() < 4));
    /// buffer.shrink_to(0);
    /// assert!(buffer.capacity() >= 4);
    /// ```
    pub fn shrink_to(&mut self, min_capacity: usize) {
        let new_capacity = max(
            2,
            max(
                min_capacity.next_power_of_two(),
                self.len.next_power_of_two(),
            ),
        );
        if (new_capacity < self.capacity)
            & !self.wraps_around()
            & !self.is_empty()
            & (self.head != 0)
            & (self.head <= new_capacity)
        {
            unsafe {
                let layout = Layout::from_size_align_unchecked(
                    new_capacity * size_of::<T>(),
                    align_of::<T>(),
                );
                let new_ptr: *mut T = alloc(layout) as *mut T;
                if new_ptr.is_null() {
                    handle_alloc_error(layout);
                }

                self.data
                    .as_ptr()
                    .add(self.tail)
                    .copy_to(new_ptr.add(self.tail), self.len);

                dealloc(
                    self.data.as_ptr() as *mut u8,
                    Layout::from_size_align(self.capacity * size_of::<T>(), align_of::<T>())
                        .unwrap(),
                );

                self.data = NonNull::new_unchecked(new_ptr);
            }

            self.moved_value = self
                .moved_value
                .iter()
                .copied()
                .take(new_capacity)
                .collect();
            self.capacity = new_capacity;
            self.head &= self.mask();
            self.tail &= self.mask();
        }
    }

    /// Shrinks the capacity of the `RingBuffer` as much as possible.
    ///
    /// It will drop down as close as possible to the length but the allocator may still inform the
    /// `RingBuffer` that there is space for a few more elements.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::with_capacity(15);
    /// buffer.extend(0..4);
    /// assert!(buffer.capacity() >= 15);
    /// buffer.shrink_to_fit();
    /// assert!(buffer.capacity() >= 4);
    /// ```
    pub fn shrink_to_fit(&mut self) {
        self.shrink_to(0);
    }

    /// Swaps elements at relative indices `i` and `j`.
    ///
    /// `i` and `j` may be equal.
    ///
    /// Element at index 0 is the front of the queue.
    ///
    /// # Panics
    ///
    /// Panics if either index is out of bounds.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// buffer.push_back(3);
    /// buffer.push_back(4);
    /// buffer.push_back(5);
    /// buffer.push_back(6);
    /// buffer.push_back(7);
    ///
    /// assert_eq!(buffer.get_relative(0), Some(&3));
    /// assert_eq!(buffer.get_relative(2), Some(&5));
    ///
    /// buffer.swap_relative(0, 2);
    ///
    /// assert_eq!(buffer.get_relative(0), Some(&5));
    /// assert_eq!(buffer.get_relative(2), Some(&3));
    /// ```
    pub fn swap_relative(&mut self, i: usize, j: usize) {
        assert!(
            (i < self.len) & (j < self.len),
            "At least one index is out of bounds, i is {}, j is {}, length of buffer is {}",
            i,
            j,
            self.len
        );
        unsafe {
            self.get_relative_pointer(i)
                .swap(self.get_relative_pointer(j));
        }
    }

    /// Swaps elements at absolute indices `i` and `j`.
    ///
    /// `i` and `j` may be equal.
    ///
    /// This is designed to be used in conjunction with [`push_back`].
    ///
    /// [`push_back`]: Self::push_back
    ///
    /// # Panics
    ///
    /// Panics if either index is out of bounds.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// buffer.push_back(3);
    /// let first = buffer.push_back(4);
    /// buffer.push_back(5);
    /// let second = buffer.push_back(6);
    /// buffer.push_back(7);
    ///
    /// assert_eq!(buffer.get_absolute(first), Some(&4));
    /// assert_eq!(buffer.get_absolute(second), Some(&6));
    ///
    /// buffer.swap_absolute(first, second);
    ///
    /// assert_eq!(buffer.get_absolute(first), Some(&6));
    /// assert_eq!(buffer.get_absolute(second), Some(&4));
    /// ```
    pub fn swap_absolute(&mut self, i: RingBufferIndex, j: RingBufferIndex) {
        assert!(
            self.is_index_in_range(i) & self.is_index_in_range(j),
            "At least one index is out of bounds, i is {}, j is {}, buffer is from {} to {}",
            self.resolve_index(i),
            self.resolve_index(j),
            self.tail,
            self.head
        );
        unsafe {
            self.data
                .as_ptr()
                .add(self.resolve_index(i))
                .swap(self.data.as_ptr().add(self.resolve_index(j)));
        }
    }

    /// Shortens the `RingBuffer`, dropping excess elements from the back.
    ///
    /// If `len` is greater than the `RingBuffer`'s current length, this has no
    /// effect.
    ///
    /// # Example
    ///
    /// ```
    /// # use ring_buffer::RingBuffer;
    /// #
    /// let mut buffer = RingBuffer::new();
    /// buffer.push_back(5);
    /// buffer.push_back(10);
    /// buffer.push_back(15);
    /// assert_eq!(buffer.len(), 3);
    /// buffer.truncate(1);
    /// assert_eq!(buffer.len(), 1);
    /// assert_eq!(buffer.get_relative(0), Some(&15));
    /// ```
    pub fn truncate(&mut self, len: usize) {
        for _ in len..self.len {
            self.pop_front();
        }
    }

    // private functions
    /// Tests if the given address is in the valid
    #[inline]
    fn is_index_in_range(&self, index: RingBufferIndex) -> bool {
        let base_index = self.resolve_index(index);
        if self.wraps_around() {
            base_index.wrapping_sub(self.head) >= (self.capacity - self.len)
        } else {
            base_index.wrapping_sub(self.tail) < self.len
        }
    }

    /// Expands the container to a larger one and copies the data. Unwraps the `RingBuffer` if it
    /// was wrapped before.
    fn grow(&mut self, new_capacity: usize) {
        let mut moved_value = vec![0; (new_capacity + u64::BITS as usize - 1) / u64::BITS as usize];
        moved_value[..(self.capacity + u64::BITS as usize - 1) / u64::BITS as usize]
            .copy_from_slice(&self.moved_value[..]);

        unsafe {
            assert_ne!(size_of::<T>(), 0, "capacity overflow");
            assert!(new_capacity.is_power_of_two());

            let layout =
                Layout::from_size_align_unchecked(new_capacity * size_of::<T>(), align_of::<T>());
            let new_ptr: *mut T = alloc(layout) as *mut T;
            if new_ptr.is_null() {
                handle_alloc_error(layout);
            }

            if self.wraps_around() {
                self.data
                    .as_ptr()
                    .add(self.tail)
                    .copy_to(new_ptr.add(self.tail), self.capacity - self.tail);
                self.data
                    .as_ptr()
                    .copy_to(new_ptr.add(self.capacity), self.head);
                self.head += self.capacity;

                for i in self.capacity..self.head {
                    let check_bit = 1 << (i & (u64::BITS as usize - 1));
                    moved_value[i / u64::BITS as usize] |= check_bit;
                }
            } else if !self.is_empty() {
                self.data
                    .as_ptr()
                    .add(self.tail)
                    .copy_to(new_ptr.add(self.tail), self.len);
            }

            dealloc(
                self.data.as_ptr() as *mut u8,
                Layout::from_size_align(self.capacity * size_of::<T>(), align_of::<T>()).unwrap(),
            );

            self.data = NonNull::new_unchecked(new_ptr);
        }

        self.capacity = new_capacity;
        self.moved_value = moved_value.into();
    }

    /// A more convenient way to access a relative addressed element. Public access method only
    /// need to add their sugar.
    #[inline]
    unsafe fn get_relative_pointer(&self, index: usize) -> *mut T {
        self.data
            .as_ptr()
            .add(self.tail.wrapping_add(index) & self.mask())
    }

    /// The name conveys the meaning better than its content.
    #[inline]
    fn mask(&self) -> usize {
        self.capacity - 1
    }

    /// Converts a [`RingBufferIndex`] into its effective index.
    #[inline]
    fn resolve_index(&self, index: RingBufferIndex) -> usize {
        if index.wrap_offset < self.capacity {
            let check_index = index.base_index + index.wrap_offset;
            let check_bit = 1 << (check_index as u64 & (u64::BITS as u64 - 1));
            let apply_offset = (self.moved_value[check_index / u64::BITS as usize] & check_bit) > 0;
            index.base_index + index.wrap_offset * apply_offset as usize
        } else {
            index.base_index
        }
    }

    /// If the container wraps around.
    #[inline]
    fn wraps_around(&self) -> bool {
        !self.is_empty() & (self.head <= self.tail)
    }
}

impl RingBufferIndex {
    /// Uses the buffer to resolve any aliasing that can occur because of a growing buffer and wrap-
    /// around.
    #[inline]
    pub fn eq<T>(self, buffer: &RingBuffer<T>, other: Self) -> bool {
        buffer.resolve_index(self) == buffer.resolve_index(other)
    }
}

impl<T> Clone for RingBuffer<T>
where
    T: Clone,
{
    fn clone(&self) -> RingBuffer<T> {
        self.iter().cloned().collect()
    }
}

impl<T> Debug for RingBuffer<T>
where
    T: Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_list().entries(self).finish()
    }
}

impl<T> Default for RingBuffer<T> {
    #[inline]
    fn default() -> RingBuffer<T> {
        RingBuffer::new()
    }
}

impl<T> Drop for RingBuffer<T> {
    fn drop(&mut self) {
        while !self.is_empty() {
            self.pop_front();
        }

        if size_of::<T>() > 0 {
            unsafe {
                dealloc(
                    self.data.as_ptr() as *mut u8,
                    Layout::from_size_align_unchecked(
                        self.capacity * size_of::<T>(),
                        align_of::<T>(),
                    ),
                )
            }
        }
    }
}

impl<T> Eq for RingBuffer<T> where T: Eq {}

impl<T> Extend<T> for RingBuffer<T> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        for elem in iter.into_iter() {
            self.push_back(elem);
        }
    }
}

impl<'a, T> Extend<&'a T> for RingBuffer<T>
where
    T: 'a + Copy,
{
    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
        self.extend(iter.into_iter().cloned());
    }
}

impl<T> From<Vec<T>> for RingBuffer<T> {
    // This can be optimized to avoid all the copying
    fn from(other: Vec<T>) -> Self {
        let mut buffer = RingBuffer::with_capacity(other.len());
        for elem in other.into_iter() {
            buffer.push_back(elem);
        }
        buffer
    }
}

impl<T> Hash for RingBuffer<T>
where
    T: Hash,
{
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.len.hash(state);
        self.head.hash(state);
        self.tail.hash(state);
        let (a, b) = self.as_slices();
        Hash::hash_slice(a, state);
        Hash::hash_slice(b, state);
    }
}

impl<T> From<RingBuffer<T>> for VecDeque<T> {
    // This can be optimized to avoid all the copying
    fn from(buffer: RingBuffer<T>) -> Self {
        let mut vec = VecDeque::<T>::with_capacity(buffer.len());
        for elem in buffer.into_iter() {
            vec.push_back(elem);
        }
        vec
    }
}

impl<T> FromIterator<T> for RingBuffer<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> RingBuffer<T> {
        let iterator = iter.into_iter();
        let (bound, _) = iterator.size_hint();
        let mut ring_buffer = RingBuffer::<T>::with_capacity(bound);
        ring_buffer.extend(iterator);
        ring_buffer
    }
}

impl<T> Index<RingBufferIndex> for RingBuffer<T> {
    type Output = T;

    #[inline]
    fn index(&self, index: RingBufferIndex) -> &T {
        self.get_absolute(index).expect("Out of bounds access")
    }
}

impl<T> IndexMut<RingBufferIndex> for RingBuffer<T> {
    #[inline]
    fn index_mut(&mut self, index: RingBufferIndex) -> &mut T {
        self.get_absolute_mut(index).expect("Out of bounds access")
    }
}

impl<T> IntoIterator for RingBuffer<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    /// Consumes the `RingBuffer` into a front-to-back iterator yielding elements by
    /// value.
    fn into_iter(self) -> Self::IntoIter {
        IntoIter { inner: self }
    }
}

impl<'a, T> IntoIterator for &'a RingBuffer<T> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a, T> IntoIterator for &'a mut RingBuffer<T> {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

impl<T> Ord for RingBuffer<T>
where
    T: Ord,
{
    fn cmp(&self, other: &RingBuffer<T>) -> Ordering {
        self.iter().cmp(other.iter())
    }
}

impl<T> PartialEq<RingBuffer<T>> for RingBuffer<T>
where
    T: PartialEq,
{
    fn eq(&self, other: &RingBuffer<T>) -> bool {
        if (self.len == other.len) & (self.tail == other.tail) & (self.head == other.head) {
            let mut other_iter = other.iter();
            for elem in self.iter() {
                if elem != other_iter.next().unwrap() {
                    return false;
                }
            }
            true
        } else {
            false
        }
    }
}

impl<T> PartialOrd<RingBuffer<T>> for RingBuffer<T>
where
    T: PartialOrd,
{
    fn partial_cmp(&self, other: &RingBuffer<T>) -> Option<Ordering> {
        self.iter().partial_cmp(other.iter())
    }
}

unsafe impl<T> Send for RingBuffer<T> where T: Send {}
unsafe impl<T> Sync for RingBuffer<T> where T: Sync {}

/// An iterator over the elements of a `RingBuffer`.
///
/// This `struct` is created by the [`iter`] method on [`RingBuffer`]. See its
/// documentation for more.
///
/// [`iter`]: crate::RingBuffer::iter
/// [`RingBuffer`]: crate::RingBuffer
pub struct Iter<'a, T: 'a> {
    buffer: &'a [T],
    len: usize,
    index: usize,
}

impl<T> Iter<'_, T> {
    fn as_slices(&self) -> (&[T], &[T]) {
        if (self.index + self.len) > self.buffer.len() {
            let remaining_len = self.index + self.len - self.buffer.len();
            (&self.buffer[self.index..], &self.buffer[..remaining_len])
        } else {
            (&self.buffer[self.index..self.index + self.len], &[])
        }
    }
}

impl<T> Clone for Iter<'_, T> {
    fn clone(&self) -> Self {
        Iter {
            buffer: self.buffer,
            len: self.len,
            index: self.index,
        }
    }
}

impl<T> Debug for Iter<'_, T>
where
    T: Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let (front, back) = self.as_slices();
        f.debug_tuple("Iter").field(&front).field(&back).finish()
    }
}

impl<'a, T> Iterator for Iter<'a, T>
where
    T: 'a,
{
    type Item = &'a T;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.len > 0 {
            let current_index = self.index;
            self.index = (self.index + 1) & (self.buffer.len() - 1);
            self.len -= 1;

            unsafe { Some(self.buffer.get_unchecked(current_index)) }
        } else {
            None
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }
}

impl<T> ExactSizeIterator for Iter<'_, T> {}

impl<T> FusedIterator for Iter<'_, T> {}

/// A mutable iterator over the elements of a `RingBuffer`.
///
/// This `struct` is created by the [`iter_mut`] method on [`RingBuffer`]. See its
/// documentation for more.
///
/// [`iter_mut`]: crate::RingBuffer::iter_mut
/// [`RingBuffer`]: crate::RingBuffer
pub struct IterMut<'a, T: 'a> {
    buffer: &'a mut [T],
    len: usize,
    index: usize,
}

impl<T> IterMut<'_, T> {
    fn as_slices(&self) -> (&[T], &[T]) {
        if (self.index + self.len) > self.buffer.len() {
            let remaining_len = self.index + self.len - self.buffer.len();
            (&self.buffer[self.index..], &self.buffer[..remaining_len])
        } else {
            (&self.buffer[self.index..self.index + self.len], &[])
        }
    }
}

impl<T> Debug for IterMut<'_, T>
where
    T: Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let (front, back) = self.as_slices();
        f.debug_tuple("IterMut").field(&front).field(&back).finish()
    }
}

impl<'a, T> Iterator for IterMut<'a, T>
where
    T: 'a,
{
    type Item = &'a mut T;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.len > 0 {
            let current_index = self.index;
            self.index = (self.index + 1) & (self.buffer.len() - 1);
            self.len -= 1;

            unsafe {
                let elem = self.buffer.get_unchecked_mut(current_index);
                // and now for some black magic
                // the std stuff does this too, but afaik this breaks the borrow checker
                Some(&mut *(elem as *mut T))
            }
        } else {
            None
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }
}

impl<T> ExactSizeIterator for IterMut<'_, T> {}

impl<T> FusedIterator for IterMut<'_, T> {}

/// An owning iterator over the elements of a `RingBuffer`.
///
/// This `struct` is created by the [`into_iter`] method on [`RingBuffer`]. See its
/// documentation for more.
///
/// [`into_iter`]: crate::RingBuffer::into_iter
/// [`RingBuffer`]: crate::RingBuffer
#[derive(Clone)]
pub struct IntoIter<T> {
    inner: RingBuffer<T>,
}

impl<T> Debug for IntoIter<T>
where
    T: Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let (front, back) = self.inner.as_slices();
        f.debug_tuple("OwnedIter")
            .field(&front)
            .field(&back)
            .finish()
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.inner.pop_front()
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.inner.len, Some(self.inner.len))
    }
}

impl<T> ExactSizeIterator for IntoIter<T> {}

impl<T> FusedIterator for IntoIter<T> {}

#[cfg(test)]
mod tests {
    use crate::{RingBuffer, RingBufferIndex};

    #[test]
    fn access_and_reallocations() {
        let mut buffer = RingBuffer::<usize>::with_capacity(2);
        let mut indices = Vec::with_capacity(8);
        assert_eq!(buffer.capacity, 2, "Initialised with too much capacity");

        // Phase 1: Filling the buffer and trigger extensions
        for i in 1..=8 {
            indices.push(buffer.push_back(i));
        }
        assert!(indices[0].eq(
            &buffer,
            RingBufferIndex {
                base_index: 0,
                wrap_offset: 0
            }
        ));
        assert!(indices[7].eq(
            &buffer,
            RingBufferIndex {
                base_index: 7,
                wrap_offset: 0
            }
        ));
        assert_eq!(buffer.capacity, 8);
        assert_eq!(buffer.as_slices(), (&[1, 2, 3, 4, 5, 6, 7, 8][..], &[][..]));
        for i in 0..8 {
            assert_eq!(buffer.get_relative(i), Some(&(i + 1)));
            assert_eq!(buffer.get_absolute(indices[i]), Some(&(i + 1)));
        }

        // Phase 2: Wrap around and trigger extension
        indices.clear();
        for i in 1..=4 {
            indices.push(RingBufferIndex {
                base_index: i + 3,
                wrap_offset: 0,
            });
            assert_eq!(buffer.pop_front(), Some(i));
        }

        for i in 9..=12 {
            indices.push(buffer.push_back(i));
        }
        assert!(indices[0].eq(
            &buffer,
            RingBufferIndex {
                base_index: 4,
                wrap_offset: 0
            }
        ));
        assert!(indices[3].eq(
            &buffer,
            RingBufferIndex {
                base_index: 7,
                wrap_offset: 0
            }
        ));
        assert!(indices[4].eq(
            &buffer,
            RingBufferIndex {
                base_index: 0,
                wrap_offset: 8
            }
        ));
        assert!(indices[7].eq(
            &buffer,
            RingBufferIndex {
                base_index: 3,
                wrap_offset: 8
            }
        ));
        assert_eq!(buffer.capacity, 8);
        assert_eq!(
            buffer.as_slices(),
            (&[5, 6, 7, 8][..], &[9, 10, 11, 12][..])
        );

        for i in 13..=16 {
            indices.push(buffer.push_back(i));
        }
        assert!(indices[8].eq(
            &buffer,
            RingBufferIndex {
                base_index: 12,
                wrap_offset: 0
            }
        ));
        assert!(indices[11].eq(
            &buffer,
            RingBufferIndex {
                base_index: 15,
                wrap_offset: 0
            }
        ));
        assert_eq!(buffer.capacity, 16);
        assert_eq!(
            buffer.as_slices(),
            (&[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16][..], &[][..])
        );

        for i in 0..12 {
            assert_eq!(buffer.get_relative(i), Some(&(i + 5)));
            assert_eq!(buffer.get_absolute(indices[i]), Some(&(i + 5)));
        }
    }
}