Method and apparatus for implementing a lock-free skip list that supports concurrent accesses

摘要

One embodiment of the present invention provides a system that supports concurrent accesses to a skip list that is lock-free, which means that the skip list can be simultaneously accessed by multiple processes without requiring the processes to perform locking operations. During a node deletion operation, the system receives reference to a target node to be deleted from the skip list. The system marks a next pointer in the target node to indicate that the target node is deleted, wherein next pointer contains the address of an immediately following node in the skip list. This marking operation does not destroy the address of the immediately following node, and furthermore, the marking operation is performed atomically and thereby without interference from other processes. The system then atomically modifies the next pointer of an immediately preceding node in the skip list to point to an immediately following node in the skip list, instead of pointing to the target node, thereby splicing the target node out of the skip list.