[−][src]Module terminus_store::structure::logarray

Code for storing, loading, and using log arrays.

A log array is a contiguous sequence of N unsigned integers, with each value occupying exactly W bits. By choosing W as the minimal bit width required for the largest value in the array, the whole sequence can be compressed while increasing the constant cost of indexing by a few operations over the typical byte-aligned array.

The log array operations in this module use the following implementation:

  1. The input buffer can be evenly divided into L+1 words, where a word is 64 bits.
  2. The first L words are the data buffer, a contiguous sequence of elements, where an element is an unsigned integer represented by W bits.
  3. The L+1 word is the control word and contains the following sequence:
    1. a 32-bit unsigned integer representing N, the number of elements,
    2. an 8-bit unsigned integer representing W, the number of bits used to store each element, and
    3. 24 unused bits.

Notes

  • All integers are stored in a standard big-endian encoding.
  • The maximum bit width W is 64.
  • The maximum number of elements is 2^32-1.

Naming

Because of the ambiguity of the English language and possibility to confuse the meanings of the words used to describe aspects of this code, we try to use the following definitions consistently throughout:

  • buffer: a contiguous sequence of bytes

  • size: the number of bytes in a buffer

  • word: a 64-bit contiguous sequence aligned on 8-byte boundaries starting at the beginning of the input buffer

  • element: a logical unsigned integer value that is a member of the log array

  • index: the logical address of an element in the data buffer. A physical index is preceded by word, byte, or bit to indicate the address precision of the index.

  • offset: the number of bits preceding the msb of an element within the first word containing that element

  • width: the number of bits that every element occupies in the log array

  • length: the number of elements in the log array

Structs

LogArray

An in-memory log array

LogArrayFileBuilder

write a logarray directly to an AsyncWrite

LogArrayIterator
MonotonicLogArray

Enums

LogArrayError

An error that occurred during a log array operation.

Functions

logarray_file_get_length_and_width
logarray_stream_entries