bloom_filter.hpp

Go to the documentation of this file.

 
#ifndef __BOXES_BLOOM_FILTER_HPP__
#define __BOXES_BLOOM_FILTER_HPP__
 
#include "compiler.hpp"
#include "hash_utils.hpp"
#include "hashes.hpp"
 
#include <algorithm>
#include <bit>
#include <cmath>
#include <numeric>
#include <vector>
 
namespace boxes::filter::bloom {
 
template <typename KeyT, hash::HashFamily64 HashT> class Bloom {
  using Base = uint64_t;
  using Bitmap = std::vector<Base>;
 
public:
  Bloom(std::size_t m, HashT h)
      : bitmapSize{calcBitmapElems(m)}, bitmapBits{bitmapSize * baseSize()},
        h{std::move(h)}, bitmap(bitmapSize, 0) {}
 
  void insert(const KeyT &key) {
    h.reset();
    for (std::size_t i = 0; i < k(); ++i) {
      const auto hResult = hash::hashType64(h, i, key);
      const auto idx = hResult % bitmapBits;
      set(idx);
    }
  }
 
  bool contains(const KeyT &key) const {
    h.reset();
    for (std::size_t i = 0; i < k(); ++i) {
      const auto hResult = hash::hashType64(h, i, key);
      const auto idx = hResult % bitmapBits;
      if (!at(idx)) {
        return false;
      }
    }
    return true;
  }
 
  std::size_t capacity() const BOXES_NOTHROW { return bitmapBits; }
 
  std::size_t k() const BOXES_NOTHROW { return h.size(); }
 
  std::size_t size() const BOXES_NOTHROW {
    const std::size_t x = count();
    return -1 * (bitmapBits / k()) * std::log(1 - x / bitmapBits);
  }
 
  std::size_t count() const {
    return std::accumulate(
        bitmap.begin(), bitmap.end(), 0,
        [](const auto &a, const auto &b) { return a + std::popcount(b); });
  }
 
  void swap(Bloom &other) {
    std::swap(bitmapSize, other.bitmapSize);
    std::swap(bitmapBits, other.bitmapBits);
    std::swap(h, other.h);
    bitmap.swap(other.bitmap);
  }
 
  void clear() BOXES_NOTHROW { std::fill(bitmap.begin(), bitmap.end(), 0); }
 
protected:
  // non-const to allow for swapping
  std::size_t bitmapSize;
  std::size_t bitmapBits;
 
  mutable HashT h;
  Bitmap bitmap;
 
  bool at(std::size_t index) const {
    const auto &res = std::div(static_cast<long long>(index), baseSize());
    return bitmap.at(res.quot) & (static_cast<Base>(0x01) << res.rem);
  }
 
  void set(std::size_t index) {
    const auto &res = std::div(static_cast<long long>(index), baseSize());
    bitmap[res.quot] |= (static_cast<Base>(0x01) << res.rem);
  }
 
  static constexpr std::size_t baseSize() { return sizeof(Base) * 8; }
 
  static constexpr std::size_t calcBitmapElems(std::size_t reqBits) {
    return (reqBits / baseSize()) + 1;
  }
};
 
std::size_t calcSize(std::size_t maxElements, double collisionProb) {
  return static_cast<std::size_t>(
      std::ceil(maxElements * std::log(collisionProb)) /
      std::log(1 / std::pow(2, std::log(2))));
}
 
std::size_t calcHashes(std::size_t bloomSize, std::size_t maxElements) {
  return std::round((double)(std::log(2) * bloomSize) / maxElements);
}
 
template <typename T, hash::Hash64 HT>
auto makeWithHashWithSeedFamily(std::size_t maxElements, double collisionProb) {
  using namespace boxes::hash;
  const auto m = calcSize(maxElements, collisionProb);
  const std::size_t k = calcHashes(m, maxElements);
  return Bloom<T, HashWithSeedFamily<HT>>{m, HashWithSeedFamily<HT>{k}};
}
 
template <typename T, hash::Hash64 H1T, hash::Hash64 H2T>
auto makeWithKirschMitzenmacherFamily(std::size_t maxElements,
                                      double collisionProb, H1T h1, H2T h2) {
  using namespace boxes::hash;
  const auto m = calcSize(maxElements, collisionProb);
  const std::size_t k = calcHashes(m, maxElements);
 
  return Bloom<T, KirschMitzenmacher<H1T, H2T>>{
      static_cast<std::size_t>(m),
      makeKirschMitzenmacher(std::move(h1), std::move(h2), k)};
}
 
} // namespace boxes::filter::bloom
 
#endif // __BOXES_BLOOM_FILTER_HPP__