Concurrent lock-free skiplist with wait-free contains operator
First Claim
Patent Images
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.
2 Assignments
0 Petitions
Accused Products
Abstract
Apparatus, methods, and computer program products are disclosed for performing a wait-free search of a concurrent, lock-free skiplist to determine existence of a sought-after key.
-
Citations
14 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. An apparatus having a central processing unit (CPU) and a memory coupled to said CPU, said memory containing a lock-free skiplist data structure, said apparatus comprising:
-
a locator logic configured to locate 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; a wait-free search logic configured to perform a wait-free search traversal by a first execution thread for a 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; a key comparison logic configured to determine whether said sought-after key equals said comparison transition key of said located node found by the wait-free search logic;
a result logic configured to return a result responsive to the key comparison logic;
a lock-free traversal logic configured to traverse said lock-free skiplist data structure for said sought-after key by said second execution thread; and
a node locator logic configured to determine a node position of said located node responsive to the lock-free traversal logic;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 apparatus further comprising;
a node allocation logic configured to allocate a new node, to set said key field to said sought-after key and to set 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, said new node identified by a new node reference; and
an atomic linking logic, responsive to the node allocation logic, configured to link 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. - View Dependent Claims (9, 10, 11)
-
-
12. A computer program product 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 product comprising:
-
a computer readable storage medium providing instructions that, when executed by a computer, cause said computer to perform a 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 product 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. - View Dependent Claims (13, 14)
-
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
-
Current AssigneeOracle America, Inc. (Oracle Corporation)
-
Original AssigneeOracle America, Inc. (Oracle Corporation)
-
InventorsHerlihy, Maurice P., Shavit, Nir N., Lev, Yosef
-
Primary Examiner(s)Ly; Cheyne D
-
Application NumberUS12/191,008Publication NumberTime in Patent Office993 DaysField of Search719/321, 707/704, 707/800US Class Current707/704CPC Class CodesG06F 16/90344 by using string matching te...
