×

Shared synchronized skip-list data structure and technique employing linearizable operations

  • US 7,424,477 B1
  • Filed: 09/03/2003
  • Issued: 09/09/2008
  • Est. Priority Date: 09/03/2003
  • Status: Active Grant
First Claim
Patent Images

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, andwherein the delete-type operation performs a synchronized update of pointers beginning at a Kth level thereof and continuing downward to the first level.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×