interleaved_bloom_filter.hpp

Go to the documentation of this file.

// SPDX-FileCopyrightText: 2006-2026, Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2026, Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: BSD-3-Clause
 
#pragma once
 
#include <algorithm>   // for fill
#include <array>       // for array
#include <cstddef>     // for size_t
#include <cstdint>     // for uint16_t, uint64_t, uint32_t
#include <memory>      // for addressof
#include <ranges>      // for forward_range, integral, range, range_value_t, unsigned_integral
#include <type_traits> // for false_type, remove_cvref_t
#include <vector>      // for vector, operator==
 
#include <cereal/cereal.hpp>           // for make_nvp
#include <cereal/macros.hpp>           // for CEREAL_SERIALIZE_FUNCTION_NAME
#include <cereal/types/base_class.hpp> // for base_class
#include <cereal/types/vector.hpp>     // IWYU pragma: keep
 
#include <hibf/cereal/concepts.hpp>            // for cereal_archive
#include <hibf/contrib/std/enumerate_view.hpp> // for enumerate
#include <hibf/misc/bit_vector.hpp>            // for bit_vector
#include <hibf/misc/counting_vector.hpp>       // for counting_vector
#include <hibf/misc/next_multiple_of_64.hpp>   // for next_multiple_of_64
#include <hibf/misc/unreachable.hpp>           // for assert, unreachable, forward
#include <hibf/platform.hpp>                   // for HIBF_HAS_AVX512
 
namespace seqan::hibf
{
 
// config.hpp -> misc/insert_iterator.hpp (Needs interleaved_bloom_filter to be a complete class)
struct config;
struct inspector;
 
struct bin_count
{
    size_t value;
};
 
struct bin_size
{
    size_t value;
};
 
struct hash_function_count
{
    size_t value;
};
 
struct bin_index
{
    size_t value;
};
 
struct empty_bin_fraction
{
    double value;
};
 
struct track_occupancy
{
    bool value;
};
 
class interleaved_bloom_filter : private seqan::hibf::bit_vector
{
private:
    using base_t = seqan::hibf::bit_vector;
 
    template <typename t>
    friend struct cereal::base_class;
 
    friend struct seqan::hibf::inspector;
 
    size_t bins{};
    size_t technical_bins{};
    size_t bin_size_{};
    size_t hash_shift{};
    size_t bin_words{};
    size_t hash_funs{};
    static constexpr std::array<size_t, 5> hash_seeds{13572355802537770549ULL, // 2**64 / (e/2)
                                                      13043817825332782213ULL, // 2**64 / sqrt(2)
                                                      10650232656628343401ULL, // 2**64 / sqrt(3)
                                                      16499269484942379435ULL, // 2**64 / (sqrt(5)/2)
                                                      4893150838803335377ULL}; // 2**64 / (3*pi/5)
 
    [[gnu::always_inline]] inline constexpr size_t hash_and_fit(size_t h, size_t const seed) const
    {
        h *= seed;
        assert(hash_shift < 64);
        h ^= h >> hash_shift;         // XOR and shift higher bits into lower bits
        h *= 11400714819323198485ULL; // = 2^64 / golden_ration, to expand h to 64 bit range
        // Use fastrange (integer modulo without division).
        h = static_cast<uint64_t>((static_cast<__uint128_t>(h) * static_cast<__uint128_t>(bin_size_)) >> 64);
        h *= technical_bins;
        return h;
    }
 
public:
    class containment_agent_type; // documented upon definition below
    template <std::integral value_t>
    class counting_agent_type;   // documented upon definition below
    class membership_agent_type; // documented upon definition below
 
    interleaved_bloom_filter() = default;                                                 
    interleaved_bloom_filter(interleaved_bloom_filter const &) = default;                 
    interleaved_bloom_filter & operator=(interleaved_bloom_filter const &) = default;     
    interleaved_bloom_filter(interleaved_bloom_filter &&) noexcept = default;             
    interleaved_bloom_filter & operator=(interleaved_bloom_filter &&) noexcept = default; 
    ~interleaved_bloom_filter() = default;                                                
 
    interleaved_bloom_filter(
        seqan::hibf::bin_count const bins_,
        seqan::hibf::bin_size const size,
        seqan::hibf::hash_function_count const funs = seqan::hibf::hash_function_count{2u},
        seqan::hibf::empty_bin_fraction const empty_bin_fraction = seqan::hibf::empty_bin_fraction{0.0},
        seqan::hibf::track_occupancy const track_occupancy = seqan::hibf::track_occupancy{false});
 
