src/leveldb/table/filter_block_test.cc

   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   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 (int 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
  41 class FilterBlockTest {
  42  public:
  43   TestHashFilter policy_;
  44 };
  45
  46 TEST(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
  55 TEST(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
  76 TEST(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
 126 int main(int argc, char** argv) {
 127   return leveldb::test::RunAllTests();
 128 }