Patent ID: 7788242

Claim:
A method for inserting an object into a concurrent set in memory, the method comprising: obtaining a key associated with the object; traversing the concurrent set in memory using a first thread containing the key, wherein the first thread is executed as a first sequence of instructions on a processor; traversing the concurrent set in memory using a second thread, wherein the second thread is executed as a second sequence of instructions on the processor, and wherein the second thread executes a concurrent operation concurrently with the first thread; identifying a first insertion point while traversing the concurrent set in memory, wherein the first insertion point is before a current node and after a predecessor node; obtaining a first lock for the predecessor node after identifying the first insertion point; validating the predecessor node and the current node by: confirming, after obtaining the first lock, that the current node and the predecessor node are logical members of the concurrent set in memory by checking a marked field, and confirming that the current node is a successor of the predecessor node; inserting, while the predecessor node is locked, a new node into the concurrent set in memory after validating, wherein the new node is associated with the object; and releasing the first lock after inserting the new node.