    interleaved_bloom_filter(config & configuration, size_t const max_bin_elements = 0u);
 
    void emplace(size_t const value, bin_index const bin) noexcept;
 
    void clear(bin_index const bin) noexcept;
 
    template <typename rng_t>
    void clear(rng_t && bin_range) noexcept
    {
        static_assert(std::ranges::forward_range<rng_t>, "The range of bins to clear must model a forward_range.");
        static_assert(std::same_as<std::remove_cvref_t<std::ranges::range_reference_t<rng_t>>, bin_index>,
                      "The reference type of the range to clear must be seqan::hibf::bin_index.");
#ifndef NDEBUG
        for (auto && bin : bin_range)
            assert(bin.value < technical_bins);
#endif // NDEBUG
 
        for (size_t offset = 0, i = 0; i < bin_size_; offset += technical_bins, ++i)
            for (auto && bin : bin_range)
                (*this)[bin.value + offset] = 0;
    }
 
    bool try_increase_bin_number_to(bin_count const new_bin_count) noexcept;
 
    void increase_bin_number_to(bin_count const new_bin_count);
 
    containment_agent_type containment_agent() const;
 
    template <typename value_t = uint16_t>
    counting_agent_type<value_t> counting_agent() const
    {
        return counting_agent_type<value_t>{*this};
    }
 
    membership_agent_type membership_agent() const;
 
    size_t hash_function_count() const noexcept
    {
        return hash_funs;
    }
 
    size_t bin_count() const noexcept
    {
        return bins;
    }
 
    size_t bin_size() const noexcept
    {
        return bin_size_;
    }
 
    size_t bit_size() const noexcept
    {
        return base_t::size();
    }
 
    constexpr bool operator==(interleaved_bloom_filter const &) const = default;
 
    using base_t::data;
 
    std::vector<size_t> occupancy{};
 
    bool track_occupancy{false};
 
    static constexpr uint32_t version{1};
 
    template <cereal_archive archive_t>
    void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
    {
        uint32_t parsed_version{version};
        archive(cereal::make_nvp("version", parsed_version));
        archive(bins);
        archive(technical_bins);
        archive(bin_size_);
        archive(hash_shift);
        archive(bin_words);
        archive(hash_funs);
        archive(cereal::base_class<base_t>(this));
        archive(occupancy);
        archive(track_occupancy);
    }
};
 
class interleaved_bloom_filter::containment_agent_type
{
private:
    interleaved_bloom_filter const * ibf_ptr{nullptr};
 
    std::array<size_t, 5> bloom_filter_indices;
 
    bit_vector result_buffer;
 
public:
    containment_agent_type() = default;                                               
    containment_agent_type(containment_agent_type const &) = default;                 
    containment_agent_type & operator=(containment_agent_type const &) = default;     
    containment_agent_type(containment_agent_type &&) noexcept = default;             
    containment_agent_type & operator=(containment_agent_type &&) noexcept = default; 
    ~containment_agent_type() = default;                                              
 
    explicit containment_agent_type(interleaved_bloom_filter const & ibf) :
        ibf_ptr(std::addressof(ibf)),
        result_buffer(ibf.bin_count())
    {}
 
    [[nodiscard]] bit_vector const & bulk_contains(size_t const value) & noexcept;
 
    [[nodiscard]] bit_vector const & bulk_contains(size_t const value) && noexcept = delete;
};
 
inline interleaved_bloom_filter::containment_agent_type interleaved_bloom_filter::containment_agent() const
{
    return interleaved_bloom_filter::containment_agent_type{*this};
}
 
template <std::integral value_t>
class interleaved_bloom_filter::counting_agent_type
{
private:
    containment_agent_type containment_agent;
 
    counting_vector<value_t> result_buffer;
 
public:
    counting_agent_type() = default;                                            
    counting_agent_type(counting_agent_type const &) = default;                 
    counting_agent_type & operator=(counting_agent_type const &) = default;     
    counting_agent_type(counting_agent_type &&) noexcept = default;             
    counting_agent_type & operator=(counting_agent_type &&) noexcept = default; 
    ~counting_agent_type() = default;                                           
 
