Concurrent reads and inserts into a data structure without latching or waiting by readers
US10108653B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 27, 2015 |
| Grant date | Oct 23, 2018 |
| Priority date | — |
| Expiry date | Nov 20, 2036 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/182
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method includes performing, by a data structure processor, concurrent read and write operations into a hierarchical data structure. Writers acquire latches on the hierarchical data structure elements that the latches modify. The hierarchical data structure elements are directly accessed by readers without acquiring latches. A modify operation is executed by a writer for one or more levels of the hierarchical data structure. When removed portions of the hierarchical data structure are no longer referenced, tracking is performed by use of a combination of a global state value and a copied local state value. The global state value transitions through a non-repeating sequence of values. No longer referenced portions of the hierarchical data structure are tagged with the current global state value.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.