Simple optimistic skiplist
Apparatus, methods, and computer program products are disclosed for concurrently searching a memory containing a skiplist data structure. The method locates the skiplist data structure in the memory. The skiplist data structure includes a plurality of linked lists related by a skiplist invariant. Furthermore, the plurality of linked lists includes a first-level linked list and one or more higher-level linked lists. The skiplist data structure also includes a plurality of nodes, each of which includes a key field, at least one pointer field, and a lock field, respectively. Each of the plurality of nodes is linked to the first-level linked list through the at least one pointer field and ordered responsive to the key field. The method performs a search operation on the skiplist data structure, while the skiplist data structure is subject to concurrent alteration of the plurality of nodes by a plurality of execution threads that are configured to maintain the skiplist invariant and returns a result of the search operation.
1. A computer-controlled method for concurrently searching a memory containing a skiplist data structure, said method comprising:
locating said skiplist data structure in said memory, said skiplist data structure comprising a plurality of linked lists related by a skiplist invariant, said plurality of linked lists including a first-level linked list and one or more higher-level linked lists, said skiplist data structure further comprising a plurality of nodes each of which comprises a key field, at least one pointer field, and a lock field respectively, each of said plurality of nodes linked to said first-level linked list through said at least one pointer field and ordered responsive to said key field;
performing a search operation for a key in said skiplist data structure while said skiplist data structure is subject to concurrent alteration of said plurality of nodes by a plurality of execution threads configured to maintain said skiplist invariant;
when the key is found in the skiplist data structure during the search operation, recording a result of the search operation that comprises:
a highest level where a node that contains the key was found in the skiplist data structure;
a list of preceding nodes that comprises an identity of a node that precedes the node on each level that comprises a node that contains the key; and
a list of succeeding nodes that comprises an identity of a node that follows the node where the key was found on each level that comprises a node that contains the key; and
returning a result of said search operation.
2. The computer-controlled method of claim 1 , wherein said search operation is characterized as being wait-free.
3. The computer-controlled method of claim 1 , wherein at least one of said plurality of nodes further comprises additional data.
4. The computer-controlled method of claim 1 , further comprising:
performing an add operation on said skiplist data structure while said skiplist data structure is subject to concurrent alteration of said plurality of nodes by a plurality of execution threads configured to maintain said skiplist invariant, a portion of said plurality of nodes representing a set of elements, said add operation configured to add a new node to said plurality of nodes, said new node added to said set of elements when linked to one of said one or more higher-level linked lists.
5. The computer-controlled method of claim 1 , further comprising:
performing an add operation on said skiplist data structure while said skiplist data structure is subject to concurrent alteration of said plurality of nodes by a plurality of execution threads configured to maintain said skiplist invariant, a portion of said plurality of nodes representing a set of elements, said add operation configured to add a new node to said plurality of nodes, said new node added to said set of elements when linked to said first-level linked list.
6. The method of claim 1 , wherein each of the plurality of nodes additionally comprises a marked flag that is used to make remove operations for the skiplist data structure appear atomic.
7. An apparatus having a central processing unit (CPU) and a memory coupled to said CPU for concurrently searching said memory containing a skiplist data structure, said apparatus comprising:
a locator logic configured to locate said skiplist data structure in said memory, said skiplist data structure comprising a plurality of linked lists related by a skiplist invariant, said plurality of linked lists including a first-level linked list and one or more higher-level linked lists, said skiplist data structure further comprising a plurality of nodes each of which comprises a key field, at least one pointer field, and a lock field respectively, each of said plurality of nodes linked to said first-level linked list through said at least one pointer field and ordered responsive to said key field;
a search logic configured to perform a search operation for a key in said skiplist data structure while said skiplist data structure is subject to concurrent alteration of said plurality of nodes by a plurality of execution threads configured to maintain said skiplist invariant;
wherein, when the key is found in the skiplist data structure during the search operation, the search logic is configured to record a result of the search operation that comprises:
a highest level where a node that contains the key was found in the skiplist data structure;
a list of preceding nodes that comprises an identity of a node that precedes the node on each level that comprises a node that contains the key; and
a list of succeeding nodes that comprises an identity of a node that follows the node where the key was found on each level that comprises a node that contains the key; and
a result logic configured to return a result of said search operation.
8. The apparatus of claim 7 , wherein said search operation is characterized as being wait-free.
9. The apparatus of claim 7 , wherein at least one of said plurality of nodes further comprises additional data.
10. The apparatus of claim 7 , further comprising:
an add logic configured to perform an add operation on said skiplist data structure while said skiplist data structure is subject to concurrent alteration of said plurality of nodes by a plurality of execution threads configured to maintain said skiplist invariant, a portion of said plurality of nodes representing a set of elements, said add operation configured to add a new node to said plurality of nodes, said new node added to said set of elements when linked to one of said one or more higher-level linked lists.
11. The apparatus of claim 7 , further comprising:
an add logic configured to perform an add operation on said skiplist data structure while said skiplist data structure is subject to concurrent alteration of said plurality of nodes by a plurality of execution threads configured to maintain said skiplist invariant, a portion of said plurality of nodes representing a set of elements, said add operation configured to add a new node to said plurality of nodes, said new node added to said set of elements when linked to said first-level linked list.
12. A non-transitory computer-usable data carrier for concurrently searching a memory containing a skiplist data structure, said product comprising:
a computer-usable data carrier providing instructions that, when executed by a computer, cause said computer to perform a method comprising:
locating said skiplist data structure in said memory, said skiplist data structure comprising a plurality of linked lists related by a skiplist invariant, said plurality of linked lists including a first-level linked list and one or more higher-level linked lists, said skiplist data structure further comprising a plurality of nodes each of which comprises a key field, at least one pointer field, and a lock field respectively, each of said plurality of nodes linked to said first-level linked list through said at least one pointer field and ordered responsive to said key field;
performing a search operation for a key in said skiplist data structure while said skiplist data structure is subject to concurrent alteration of said plurality of nodes by a plurality of execution threads configured to maintain said skiplist invariant;
when the key is found in the skiplist data structure during the search operation, recording a result of the search operation that comprises:
a highest level where a node that contains the key was found in the skiplist data structure;
a list of preceding nodes that comprises an identity of a node that precedes the node on each level that comprises a node that contains the key; and
a list of succeeding nodes that comprises an identity of a node that follows the node where the key was found on each level that comprises a node that contains the key; and
returning a result of said search operation.
13. The computer-usable data carrier of claim 12 , wherein said search operation is characterized as being wait-free.
14. The computer-usable data carrier of claim 12 , wherein at least one of said plurality of nodes further comprises additional data.
15. The computer-usable data carrier of claim 12 , further comprising:
performing an add operation on said skiplist data structure while said skiplist data structure is subject to concurrent alteration of said plurality of nodes by a plurality of execution threads configured to maintain said skiplist invariant, a portion of said plurality of nodes representing a set of elements, said add operation configured to add a new node to said plurality of nodes, said new node added to said set of elements when linked to one of said one or more higher-level linked lists.
16. The computer-usable data carrier of claim 12 , further comprising:
performing an add operation on said skiplist data structure while said skiplist data structure is subject to concurrent alteration of said plurality of nodes by a plurality of execution threads configured to maintain said skiplist invariant, a portion of said plurality of nodes representing a set of elements, said add operation configured to add a new node to said plurality of nodes, said new node added to said set of elements when linked to said first-level linked list.