filter_bloom.hpp

Go to the documentation of this file.

#pragma once
 
/// @file userver/utils/filter_bloom.hpp
/// @brief @copybrief utils::FilterBloom
 
#include <array>
#include <functional>
#include <optional>
#include <type_traits>
#include <utility>
 
#include <boost/container_hash/hash.hpp>
 
#include <userver/utils/assert.hpp>
#include <userver/utils/fixed_array.hpp>
 
USERVER_NAMESPACE_BEGIN
 
namespace utils {
 
/// @ingroup userver_universal
///
/// @brief Space-efficient probabilistic data structure
///
/// @details Used to test whether a count number of a given element is
/// smaller than a given threshold when a sequence of elements is given.
/// As a generalized form of Bloom filter,
/// false positive matches are possible, but false negatives are not.
/// @param T the type of element that counts
/// @param Counter the type of counter
/// @param Hash1 the first callable hash struct
/// @param Hash2 the second callable hash struct
///
/// Example:
/// @snippet src/utils/filter_bloom_test.cpp  Sample filter bloom usage
template <typename T, typename Counter = unsigned, typename Hash1 = boost::hash<T>, typename Hash2 = std::hash<T>>
class FilterBloom final {
public:
    /// @brief Constructs filter Bloom with the specified number of counters
    /// @note If expected to increment n times is recommended to set counters_num
    /// to 16 * n
    explicit FilterBloom(std::size_t counters_num = 256, Hash1 hash_1 = Hash1{}, Hash2 hash_2 = Hash2{})
        : counters_(counters_num, 0), hasher_1(std::move(hash_1)), hasher_2(std::move(hash_2)) {
        UASSERT((!std::is_same_v<Hash1, Hash2>));
        UASSERT((std::is_same_v<std::invoke_result_t<Hash1, const T&>, std::invoke_result_t<Hash2, const T&>>));
    }
 
    /// @brief Increments the smallest item counters
    void Increment(const T& item);
 
    /// @brief Returns the value of the smallest item counter
    Counter Estimate(const T& item) const;
 
    /// @brief Checks that all counters of the item have been incremented
    bool Has(const T& item) const;
 
    /// @brief Resets all counters
    void Clear();
 
private:
    using HashedType = std::invoke_result_t<Hash1, const T&>;
 
    inline uint64_t Coefficient(std::size_t step) const;
    uint64_t GetHash(const HashedType& hashed_value_1, const HashedType& hashed_value_2, uint64_t coefficient) const;
    Counter MinFrequency(const HashedType& hashed_value_1, const HashedType& hashed_value_2) const;
 
    utils::FixedArray<Counter> counters_;
    const Hash1 hasher_1;
    const Hash2 hasher_2;
 
    static constexpr std::size_t kHashFunctionsCount = 4;
};
 
template <typename T, typename Counter, typename Hash1, typename Hash2>
inline uint64_t FilterBloom<T, Counter, Hash1, Hash2>::Coefficient(std::size_t step) const {
    return 1 << step;
}
 
template <typename T, typename Counter, typename Hash1, typename Hash2>
uint64_t FilterBloom<T, Counter, Hash1, Hash2>::GetHash(
    const HashedType& hashed_value_1,
    const HashedType& hashed_value_2,
    uint64_t coefficient
) const {
    // the idea was taken from
    // https://www.eecs.harvard.edu/~michaelm/postscripts/tr-02-05.pdf
    return hashed_value_1 + hashed_value_2 * coefficient;
}
 
template <typename T, typename Counter, typename Hash1, typename Hash2>
Counter FilterBloom<T, Counter, Hash1, Hash2>::MinFrequency(
    const HashedType& hashed_value_1,
    const HashedType& hashed_value_2
) const {
    std::optional<Counter> min_count;
    for (std::size_t step = 0; step < kHashFunctionsCount; ++step) {
        auto current_count = counters_[GetHash(hashed_value_1, hashed_value_2, Coefficient(step)) % counters_.size()];
        if (!min_count.has_value() || min_count.value() > current_count) {
            min_count = current_count;
        }
    }
    return min_count.value();
}
 
template <typename T, typename Counter, typename Hash1, typename Hash2>
void FilterBloom<T, Counter, Hash1, Hash2>::Increment(const T& item) {
    auto hash_value_1 = hasher_1(item);
    auto hash_value_2 = hasher_2(item);
    Counter min_frequency = MinFrequency(hash_value_1, hash_value_2);
 
    for (std::size_t step = 0; step < kHashFunctionsCount; ++step) {
        auto& current_count = counters_[GetHash(hash_value_1, hash_value_2, Coefficient(step)) % counters_.size()];
        if (current_count == min_frequency) {
            current_count++;
        }
    }
}
 
template <typename T, typename Counter, typename Hash1, typename Hash2>
Counter FilterBloom<T, Counter, Hash1, Hash2>::Estimate(const T& item) const {
    auto hash_value_1 = hasher_1(item);
    auto hash_value_2 = hasher_2(item);
    return MinFrequency(hash_value_1, hash_value_2);
}
 
template <typename T, typename Counter, typename Hash1, typename Hash2>
bool FilterBloom<T, Counter, Hash1, Hash2>::Has(const T& item) const {
    return Estimate(item) > 0;
}
 
template <typename T, typename Counter, typename Hash1, typename Hash2>
void FilterBloom<T, Counter, Hash1, Hash2>::Clear() {
    for (auto& counter : counters_) {
        counter = 0;
    }
}
 
}  // namespace utils
 
USERVER_NAMESPACE_END