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
§Adding multiple elements at once
§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.
Method | Complexity |
---|---|
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) |
fill() , fill_with() | O(c + n) for types that implement Drop , O(n) otherwise |
fill_spare() , fill_spare_with() | O(c − n) |
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) |
Notation: n is the length of the buffer, c is the capacity of the buffer, i and j are variables.
§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 by default 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", default-features = false }
When using no_std
mode, this crate supports heap-allocation features through the alloc
crate. To enable the use of the alloc
crate, enable the alloc
feature:
[dependencies]
circular-buffer = { version = "0.1", default-features = false, features = ["alloc"] }
§Cargo feature flags
std
: enables support for thestd
library (enabled by default).alloc
: enables support for thealloc
crate (enabled by default).embedded-io
: enables implementation for theembedded_io
traits.embedded-io-async
: enables implementation for theembedded_io_async
traits.
Structs§
- Circular
Buffer - A fixed-size circular buffer.
- Drain
- A draining iterator that removes and returns elements from a
CircularBuffer
. - Into
Iter - An owning iterator over the elements of a
CircularBuffer
. - Iter
- An iterator over the elements of a
CircularBuffer
. - IterMut
- A mutable iterator over the elements of a
CircularBuffer
.