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