Inside Bitcoin

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  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 {
40 public:
41  TestHashFilter policy_;
42};
43
44TEST(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(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(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
124int main(int argc, char** argv) { return leveldb::test::RunAllTests(); }
125