fastfilter::Bloom Struct Reference

#include <fast_filter.h>

Public Member Functions
void	init (size_t n_items, double fp_rate)
void	_setbit (uint64_t h)
bool	_getbit (uint64_t h) const
void	add (const std::string &s)
bool	might_contain (const std::string &s) const

Public Attributes
size_t	m_bits = 0
size_t	k_hashes = 0
std::vector< uint8_t >	buf

Detailed Description

Definition at line 87 of file fast_filter.h.

Member Function Documentation

_getbit()

bool fastfilter::Bloom::_getbit ( uint64_t h ) const

inline

Definition at line 98 of file fast_filter.h.

{ size_t i = h % m_bits; return (buf[i>>3] >> (i & 7)) & 1u; }

References buf, and m_bits.

Referenced by might_contain().

_setbit()

void fastfilter::Bloom::_setbit ( uint64_t h )

inline

Definition at line 97 of file fast_filter.h.

{ size_t i = h % m_bits; buf[i>>3] |= (uint8_t)(1u << (i & 7)); }

References buf, and m_bits.

Referenced by add().

add()

void fastfilter::Bloom::add ( const std::string & s )

inline

Definition at line 99 of file fast_filter.h.

                              {
    uint64_t h1 = murmur3_64(s.data(), s.size(), 0xA5A5A5A5);
    uint64_t h2 = murmur3_64(s.data(), s.size(), 0x5A5A5A5A);
    for(size_t i=0;i<k_hashes;i++) _setbit(h1 + i*h2);
  }

References _setbit(), k_hashes, and fastfilter::murmur3_64().

Referenced by fastfilter::Engine::load_patterns_file(), and fastfilter::Engine::load_patterns_sqlite().

init()

void fastfilter::Bloom::init ( size_t n_items, double fp_rate )

inline

Definition at line 89 of file fast_filter.h.

                                           {
 
    double ln2 = 0.6931471805599453;
    double m = -(double)n_items * std::log(fp_rate) / (ln2*ln2);
    m_bits = (size_t)std::max( (double)8.0, std::ceil(m) );
    k_hashes = std::max<size_t>(1, (size_t)std::round((m_bits/(double)std::max<size_t>(1,n_items))*ln2));
    buf.assign((m_bits + 7)/8, 0);
  }

References buf, k_hashes, and m_bits.

Referenced by fastfilter::Engine::build_bloom().

might_contain()

bool fastfilter::Bloom::might_contain ( const std::string & s ) const

inline

Definition at line 104 of file fast_filter.h.

                                               {
    uint64_t h1 = murmur3_64(s.data(), s.size(), 0xA5A5A5A5);
    uint64_t h2 = murmur3_64(s.data(), s.size(), 0x5A5A5A5A);
    for(size_t i=0;i<k_hashes;i++) if(!_getbit(h1 + i*h2)) return false; return true;
  }

References _getbit(), k_hashes, and fastfilter::murmur3_64().

Referenced by fastfilter::Engine::check_url().

Member Data Documentation

buf

std::vector<uint8_t> fastfilter::Bloom::buf

Definition at line 88 of file fast_filter.h.

Referenced by _getbit(), _setbit(), and init().

k_hashes

size_t fastfilter::Bloom::k_hashes = 0

Definition at line 88 of file fast_filter.h.

Referenced by add(), init(), and might_contain().

m_bits

size_t fastfilter::Bloom::m_bits = 0

Definition at line 88 of file fast_filter.h.

Referenced by _getbit(), _setbit(), fastfilter::Engine::check_url(), and init().

---

The documentation for this struct was generated from the following file:

• BastionGuard/src/filters/fast_filter.h