Concurrent reads and inserts into a data structure without latching or waiting by readers
US11080260B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 27, 2018 |
| Grant date | Aug 3, 2021 |
| Priority date | — |
| Expiry date | Dec 27, 2039 |
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 that includes a mutable tier including extendible hashing, a hash table, and an immutable tier including a concise hash table (CHT) bitmap. 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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.