Patent ID: 7533138
Filing Date: 2009-05-12
Classification: G06F,Y10S

Abstract:
1. A computer-implemented method for deleting a node from a doubly-linked list which is lock-free, wherein lock-free means that the doubly-linked list can be simultaneously accessed by multiple processes without requiring the processes to perform locking operations and furthermore that a finite number of steps taken by a process will guarantee progress by at least one process, the method comprising: a processor receiving a reference to a target node to be deleted from the doubly-linked list; atomically marking a forward pointer in the target node to indicate that the target node is deleted by using a CAS (Compare And Swap) instruction with only one compare-and-swap per atomic operation to change the delete bit of the target node's forward pointer cell from live to dead, wherein the forward pointer contains the address of an immediately following node in the doubly-linked list, wherein the marking operation does not destroy the address of the immediately following node; and splicing the target node out of the doubly-linked list by, atomically modifying the forward pointer of an immediately preceding node in the doubly-linked list to point to the immediately following node in the doubly-linked list, instead of pointing to the target node, by using a CAS to change the forward pointer of the immediately preceding node from the target node to the address of the immediately following node, and modifying the backward pointer of an immediately following node in the doubly-linked list to point to the immediately preceding node in the doubly-linked list, instead of pointing to the target node.