Patent ID: 8375062

Claim:
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.