Patent ID: 7583687

Claim:
A method for popping a value from a lock-free free double-ended queue (deque), the method comprising: receiving a command to pop a value from a selected end of the deque, wherein the deque is implemented as a doubly-linked list of nodes formed into a ring, so that node pointers in one direction form an inner ring, and node pointers in the other direction form an outer ring, and wherein the deque has an inner hat, which points to a node next to the last occupied node along the inner ring, wherein the deque has an outer hat, which points to a node next to the last occupied node along the outer ring; and in response to the command, attempting to perform a double compare-and-swap (DCAS) operation; wherein the DCAS operation predicts that the hat for the selected end of the deque remains unchanged and that the value in a node-to-be-popped located in a closest node to the hat in a popping direction remains unchanged, is not null and is not a special value; and wherein if this DCAS operation succeeds, the value is returned, the corresponding value field in the node-to-be-popped is set to null, and the hat is updated to point to the node that was popped from.