]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | ||
4 | #include "common/bloom_filter.hpp" | |
7c673cae | 5 | |
20effc67 TL |
6 | #include <numeric> |
7 | #include "include/intarith.h" | |
7c673cae | 8 | |
f67539c2 TL |
9 | using ceph::bufferlist; |
10 | using ceph::bufferptr; | |
11 | using ceph::Formatter; | |
12 | ||
20effc67 TL |
13 | double bloom_filter::density() const |
14 | { | |
15 | // TODO: use transform_reduce() in GCC-9 and up | |
16 | unsigned set = std::accumulate( | |
17 | bit_table_.begin(), | |
18 | bit_table_.begin() + table_size_, | |
19 | 0u, [](unsigned set, cell_type cell) { | |
20 | return set + popcount(cell); | |
21 | }); | |
22 | return (double)set / (table_size_ * sizeof(cell_type) * CHAR_BIT); | |
23 | } | |
24 | ||
7c673cae FG |
25 | void bloom_filter::encode(bufferlist& bl) const |
26 | { | |
27 | ENCODE_START(2, 2, bl); | |
11fdf7f2 TL |
28 | encode((uint64_t)salt_count_, bl); |
29 | encode((uint64_t)insert_count_, bl); | |
30 | encode((uint64_t)target_element_count_, bl); | |
31 | encode((uint64_t)random_seed_, bl); | |
20effc67 | 32 | encode(bit_table_, bl); |
7c673cae FG |
33 | ENCODE_FINISH(bl); |
34 | } | |
35 | ||
11fdf7f2 | 36 | void bloom_filter::decode(bufferlist::const_iterator& p) |
7c673cae FG |
37 | { |
38 | DECODE_START(2, p); | |
39 | uint64_t v; | |
11fdf7f2 | 40 | decode(v, p); |
7c673cae | 41 | salt_count_ = v; |
11fdf7f2 | 42 | decode(v, p); |
7c673cae | 43 | insert_count_ = v; |
11fdf7f2 | 44 | decode(v, p); |
7c673cae | 45 | target_element_count_ = v; |
11fdf7f2 | 46 | decode(v, p); |
7c673cae | 47 | random_seed_ = v; |
7c673cae FG |
48 | salt_.clear(); |
49 | generate_unique_salt(); | |
20effc67 TL |
50 | decode(bit_table_, p); |
51 | table_size_ = bit_table_.size(); | |
7c673cae FG |
52 | DECODE_FINISH(p); |
53 | } | |
54 | ||
55 | void bloom_filter::dump(Formatter *f) const | |
56 | { | |
57 | f->dump_unsigned("salt_count", salt_count_); | |
58 | f->dump_unsigned("table_size", table_size_); | |
59 | f->dump_unsigned("insert_count", insert_count_); | |
60 | f->dump_unsigned("target_element_count", target_element_count_); | |
61 | f->dump_unsigned("random_seed", random_seed_); | |
62 | ||
63 | f->open_array_section("salt_table"); | |
64 | for (std::vector<bloom_type>::const_iterator i = salt_.begin(); i != salt_.end(); ++i) | |
65 | f->dump_unsigned("salt", *i); | |
66 | f->close_section(); | |
67 | ||
68 | f->open_array_section("bit_table"); | |
20effc67 TL |
69 | for (auto byte : bit_table_) { |
70 | f->dump_unsigned("byte", (unsigned)byte); | |
71 | } | |
7c673cae FG |
72 | f->close_section(); |
73 | } | |
74 | ||
75 | void bloom_filter::generate_test_instances(std::list<bloom_filter*>& ls) | |
76 | { | |
77 | ls.push_back(new bloom_filter(10, .5, 1)); | |
78 | ls.push_back(new bloom_filter(10, .5, 1)); | |
79 | ls.back()->insert("foo"); | |
80 | ls.back()->insert("bar"); | |
81 | ls.push_back(new bloom_filter(50, .5, 1)); | |
82 | ls.back()->insert("foo"); | |
83 | ls.back()->insert("bar"); | |
84 | ls.back()->insert("baz"); | |
85 | ls.back()->insert("boof"); | |
86 | ls.back()->insert("boogggg"); | |
87 | } | |
88 | ||
89 | ||
90 | void compressible_bloom_filter::encode(bufferlist& bl) const | |
91 | { | |
92 | ENCODE_START(2, 2, bl); | |
93 | bloom_filter::encode(bl); | |
94 | ||
95 | uint32_t s = size_list.size(); | |
11fdf7f2 | 96 | encode(s, bl); |
7c673cae FG |
97 | for (std::vector<size_t>::const_iterator p = size_list.begin(); |
98 | p != size_list.end(); ++p) | |
11fdf7f2 | 99 | encode((uint64_t)*p, bl); |
7c673cae FG |
100 | |
101 | ENCODE_FINISH(bl); | |
102 | } | |
103 | ||
11fdf7f2 | 104 | void compressible_bloom_filter::decode(bufferlist::const_iterator& p) |
7c673cae FG |
105 | { |
106 | DECODE_START(2, p); | |
107 | bloom_filter::decode(p); | |
108 | ||
109 | uint32_t s; | |
11fdf7f2 | 110 | decode(s, p); |
7c673cae FG |
111 | size_list.resize(s); |
112 | for (unsigned i = 0; i < s; i++) { | |
113 | uint64_t v; | |
11fdf7f2 | 114 | decode(v, p); |
7c673cae FG |
115 | size_list[i] = v; |
116 | } | |
117 | ||
118 | DECODE_FINISH(p); | |
119 | } | |
120 | ||
121 | void compressible_bloom_filter::dump(Formatter *f) const | |
122 | { | |
123 | bloom_filter::dump(f); | |
124 | ||
125 | f->open_array_section("table_sizes"); | |
126 | for (std::vector<size_t>::const_iterator p = size_list.begin(); | |
127 | p != size_list.end(); ++p) | |
128 | f->dump_unsigned("size", (uint64_t)*p); | |
129 | f->close_section(); | |
130 | } | |
131 | ||
132 | void compressible_bloom_filter::generate_test_instances(std::list<compressible_bloom_filter*>& ls) | |
133 | { | |
134 | ls.push_back(new compressible_bloom_filter(10, .5, 1)); | |
135 | ls.push_back(new compressible_bloom_filter(10, .5, 1)); | |
136 | ls.back()->insert("foo"); | |
137 | ls.back()->insert("bar"); | |
138 | ls.push_back(new compressible_bloom_filter(50, .5, 1)); | |
139 | ls.back()->insert("foo"); | |
140 | ls.back()->insert("bar"); | |
141 | ls.back()->insert("baz"); | |
142 | ls.back()->insert("boof"); | |
143 | ls.back()->compress(20); | |
144 | ls.back()->insert("boogggg"); | |
145 | } |