]>
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 | // Copyright (c) 2012 The LevelDB Authors. All rights reserved. | |
7 | // Use of this source code is governed by a BSD-style license that can be | |
8 | // found in the LICENSE file. See the AUTHORS file for names of contributors. | |
9 | ||
10 | #include "table/block_based_filter_block.h" | |
11 | ||
12 | #include "rocksdb/filter_policy.h" | |
13 | #include "util/coding.h" | |
14 | #include "util/hash.h" | |
15 | #include "util/string_util.h" | |
16 | #include "util/testharness.h" | |
17 | #include "util/testutil.h" | |
18 | ||
19 | namespace rocksdb { | |
20 | ||
21 | // For testing: emit an array with one hash value per key | |
22 | class TestHashFilter : public FilterPolicy { | |
23 | public: | |
24 | virtual const char* Name() const override { return "TestHashFilter"; } | |
25 | ||
26 | virtual void CreateFilter(const Slice* keys, int n, | |
27 | std::string* dst) const override { | |
28 | for (int i = 0; i < n; i++) { | |
29 | uint32_t h = Hash(keys[i].data(), keys[i].size(), 1); | |
30 | PutFixed32(dst, h); | |
31 | } | |
32 | } | |
33 | ||
34 | virtual bool KeyMayMatch(const Slice& key, | |
35 | const Slice& filter) const override { | |
36 | uint32_t h = Hash(key.data(), key.size(), 1); | |
37 | for (unsigned int i = 0; i + 4 <= filter.size(); i += 4) { | |
38 | if (h == DecodeFixed32(filter.data() + i)) { | |
39 | return true; | |
40 | } | |
41 | } | |
42 | return false; | |
43 | } | |
44 | }; | |
45 | ||
46 | class FilterBlockTest : public testing::Test { | |
47 | public: | |
48 | TestHashFilter policy_; | |
49 | BlockBasedTableOptions table_options_; | |
50 | ||
51 | FilterBlockTest() { | |
52 | table_options_.filter_policy.reset(new TestHashFilter()); | |
53 | } | |
54 | }; | |
55 | ||
56 | TEST_F(FilterBlockTest, EmptyBuilder) { | |
57 | BlockBasedFilterBlockBuilder builder(nullptr, table_options_); | |
58 | BlockContents block(builder.Finish(), false, kNoCompression); | |
59 | ASSERT_EQ("\\x00\\x00\\x00\\x00\\x0b", EscapeString(block.data)); | |
60 | BlockBasedFilterBlockReader reader(nullptr, table_options_, true, | |
61 | std::move(block), nullptr); | |
11fdf7f2 TL |
62 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr, uint64_t{0})); |
63 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr, 100000)); | |
7c673cae FG |
64 | } |
65 | ||
66 | TEST_F(FilterBlockTest, SingleChunk) { | |
67 | BlockBasedFilterBlockBuilder builder(nullptr, table_options_); | |
11fdf7f2 | 68 | ASSERT_EQ(0, builder.NumAdded()); |
7c673cae FG |
69 | builder.StartBlock(100); |
70 | builder.Add("foo"); | |
71 | builder.Add("bar"); | |
72 | builder.Add("box"); | |
73 | builder.StartBlock(200); | |
74 | builder.Add("box"); | |
75 | builder.StartBlock(300); | |
76 | builder.Add("hello"); | |
11fdf7f2 | 77 | ASSERT_EQ(5, builder.NumAdded()); |
7c673cae FG |
78 | BlockContents block(builder.Finish(), false, kNoCompression); |
79 | BlockBasedFilterBlockReader reader(nullptr, table_options_, true, | |
80 | std::move(block), nullptr); | |
11fdf7f2 TL |
81 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr, 100)); |
82 | ASSERT_TRUE(reader.KeyMayMatch("bar", nullptr, 100)); | |
83 | ASSERT_TRUE(reader.KeyMayMatch("box", nullptr, 100)); | |
84 | ASSERT_TRUE(reader.KeyMayMatch("hello", nullptr, 100)); | |
85 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr, 100)); | |
86 | ASSERT_TRUE(!reader.KeyMayMatch("missing", nullptr, 100)); | |
87 | ASSERT_TRUE(!reader.KeyMayMatch("other", nullptr, 100)); | |
7c673cae FG |
88 | } |
89 | ||
90 | TEST_F(FilterBlockTest, MultiChunk) { | |
91 | BlockBasedFilterBlockBuilder builder(nullptr, table_options_); | |
92 | ||
93 | // First filter | |
94 | builder.StartBlock(0); | |
95 | builder.Add("foo"); | |
96 | builder.StartBlock(2000); | |
97 | builder.Add("bar"); | |
98 | ||
99 | // Second filter | |
100 | builder.StartBlock(3100); | |
101 | builder.Add("box"); | |
102 | ||
103 | // Third filter is empty | |
104 | ||
105 | // Last filter | |
106 | builder.StartBlock(9000); | |
107 | builder.Add("box"); | |
108 | builder.Add("hello"); | |
109 | ||
110 | BlockContents block(builder.Finish(), false, kNoCompression); | |
111 | BlockBasedFilterBlockReader reader(nullptr, table_options_, true, | |
112 | std::move(block), nullptr); | |
113 | ||
114 | // Check first filter | |
11fdf7f2 TL |
115 | ASSERT_TRUE(reader.KeyMayMatch("foo", nullptr, uint64_t{0})); |
116 | ASSERT_TRUE(reader.KeyMayMatch("bar", nullptr, 2000)); | |
117 | ASSERT_TRUE(!reader.KeyMayMatch("box", nullptr, uint64_t{0})); | |
118 | ASSERT_TRUE(!reader.KeyMayMatch("hello", nullptr, uint64_t{0})); | |
7c673cae FG |
119 | |
120 | // Check second filter | |
11fdf7f2 TL |
121 | ASSERT_TRUE(reader.KeyMayMatch("box", nullptr, 3100)); |
122 | ASSERT_TRUE(!reader.KeyMayMatch("foo", nullptr, 3100)); | |
123 | ASSERT_TRUE(!reader.KeyMayMatch("bar", nullptr, 3100)); | |
124 | ASSERT_TRUE(!reader.KeyMayMatch("hello", nullptr, 3100)); | |
7c673cae FG |
125 | |
126 | // Check third filter (empty) | |
11fdf7f2 TL |
127 | ASSERT_TRUE(!reader.KeyMayMatch("foo", nullptr, 4100)); |
128 | ASSERT_TRUE(!reader.KeyMayMatch("bar", nullptr, 4100)); | |
129 | ASSERT_TRUE(!reader.KeyMayMatch("box", nullptr, 4100)); | |
130 | ASSERT_TRUE(!reader.KeyMayMatch("hello", nullptr, 4100)); | |
7c673cae FG |
131 | |
132 | // Check last filter | |
11fdf7f2 TL |
133 | ASSERT_TRUE(reader.KeyMayMatch("box", nullptr, 9000)); |
134 | ASSERT_TRUE(reader.KeyMayMatch("hello", nullptr, 9000)); | |
135 | ASSERT_TRUE(!reader.KeyMayMatch("foo", nullptr, 9000)); | |
136 | ASSERT_TRUE(!reader.KeyMayMatch("bar", nullptr, 9000)); | |
7c673cae FG |
137 | } |
138 | ||
139 | // Test for block based filter block | |
140 | // use new interface in FilterPolicy to create filter builder/reader | |
141 | class BlockBasedFilterBlockTest : public testing::Test { | |
142 | public: | |
143 | BlockBasedTableOptions table_options_; | |
144 | ||
145 | BlockBasedFilterBlockTest() { | |
146 | table_options_.filter_policy.reset(NewBloomFilterPolicy(10)); | |
147 | } | |
148 | ||
149 | ~BlockBasedFilterBlockTest() {} | |
150 | }; | |
151 | ||
152 | TEST_F(BlockBasedFilterBlockTest, BlockBasedEmptyBuilder) { | |
153 | FilterBlockBuilder* builder = new BlockBasedFilterBlockBuilder( | |
154 | nullptr, table_options_); | |
155 | BlockContents block(builder->Finish(), false, kNoCompression); | |
156 | ASSERT_EQ("\\x00\\x00\\x00\\x00\\x0b", EscapeString(block.data)); | |
157 | FilterBlockReader* reader = new BlockBasedFilterBlockReader( | |
158 | nullptr, table_options_, true, std::move(block), nullptr); | |
11fdf7f2 TL |
159 | ASSERT_TRUE(reader->KeyMayMatch("foo", nullptr, uint64_t{0})); |
160 | ASSERT_TRUE(reader->KeyMayMatch("foo", nullptr, 100000)); | |
7c673cae FG |
161 | |
162 | delete builder; | |
163 | delete reader; | |
164 | } | |
165 | ||
166 | TEST_F(BlockBasedFilterBlockTest, BlockBasedSingleChunk) { | |
167 | FilterBlockBuilder* builder = new BlockBasedFilterBlockBuilder( | |
168 | nullptr, table_options_); | |
169 | builder->StartBlock(100); | |
170 | builder->Add("foo"); | |
171 | builder->Add("bar"); | |
172 | builder->Add("box"); | |
173 | builder->StartBlock(200); | |
174 | builder->Add("box"); | |
175 | builder->StartBlock(300); | |
176 | builder->Add("hello"); | |
177 | BlockContents block(builder->Finish(), false, kNoCompression); | |
178 | FilterBlockReader* reader = new BlockBasedFilterBlockReader( | |
179 | nullptr, table_options_, true, std::move(block), nullptr); | |
11fdf7f2 TL |
180 | ASSERT_TRUE(reader->KeyMayMatch("foo", nullptr, 100)); |
181 | ASSERT_TRUE(reader->KeyMayMatch("bar", nullptr, 100)); | |
182 | ASSERT_TRUE(reader->KeyMayMatch("box", nullptr, 100)); | |
183 | ASSERT_TRUE(reader->KeyMayMatch("hello", nullptr, 100)); | |
184 | ASSERT_TRUE(reader->KeyMayMatch("foo", nullptr, 100)); | |
185 | ASSERT_TRUE(!reader->KeyMayMatch("missing", nullptr, 100)); | |
186 | ASSERT_TRUE(!reader->KeyMayMatch("other", nullptr, 100)); | |
7c673cae FG |
187 | |
188 | delete builder; | |
189 | delete reader; | |
190 | } | |
191 | ||
192 | TEST_F(BlockBasedFilterBlockTest, BlockBasedMultiChunk) { | |
193 | FilterBlockBuilder* builder = new BlockBasedFilterBlockBuilder( | |
194 | nullptr, table_options_); | |
195 | ||
196 | // First filter | |
197 | builder->StartBlock(0); | |
198 | builder->Add("foo"); | |
199 | builder->StartBlock(2000); | |
200 | builder->Add("bar"); | |
201 | ||
202 | // Second filter | |
203 | builder->StartBlock(3100); | |
204 | builder->Add("box"); | |
205 | ||
206 | // Third filter is empty | |
207 | ||
208 | // Last filter | |
209 | builder->StartBlock(9000); | |
210 | builder->Add("box"); | |
211 | builder->Add("hello"); | |
212 | ||
213 | BlockContents block(builder->Finish(), false, kNoCompression); | |
214 | FilterBlockReader* reader = new BlockBasedFilterBlockReader( | |
215 | nullptr, table_options_, true, std::move(block), nullptr); | |
216 | ||
217 | // Check first filter | |
11fdf7f2 TL |
218 | ASSERT_TRUE(reader->KeyMayMatch("foo", nullptr, uint64_t{0})); |
219 | ASSERT_TRUE(reader->KeyMayMatch("bar", nullptr, 2000)); | |
220 | ASSERT_TRUE(!reader->KeyMayMatch("box", nullptr, uint64_t{0})); | |
221 | ASSERT_TRUE(!reader->KeyMayMatch("hello", nullptr, uint64_t{0})); | |
7c673cae FG |
222 | |
223 | // Check second filter | |
11fdf7f2 TL |
224 | ASSERT_TRUE(reader->KeyMayMatch("box", nullptr, 3100)); |
225 | ASSERT_TRUE(!reader->KeyMayMatch("foo", nullptr, 3100)); | |
226 | ASSERT_TRUE(!reader->KeyMayMatch("bar", nullptr, 3100)); | |
227 | ASSERT_TRUE(!reader->KeyMayMatch("hello", nullptr, 3100)); | |
7c673cae FG |
228 | |
229 | // Check third filter (empty) | |
11fdf7f2 TL |
230 | ASSERT_TRUE(!reader->KeyMayMatch("foo", nullptr, 4100)); |
231 | ASSERT_TRUE(!reader->KeyMayMatch("bar", nullptr, 4100)); | |
232 | ASSERT_TRUE(!reader->KeyMayMatch("box", nullptr, 4100)); | |
233 | ASSERT_TRUE(!reader->KeyMayMatch("hello", nullptr, 4100)); | |
7c673cae FG |
234 | |
235 | // Check last filter | |
11fdf7f2 TL |
236 | ASSERT_TRUE(reader->KeyMayMatch("box", nullptr, 9000)); |
237 | ASSERT_TRUE(reader->KeyMayMatch("hello", nullptr, 9000)); | |
238 | ASSERT_TRUE(!reader->KeyMayMatch("foo", nullptr, 9000)); | |
239 | ASSERT_TRUE(!reader->KeyMayMatch("bar", nullptr, 9000)); | |
7c673cae FG |
240 | |
241 | delete builder; | |
242 | delete reader; | |
243 | } | |
244 | ||
245 | } // namespace rocksdb | |
246 | ||
247 | int main(int argc, char** argv) { | |
248 | ::testing::InitGoogleTest(&argc, argv); | |
249 | return RUN_ALL_TESTS(); | |
250 | } |