pub struct LockFreeQueue<T> { /* private fields */ }Expand description
A bounded, genuinely lock-free multi-producer multi-consumer queue.
This is an array-based MPMC queue using per-slot sequence numbers (the Vyukov algorithm). Producers and consumers operate through independent atomic head/tail cursors and never acquire a mutex or spinlock. The sequence-number protocol eliminates the ABA problem without tagged pointers or epoch-based reclamation: slots are reused in place, so no node allocation or deallocation occurs during enqueue/dequeue.
§Capacity
The queue is bounded. LockFreeQueue::new creates a queue with
DEFAULT_QUEUE_CAPACITY usable slots. LockFreeQueue::with_capacity
accepts any request of one slot or more: the ring is sized to the next power
of two at least two, while capacity keeps
reporting the request, so a non-power-of-two capacity bounds the queue
exactly and only the ring’s unused tail is wasted. When the queue is full,
enqueue retries with exponential backoff (preserving the
unblocked-sender contract of the previous API), while try_enqueue
returns Err(item) for callers that prefer explicit backpressure. Full
means capacity items queued: a slot a dequeue has emptied but not yet
reopened is waited for, never reported as fullness.
§Memory safety
Each slot’s MaybeUninit<T> is written by the producer — the only writer,
between sequence == pos and sequence == pos + 1 — and moved out by the
consumer, which is the only reader, between sequence == pos + 1 and
sequence == pos + ring_len. The sequence-number protocol therefore
guarantees that only one thread ever touches a slot’s payload.
Implementations§
Source§impl<T> LockFreeQueue<T>
impl<T> LockFreeQueue<T>
Sourcepub fn with_capacity(capacity: usize) -> Self
pub fn with_capacity(capacity: usize) -> Self
Create a new queue holding up to capacity items.
The ring is the next power of two at least two, which the sequence protocol needs to tell a slot’s empty generation from its full one; a one-slot request therefore gets a two-slot ring and still bounds the queue at one item.
Sourcepub fn try_enqueue(&self, item: T) -> Result<(), T>
pub fn try_enqueue(&self, item: T) -> Result<(), T>
Try to enqueue an item without waiting for space.
Returns Ok(()) if the item was enqueued, or Err(item) if the queue
holds capacity items. It takes no lock.
When the queue has room but the item’s slot still belongs to a dequeue
that has moved its item out and not yet reopened the slot, it waits for
that reopening instead of reporting a full queue; the wait is one store
unless the dequeuing thread was preempted.
Sourcepub fn enqueue(&self, item: T)
pub fn enqueue(&self, item: T)
Enqueue an item, retrying with exponential backoff if the queue is full.
This preserves the unblocked-sender contract of the previous API: the
call always eventually succeeds (assuming consumers make progress).
The backoff path uses core::hint::spin_loop and, on std targets,
std::thread::yield_now after heavy contention, but never acquires a
global lock, so multiple producers can enqueue concurrently.
Sourcepub fn try_dequeue(&self) -> Option<T>
pub fn try_dequeue(&self) -> Option<T>
Try to dequeue an item from the front of the queue.
Returns None if the queue is empty.
This is the lock-free fast path: no spinlock, no mutex.
Sourcepub fn is_empty(&self) -> bool
pub fn is_empty(&self) -> bool
Check if the queue is empty.
This is a best-effort check: the queue may have items added or removed between this call and the next operation. It is safe to call concurrently with enqueue/dequeue.
Sourcepub fn is_full(&self) -> bool
pub fn is_full(&self) -> bool
Check if the queue holds capacity items.
Best-effort in the same sense as is_empty.