]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
2 | // This source code is licensed under both the GPLv2 (found in the |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
7c673cae FG |
5 | |
6 | #include "table/full_filter_block.h" | |
7 | ||
8 | #include "rocksdb/filter_policy.h" | |
11fdf7f2 | 9 | #include "table/full_filter_bits_builder.h" |
7c673cae FG |
10 | #include "util/coding.h" |
11 | #include "util/hash.h" | |
12 | #include "util/string_util.h" | |
13 | #include "util/testharness.h" | |
14 | #include "util/testutil.h" | |
15 | ||
16 | namespace rocksdb { | |
17 | ||
18 | class TestFilterBitsBuilder : public FilterBitsBuilder { | |
19 | public: | |
20 | explicit TestFilterBitsBuilder() {} | |
21 | ||
22 | // Add Key to filter | |
23 | virtual void AddKey(const Slice& key) override { | |
24 | hash_entries_.push_back(Hash(key.data(), key.size(), 1)); | |
25 | } | |
26 | ||
27 | // Generate the filter using the keys that are added | |
28 | virtual Slice Finish(std::unique_ptr<const char[]>* buf) override { | |
29 | uint32_t len = static_cast<uint32_t>(hash_entries_.size()) * 4; | |
30 | char* data = new char[len]; | |
31 | for (size_t i = 0; i < hash_entries_.size(); i++) { | |
32 | EncodeFixed32(data + i * 4, hash_entries_[i]); | |
33 | } | |
34 | const char* const_data = data; | |
35 | buf->reset(const_data); | |
36 | return Slice(data, len); | |
37 | } | |
38 | ||
39 | private: | |
40 | std::vector<uint32_t> hash_entries_; | |
41 | }; | |
42 | ||
43 | class TestFilterBitsReader : public FilterBitsReader { | |
44 | public: | |
45 | explicit TestFilterBitsReader(const Slice& contents) | |
46 | : data_(contents.data()), len_(static_cast<uint32_t>(contents.size())) {} | |
47 | ||
48 | virtual bool MayMatch(const Slice& entry) override { | |
49 | uint32_t h = Hash(entry.data(), entry.size(), 1); | |
50 | for (size_t i = 0; i + 4 <= len_; i += 4) { | |
51 | if (h == DecodeFixed32(data_ + i)) { | |
52 | return true; | |
53 | } | |
54 | } | |
55 | return false; | |
56 | } | |
57 | ||
58 | private: | |
59 | const char* data_; | |
60 | uint32_t len_; | |
61 | }; | |
62 | ||
63 | ||
64 | class TestHashFilter : public FilterPolicy { | |
65 | public: | |
66 | virtual const char* Name() const override { return "TestHashFilter"; } | |
67 | ||
68 | virtual void CreateFilter(const Slice* keys, int n, | |
69 | std::string* dst) const override { | |
70 | for (int i = 0; i < n; i++) { | |
71 | uint32_t h = Hash(keys[i].data(), keys[i].size(), 1); | |
72 | PutFixed32(dst, h); | |
73 | } | |
74 | } | |
75 | ||
76 | virtual bool KeyMayMatch(const Slice& key, | |
77 | const Slice& filter) const override { | |
78 | uint32_t h = Hash(key.data(), key.size(), 1); | |
79 | for (unsigned int i = 0; i + 4 <= filter.size(); i += 4) { | |
80 | if (h == DecodeFixed32(filter.data() + i)) { | |
81 | return true; | |
82 | } | |
83 | } | |
84 | return false; | |
85 | } | |
86 | ||
87 | virtual FilterBitsBuilder* GetFilterBitsBuilder() const override { | |
88 | return new TestFilterBitsBuilder(); | |
89 | } | |
90 | ||
91 | virtual FilterBitsReader* GetFilterBitsReader(const Slice& contents) | |
92 | const override { | |
93 | return new TestFilterBitsReader(contents); | |
94 | } | |
95 | }; | |
96 | ||
97 | class PluginFullFilterBlockTest : public testing::Test { | |
98 | public: | |
99 | BlockBasedTableOptions table_options_; | |
100 | ||
101 | PluginFullFilterBlockTest() { | |
102 | table_options_.filter_policy.reset(new TestHashFilter()); | |
103 | } | |
104 | }; | |
105 | ||
106 | TEST_F(PluginFullFilterBlockTest, PluginEmptyBuilder) { | |
107 | FullFilterBlockBuilder builder( | |
108 | nullptr, true, table_options_.filter_policy->GetFilterBitsBuilder()); | |
109 | Slice block = builder.Finish(); | |
110 | ASSERT_EQ("", EscapeString(block)); | |
111 | ||
112 | FullFilterBlockReader reader( | |
113 | nullptr, true, block, | |
114 | table_options_.filter_policy->GetFilterBitsReader(block), nullptr); | |
115 | // Remain same symantic with blockbased filter | |
11fdf7f2 | 116 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr)); |
7c673cae FG |
117 | } |
118 | ||
119 | TEST_F(PluginFullFilterBlockTest, PluginSingleChunk) { | |
120 | FullFilterBlockBuilder builder( | |
121 | nullptr, true, table_options_.filter_policy->GetFilterBitsBuilder()); | |
122 | builder.Add("foo"); | |
123 | builder.Add("bar"); | |
124 | builder.Add("box"); | |
125 | builder.Add("box"); | |
126 | builder.Add("hello"); | |
127 | Slice block = builder.Finish(); | |
128 | FullFilterBlockReader reader( | |
129 | nullptr, true, block, | |
130 | table_options_.filter_policy->GetFilterBitsReader(block), nullptr); | |
11fdf7f2 TL |
131 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr)); |
132 | ASSERT_TRUE(reader.KeyMayMatch("bar", nullptr)); | |
133 | ASSERT_TRUE(reader.KeyMayMatch("box", nullptr)); | |
134 | ASSERT_TRUE(reader.KeyMayMatch("hello", nullptr)); | |
135 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr)); | |
136 | ASSERT_TRUE(!reader.KeyMayMatch("missing", nullptr)); | |
137 | ASSERT_TRUE(!reader.KeyMayMatch("other", nullptr)); | |
7c673cae FG |
138 | } |
139 | ||
140 | class FullFilterBlockTest : public testing::Test { | |
141 | public: | |
142 | BlockBasedTableOptions table_options_; | |
143 | ||
144 | FullFilterBlockTest() { | |
145 | table_options_.filter_policy.reset(NewBloomFilterPolicy(10, false)); | |
146 | } | |
147 | ||
148 | ~FullFilterBlockTest() {} | |
149 | }; | |
150 | ||
151 | TEST_F(FullFilterBlockTest, EmptyBuilder) { | |
152 | FullFilterBlockBuilder builder( | |
153 | nullptr, true, table_options_.filter_policy->GetFilterBitsBuilder()); | |
154 | Slice block = builder.Finish(); | |
155 | ASSERT_EQ("", EscapeString(block)); | |
156 | ||
157 | FullFilterBlockReader reader( | |
158 | nullptr, true, block, | |
159 | table_options_.filter_policy->GetFilterBitsReader(block), nullptr); | |
160 | // Remain same symantic with blockbased filter | |
11fdf7f2 TL |
161 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr)); |
162 | } | |
163 | ||
164 | TEST_F(FullFilterBlockTest, DuplicateEntries) { | |
165 | { // empty prefixes | |
166 | std::unique_ptr<const SliceTransform> prefix_extractor( | |
167 | NewFixedPrefixTransform(0)); | |
168 | auto bits_builder = dynamic_cast<FullFilterBitsBuilder*>( | |
169 | table_options_.filter_policy->GetFilterBitsBuilder()); | |
170 | const bool WHOLE_KEY = true; | |
171 | FullFilterBlockBuilder builder(prefix_extractor.get(), WHOLE_KEY, | |
172 | bits_builder); | |
173 | ASSERT_EQ(0, builder.NumAdded()); | |
174 | builder.Add("key"); // test with empty prefix | |
175 | ASSERT_EQ(2, bits_builder->hash_entries_.size()); | |
176 | } | |
177 | ||
178 | // mix of empty and non-empty | |
179 | std::unique_ptr<const SliceTransform> prefix_extractor( | |
180 | NewFixedPrefixTransform(7)); | |
181 | auto bits_builder = dynamic_cast<FullFilterBitsBuilder*>( | |
182 | table_options_.filter_policy->GetFilterBitsBuilder()); | |
183 | const bool WHOLE_KEY = true; | |
184 | FullFilterBlockBuilder builder(prefix_extractor.get(), WHOLE_KEY, | |
185 | bits_builder); | |
186 | ASSERT_EQ(0, builder.NumAdded()); | |
187 | builder.Add(""); // test with empty key too | |
188 | builder.Add("prefix1key1"); | |
189 | builder.Add("prefix1key1"); | |
190 | builder.Add("prefix1key2"); | |
191 | builder.Add("prefix1key3"); | |
192 | builder.Add("prefix2key4"); | |
193 | // two prefix adn 4 keys | |
194 | ASSERT_EQ(1 + 2 + 4, bits_builder->hash_entries_.size()); | |
7c673cae FG |
195 | } |
196 | ||
197 | TEST_F(FullFilterBlockTest, SingleChunk) { | |
198 | FullFilterBlockBuilder builder( | |
199 | nullptr, true, table_options_.filter_policy->GetFilterBitsBuilder()); | |
11fdf7f2 | 200 | ASSERT_EQ(0, builder.NumAdded()); |
7c673cae FG |
201 | builder.Add("foo"); |
202 | builder.Add("bar"); | |
203 | builder.Add("box"); | |
204 | builder.Add("box"); | |
205 | builder.Add("hello"); | |
11fdf7f2 | 206 | ASSERT_EQ(5, builder.NumAdded()); |
7c673cae FG |
207 | Slice block = builder.Finish(); |
208 | FullFilterBlockReader reader( | |
209 | nullptr, true, block, | |
210 | table_options_.filter_policy->GetFilterBitsReader(block), nullptr); | |
11fdf7f2 TL |
211 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr)); |
212 | ASSERT_TRUE(reader.KeyMayMatch("bar", nullptr)); | |
213 | ASSERT_TRUE(reader.KeyMayMatch("box", nullptr)); | |
214 | ASSERT_TRUE(reader.KeyMayMatch("hello", nullptr)); | |
215 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr)); | |
216 | ASSERT_TRUE(!reader.KeyMayMatch("missing", nullptr)); | |
217 | ASSERT_TRUE(!reader.KeyMayMatch("other", nullptr)); | |
7c673cae FG |
218 | } |
219 | ||
220 | } // namespace rocksdb | |
221 | ||
222 | int main(int argc, char** argv) { | |
223 | ::testing::InitGoogleTest(&argc, argv); | |
224 | return RUN_ALL_TESTS(); | |
225 | } |