2 releases

0.0.2 Apr 6, 2023
0.0.1 Apr 3, 2023

#2210 in Data structures

MIT license

59KB
956 lines

Bufferring: Ring buffers for Rust

A ring buffer is a fixed-size queue of items, where new items replace older ones when a fixed limit (the buffer's capacity) is hit. This crate provides a safe interface for ring buffers, along with some implementations of this interface.

WARNING: This crate is not ready for use. It contains a significant amount of unsafe code, and the majority of it is currently untested.

Usage

The RingBuffer trait is the core of this crate; it represents a type that can be used like a ring buffer. An implementor of this trait, MaskingBuffer, provides ring buffers with power-of-two sizes. MaskingBuffer relies upon an implementor of Storage to actually hold the buffer data; currently, there are two options (ArrayStorage for compile-time sizes, and HeapStorage for dynamic allocation).

use core::num::NonZeroUsize;
use bufferring::{
    RingBuffer, MaskingBuffer,
    storage::{Storage, HeapStorage},
};

// Create a masking-based ring buffer using heap-allocated storage.
let capacity = NonZeroUsize::new(8).unwrap();
let storage = HeapStorage::with_capacity(capacity);
let mut buffer = MaskingBuffer::new(storage).unwrap();

// Push some elements into the buffer.
for item in 0 .. 14 {
    // Drop removed items immediately.
    let _ = buffer.enqueue(item);
}

// See what elements are in the buffer.
println!("{:?}", buffer);
assert!(buffer.is_full());
assert!(buffer.iter().copied().eq(6 .. 14));

// Remove those elements from the buffer.
for item in 6 .. 14 {
    assert_eq!(buffer.dequeue(), Some(item));
}
assert!(buffer.is_empty());

Features

  • alloc (enabled by default): use the alloc crate for dynamic allocation. This enables the HeapStorage type, so that ring buffers can store their data on the heap.

  • proptest (disabled by default): expose generators (Strategy functions) for ring buffers and ring buffer inputs, using the proptest crate. This is used for property-based testing (and must be enabled to run bufferring tests).

Testing

To run tests:

cargo test --all-features

This crate tests its code using property-based testing, à la proptest. When the proptest feature is enabled (required for testing), functions are exposed for randomly generating ring buffers (and ring buffer inputs), so that crates depending upon bufferring can easily perform property-based testing as well.

Dependencies

With all features disabled, bufferring does not have any dependencies beyond core; it can be used in no_std environments.

  • With the alloc feature (enabled by default), the alloc crate (which is a subset of std) is used.

  • With the proptest feature (disabled by default), the proptest crate and a utility bit-vec crate (already depended upon by proptest) are used.

License

Copyright (c) 2023 The Depressed Milkman

bufferring is under the MIT license. See the LICENSE file for a full text.

Origin

This crate is heavily inspired by ringbuffer; attempts were made to port some of the changes over, but the core RingBuffer traits these crates expose are incompatibly different, and this crate introduces a new Storage interface that simplifies the primary ring-buffer code.

Dependencies

~0–1MB
~19K SLoC