A constant-size lock-free and almost wait-free ring buffer

Upsides:

• Writes and reads should be approx. O(1) even during heavy concurrency

• No allocs

  Downsides:

• Fixed size, growing/shrinking is not supported

• No blocking wait/poll
• only efficient on 64bit architectures
• maximum capacity of 65536 entries

• capacity is

  Implementation details:

  This implementation uses a 64 Bit atomic to store the state

+--------+--------+----------------+--------+--------+----------------+ | w_done | w_pend | write_index | r_done | r_pend | read_index | +--------+--------+----------------+--------+--------+----------------+

• writeindex/readindex are 16bit indizes on the current read/write position of the ring buffer.
• rpend/wpend is the number of pending concurrent read/writes

• rdone/wdone is the 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 and rdone never quite reaches rpend. If rpend == 255 or w_pend == 255 a spinloop waits it to be <255 to continue.

  Examples

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

  asserteq!(None, ring.trypop()); ring.pushoverwrite(1); asserteq!(Some(1), ring.trypop()); asserteq!(None, ring.try_pop()); ```

Usage

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

toml [dependencies] atomicring = "0.1.0"