Patent ID: 7424477
Filing Date: 2008-09-09
Classification: G06F,Y10S

Abstract:
1. A method of operating on a shared data structure that includes a representation of an ordered set of keys, the method comprising: instantiating nodes of the shared data structure in memory, wherein plural levels of same direction referencing chains traverse respective subsets of the nodes in accordance with a key ordering relationship thereof, a first-level of the referencing chains traversing each node of the shared data structure and at least one other level of the referencing chains traversing less than all nodes of the shared data structure; and operating on the shared data structure using insert-type and delete-type operations that are linearizable and lock-free for all concurrent executions thereof, wherein the insert-type operation performs a synchronized update of pointers beginning at the first level thereof and continuing upward, and wherein the delete-type operation performs a synchronized update of pointers beginning at a K