filter_block_test.cc raw

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