]>
Commit | Line | Data |
---|---|---|
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" | |
5 | ||
6 | MEMPOOL_DEFINE_FACTORY(unsigned char, byte, bloom_filter); | |
7 | ||
8 | void bloom_filter::encode(bufferlist& bl) const | |
9 | { | |
10 | ENCODE_START(2, 2, bl); | |
11 | ::encode((uint64_t)salt_count_, bl); | |
12 | ::encode((uint64_t)insert_count_, bl); | |
13 | ::encode((uint64_t)target_element_count_, bl); | |
14 | ::encode((uint64_t)random_seed_, bl); | |
15 | bufferptr bp((const char*)bit_table_, table_size_); | |
16 | ::encode(bp, bl); | |
17 | ENCODE_FINISH(bl); | |
18 | } | |
19 | ||
20 | void bloom_filter::decode(bufferlist::iterator& p) | |
21 | { | |
22 | DECODE_START(2, p); | |
23 | uint64_t v; | |
24 | ::decode(v, p); | |
25 | salt_count_ = v; | |
26 | ::decode(v, p); | |
27 | insert_count_ = v; | |
28 | ::decode(v, p); | |
29 | target_element_count_ = v; | |
30 | ::decode(v, p); | |
31 | random_seed_ = v; | |
32 | bufferlist t; | |
33 | ::decode(t, p); | |
34 | ||
35 | salt_.clear(); | |
36 | generate_unique_salt(); | |
37 | table_size_ = t.length(); | |
38 | delete[] bit_table_; | |
39 | if (table_size_) { | |
40 | bit_table_ = new cell_type[table_size_]; | |
41 | t.copy(0, table_size_, (char *)bit_table_); | |
42 | } else { | |
43 | bit_table_ = NULL; | |
44 | } | |
45 | ||
46 | DECODE_FINISH(p); | |
47 | } | |
48 | ||
49 | void bloom_filter::dump(Formatter *f) const | |
50 | { | |
51 | f->dump_unsigned("salt_count", salt_count_); | |
52 | f->dump_unsigned("table_size", table_size_); | |
53 | f->dump_unsigned("insert_count", insert_count_); | |
54 | f->dump_unsigned("target_element_count", target_element_count_); | |
55 | f->dump_unsigned("random_seed", random_seed_); | |
56 | ||
57 | f->open_array_section("salt_table"); | |
58 | for (std::vector<bloom_type>::const_iterator i = salt_.begin(); i != salt_.end(); ++i) | |
59 | f->dump_unsigned("salt", *i); | |
60 | f->close_section(); | |
61 | ||
62 | f->open_array_section("bit_table"); | |
63 | for (unsigned i = 0; i < table_size_; ++i) | |
64 | f->dump_unsigned("byte", (unsigned)bit_table_[i]); | |
65 | f->close_section(); | |
66 | } | |
67 | ||
68 | void bloom_filter::generate_test_instances(std::list<bloom_filter*>& ls) | |
69 | { | |
70 | ls.push_back(new bloom_filter(10, .5, 1)); | |
71 | ls.push_back(new bloom_filter(10, .5, 1)); | |
72 | ls.back()->insert("foo"); | |
73 | ls.back()->insert("bar"); | |
74 | ls.push_back(new bloom_filter(50, .5, 1)); | |
75 | ls.back()->insert("foo"); | |
76 | ls.back()->insert("bar"); | |
77 | ls.back()->insert("baz"); | |
78 | ls.back()->insert("boof"); | |
79 | ls.back()->insert("boogggg"); | |
80 | } | |
81 | ||
82 | ||
83 | void compressible_bloom_filter::encode(bufferlist& bl) const | |
84 | { | |
85 | ENCODE_START(2, 2, bl); | |
86 | bloom_filter::encode(bl); | |
87 | ||
88 | uint32_t s = size_list.size(); | |
89 | ::encode(s, bl); | |
90 | for (std::vector<size_t>::const_iterator p = size_list.begin(); | |
91 | p != size_list.end(); ++p) | |
92 | ::encode((uint64_t)*p, bl); | |
93 | ||
94 | ENCODE_FINISH(bl); | |
95 | } | |
96 | ||
97 | void compressible_bloom_filter::decode(bufferlist::iterator& p) | |
98 | { | |
99 | DECODE_START(2, p); | |
100 | bloom_filter::decode(p); | |
101 | ||
102 | uint32_t s; | |
103 | ::decode(s, p); | |
104 | size_list.resize(s); | |
105 | for (unsigned i = 0; i < s; i++) { | |
106 | uint64_t v; | |
107 | ::decode(v, p); | |
108 | size_list[i] = v; | |
109 | } | |
110 | ||
111 | DECODE_FINISH(p); | |
112 | } | |
113 | ||
114 | void compressible_bloom_filter::dump(Formatter *f) const | |
115 | { | |
116 | bloom_filter::dump(f); | |
117 | ||
118 | f->open_array_section("table_sizes"); | |
119 | for (std::vector<size_t>::const_iterator p = size_list.begin(); | |
120 | p != size_list.end(); ++p) | |
121 | f->dump_unsigned("size", (uint64_t)*p); | |
122 | f->close_section(); | |
123 | } | |
124 | ||
125 | void compressible_bloom_filter::generate_test_instances(std::list<compressible_bloom_filter*>& ls) | |
126 | { | |
127 | ls.push_back(new compressible_bloom_filter(10, .5, 1)); | |
128 | ls.push_back(new compressible_bloom_filter(10, .5, 1)); | |
129 | ls.back()->insert("foo"); | |
130 | ls.back()->insert("bar"); | |
131 | ls.push_back(new compressible_bloom_filter(50, .5, 1)); | |
132 | ls.back()->insert("foo"); | |
133 | ls.back()->insert("bar"); | |
134 | ls.back()->insert("baz"); | |
135 | ls.back()->insert("boof"); | |
136 | ls.back()->compress(20); | |
137 | ls.back()->insert("boogggg"); | |
138 | } |