varint.hpp File Reference

Implements a prefix-style variable-length integer. More...

#include "pstore/support/bit_count.hpp"

Include dependency graph for varint.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
constexpr unsigned	pstore::varint::encoded_size (std::uint64_t const x) noexcept
template<typename OutputIterator >
OutputIterator	pstore::varint::encode (std::uint64_t x, OutputIterator out)
template<typename InputIterator >
unsigned	pstore::varint::decode_size (InputIterator in)
template<typename InputIterator >
std::uint64_t	pstore::varint::details::decode9 (InputIterator in)
template<typename InputIterator >
std::uint64_t	pstore::varint::decode (InputIterator in, unsigned size)
template<typename InputIterator >
std::uint64_t	pstore::varint::decode (InputIterator in)

Variables
constexpr std::size_t const	pstore::varint::max_output_length = 9
	The maximum number of bytes that encode() will produce.

Detailed Description

Implements a prefix-style variable-length integer.

This code implements a variation on the UTF-8/LEB128 style variable-length integer in which the first bit of each byte indicates whether further bytes are to follow. The motivation for this difference is that we'd like to minimize the number of calls to database::get() and its variant so its useful to know immediately how many bytes make up the value rather than having to discover this as we go. Otherwise the concepts are the same.

In the code here, the low bits of the first byte of the number denote the length of the encoding. The number of bytes can be found simply by call ctz(x | 0x100)+1 where ctz() is a function which returns the number of trailing zeros starting at the LSB) and x is the value of the first byte. See decode_size() for the real implementation.

Example: The number 1 is encoded in a single byte.

    +---------------------------------+

bit | 7 6 5 4 3 2 1 0 | +------------------------—+--—+ meaning | value | (*) | +------------------------—+--—+ value | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | +------------------------—+--—+ (*) "1 byte varint value"

The number 2^8 is encoded in two bytes as shown below:

                 byte 0                            byte 1
    +-----------------------+-------+ +-------------------------------+

bit | 7 6 5 4 3 2 1 0 | | 7 6 5 4 3 2 1 0 | +--------------------—+----—+ +----------------------------—+ meaning | value | 2 | | value | | bits 0-5 | bytes | | bits 6-13 | +--------------------—+----—+ +-----------------------------— value | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | +--------------------—+----—+ +----------------------------—+