AtomicRingBuffer

A 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

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

• writeindex/readindex (16bit): current read/write position in the ring buffer (head and tail).
• rpend/wpend (8bit): number of pending concurrent read/writes

• rdone/wdone (8bit): number of completed read/writes.

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

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

  In rare cases this can result in a race where multiple threads increment rpend in turn and rdone never quite reaches rpend. If rpend == 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:

toml [dependencies] atomicring = "0.2.0"

And something like this to your code

```rust

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

// trypop removes an element of the buffer and returns None if the buffer is empty asserteq!(None, ring.trypop()); // pushoverwrite adds an element to the buffer, overwriting the oldest element if the buffer is full: ring.pushoverwrite(1); asserteq!(Some(1), ring.trypop()); asserteq!(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.