libbf  0.1
 All Classes Functions Typedefs Friends Pages
stable.cc
1 #include <bf/bloom_filter/stable.h>
2 
3 #include <cassert>
4 
5 namespace bf {
6 
7 stable_bloom_filter::stable_bloom_filter(hasher h, size_t cells, size_t width,
8  size_t d)
9  : counting_bloom_filter(std::move(h), cells, width),
10  d_(d),
11  unif_(0, cells - 1)
12 {
13  assert(d <= cells);
14 }
15 
16 void stable_bloom_filter::add(object const& o)
17 {
18  // Decrement d distinct cells uniformly at random.
19  std::vector<size_t> indices;
20  for (size_t d = 0; d < d_; ++d)
21  {
22  bool unique;
23  do
24  {
25  size_t u = unif_(generator_);
26  unique = true;
27  for (auto i : indices)
28  if (i == u)
29  {
30  unique = false;
31  break;
32  }
33  if (unique)
34  {
35  indices.push_back(u);
36  cells_.decrement(u);
37  }
38  } while (! unique);
39  }
40 
41  increment(find_indices(o), cells_.max());
42 }
43 
44 } // namespace bf