interleaved_bloom_filter.hpp

Go to the documentation of this file.

// SPDX-FileCopyrightText: 2006-2025, Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2025, Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: BSD-3-Clause
 
#pragma once
 
#include <algorithm>   // for fill
#include <array>       // for array
#include <cassert>     // for assert
#include <concepts>    // for integral, same_as, unsigned_integral
#include <cstdint>     // for uint32_t, uint16_t, uint64_t
#include <cstring>     // for size_t
#include <memory>      // for addressof
#include <ranges>      // for range, range_reference_t, range_value_t, forward_range, input_...
#include <type_traits> // for 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/aligned_allocator.hpp> // for aligned_allocator
#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/platform.hpp>                  // for HIBF_CONSTEXPR_VECTOR, HIBF_HAS_AVX512
 
namespace seqan::hibf
{
 
// config.hpp -> misc/insert_iterator.hpp (Needs interleaved_bloom_filter to be a complete class)
struct config;
 
struct bin_count
{
    size_t value;
};
struct bin_count {…};
 
struct bin_size
{
    size_t value;
};
struct bin_size {…};
 
struct hash_function_count
{
    size_t value;
};
struct hash_function_count {…};
 
struct bin_index
{
    size_t value;
};
struct bin_index {…};
 
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;
 
    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 membership_agent_type; // documented upon definition below
    template <std::integral value_t>
    class counting_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},
                             bool const 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;
    }
    void clear(rng_t && bin_range) noexcept {…}
 
    bool try_increase_bin_number_to(bin_count const new_bin_count) noexcept;
 
    void increase_bin_number_to(bin_count const new_bin_count);
 
    membership_agent_type membership_agent() const;
 
    template <typename value_t = uint16_t>
    counting_agent_type<value_t> counting_agent() const
    {
        return counting_agent_type<value_t>{*this};
    }
    counting_agent_type<value_t> counting_agent() const {…}
 
    size_t hash_function_count() const noexcept
    {
        return hash_funs;
    }
    size_t hash_function_count() const noexcept {…}
 
    size_t bin_count() const noexcept
    {
        return bins;
    }
    size_t bin_count() const noexcept {…}
 
    size_t bin_size() const noexcept
    {
        return bin_size_;
    }
    size_t bin_size() const noexcept {…}
 
    size_t bit_size() const noexcept
    {
        return base_t::size();
    }
    size_t bit_size() const noexcept {…}
 
    HIBF_CONSTEXPR_VECTOR 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);
    }
    void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive) {…}
};
class interleaved_bloom_filter : private seqan::hibf::bit_vector {…};
 
class interleaved_bloom_filter::membership_agent_type
{
private:
    interleaved_bloom_filter const * ibf_ptr{nullptr};
 
    std::array<size_t, 5> bloom_filter_indices;
 
    bit_vector 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) :
        ibf_ptr(std::addressof(ibf)),
        result_buffer(ibf.bin_count())
    {}
 
    [[nodiscard]] bit_vector const & bulk_contains(size_t const value) & noexcept;
 
    // `bulk_contains` cannot be called on a temporary, since the object the returned reference points to
    // is immediately destroyed.
    [[nodiscard]] bit_vector const & bulk_contains(size_t const value) && noexcept = delete;
};
class interleaved_bloom_filter::membership_agent_type {…};
 
inline interleaved_bloom_filter::membership_agent_type interleaved_bloom_filter::membership_agent() const
{
    return interleaved_bloom_filter::membership_agent_type{*this};
}
inline interleaved_bloom_filter::membership_agent_type interleaved_bloom_filter::membership_agent() const {…}
 
template <std::integral value_t>
class interleaved_bloom_filter::counting_agent_type
{
private:
    interleaved_bloom_filter const * ibf_ptr{nullptr};
 
    membership_agent_type membership_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) :
        ibf_ptr(std::addressof(ibf)),
        membership_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) && !defined(_LIBCPP_HAS_NO_ASAN)
        __sanitizer_annotate_contiguous_container(result_buffer.data(),
                                                  result_buffer.data() + result_buffer.capacity(),
                                                  result_buffer.data() + result_buffer.size(),
                                                  result_buffer.data() + result_buffer.capacity());
#    endif
    }
#endif
 
 
    template <std::ranges::range value_range_t>
    [[nodiscard]] counting_vector<value_t> const & bulk_count(value_range_t && values) & noexcept
    {
        assert(ibf_ptr != nullptr);
        assert(result_buffer.size() == ibf_ptr->bin_count());
 
        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 += membership_agent.bulk_contains(value);
 
        return result_buffer;
    }
    [[nodiscard]] counting_vector<value_t> const & bulk_count(value_range_t && values) & noexcept {…}
 
    // `bulk_count` cannot be called on a temporary, since the object the returned reference points to
    // is immediately destroyed.
    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::counting_agent_type {…};
 
} // namespace seqan::hibf