libbf  0.1
 All Classes Functions Typedefs Friends Pages
bitwise.cc
1 #include <bf/bloom_filter/bitwise.h>
2 
3 namespace bf {
4 
5 bitwise_bloom_filter::bitwise_bloom_filter(size_t k, size_t cells, size_t seed)
6  : k_(k), cells_(cells), seed_(seed)
7 {
8  grow();
9 }
10 
11 void bitwise_bloom_filter::add(object const& o)
12 {
13  size_t l = 0;
14  // FIXME: do not hash element more than once for better performance.
15  while (l < levels_.size())
16  if (levels_[l].lookup(o))
17  {
18  levels_[l++].remove(o);
19  }
20  else
21  {
22  levels_[l].add(o);
23  return;
24  }
25 
26  grow();
27  levels_.back().add(o);
28 }
29 
30 size_t bitwise_bloom_filter::lookup(object const& o) const
31 {
32  size_t result = 0;
33  for (size_t l = 0; l < levels_.size(); ++l)
34  result += levels_[l].lookup(o) << l;
35  return result;
36 }
37 
39 {
40  levels_.clear();
41  grow();
42 }
43 
45 {
46  auto l = levels_.size();
47 
48  // TODO: come up with a reasonable growth scheme.
49  static size_t const min_size = 128;
50  auto cells = l == 0 ? min_size : cells_ / (2 * l);
51  if (cells < min_size)
52  cells = min_size;
53 
54  size_t seed = seed_;
55  std::minstd_rand0 prng(seed);
56  for (size_t i = 0; i < l; ++i)
57  seed = prng();
58 
59  levels_.emplace_back(make_hasher(k_, seed), cells);
60 }
61 
62 } // namespace bf