Multiple non-blocking FIFO queues are concurrently maintained using atomic
compare-and-swap (CAS) operations. In accordance with the invention, each queue
provides direct access to the nodes stored therein to an application or thread,
so that each thread may enqueue and dequeue nodes that it may choose. The prior
art merely provided access to the values stored in the node. In order to avoid
anomalies, the queue is never allowed to become empty by requiring the presence
of at least a dummy node in the queue. The ABA problem is solved by requiring that
the next pointer of the tail node in each queue point to a "magic number" unique
to the particular queue, such as the pointer to the queue head or the address of
the queue head, for example. This obviates any need to maintain a separate count
for each node.
