libbf
0.1
Main Page
Classes
All
Classes
Functions
Typedefs
Friends
Pages
src
bf
bloom_filter
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
Generated by
1.8.3.1