Patent ID: 7962923

Claim:
A method of supporting condition synchronization for a shared data structure so as to provide concurrent access, the method comprising: providing a linked list of nodes representing the data structure and having corresponding addresses, including a head pointer pointing to a first node in a list and a tail pointer pointing to a last node in the list, and all nodes therebetween pointing to their next successive node, respectively, the data structure having add and remove operations that are defined depending on a state of the data structure; setting, by a request thread, a requestor_id field of a dummy node in the list with a value that identifies the request thread, setting a request field to true, and setting a next field to an address associated with a new node in the list, so as to transform the dummy node to a request node and alert a fulfilling thread to signal the request thread; setting, by the fulfilling thread, a request_value field of the request node with an address of a data node using a Compare-and-Swap (CAS) instruction; signaling the request thread of the dummy node that the request_value field of the request node has been set, wherein the request thread is identified for signaling using the requestor_id field; and retrieving the value of the data node pointed to by the request_value field of the request node.