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 "leveldb/filter_policy.h" 8 #include "util/coding.h" 9 #include "util/hash.h" 10 #include "util/logging.h" 11 #include "util/testharness.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 virtual const char* Name() const { 20 return "TestHashFilter"; 21 } 22 23 virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const { 24 for (int i = 0; i < n; i++) { 25 uint32_t h = Hash(keys[i].data(), keys[i].size(), 1); 26 PutFixed32(dst, h); 27 } 28 } 29 30 virtual bool KeyMayMatch(const Slice& key, const Slice& filter) const { 31 uint32_t h = Hash(key.data(), key.size(), 1); 32 for (size_t i = 0; i + 4 <= filter.size(); i += 4) { 33 if (h == DecodeFixed32(filter.data() + i)) { 34 return true; 35 } 36 } 37 return false; 38 } 39 }; 40 41 class FilterBlockTest { 42 public: 43 TestHashFilter policy_; 44 }; 45 46 TEST(FilterBlockTest, EmptyBuilder) { 47 FilterBlockBuilder builder(&policy_); 48 Slice block = builder.Finish(); 49 ASSERT_EQ("\\x00\\x00\\x00\\x00\\x0b", EscapeString(block)); 50 FilterBlockReader reader(&policy_, block); 51 ASSERT_TRUE(reader.KeyMayMatch(0, "foo")); 52 ASSERT_TRUE(reader.KeyMayMatch(100000, "foo")); 53 } 54 55 TEST(FilterBlockTest, SingleChunk) { 56 FilterBlockBuilder builder(&policy_); 57 builder.StartBlock(100); 58 builder.AddKey("foo"); 59 builder.AddKey("bar"); 60 builder.AddKey("box"); 61 builder.StartBlock(200); 62 builder.AddKey("box"); 63 builder.StartBlock(300); 64 builder.AddKey("hello"); 65 Slice block = builder.Finish(); 66 FilterBlockReader reader(&policy_, block); 67 ASSERT_TRUE(reader.KeyMayMatch(100, "foo")); 68 ASSERT_TRUE(reader.KeyMayMatch(100, "bar")); 69 ASSERT_TRUE(reader.KeyMayMatch(100, "box")); 70 ASSERT_TRUE(reader.KeyMayMatch(100, "hello")); 71 ASSERT_TRUE(reader.KeyMayMatch(100, "foo")); 72 ASSERT_TRUE(! reader.KeyMayMatch(100, "missing")); 73 ASSERT_TRUE(! reader.KeyMayMatch(100, "other")); 74 } 75 76 TEST(FilterBlockTest, MultiChunk) { 77 FilterBlockBuilder builder(&policy_); 78 79 // First filter 80 builder.StartBlock(0); 81 builder.AddKey("foo"); 82 builder.StartBlock(2000); 83 builder.AddKey("bar"); 84 85 // Second filter 86 builder.StartBlock(3100); 87 builder.AddKey("box"); 88 89 // Third filter is empty 90 91 // Last filter 92 builder.StartBlock(9000); 93 builder.AddKey("box"); 94 builder.AddKey("hello"); 95 96 Slice block = builder.Finish(); 97 FilterBlockReader reader(&policy_, block); 98 99 // Check first filter 100 ASSERT_TRUE(reader.KeyMayMatch(0, "foo")); 101 ASSERT_TRUE(reader.KeyMayMatch(2000, "bar")); 102 ASSERT_TRUE(! reader.KeyMayMatch(0, "box")); 103 ASSERT_TRUE(! reader.KeyMayMatch(0, "hello")); 104 105 // Check second filter 106 ASSERT_TRUE(reader.KeyMayMatch(3100, "box")); 107 ASSERT_TRUE(! reader.KeyMayMatch(3100, "foo")); 108 ASSERT_TRUE(! reader.KeyMayMatch(3100, "bar")); 109 ASSERT_TRUE(! reader.KeyMayMatch(3100, "hello")); 110 111 // Check third filter (empty) 112 ASSERT_TRUE(! reader.KeyMayMatch(4100, "foo")); 113 ASSERT_TRUE(! reader.KeyMayMatch(4100, "bar")); 114 ASSERT_TRUE(! reader.KeyMayMatch(4100, "box")); 115 ASSERT_TRUE(! reader.KeyMayMatch(4100, "hello")); 116 117 // Check last filter 118 ASSERT_TRUE(reader.KeyMayMatch(9000, "box")); 119 ASSERT_TRUE(reader.KeyMayMatch(9000, "hello")); 120 ASSERT_TRUE(! reader.KeyMayMatch(9000, "foo")); 121 ASSERT_TRUE(! reader.KeyMayMatch(9000, "bar")); 122 } 123 124 } // namespace leveldb 125 126 int main(int argc, char** argv) { 127 return leveldb::test::RunAllTests(); 128 } 129
