ceph/src/rocksdb/table/full_filter_block_test.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under the BSD-style license found in the
   3 //  LICENSE file in the root directory of this source tree. An additional grant
   4 //  of patent rights can be found in the PATENTS file in the same directory.
   5
   6 #include "table/full_filter_block.h"
   7
   8 #include "rocksdb/filter_policy.h"
   9 #include "util/coding.h"
  10 #include "util/hash.h"
  11 #include "util/string_util.h"
  12 #include "util/testharness.h"
  13 #include "util/testutil.h"
  14
  15 namespace rocksdb {
  16
  17 class TestFilterBitsBuilder : public FilterBitsBuilder {
  18  public:
  19   explicit TestFilterBitsBuilder() {}
  20
  21   // Add Key to filter
  22   virtual void AddKey(const Slice& key) override {
  23     hash_entries_.push_back(Hash(key.data(), key.size(), 1));
  24   }
  25
  26   // Generate the filter using the keys that are added
  27   virtual Slice Finish(std::unique_ptr<const char[]>* buf) override {
  28     uint32_t len = static_cast<uint32_t>(hash_entries_.size()) * 4;
  29     char* data = new char[len];
  30     for (size_t i = 0; i < hash_entries_.size(); i++) {
  31       EncodeFixed32(data + i * 4, hash_entries_[i]);
  32     }
  33     const char* const_data = data;
  34     buf->reset(const_data);
  35     return Slice(data, len);
  36   }
  37
  38  private:
  39   std::vector<uint32_t> hash_entries_;
  40 };
  41
  42 class TestFilterBitsReader : public FilterBitsReader {
  43  public:
  44   explicit TestFilterBitsReader(const Slice& contents)
  45       : data_(contents.data()), len_(static_cast<uint32_t>(contents.size())) {}
  46
  47   virtual bool MayMatch(const Slice& entry) override {
  48     uint32_t h = Hash(entry.data(), entry.size(), 1);
  49     for (size_t i = 0; i + 4 <= len_; i += 4) {
  50       if (h == DecodeFixed32(data_ + i)) {
  51         return true;
  52       }
  53     }
  54     return false;
  55   }
  56
  57  private:
  58   const char* data_;
  59   uint32_t len_;
  60 };
  61
  62
  63 class TestHashFilter : public FilterPolicy {
  64  public:
  65   virtual const char* Name() const override { return "TestHashFilter"; }
  66
  67   virtual void CreateFilter(const Slice* keys, int n,
  68                             std::string* dst) const override {
  69     for (int i = 0; i < n; i++) {
  70       uint32_t h = Hash(keys[i].data(), keys[i].size(), 1);
  71       PutFixed32(dst, h);
  72     }
  73   }
  74
  75   virtual bool KeyMayMatch(const Slice& key,
  76                            const Slice& filter) const override {
  77     uint32_t h = Hash(key.data(), key.size(), 1);
  78     for (unsigned int i = 0; i + 4 <= filter.size(); i += 4) {
  79       if (h == DecodeFixed32(filter.data() + i)) {
  80         return true;
  81       }
  82     }
  83     return false;
  84   }
  85
  86   virtual FilterBitsBuilder* GetFilterBitsBuilder() const override {
  87     return new TestFilterBitsBuilder();
  88   }
  89
  90   virtual FilterBitsReader* GetFilterBitsReader(const Slice& contents)
  91       const override {
  92     return new TestFilterBitsReader(contents);
  93   }
  94 };
  95
  96 class PluginFullFilterBlockTest : public testing::Test {
  97  public:
  98   BlockBasedTableOptions table_options_;
  99
 100   PluginFullFilterBlockTest() {
 101     table_options_.filter_policy.reset(new TestHashFilter());
 102   }
 103 };
 104
 105 TEST_F(PluginFullFilterBlockTest, PluginEmptyBuilder) {
 106   FullFilterBlockBuilder builder(
 107       nullptr, true, table_options_.filter_policy->GetFilterBitsBuilder());
 108   Slice block = builder.Finish();
 109   ASSERT_EQ("", EscapeString(block));
 110
 111   FullFilterBlockReader reader(
 112       nullptr, true, block,
 113       table_options_.filter_policy->GetFilterBitsReader(block), nullptr);
 114   // Remain same symantic with blockbased filter
 115   ASSERT_TRUE(reader.KeyMayMatch("foo"));
 116 }
 117
 118 TEST_F(PluginFullFilterBlockTest, PluginSingleChunk) {
 119   FullFilterBlockBuilder builder(
 120       nullptr, true, table_options_.filter_policy->GetFilterBitsBuilder());
 121   builder.Add("foo");
 122   builder.Add("bar");
 123   builder.Add("box");
 124   builder.Add("box");
 125   builder.Add("hello");
 126   Slice block = builder.Finish();
 127   FullFilterBlockReader reader(
 128       nullptr, true, block,
 129       table_options_.filter_policy->GetFilterBitsReader(block), nullptr);
 130   ASSERT_TRUE(reader.KeyMayMatch("foo"));
 131   ASSERT_TRUE(reader.KeyMayMatch("bar"));
 132   ASSERT_TRUE(reader.KeyMayMatch("box"));
 133   ASSERT_TRUE(reader.KeyMayMatch("hello"));
 134   ASSERT_TRUE(reader.KeyMayMatch("foo"));
 135   ASSERT_TRUE(!reader.KeyMayMatch("missing"));
 136   ASSERT_TRUE(!reader.KeyMayMatch("other"));
 137 }
 138
 139 class FullFilterBlockTest : public testing::Test {
 140  public:
 141   BlockBasedTableOptions table_options_;
 142
 143   FullFilterBlockTest() {
 144     table_options_.filter_policy.reset(NewBloomFilterPolicy(10, false));
 145   }
 146
 147   ~FullFilterBlockTest() {}
 148 };
 149
 150 TEST_F(FullFilterBlockTest, EmptyBuilder) {
 151   FullFilterBlockBuilder builder(
 152       nullptr, true, table_options_.filter_policy->GetFilterBitsBuilder());
 153   Slice block = builder.Finish();
 154   ASSERT_EQ("", EscapeString(block));
 155
 156   FullFilterBlockReader reader(
 157       nullptr, true, block,
 158       table_options_.filter_policy->GetFilterBitsReader(block), nullptr);
 159   // Remain same symantic with blockbased filter
 160   ASSERT_TRUE(reader.KeyMayMatch("foo"));
 161 }
 162
 163 TEST_F(FullFilterBlockTest, SingleChunk) {
 164   FullFilterBlockBuilder builder(
 165       nullptr, true, table_options_.filter_policy->GetFilterBitsBuilder());
 166   builder.Add("foo");
 167   builder.Add("bar");
 168   builder.Add("box");
 169   builder.Add("box");
 170   builder.Add("hello");
 171   Slice block = builder.Finish();
 172   FullFilterBlockReader reader(
 173       nullptr, true, block,
 174       table_options_.filter_policy->GetFilterBitsReader(block), nullptr);
 175   ASSERT_TRUE(reader.KeyMayMatch("foo"));
 176   ASSERT_TRUE(reader.KeyMayMatch("bar"));
 177   ASSERT_TRUE(reader.KeyMayMatch("box"));
 178   ASSERT_TRUE(reader.KeyMayMatch("hello"));
 179   ASSERT_TRUE(reader.KeyMayMatch("foo"));
 180   ASSERT_TRUE(!reader.KeyMayMatch("missing"));
 181   ASSERT_TRUE(!reader.KeyMayMatch("other"));
 182 }
 183
 184 }  // namespace rocksdb
 185
 186 int main(int argc, char** argv) {
 187   ::testing::InitGoogleTest(&argc, argv);
 188   return RUN_ALL_TESTS();
 189 }