M&S Queue

A Michael-Scott lock-free queue with support for blocking pops. Usable with any number of producers and consumers.

The queue is implemented as a singly linked list, with pointers to the head and tail. The following technique is used to manage both of them without double CAS: the queue is never empty (head/tail are never checked for equality with nullptr). To provide physical (but not logical) nonemptiness, a dummy node is added in the constructor of the queue, which is both head and tail.

Tagged pointers are used to deal with the ABA problem.