1 | // Copyright (c) 2012 The LevelDB Authors. All rights reserved. |
2 | // Use of this source code is governed by a BSD-style license that can be |
3 | // found in the LICENSE file. See the AUTHORS file for names of contributors. |
4 | |
5 | #include "table/filter_block.h" |
6 | |
7 | #include "gtest/gtest.h" |
8 | #include "leveldb/filter_policy.h" |
9 | #include "util/coding.h" |
10 | #include "util/hash.h" |
11 | #include "util/logging.h" |
12 | #include "util/testutil.h" |
13 | |
14 | namespace leveldb { |
15 | |
16 | // For testing: emit an array with one hash value per key |
17 | class TestHashFilter : public FilterPolicy { |
18 | public: |
19 | const char* Name() const override { return "TestHashFilter" ; } |
20 | |
21 | void CreateFilter(const Slice* keys, int n, std::string* dst) const override { |
22 | for (int i = 0; i < n; i++) { |
23 | uint32_t h = Hash(keys[i].data(), keys[i].size(), 1); |
24 | PutFixed32(dst, h); |
25 | } |
26 | } |
27 | |
28 | bool KeyMayMatch(const Slice& key, const Slice& filter) const override { |
29 | uint32_t h = Hash(key.data(), key.size(), 1); |
30 | for (size_t i = 0; i + 4 <= filter.size(); i += 4) { |
31 | if (h == DecodeFixed32(filter.data() + i)) { |
32 | return true; |
33 | } |
34 | } |
35 | return false; |
36 | } |
37 | }; |
38 | |
39 | class FilterBlockTest : public testing::Test { |
40 | public: |
41 | TestHashFilter policy_; |
42 | }; |
43 | |
44 | TEST_F(FilterBlockTest, EmptyBuilder) { |
45 | FilterBlockBuilder builder(&policy_); |
46 | Slice block = builder.Finish(); |
47 | ASSERT_EQ("\\x00\\x00\\x00\\x00\\x0b" , EscapeString(block)); |
48 | FilterBlockReader reader(&policy_, block); |
49 | ASSERT_TRUE(reader.KeyMayMatch(0, "foo" )); |
50 | ASSERT_TRUE(reader.KeyMayMatch(100000, "foo" )); |
51 | } |
52 | |
53 | TEST_F(FilterBlockTest, SingleChunk) { |
54 | FilterBlockBuilder builder(&policy_); |
55 | builder.StartBlock(100); |
56 | builder.AddKey("foo" ); |
57 | builder.AddKey("bar" ); |
58 | builder.AddKey("box" ); |
59 | builder.StartBlock(200); |
60 | builder.AddKey("box" ); |
61 | builder.StartBlock(300); |
62 | builder.AddKey("hello" ); |
63 | Slice block = builder.Finish(); |
64 | FilterBlockReader reader(&policy_, block); |
65 | ASSERT_TRUE(reader.KeyMayMatch(100, "foo" )); |
66 | ASSERT_TRUE(reader.KeyMayMatch(100, "bar" )); |
67 | ASSERT_TRUE(reader.KeyMayMatch(100, "box" )); |
68 | ASSERT_TRUE(reader.KeyMayMatch(100, "hello" )); |
69 | ASSERT_TRUE(reader.KeyMayMatch(100, "foo" )); |
70 | ASSERT_TRUE(!reader.KeyMayMatch(100, "missing" )); |
71 | ASSERT_TRUE(!reader.KeyMayMatch(100, "other" )); |
72 | } |
73 | |
74 | TEST_F(FilterBlockTest, MultiChunk) { |
75 | FilterBlockBuilder builder(&policy_); |
76 | |
77 | // First filter |
78 | builder.StartBlock(0); |
79 | builder.AddKey("foo" ); |
80 | builder.StartBlock(2000); |
81 | builder.AddKey("bar" ); |
82 | |
83 | // Second filter |
84 | builder.StartBlock(3100); |
85 | builder.AddKey("box" ); |
86 | |
87 | // Third filter is empty |
88 | |
89 | // Last filter |
90 | builder.StartBlock(9000); |
91 | builder.AddKey("box" ); |
92 | builder.AddKey("hello" ); |
93 | |
94 | Slice block = builder.Finish(); |
95 | FilterBlockReader reader(&policy_, block); |
96 | |
97 | // Check first filter |
98 | ASSERT_TRUE(reader.KeyMayMatch(0, "foo" )); |
99 | ASSERT_TRUE(reader.KeyMayMatch(2000, "bar" )); |
100 | ASSERT_TRUE(!reader.KeyMayMatch(0, "box" )); |
101 | ASSERT_TRUE(!reader.KeyMayMatch(0, "hello" )); |
102 | |
103 | // Check second filter |
104 | ASSERT_TRUE(reader.KeyMayMatch(3100, "box" )); |
105 | ASSERT_TRUE(!reader.KeyMayMatch(3100, "foo" )); |
106 | ASSERT_TRUE(!reader.KeyMayMatch(3100, "bar" )); |
107 | ASSERT_TRUE(!reader.KeyMayMatch(3100, "hello" )); |
108 | |
109 | // Check third filter (empty) |
110 | ASSERT_TRUE(!reader.KeyMayMatch(4100, "foo" )); |
111 | ASSERT_TRUE(!reader.KeyMayMatch(4100, "bar" )); |
112 | ASSERT_TRUE(!reader.KeyMayMatch(4100, "box" )); |
113 | ASSERT_TRUE(!reader.KeyMayMatch(4100, "hello" )); |
114 | |
115 | // Check last filter |
116 | ASSERT_TRUE(reader.KeyMayMatch(9000, "box" )); |
117 | ASSERT_TRUE(reader.KeyMayMatch(9000, "hello" )); |
118 | ASSERT_TRUE(!reader.KeyMayMatch(9000, "foo" )); |
119 | ASSERT_TRUE(!reader.KeyMayMatch(9000, "bar" )); |
120 | } |
121 | |
122 | } // namespace leveldb |
123 | |