]>
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 | |
494da23a | 23 | void AddKey(const Slice& key) override { |
7c673cae FG |
24 | hash_entries_.push_back(Hash(key.data(), key.size(), 1)); |
25 | } | |
26 | ||
27 | // Generate the filter using the keys that are added | |
494da23a | 28 | Slice Finish(std::unique_ptr<const char[]>* buf) override { |
7c673cae FG |
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 | ||
494da23a | 48 | bool MayMatch(const Slice& entry) override { |
7c673cae FG |
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: | |
494da23a | 66 | const char* Name() const override { return "TestHashFilter"; } |
7c673cae | 67 | |
494da23a | 68 | void CreateFilter(const Slice* keys, int n, std::string* dst) const override { |
7c673cae FG |
69 | for (int i = 0; i < n; i++) { |
70 | uint32_t h = Hash(keys[i].data(), keys[i].size(), 1); | |
71 | PutFixed32(dst, h); | |
72 | } | |
73 | } | |
74 | ||
494da23a | 75 | bool KeyMayMatch(const Slice& key, const Slice& filter) const override { |
7c673cae FG |
76 | uint32_t h = Hash(key.data(), key.size(), 1); |
77 | for (unsigned int i = 0; i + 4 <= filter.size(); i += 4) { | |
78 | if (h == DecodeFixed32(filter.data() + i)) { | |
79 | return true; | |
80 | } | |
81 | } | |
82 | return false; | |
83 | } | |
84 | ||
494da23a | 85 | FilterBitsBuilder* GetFilterBitsBuilder() const override { |
7c673cae FG |
86 | return new TestFilterBitsBuilder(); |
87 | } | |
88 | ||
494da23a | 89 | FilterBitsReader* GetFilterBitsReader(const Slice& contents) const override { |
7c673cae FG |
90 | return new TestFilterBitsReader(contents); |
91 | } | |
92 | }; | |
93 | ||
94 | class PluginFullFilterBlockTest : public testing::Test { | |
95 | public: | |
96 | BlockBasedTableOptions table_options_; | |
97 | ||
98 | PluginFullFilterBlockTest() { | |
99 | table_options_.filter_policy.reset(new TestHashFilter()); | |
100 | } | |
101 | }; | |
102 | ||
103 | TEST_F(PluginFullFilterBlockTest, PluginEmptyBuilder) { | |
104 | FullFilterBlockBuilder builder( | |
105 | nullptr, true, table_options_.filter_policy->GetFilterBitsBuilder()); | |
106 | Slice block = builder.Finish(); | |
107 | ASSERT_EQ("", EscapeString(block)); | |
108 | ||
109 | FullFilterBlockReader reader( | |
110 | nullptr, true, block, | |
111 | table_options_.filter_policy->GetFilterBitsReader(block), nullptr); | |
112 | // Remain same symantic with blockbased filter | |
11fdf7f2 | 113 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr)); |
7c673cae FG |
114 | } |
115 | ||
116 | TEST_F(PluginFullFilterBlockTest, PluginSingleChunk) { | |
117 | FullFilterBlockBuilder builder( | |
118 | nullptr, true, table_options_.filter_policy->GetFilterBitsBuilder()); | |
119 | builder.Add("foo"); | |
120 | builder.Add("bar"); | |
121 | builder.Add("box"); | |
122 | builder.Add("box"); | |
123 | builder.Add("hello"); | |
124 | Slice block = builder.Finish(); | |
125 | FullFilterBlockReader reader( | |
126 | nullptr, true, block, | |
127 | table_options_.filter_policy->GetFilterBitsReader(block), nullptr); | |
11fdf7f2 TL |
128 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr)); |
129 | ASSERT_TRUE(reader.KeyMayMatch("bar", nullptr)); | |
130 | ASSERT_TRUE(reader.KeyMayMatch("box", nullptr)); | |
131 | ASSERT_TRUE(reader.KeyMayMatch("hello", nullptr)); | |
132 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr)); | |
133 | ASSERT_TRUE(!reader.KeyMayMatch("missing", nullptr)); | |
134 | ASSERT_TRUE(!reader.KeyMayMatch("other", nullptr)); | |
7c673cae FG |
135 | } |
136 | ||
137 | class FullFilterBlockTest : public testing::Test { | |
138 | public: | |
139 | BlockBasedTableOptions table_options_; | |
140 | ||
141 | FullFilterBlockTest() { | |
142 | table_options_.filter_policy.reset(NewBloomFilterPolicy(10, false)); | |
143 | } | |
144 | ||
494da23a | 145 | ~FullFilterBlockTest() override {} |
7c673cae FG |
146 | }; |
147 | ||
148 | TEST_F(FullFilterBlockTest, EmptyBuilder) { | |
149 | FullFilterBlockBuilder builder( | |
150 | nullptr, true, table_options_.filter_policy->GetFilterBitsBuilder()); | |
151 | Slice block = builder.Finish(); | |
152 | ASSERT_EQ("", EscapeString(block)); | |
153 | ||
154 | FullFilterBlockReader reader( | |
155 | nullptr, true, block, | |
156 | table_options_.filter_policy->GetFilterBitsReader(block), nullptr); | |
157 | // Remain same symantic with blockbased filter | |
11fdf7f2 TL |
158 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr)); |
159 | } | |
160 | ||
161 | TEST_F(FullFilterBlockTest, DuplicateEntries) { | |
162 | { // empty prefixes | |
163 | std::unique_ptr<const SliceTransform> prefix_extractor( | |
164 | NewFixedPrefixTransform(0)); | |
165 | auto bits_builder = dynamic_cast<FullFilterBitsBuilder*>( | |
166 | table_options_.filter_policy->GetFilterBitsBuilder()); | |
167 | const bool WHOLE_KEY = true; | |
168 | FullFilterBlockBuilder builder(prefix_extractor.get(), WHOLE_KEY, | |
169 | bits_builder); | |
170 | ASSERT_EQ(0, builder.NumAdded()); | |
171 | builder.Add("key"); // test with empty prefix | |
172 | ASSERT_EQ(2, bits_builder->hash_entries_.size()); | |
173 | } | |
174 | ||
175 | // mix of empty and non-empty | |
176 | std::unique_ptr<const SliceTransform> prefix_extractor( | |
177 | NewFixedPrefixTransform(7)); | |
178 | auto bits_builder = dynamic_cast<FullFilterBitsBuilder*>( | |
179 | table_options_.filter_policy->GetFilterBitsBuilder()); | |
180 | const bool WHOLE_KEY = true; | |
181 | FullFilterBlockBuilder builder(prefix_extractor.get(), WHOLE_KEY, | |
182 | bits_builder); | |
183 | ASSERT_EQ(0, builder.NumAdded()); | |
184 | builder.Add(""); // test with empty key too | |
185 | builder.Add("prefix1key1"); | |
186 | builder.Add("prefix1key1"); | |
187 | builder.Add("prefix1key2"); | |
188 | builder.Add("prefix1key3"); | |
189 | builder.Add("prefix2key4"); | |
190 | // two prefix adn 4 keys | |
191 | ASSERT_EQ(1 + 2 + 4, bits_builder->hash_entries_.size()); | |
7c673cae FG |
192 | } |
193 | ||
194 | TEST_F(FullFilterBlockTest, SingleChunk) { | |
195 | FullFilterBlockBuilder builder( | |
196 | nullptr, true, table_options_.filter_policy->GetFilterBitsBuilder()); | |
11fdf7f2 | 197 | ASSERT_EQ(0, builder.NumAdded()); |
7c673cae FG |
198 | builder.Add("foo"); |
199 | builder.Add("bar"); | |
200 | builder.Add("box"); | |
201 | builder.Add("box"); | |
202 | builder.Add("hello"); | |
11fdf7f2 | 203 | ASSERT_EQ(5, builder.NumAdded()); |
7c673cae FG |
204 | Slice block = builder.Finish(); |
205 | FullFilterBlockReader reader( | |
206 | nullptr, true, block, | |
207 | table_options_.filter_policy->GetFilterBitsReader(block), nullptr); | |
11fdf7f2 TL |
208 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr)); |
209 | ASSERT_TRUE(reader.KeyMayMatch("bar", nullptr)); | |
210 | ASSERT_TRUE(reader.KeyMayMatch("box", nullptr)); | |
211 | ASSERT_TRUE(reader.KeyMayMatch("hello", nullptr)); | |
212 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr)); | |
213 | ASSERT_TRUE(!reader.KeyMayMatch("missing", nullptr)); | |
214 | ASSERT_TRUE(!reader.KeyMayMatch("other", nullptr)); | |
7c673cae FG |
215 | } |
216 | ||
217 | } // namespace rocksdb | |
218 | ||
219 | int main(int argc, char** argv) { | |
220 | ::testing::InitGoogleTest(&argc, argv); | |
221 | return RUN_ALL_TESTS(); | |
222 | } |