An offset in the secondary index file.

We need 4 bytes ( Word32 ) because the secondary index file can grow to +1MiB.

In-memory representation of the primary index file.

The primary index maps relative slots to offsets in the secondary index file. The first offset is always 0, as the first entry in the secondary index file will always start at offset 0. The second offset will be equal to the size of a secondary index entry, unless the slot is empty, in which case it will be 0. In general, an offset will either be a repetition of the offset before it, to indicate the slot is empty, or the offset before it + the fixed size of a secondary index entry, in case the slot is filled.

The size of a secondary index entry can be computed by subtracting the offset corresponding to the respective slot from the offset corresponding to the slot after it.

For example, if slots 0, 1 and 4 are filled, we'd have the following offsets in the primary index file:

slot:       0   1   2   3   4
        ┌───┬───┬───┬───┬───┬───┐
offset: │ 0 │ x │ y │ y │ y │ z │
        └───┴───┴───┴───┴───┴───┘

We use x, y, z in the example above, but in practice these will be multiples of the (fixed) size of an entry in secondary index.

TODO As all entries have the same size, we could use a bitvector instead, see #1234.

The serialisation of a primary index file starts with currentVersionNumber followed by all its offset.

Append the given SecondaryOffset to the end of the file (passed as a handle).

Return the slots to backfill the primary index file with.

A situation may arise in which we "skip" some relative slots, and we write into the DB, for example, every other relative slot. In this case, we need to backfill the primary index file with offsets for the skipped relative slots. Similarly, before we start a new chunk, we must backfill the primary index file of the current chunk to indicate that the remaining slots in the chunk are empty.

For example, say we have written to relative slots 0 and 1. We have the following primary index file:

slot:       0   1
        ┌───┬───┬───┐
offset: │ 0 │ x │ y │
        └───┴───┴───┘

Now we want to write to relative slot 4, skipping 2 and 3. We first have to backfill the primary index by repeating the last offset for the two missing slots:

slot:       0   1   2   3
        ┌───┬───┬───┬───┬───┐
offset: │ 0 │ x │ y │ y │ y │
        └───┴───┴───┴───┴───┘

After backfilling (writing the offset y twice), we can write the next offset:

slot:       0   1   2   3   4
        ┌───┬───┬───┬───┬───┬───┐
offset: │ 0 │ x │ y │ y │ y │ z │
        └───┴───┴───┴───┴───┴───┘

For the example above, the output of this function would thus be: [y, y] .

We use x, y, z in the examples above, but in practice these will be multiples of the (fixed) size of an entry in secondary index.

Return the slots to backfill the primary index file with when padding it to the chunk size.

See backfill for more details.

Check whether the given slot is within the primary index.

Version number of the index format

Return a list of all the filled (length > zero) slots in the primary index.

Find the first filled (length > zero) slot in the primary index. If there is none, return Nothing .

Example: given the primary index below:

slot:       0   1
        ┌───┬───┬───┐
offset: │ 0 │ 0 │ x │
        └───┴───┴───┘

Return slot 1.

Return the last slot of the primary index (empty or not).

Returns Nothing if the index is empty.

Return True when the given slot is filled.

Precondition: the given slot must be within the primary index ( containsSlot ).

Return the last filled slot in the primary index.

Return the last SecondaryOffset in the primary index file.

Load a primary index file in memory.

Find the next filled (length > zero) slot after the given slot in the primary index. If there is none, return Nothing .

Precondition: the given slot must be within the primary index ( containsSlot ).

Example: given the primary index below and slot 1:

slot:       0   1   2   3   4
        ┌───┬───┬───┬───┬───┬───┐
offset: │ 0 │ x │ y │ y │ y │ z │
        └───┴───┴───┴───┴───┴───┘

Return slot 4.

Return the offset for the given slot.

Precondition: the given slot must be within the primary index ( containsSlot ).

Open a primary index file for the given chunk and return a handle to it.

The file is opened with the given AllowExisting value. When given MustBeNew , the version number is written to the file.

Return the first filled slot in the primary index file, or Nothing in case there are no filled slots.

PRECONDITION: the index file must exist and contain at least the version number and offset 0.

May throw InvalidPrimaryIndexException .

Read the SecondaryOffset corresponding to the given relative slot in the primary index. Return Nothing when the slot is empty.

Same as readOffset , but for multiple offsets.

NOTE: only use this for a few offsets, as we will seek ( pread ) for each offset. Use load if you want to read the whole primary index.

The size of each entry in the primary index file, i.e., the size of a SecondaryOffset .

Return the size of the given slot according to the primary index.

Precondition: the given slot must be within the primary index ( containsSlot ).

Count the number of (filled or unfilled) slots currently in the index

Truncate the primary index so that the given RelativeSlot will be the last slot (filled or not) in the primary index, unless the primary index didn't contain the RelativeSlot in the first place.

On-disk variant of truncateToSlot . The truncation is done without reading the primary index from disk.

Remove all trailing empty slots that were added during the finalisation/backfilling of the primary index.

POSTCONDITION: the last slot of the primary index file will be filled, unless the index itself is empty.

Write a primary index to a file.

Property: for hasFS , err , chunk

'write' hasFS chunk primaryIndex
primaryIndex' <- 'load' hasFS err chunk

Then it must be that:

primaryIndex === primaryIndex'

Smart constructor: checks that the offsets are non-decreasing, there is at least one offset, and that the first offset is 0.

Return the SecondaryOffset s in the PrimaryIndex .