libbf  0.1
 All Classes Functions Typedefs Friends Pages
basic.cc
1 #include <bf/bloom_filter/basic.h>
2 
3 #include <cmath>
4 
5 namespace bf {
6 
7 size_t basic_bloom_filter::m(double fp, size_t capacity)
8 {
9  auto ln2 = std::log(2);
10  return std::ceil(-(capacity * std::log(fp) / ln2 / ln2));
11 }
12 
13 size_t basic_bloom_filter::k(size_t cells, size_t capacity)
14 {
15  auto frac = static_cast<double>(cells) / static_cast<double>(capacity);
16  return std::ceil(frac * std::log(2));
17 }
18 
20  : hasher_(std::move(h)),
21  bits_(cells)
22 {
23 }
24 
25 basic_bloom_filter::basic_bloom_filter(double fp, size_t capacity, size_t seed,
26  bool double_hashing)
27 {
28  auto required_cells = m(fp, capacity);
29  auto optimal_k = k(required_cells, capacity);
30  bits_.resize(required_cells);
31  hasher_ = make_hasher(optimal_k, seed, double_hashing);
32 }
33 
35  : hasher_(std::move(other.hasher_)),
36  bits_(std::move(other.bits_))
37 {
38 }
39 
40 void basic_bloom_filter::add(object const& o)
41 {
42  for (auto d : hasher_(o))
43  bits_.set(d % bits_.size());
44 }
45 
46 size_t basic_bloom_filter::lookup(object const& o) const
47 {
48  for (auto d : hasher_(o))
49  if (! bits_[d % bits_.size()])
50  return 0;
51  return 1;
52 }
53 
55 {
56  bits_.reset();
57 }
58 
59 void basic_bloom_filter::remove(object const& o)
60 {
61  for (auto d : hasher_(o))
62  bits_.reset(d % bits_.size());
63 }
64 
66 {
67  using std::swap;
68  swap(hasher_, other.hasher_);
69  swap(bits_, other.bits_);
70 }
71 
72 } // namespace bf