-
Kirill Smelkov authored
For BigFiles we'll needs to maintain `{} offset-in-file -> void *` mapping. A hash or a binary tree could be used there, but since we know files are most of the time accessed sequentially and locally in pages-batches, we can also organize the mapping in batches of keys. Specifically offset bits are so divided into parts, that every part addresses 1 entry in a table of hardware-page in size. To get to the actual value, the system lookups first table by first part of offset, then from first table and next part from address - second table, etc. To clients this looks like a dictionary with get/set/del & clear methods, but lookups are O(1) time always, and in contrast to hashes values are stored with locality (= adjacent lookups almost always access the same tables).
45af76e6