Cirque
is a FIFO queue with generics backed by a circular list (Ring
from container/ring
) that enables
independent reads and writes.
Independent reads and writes are achieved by holding two separate pointers (heads) to that list, one for reading and one for writing, which follow this set of rules:
- Both heads are initialized at the same point.
- The writer head does not write if it is next to the reader head.
- The reader head does not read if it's on the same place as the writer head.
The procedure for writing is:
- The writer head checks if reader head is next to it.
- If it isn't, there is free space, so it continues.
- If it is, the queue is full, so read lock is requested and the list is resized.
- Data is written in the current position.
- The writer head moves forward by 1 position.
The procedure for reading is:
- Gain read lock.
- The reader head checks if it's on the same position with the writer head. If it is, no data is available to read, so it returns.
- Data is read from the current position.
- The reader head moves forward by 1 position.
Concurrent reads are policed with a mutex lock. As long as list capacity is sufficient, a single writer can operate lock-free without disturbing reads. However, no reads can be made while the list is being resized.