Atomically Moving Data Elements Between Or Within Linked Data Structures

摘要

A data element of a linked data structure is atomically moved without delaying lockless readers. A status-indicating entity is allocated, associated with the data element, and indicates validity of the data element with respect to the first linked data structure. A copy element, or a pointer thereto, is created from the data element. The status-indicating entity is associated with the copy element and indicates no validity of the copy element with respect to a second linked data structure. The copy element is linked to the second linked data structure. The status-indicating entity is atomically updated to indicate no validity of the data element with respect to the first linked data structure and validity of the copy element with respect to the second linked data structure. The data element is deleted and the status-indicating entity is disassociated from the copy element. Both structures may be deallocated in a deferred reader-friendly manner.

主权项

1. A method for atomically moving a data element of a linked data structure without delaying lockless readers that reference said data element, comprising:
allocating a status-indicating entity if one does not already exist and associating it with a data element that is linked to a first linked data structure; copying said data element, or a pointer thereto, to create a copy element that is to be linked to a second linked data structure; associating said status-indicating entity with said copy element; linking said copy element to said second linked data structure; said status-indicating entity initially indicating that said data element has validity with respect to said first linked data structure and said copy element has no validity with respect to said second linked data structure; atomically updating said status-indicating entity to indicate that said data element has no validity with respect to said first linked data structure and said copy element has validity with respect to the second linked data structure; deleting said data element from said first linked data structure and deallocating it in a deferred manner that guarantees none of said lockless readers will be referencing said data element at the time of deallocation; disassociating said status-indicating entity from said copy element, and if no longer needed, deallocating it in a deferred manner that guarantees none of said lockless readers will be referencing said status-indicating entity at the time of deallocation.