Crate circular_buffer 

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

A circular buffer is a 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 dropped and overwritten.

The main structs are CircularBuffer, FixedCircularBuffer, and HeapCircularBuffer. You can think of them as conceptually similar to slice, array, and Vec respectively:

• A CircularBuffer provides a reference to either a FixedCircularBuffer or a HeapCircularBuffer. It can be used to get/add/remove elements.
• A FixedCircularBuffer is an owned fixed-capacity buffer that can live on the stack or can be constructed in const contexts.
• A HeapCircularBuffer is an owned buffer that is heap-allocated and its capacity can be adjusted at runtime.

CircularBuffer and FixedCircularBuffer can be used in a no_std environment. HeapCircularBuffer requires either the std library or the alloc crate.

Examples

use circular_buffer::FixedCircularBuffer;

// Initialize a new, empty circular buffer with a capacity of 5 elements
let mut buf = FixedCircularBuffer::<u32, 5>::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 to 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

• push_back(), push_front()
• pop_back(), pop_front()
• swap_remove_back(), swap_remove_front()

Getting/mutating elements

• get(), get_mut()
• front(), front_mut()
• back(), back_mut()
• nth_front(), nth_front_mut()
• nth_back(), nth_back_mut()

Adding multiple elements at once

• extend(), extend_from_slice()
• fill(), fill_with()
• fill_spare(), fill_spare_with()

Iterators

• into_iter()
• iter(), iter_mut()
• range(), range_mut()
• drain()

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 will consume elements from the buffer.

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

let mut buf = FixedCircularBuffer::<u8, 5>::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"");

For no_std environments, this crate provides optional integration with the embedded_io and embedded_io_async crates.

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 dropped 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(c) otherwise
fill_spare(), fill_spare_with()	O(c − n)
get(), front(), back(), nth_front(), nth_back()	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 FixedCircularBuffer struct is compact and has a fixed size specified at compile time, 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::FixedCircularBuffer;

let mut buf = FixedCircularBuffer::<u32, 4096>::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);

For buffers whose capacity is not known at compile time, HeapCircularBuffer is the solution:

use circular_buffer::HeapCircularBuffer;

let mut buf = HeapCircularBuffer::<char>::with_capacity(3);
buf.push_back('a');
buf.push_back('b');
buf.push_back('c');
buf.push_back('d');
assert_eq!(buf, ['b', 'c', 'd']);

buf.resize(5);
buf.push_back('e');
buf.push_back('f');
buf.push_back('g');
assert_eq!(buf, ['c', 'd', 'e', 'f', 'g']);

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 = "2", 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 = "2", default-features = false, features = ["alloc"] }

Cargo feature flags

• std: enables support for the std library (enabled by default).
• alloc: enables support for the alloc crate (enabled by default).
• embedded-io: enables implementation of the embedded_io traits.
• embedded-io-async: enables implementation of the embedded_io_async traits.

Re-exports

pub use crate::fixed::FixedCircularBuffer;

pub use crate::heap::HeapCircularBuffer;

Modules

fixed

Fixed-size circular buffer.

heap

Heap-allocated, variable-size circular buffer.

Structs

CircularBuffer

A reference to a circular buffer.

Drain

A draining iterator that removes and returns elements from a CircularBuffer.

Iter

An iterator over the elements of a CircularBuffer.

IterMut

A mutable iterator over the elements of a CircularBuffer.