Patent ID: 7937378
Filing Date: 2011-05-03
Classification: G06F

Abstract:
1. A computer-controlled method for concurrently searching a memory containing a lock-free skiplist data structure to determine whether a sought-after key exists in said lock-free skiplist data structure, said method comprising: locating said lock-free skiplist data structure in said memory, said lock-free skiplist data structure comprising a plurality of linked lists that comprises a bottom-level linked list and one or more higher-level linked lists, said lock-free skiplist data structure further comprising a plurality of nodes each of which comprises a key field and one or more list-level reference fields, each of said plurality of nodes linked to said bottom-level linked list through said one or more list-level reference fields and ordered responsive to the value of said key field; performing a wait-free search traversal by a first execution thread for said sought-after key on said lock-free skiplist data structure while said lock-free skiplist data structure is subject to concurrent alteration of said plurality of nodes by a second execution thread, said wait-free search traversal terminating on said bottom-level linked list at a located node of said plurality of nodes, said key field of said located node containing a comparison transition key; determining whether said sought-after key equals said comparison transition key; returning a result responsive to said determining; performing a lock-free traversal of said lock-free skiplist data structure for said sought-after key by said second execution thread; and determining a node position of said located node; wherein said comparison transition key is not equal to said sought-after key, said node position including a first plurality of list-level references to one or more predecessor nodes and a second plurality of list-level references to one or more successor nodes, said first plurality of list-level references including a bottom-list-level predecessor reference to a predecessor node, said second plurality of list-level references including a bottom-list-level successor reference to a successor node, said predecessor node including a bottom-list-level reference field in said one or more list-level reference fields containing a bottom-level next reference; the method further comprising: allocating a new node, said new node including said key field, said new node identified by a new node reference; setting said key field to said sought-after key; setting each of said one or more list-level reference fields in said new node to a corresponding one of said second plurality of list-level references; and linking said new node into said bottom-level linked list by atomically: verifying that said bottom-level next reference is not marked; verifying said bottom-level next reference identifies said successor node; and setting said bottom-list-level reference field to said new node reference.