Method and system for implementing a concurrent set of objects

1. 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.

2. The method of claim 1 , wherein the concurrent operation executed by the second thread is a membership test operation.

3. The method of claim 1 , wherein traversing the concurrent set in memory comprises:

following a pointer variable from a head node of the concurrent set in memory.

4. The method of claim 1 , wherein the first thread obtains a second lock for the current node.

5. The method of claim 1 , further comprising:

pre-validating the predecessor node and the current node prior to obtaining the first lock.

6. The method of claim 1 , wherein at least a part of the concurrent set in memory is traversed by the first thread while not locked by the first thread.

7. The method of claim 1 , wherein the concurrent set in memory uses a list.

8. A method for removing an object from 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 on a processor as a first sequence of instructions;

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 node in the concurrent set in memory associated with the object while traversing;

obtaining a first lock for the node;

obtaining a second lock for a predecessor of the node;

validating the node and the predecessor of the node by:

confirming, after obtaining the first and second lock, that the node and the predecessor of the node are logical members of the concurrent set in memory by checking a marked field, and

confirming that the node is a successor of the predecessor of the node;

logically removing the node from the concurrent set in memory after validating;

physically removing the node from the concurrent set in memory after logically removing the node; and

releasing the first lock and the second lock after physically removing the node.

9. The method of claim 8 , wherein logically removing the node comprises:

changing a field of the node.

10. The method of claim 8 , wherein logically removing the node comprises:

changing a pointer variable of the node.

11. The method of claim 8 , wherein physically removing the node comprises:

changing a pointer variable of the predecessor of the node.

12. The method of claim 8 , further comprising:

pre-validating the node and the predecessor of the node prior to obtaining the first lock.

13. The method of claim 8 , wherein the concurrent set in memory uses a list.

14. The method of claim 8 , wherein at least a part of the concurrent set in memory is traversed by the first thread while not locked by the first thread.

15. A method for testing the membership of an object in 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 on a processor as a first sequence of instructions;

traversing the concurrent set in memory using a second thread to execute a concurrent operation using locks, wherein the second thread is executed as a second sequence of instructions on the processor;

comparing a first field of a node in the concurrent set in memory with the key;

confirming that the node belongs to the concurrent set in memory; and

generating a response based on the comparison indicating the membership status of the object and confirmation that the node belongs in the concurrent set in memory.

16. The method of claim 15 , wherein the concurrent set in memory uses a list.

17. The method of claim 15 , wherein at least a part of the concurrent set in memory is traversed by the first thread while not locked by the first thread.

18. The method of claim 15 , wherein the concurrent operation executed by the second thread is an insert operation.