    explicit counting_agent_type(interleaved_bloom_filter const & ibf) :
        containment_agent(ibf),
#if !HIBF_HAS_AVX512
        result_buffer(ibf.bin_count())
    {}
#else
        // AVX512 will access result_buffer's memory in chunks, so we need to make sure that we allocate enough memory
        // such that the last chunk is not out of bounds.
        result_buffer(next_multiple_of_64(ibf.bin_count())) // Ensure large enough capacity.
    {
        result_buffer.resize(ibf.bin_count()); // Resize to actual requested size.
                                               // Silences llvm's ASAN container-overflow warning.
#    if defined(_LIBCPP_VERSION)
#        if __has_feature(address_sanitizer)
        std::__annotate_contiguous_container<allocator_type>(result_buffer.data(),
                                                             result_buffer.data() + result_buffer.capacity(),
                                                             result_buffer.data() + result_buffer.size(),
                                                             result_buffer.data() + result_buffer.capacity());
#        endif
#    endif
    }
#endif
 
 
    template <std::ranges::range value_range_t>
    [[nodiscard]] counting_vector<value_t> const & bulk_count(value_range_t && values) & noexcept
    {
        static_assert(std::ranges::input_range<value_range_t>, "The values must model input_range.");
        static_assert(std::unsigned_integral<std::ranges::range_value_t<value_range_t>>,
                      "An individual value must be an unsigned integral.");
 
        std::ranges::fill(result_buffer, 0);
 
        for (auto && value : values)
            result_buffer += containment_agent.bulk_contains(value);
 
        return result_buffer;
    }
 
    template <std::ranges::range value_range_t>
    [[nodiscard]] counting_vector<value_t> const & bulk_count(value_range_t && values) && noexcept = delete;
};
 
class interleaved_bloom_filter::membership_agent_type
{
private:
    counting_agent_type<uint16_t> counting_agent;
 
    std::vector<uint64_t> result_buffer;
 
public:
    membership_agent_type() = default;                                              
    membership_agent_type(membership_agent_type const &) = default;                 
    membership_agent_type & operator=(membership_agent_type const &) = default;     
    membership_agent_type(membership_agent_type &&) noexcept = default;             
    membership_agent_type & operator=(membership_agent_type &&) noexcept = default; 
    ~membership_agent_type() = default;                                             
 
    explicit membership_agent_type(interleaved_bloom_filter const & ibf) :
        counting_agent(ibf),
        result_buffer(ibf.bin_count())
    {}
 
    void sort_results()
    {}
 
    template <std::ranges::forward_range value_range_t>
    [[nodiscard]] std::vector<uint64_t> const & membership_for(value_range_t && values,
                                                               uint16_t const threshold) & noexcept
    {
        static_assert(std::ranges::forward_range<value_range_t>, "The values must model forward_range.");
        static_assert(std::unsigned_integral<std::ranges::range_value_t<value_range_t>>,
                      "An individual value must be an unsigned integral.");
 
        result_buffer.clear();
 
        auto & counts_per_bin = counting_agent.bulk_count(std::forward<value_range_t>(values));
 
        if (result_buffer.capacity() < counts_per_bin.size())
            seqan::hibf::unreachable();
 
        for (auto [bin, count] : seqan::stl::views::enumerate(counts_per_bin))
            if (count >= threshold)
                result_buffer.emplace_back(bin);
 
        return result_buffer;
    }
 
    template <std::ranges::forward_range value_range_t>
    [[nodiscard]] std::vector<uint64_t> const & membership_for(value_range_t && values,
                                                               uint16_t const threshold) && noexcept = delete;
 
    // GCOVR_EXCL_START
    template <typename t>
    struct always_false : std::false_type
    {};
 
    template <typename t = void>
    [[nodiscard]] bit_vector const & bulk_contains(size_t const) & noexcept
    {
        static_assert(
            always_false<t>::value,
            "The functionality of the membership_agent has been changed to be analogous to the "
            "hierarchical_interleaved_bloom_filter's version. As such, the interleaved_bloom_filter's membership_agent "
            "now only offers membership_for, which returns bin indices that exceed a given threshold when querying a "
            "range of values. bulk_contains is now part of a new agent: containment_agent. If you want to use "
            "bulk_contains, change ibf.membership_agent() to ibf.containment_agent().");
        seqan::hibf::unreachable();
    }
 
    [[nodiscard]] bit_vector const & bulk_contains(size_t const) && noexcept = delete;
    // GCOVR_EXCL_STOP
};
 
inline interleaved_bloom_filter::membership_agent_type interleaved_bloom_filter::membership_agent() const
{
    return interleaved_bloom_filter::membership_agent_type{*this};
}
 
} // namespace seqan::hibf