Method and apparatus for performing lock-free updates in a linked list
US8768889B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Apr 7, 2004 |
| Grant date | Jul 1, 2014 |
| Priority date | — |
| Expiry date | Jul 17, 2029 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2205/123
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
One embodiment of the present invention provides a system that performs a lock-free update to one or more fields in an existing node in a linked list. To perform the update, the system first obtains a new node to be added to the linked list, wherein other processes do not possess references to the new node and therefore cannot initially access the new node. Next, the system copies a snapshot of the existing node to the new node, and then updates one or more fields in the new node that correspond to the one or more fields in the existing node. Next, in a single atomic operation the system modifies a next pointer of the existing node to point to the new node and also marks the next pointer to indicate that the existing node is deleted. In this way, the new node becomes part of the linked list and the existing node is deleted in a single atomic operation.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.