1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
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).
6 #include "table/full_filter_block.h"
8 #include "rocksdb/filter_policy.h"
9 #include "table/full_filter_bits_builder.h"
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"
18 class TestFilterBitsBuilder
: public FilterBitsBuilder
{
20 explicit TestFilterBitsBuilder() {}
23 virtual void AddKey(const Slice
& key
) override
{
24 hash_entries_
.push_back(Hash(key
.data(), key
.size(), 1));
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
]);
34 const char* const_data
= data
;
35 buf
->reset(const_data
);
36 return Slice(data
, len
);
40 std::vector
<uint32_t> hash_entries_
;
43 class TestFilterBitsReader
: public FilterBitsReader
{
45 explicit TestFilterBitsReader(const Slice
& contents
)
46 : data_(contents
.data()), len_(static_cast<uint32_t>(contents
.size())) {}
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
)) {
64 class TestHashFilter
: public FilterPolicy
{
66 virtual const char* Name() const override
{ return "TestHashFilter"; }
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);
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
)) {
87 virtual FilterBitsBuilder
* GetFilterBitsBuilder() const override
{
88 return new TestFilterBitsBuilder();
91 virtual FilterBitsReader
* GetFilterBitsReader(const Slice
& contents
)
93 return new TestFilterBitsReader(contents
);
97 class PluginFullFilterBlockTest
: public testing::Test
{
99 BlockBasedTableOptions table_options_
;
101 PluginFullFilterBlockTest() {
102 table_options_
.filter_policy
.reset(new TestHashFilter());
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
));
112 FullFilterBlockReader
reader(
113 nullptr, true, block
,
114 table_options_
.filter_policy
->GetFilterBitsReader(block
), nullptr);
115 // Remain same symantic with blockbased filter
116 ASSERT_TRUE(reader
.KeyMayMatch("foo", nullptr));
119 TEST_F(PluginFullFilterBlockTest
, PluginSingleChunk
) {
120 FullFilterBlockBuilder
builder(
121 nullptr, true, table_options_
.filter_policy
->GetFilterBitsBuilder());
126 builder
.Add("hello");
127 Slice block
= builder
.Finish();
128 FullFilterBlockReader
reader(
129 nullptr, true, block
,
130 table_options_
.filter_policy
->GetFilterBitsReader(block
), nullptr);
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));
140 class FullFilterBlockTest
: public testing::Test
{
142 BlockBasedTableOptions table_options_
;
144 FullFilterBlockTest() {
145 table_options_
.filter_policy
.reset(NewBloomFilterPolicy(10, false));
148 ~FullFilterBlockTest() {}
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
));
157 FullFilterBlockReader
reader(
158 nullptr, true, block
,
159 table_options_
.filter_policy
->GetFilterBitsReader(block
), nullptr);
160 // Remain same symantic with blockbased filter
161 ASSERT_TRUE(reader
.KeyMayMatch("foo", nullptr));
164 TEST_F(FullFilterBlockTest
, DuplicateEntries
) {
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
,
173 ASSERT_EQ(0, builder
.NumAdded());
174 builder
.Add("key"); // test with empty prefix
175 ASSERT_EQ(2, bits_builder
->hash_entries_
.size());
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
,
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());
197 TEST_F(FullFilterBlockTest
, SingleChunk
) {
198 FullFilterBlockBuilder
builder(
199 nullptr, true, table_options_
.filter_policy
->GetFilterBitsBuilder());
200 ASSERT_EQ(0, builder
.NumAdded());
205 builder
.Add("hello");
206 ASSERT_EQ(5, builder
.NumAdded());
207 Slice block
= builder
.Finish();
208 FullFilterBlockReader
reader(
209 nullptr, true, block
,
210 table_options_
.filter_policy
->GetFilterBitsReader(block
), nullptr);
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));
220 } // namespace rocksdb
222 int main(int argc
, char** argv
) {
223 ::testing::InitGoogleTest(&argc
, argv
);
224 return RUN_ALL_TESTS();