Patent ID: 8412691

Claim:
A method comprising: a first of a plurality of readers of a linked list performing an operation to attempt to read a first element of the linked list, the operation comprising, atomically reading, by at least one processor, a next field of a current element of the linked list to determine a first value, wherein the first value encodes a first pointer to the first element and a first indication of an owner of the first element; decoding the first value to determine the first pointer and the owner; storing the first indication of the owner in a first field of a first of a plurality of multi-field reservation data structures, wherein the first multi-field reservation data structure corresponds to the first reader, wherein a current indication of an owner of the current element is stored in a second field of the first multi-field reservation data structure; rereading the next field of the current element of the linked list; determining whether the next field of the current element in the linked list equals the first indication of the owner stored in the first field of the first multi-field reservation data structure; reading the first element of the linked list via the first pointer if the next field of the current element that was reread from the linked list equals the first indication of the owner stored in the first field of the first multi-field reservation data structure; and if the next field of the current element that was reread from linked list does not equal the first indication of the owner stored in the first field of the first multi-field reservation data structure, removing the first indication of the owner from the first multi-field reservation data structure; and repeating said atomically reading, decoding, storing and determining again for the next field of the current element.