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
14namespace leveldb {
15
16// For testing: emit an array with one hash value per key
17class 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
39class FilterBlockTest : public testing::Test {
40 public:
41 TestHashFilter policy_;
42};
43
44TEST_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
53TEST_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
74TEST_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