• Kirill Smelkov's avatar
    bigfile/pagemap: specialized {} uint64 -> void * mapping · 45af76e6
    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).
pagemap.c 6.15 KB