International Business Machines Corporation
Concurrent reads and inserts into a data structure without latching or waiting by readers

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.