Expand description
This crate is an implementation of “A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue”_ by Ruslan Nikolaev (arXiV/1908.04511).
It supports #![no_std]
and std
. std
gives you access to the rings backed by an allocated buffer.
§Example
use lfqueue::ConstBoundedQueue;
// We want a queue of size 2, so we make a constant queue
// with the generic set to 2 ^ 2 = 4.
let queue = ConstBoundedQueue::<usize, 4>::new_const();
// Let us add a few values.
assert!(queue.enqueue(1).is_ok());
assert!(queue.enqueue(2).is_ok());
// Let us verify the correctnes by dequeing these values.
assert_eq!(queue.dequeue(), Some(1));
assert_eq!(queue.dequeue(), Some(2));
assert_eq!(queue.dequeue(), None);
§Design
§SCQ Rings
Each data structure fundamentally relies on the SCQ ring described in the ACM paper. The ring is a MPMC queue for indices. The size must be a power of two, hence why on initialization we must pass an order instead of a capacity directly.
§Bounded Queue
The bounded queue is the SCQ queue from the ACM paper. It works by maintaining two rings:
- Free Ring: This ring contains all the available indexes that we can slot a value into.
- Allocation Ring: This ring contains all the indexes that are currently allocated. The correctness of the various methods relies
Macros§
- const_
queue - Creates a ConstBoundedQueue. This function exists mostly to creates queues of the correct size easily. For instance, to create a queue that can hold 2 values, the bound needs to be four. This macro assists with that by generating an initialization that takes this into account.
Structs§
- Bounded
Queue - The bounded queue type from the ACM paper. This uses two SCQ rings internally, one that keeps track of free indices and the other that keeps track of the allocated indices.
- Single
Size - A queue that has a capacity of 1.
- Unbounded
Enqueue Handle - A enqueue handle to an UnboundedQueue, allowing for bulk enqueues efficiently. Internally, the unbounded queue manages the queue of bounded queues with hazard pointers to avoid the ABA problem, this allows minimizing the creation of these hazard pointers.
- Unbounded
Full Handle - A full handle to an UnboundedQueue, allowing for bulk enqueues efficiently. Internally, the unbounded queue manages the queue of bounded queues with hazard pointers to avoid the ABA problem, this allows minimizing the creation of these hazard pointers.
- Unbounded
Queue - An unbounded lock-free queue. This is the LCSQ from the ACM paper, “A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue” by Ruslan Nikolaev.
Enums§
Type Aliases§
- Alloc
Bounded Queue - A bounded SCQ queue backed by an allocated array.
- Const
Bounded Queue - A constant generic constant bounded queue, this implements the SCQ from the ACM paper, “A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue” by Ruslan Nikolaev.