Struct atomicring::AtomicRingBuffer

pub struct AtomicRingBuffer<T: Sized> { /* fields omitted */ }

constant-size almost lock-free ring buffer

Upsides

• fast, try_push and pop are O(1)
• scales well even during heavy concurrency
• only 4 words of memory overhead
• no memory allocations after initial creation

Downsides

• growing/shrinking is not supported
• no blocking poll support
• only efficient on 64bit architectures (uses a Mutex on non-64bit architectures)
• maximum capacity of 65535 entries
• capacity is rounded up to the next power of 2

Implementation details

This implementation uses a 64 Bit atomic to store the entire state

+63----56+55----48+47------------32+31----24+23----16+15-------------0+
| w_done | w_pend |  write_index   | r_done | r_pend |   read_index   |
+--------+--------+----------------+--------+--------+----------------+

• write_index/read_index (16bit): current read/write position in the ring buffer (head and tail).
• r_pend/w_pend (8bit): number of pending concurrent read/writes
• r_done/w_done (8bit): number of completed read/writes.

For reading r_pend is incremented first, then the content of the ring buffer is read from memory. After reading is done r_done is incremented. read_index is only incremented if r_done is equal to r_pend.

For writing first w_pend is incremented, then the content of the ring buffer is updated. After writing w_done is incremented. If w_done is equal to w_pend then both are set to 0 and write_index is incremented.

In rare cases this can result in a race where multiple threads increment r_pend in turn and r_done never quite reaches r_pend. If r_pend == 255 or w_pend == 255 a spinloop waits it to be <255 to continue. This rarely happens in practice, that's why this is called almost lock-free.

Dependencies

This package has no dependencies

Usage

To use AtomicRingBuffer, add this to your Cargo.toml:

[dependencies]
atomicring = "0.2.0"

And something like this to your code

let ring = ::atomicring::AtomicRingBuffer::new(900);

assert_eq!(None, ring.try_pop());
ring.push_overwrite(1);
assert_eq!(Some(1), ring.try_pop());
assert_eq!(None, ring.try_pop());

License

Licensed under the terms of MIT license and the Apache License (Version 2.0).

See LICENSE-MIT and LICENSE-APACHE for details.

Methods

impl<T: Sized> AtomicRingBuffer<T>

pub fn new(capacity: usize) -> AtomicRingBuffer<T>

Constructs a new empty AtomicRingBuffer with the specified capacity the capacity is rounded up to the next power of 2

Examples

 // create an AtomicRingBuffer with capacity of 1024 elements
 let ring = ::atomicring::AtomicRingBuffer::new(900);

 // try_pop removes an element of the buffer and returns None if the buffer is empty
 assert_eq!(None, ring.try_pop());
 // push_overwrite adds an element to the buffer, overwriting the oldest element if the buffer is full:
 ring.push_overwrite(10);
 assert_eq!(Some(10), ring.try_pop());
 assert_eq!(None, ring.try_pop());

pub fn try_push(&self, content: T) -> Result<(), T>

Try to push an object to the atomic ring buffer. If the buffer has no capacity remaining, the pushed object will be returned to the caller as error.

pub fn push_overwrite(&self, content: T)

Pushes an object to the atomic ring buffer. If the buffer is full, another object will be popped to make room for the new object.

pub fn try_pop(&self) -> Option<T>

Pop an object from the ring buffer, returns None if the buffer is empty

pub fn size(&self) -> usize

Returns the number of objects stored in the ring buffer that are not in process of being removed.

pub fn is_empty(&self) -> bool

Returns the true if ring buffer is empty. Equivalent to self.size() - pending reads

pub fn cap(&self) -> usize

Returns the maximum capacity of the ring buffer

pub fn remaining_cap(&self) -> usize

Returns the remaining capacity of the ring buffer. This is equal to self.cap() - self.size() - pending writes + pending reads.

pub fn clear(&self)

Pop everything from ring buffer and discard it.

pub fn memory_usage(&self) -> usize

Returns the memory usage in bytes of the allocated region of the ring buffer. This does not include overhead.

Trait Implementations

impl<T: Send> Send for AtomicRingBuffer<T>

Any particular T should never accessed concurrently, so T does not need to be Sync If T is Send, AtomicRingBuffer is Send + Sync

impl<T: Send> Sync for AtomicRingBuffer<T>

impl<T> Debug for AtomicRingBuffer<T>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T> Drop for AtomicRingBuffer<T>

fn drop(&mut self)

Executes the destructor for this type.