Unbounded, single producer, single consumer queue idea

Chatting with a friend online about queue use and an idea struct me.

There is a well known bounded single producer single consumer queue. The Linux kernel uses it, there’s an implementation in liblfds.

I think thought it should be possible to make an unbounded single producer single consumer queue.

What’s odd about it is that the writer thread is the thread which is responsible for removing dequeued elements from the queue.

So we have a normal looking queue, elements with next pointers, an enqueue and a dequeue pointer.

The reader thread, once it’s done with an element, marks the element as read – it is however the only write to that flag. The writer is the only reader from that flag.

So we imagine the queue is empty, enqueue and dequeue both NULL. Writer writes; he is given an element (no memory allocations, remember), he sets the user data, sets next to NULL, store barrier, modifies the dequeue pointer.

Reader thread later comes to read, we assume the writes have propogated (we’ll see the user data first, so we’re safe), we read the dequeue pointer, get the element, get the user data, now set the “done with it” flag.

The writer when he nexts writes adds the element as before, but also scans from the dequeue pointer, finding dequeued elements and unlinking them.

Have to work through all the details to see if it can work.