elias_fano.h File Reference

Encodes and selects arbitrary nondecreasing integer sequences. More...

#include <algorithm>
#include <array>
#include <everett/word_view.h>
#include <everett/error_detail.h>
#include <everett/backend.h>
#include <simd/integer.h>
#include <simd/packing.h>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <numeric>
#include <span>
#include <stdexcept>
#include <utility>
#include <vector>

Go to the source code of this file.

Classes
struct	everett::elias_fano_sample
struct	everett::elias_fano_view
struct	everett::elias_fano_cursor
struct	everett::elias_fano

Namespaces
namespace	everett
namespace	everett::elias_fano_detail

Functions
constexpr std::uint64_t	everett::elias_fano_detail::add (std::uint64_t a, std::uint64_t b) noexcept
constexpr std::uint64_t	everett::elias_fano_detail::multiply (std::uint64_t a, std::uint64_t b) noexcept
std::uint64_t	everett::elias_fano_detail::words (std::uint64_t bits) noexcept
template<simd::architecture Arch = simd::scalar>
bool	everett::elias_fano_detail::monotone (std::span< std::uint64_t const > source) noexcept
template<simd::architecture Arch = simd::scalar>
unsigned	everett::elias_fano_detail::select_word (std::uint64_t value, unsigned ordinal) noexcept
template<unsigned W, std::size_t O, std::size_t I>
std::uint64_t	everett::elias_fano_detail::low_component (std::uint64_t const *source) noexcept
template<unsigned W, std::size_t O, std::size_t... I>
std::uint64_t	everett::elias_fano_detail::low_word (std::uint64_t const *source, std::index_sequence< I... >) noexcept
template<unsigned W, std::size_t... O>
void	everett::elias_fano_detail::low_tile (std::uint64_t const *source, std::uint64_t *out, std::index_sequence< O... >) noexcept
template<unsigned W, simd::architecture Arch = simd::scalar>
void	everett::elias_fano_detail::pack_low_fixed (std::span< std::uint64_t const > source, std::span< std::uint64_t > out) noexcept
template<simd::architecture Arch, std::size_t... W>
constexpr auto	everett::elias_fano_detail::low_packers (std::index_sequence< W... >) noexcept
template<simd::architecture Arch = simd::scalar>
void	everett::elias_fano_detail::pack_low (std::span< std::uint64_t const > source, std::span< std::uint64_t > out, unsigned width)
void	everett::elias_fano_detail::write_high (std::span< std::uint64_t const > source, std::span< std::uint64_t > out, unsigned width) noexcept

Detailed Description

Encodes and selects arbitrary nondecreasing integer sequences.

Author

Edward Kmett ekmet.nosp@m.t@gm.nosp@m.ail.c.nosp@m.om

SPDX-FileType: SOURCE
SPDX-FileCopyrightText: 2026 Edward Kmett <ekmett@gmail.com>
SPDX-License-Identifier: BSD-2-Clause OR Apache-2.0