Patent ID: 7536428

Claim:
A method for providing concurrent read and write access to a linked list of elements for execution on a computing device comprising a processor and a memory, the method comprising: storing in the memory of the computing device a linked list, the linked list including three internal lists and at least an updated indicator, wherein each element in the linked list includes at least a first link of a plurality of first links, a second link of a plurality of second links, and a third link of a plurality of third links, and a first internal list of the three internal lists comprises elements of the elements of the linked list referenced by the plurality of first links, a second internal list of the three internal lists comprises elements of the elements of the linked list referenced by the plurality of second links, and a third internal list of the three internal lists comprises elements of the elements of the linked list referenced by the plurality of third links; providing read access to the linked list to a reader process such that the reader process reads elements in the linked list via a read list of the three internal lists, wherein the read list comprises the first internal list; providing write access to the linked list to a writer process such that the writer process updates the linked list via a write list of the three internal lists, wherein the write list comprises the third internal list; when the writer process updates the linked list by swapping an updated version of the linked list with the second internal list, setting at least the updated indicator, wherein the updated version of the linked list includes updates to the elements of the linked list provided by the writer process; deferring updating of the read list to include the updated version of the linked list until the read process is completed, wherein the second internal list is swapped with the read list when the reader process is completed and at least the updated indicator is set, wherein the read access by the reader process and the write access by the writer process occur substantially concurrently; and receiving an update instruction from the writer process to further update the linked list according to the update instruction, wherein the writer process updates the linked list by swapping a second updated version of the linked list with the second internal list comprising the updated version of the linked list, and wherein receiving the update instruction from the writer process to update the linked list comprises: determining whether the updated indicator is set, wherein the set updated indicator indicates that the second internal list is updated and ready for swapping with the read list; and when it is determined that the updated indicator is set and the read process is completed, atomically swapping the read list and the second internal list.