Crate circular_buffer

source ·
Expand description

This crate implements a circular buffer, also known as cyclic buffer, circular queue or ring.

The main struct is CircularBuffer. It can live on the stack and does not require any heap memory allocation. A CircularBuffer is sequence of elements with a maximum capacity: elements can be added to the buffer, and once the maximum capacity is reached, the elements at the start of the buffer are discarded and overwritten.

Examples

use circular_buffer::CircularBuffer;

// Initialize a new, empty circular buffer with a capacity of 5 elements
let mut buf = CircularBuffer::<5, u32>::new();

// Add a few elements
buf.push_back(1);
buf.push_back(2);
buf.push_back(3);
assert_eq!(buf, [1, 2, 3]);

// Add more elements to fill the buffer capacity completely
buf.push_back(4);
buf.push_back(5);
assert_eq!(buf, [1, 2, 3, 4, 5]);

// Adding more elements than the buffer can contain causes the front elements to be
// automatically dropped
buf.push_back(6);
assert_eq!(buf, [2, 3, 4, 5, 6]); // `1` got dropped to make room for `6`

Interface

CircularBuffer provides methods akin the ones for the standard VecDeque and LinkedList. The list below includes the most common methods, but see the CircularBuffer struct documentation to see more.

Adding/removing elements

Getting/mutating elements

Iterators

Writing/reading bytes

For the special case of a CircularBuffer containing u8 elements, bytes can be written and read using the standard Write and Read traits. Writing past the buffer capacity will overwrite the bytes at the start of the buffer, and reading elements will consume elements from the buffer.

use circular_buffer::CircularBuffer;
use std::io::Read;
use std::io::Write;

let mut buf = CircularBuffer::<5, u8>::new();
assert_eq!(buf, b"");

write!(buf, "hello");
assert_eq!(buf, b"hello");

write!(buf, "this string will overflow the buffer and wrap around");
assert_eq!(buf, b"round");

let mut s = String::new();
buf.read_to_string(&mut s).expect("failed to read from buffer");
assert_eq!(s, "round");
assert_eq!(buf, b"");

Time complexity

Most of the methods implemented by CircularBuffer run in constant time. Some of the methods may run in linear time if the type of the elements implements Drop, as each element needs to be deallocated one-by-one.

MethodComplexity
push_back(), push_front()O(1)
pop_back(), pop_front()O(1)
remove(i)O(n − i)
truncate_back(i), truncate_front(i)O(n − i) for types that implement Drop, O(1) otherwise
clear()O(n) for types that implement Drop, O(1) otherwise
drain(i..j)O(n − j)
front(), back(), get()O(1)
swap(), swap_remove_front(), swap_remove_back()O(1)
as_slices(), as_mut_slices()O(1)
len(), capacity()O(1)

Stack vs heap

The CircularBuffer struct is compact and has a fixed size, so it may live on the stack. This can provide optimal performance for small buffers as memory allocation can be avoided.

For large buffers, or for buffers that need to be passed around often, it can be useful to allocate the buffer on the heap. Use a Box for that:

use circular_buffer::CircularBuffer;

let mut buf = CircularBuffer::<4096, u32>::boxed();
assert_eq!(buf.len(), 0);

for i in 0..1024 {
    buf.push_back(i);
}
assert_eq!(buf.len(), 1024);

buf.truncate_back(128);
assert_eq!(buf.len(), 128);

no_std

This crate can be used in a no_std environment, although the I/O features and heap-allocation features won’t be available in no_std mode. By default, this crate uses std; to use this crate in no_std mode, disable the default features for this crate in your Cargo.toml:

[dependencies]
circular-buffer = { version = "0.1", features = [] }

Structs