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
14namespace leveldb {
15
16// For testing: emit an array with one hash value per key
17class 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
41class FilterBlockTest {
42 public:
43  TestHashFilter policy_;
44};
45
46TEST(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
55TEST(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
76TEST(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
126int main(int argc, char** argv) {
127  return leveldb::test::RunAllTests();
128}
129