Based on https://github.com/grivet/mpsc-queue

intrusive_mpsc_queue.d

module intrusive_mpsc_queue;

import core.atomic;

// An intrusive MPSC queue in D.
struct IntrusiveQueue(T)
{
    private T* head;
    private T* tail;
    private T stub;

    // Initialize the queue
    void init()
    {
        head = &stub;
        tail = &stub;
        stub.next = null;
    }

    // Push an item onto the queue
    void push(T* item)
    {
        T* prev = atomicLoad(head);
        atomicStore(head, item);
        atomicStore(prev.next, item);
    }

    // Pop an item from the queue
    T* pop()
    {
        T* tail = atomicLoad(this.head);
        auto next = atomicLoad(tail.next);

        if (tail is &stub)
        {
            next = next ? next : null;
            atomicStore(this.tail, next);
            tail = next;
            next = atomicLoad(tail.next);
        }

        if (next)
        {
            atomicStore(this.tail, next);
            tail.next = null;
            return tail;
        }

        auto head = atomicLoad(this.head);
        if (tail != head)
            return null;

        push(&stub);

        next = atomicLoad(tail.next);
        if (next)
        {
            atomicStore(this.tail, next);
            tail.next = null;
            return tail;
        }

        return null;
    }
}

unittest
{
    struct Elem
    {
        Elem* next;
    }

    Elem[10] elems;
    auto queue = IntrusiveQueue!Elem();
    queue.init();

    // One element
    assert(queue.pop() is null);
    queue.push(&elems[0]);
    assert(queue.pop() == &elems[0]);
    assert(queue.pop() is null);

    // Two elements
    assert(queue.pop() is null);
    queue.push(&elems[0]);
    queue.push(&elems[1]);
    assert(queue.pop() == &elems[0]);
    assert(queue.pop() == &elems[1]);
    assert(queue.pop() is null);
}

⚠️ Not working - WiP

• dlang/dmd#15816