Skip to content

Instantly share code, notes, and snippets.

@DaTa-
Created Sep 16, 2020
Embed
What would you like to do?
use std::{alloc, alloc::Layout, convert::TryInto, ptr, ptr::NonNull};
pub struct CircularBuffer<T> {
// no need for PhantomData since NonNull is covariant over T
buffer: NonNull<T>,
offset: isize,
len: isize,
capacity: isize,
}
struct DropGuard<F: FnOnce()>(Option<F>);
impl<F: FnOnce()> DropGuard<F> {
fn new(f: F) -> Self {
Self(Some(f))
}
}
impl<F: FnOnce()> Drop for DropGuard<F> {
fn drop(&mut self) {
self.0.take().map(|f| f());
}
}
impl<T> Drop for CircularBuffer<T> {
fn drop(&mut self) {
unsafe {
let _dealloc_even_if_unwind = {
let buffer = self.buffer.as_ptr();
let capacity = self.capacity;
DropGuard::new(move || {
let layout = Layout::array::<T>(capacity as _)
.expect("Layout was validated during initialization");
if layout.size() != 0 {
alloc::dealloc(buffer as _, layout);
}
})
};
// may panic
self.clear();
}
}
}
unsafe impl<T: Send> Send for CircularBuffer<T> {}
unsafe impl<T: Sync> Sync for CircularBuffer<T> {}
#[derive(Debug, PartialEq)]
pub enum Error {
EmptyBuffer,
FullBuffer,
}
impl<T> CircularBuffer<T> {
pub fn new(capacity: usize) -> Self {
#[cold]
fn capacity_overflow<E: std::fmt::Display, NoReturn>(e: E) -> NoReturn {
panic!("Capacity overflow: {}", e);
}
// we can't offset beyond isize::MAX
let capacity: isize = capacity.try_into().unwrap_or_else(capacity_overflow);
let layout = Layout::array::<T>(capacity as _).unwrap_or_else(capacity_overflow);
let buffer = unsafe {
if layout.size() != 0 {
let ptr = alloc::alloc(layout);
if ptr.is_null() {
alloc::handle_alloc_error(layout);
}
NonNull::new_unchecked(ptr as _)
} else {
NonNull::dangling()
}
};
Self {
buffer,
offset: 0,
len: 0,
capacity,
}
}
pub fn write(&mut self, element: T) -> Result<(), Error> {
if self.len != self.capacity {
unsafe {
let tail_len = self.capacity - self.offset;
let cell = if self.len < tail_len {
self.buffer.as_ptr().offset(self.offset).offset(self.len)
} else {
self.buffer.as_ptr().offset(self.len - tail_len)
};
ptr::write(cell, element);
self.len += 1;
}
Ok(())
} else {
Err(Error::FullBuffer)
}
}
pub fn read(&mut self) -> Result<T, Error> {
if self.len != 0 {
let result = unsafe {
let result = ptr::read(self.buffer.as_ptr().offset(self.offset));
self.offset = (self.offset + 1) % self.capacity;
self.len -= 1;
result
};
Ok(result)
} else {
Err(Error::EmptyBuffer)
}
}
pub fn clear(&mut self) {
let tail_len = (self.capacity - self.offset).min(self.len);
let head_len = self.len - tail_len;
// in case of panic unwind do so before dropping
self.offset = 0;
self.len = 0;
unsafe {
let _drop_tail = DropGuard::new(|| {
let tail_offset = self.buffer.as_ptr().offset(self.capacity - tail_len);
let tail = ptr::slice_from_raw_parts_mut(tail_offset, tail_len as _);
// may panic
ptr::drop_in_place(tail);
});
let head = ptr::slice_from_raw_parts_mut(self.buffer.as_ptr(), head_len as _);
// may panic
ptr::drop_in_place(head);
}
}
/// panics if capacity is 0
pub fn overwrite(&mut self, element: T) {
#[cold]
if self.capacity == 0 {
panic!("Can't overwrite elements of circular buffer with 0 capacity");
}
if self.len == self.capacity {
unsafe {
let old_offset = self.offset;
let _write_even_if_unwind = {
let buffer = self.buffer.as_ptr();
DropGuard::new(move || {
ptr::write(buffer.offset(old_offset), element);
})
};
self.offset = (old_offset + 1) % self.capacity;
// may panic
ptr::drop_in_place(self.buffer.as_ptr().offset(old_offset));
}
} else {
self.write(element).expect("Empty space was checked before")
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment