aempsc

A header-only lock-free multiple producer, single consumer queue library in C.

What It Offers

• Lock-free MPSC queue API.
• void * payload storage.
• Selectable backend implementation.

Stub Backend

The stub backend is the default backend.

#define AEMPSC_STUB_BACKEND

• mpsc_init(queue) init queue.
• mpsc_push(queue, payload) push payload
• mpsc_try_pop(queue, dest) pop and return immediately
• mpsc_destroy(queue) free the queue

The backend uses a stub node to handle the empty and single-item queue states. Producers push by atomically exchanging the queue tail, then linking the previous tail to the new node. The consumer owns the head pointer and pops from the linked list.

The algorithmic core provides fixed-step, wait-free enqueue, assuming pointer atomic exchange is lock-free. Dequeue is obstruction-free and may return RETRY while a producer is between exchanging the tail and linking the previous node.

Batch Backend

#define AEMPSC_BATCH_BACKEND

• mpsc_init(queue) init queue.
• mpsc_push(queue, payload) push payload
• mpsc_try_pop(queue, dest) pop and return immediately
• mpsc_destroy(queue) free the queue (if queue is empty, safe to not call this)

The backend push to a internal stack by CAS. Pop uses one exchange to steal entire stack and revert it into a queue.

Compare to stub backend, this backend's algorithm is much simpler, yet pop cost amortized O(1). And pop returns only either EMPTY or OK.

Notes

• AEMPSC_OOM_DIVERGE_HANDLER defines the behavior on OOM. Default operation is abort().