text: //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
  //  This source code is licensed under both the GPLv2 (found in the
  //  COPYING file in the root directory) and Apache 2.0 License
  //  (found in the LICENSE.Apache file in the root directory).
  //
  // Copyright (c) 2012 The LevelDB Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file. See the AUTHORS file for names of contributors.
  
  #include "table/block_based_filter_block.h"
  
  #include "rocksdb/filter_policy.h"
  #include "util/coding.h"
  #include "util/hash.h"
  #include "util/string_util.h"
  #include "util/testharness.h"
  #include "util/testutil.h"
  
  namespace rocksdb
  {
  // For testing: emit an array with one hash value per key
  class TestHashFilter : public FilterPolicy {
      public:
  	virtual const char *Name() const override
  	{
  		return "TestHashFilter";
  	}
  
  	virtual void CreateFilter(const Slice *keys, int n,
  				  std::string *dst) const override
  	{
  		for (int i = 0; i < n; i++) {
  			uint32_t h = Hash(keys[i].data(), keys[i].size(), 1);
  			PutFixed32(dst, h);
  		}
  	}
  
  	virtual bool KeyMayMatch(const Slice &key,
  				 const Slice &filter) const override
  	{
  		uint32_t h = Hash(key.data(), key.size(), 1);
  		for (unsigned int i = 0; i + 4 <= filter.size(); i += 4) {
  			if (h == DecodeFixed32(filter.data() + i)) {
  				return true;
  			}
  		}
  		return false;
  	}
  };
  
  class FilterBlockTest : public testing::Test {
      public:
  	TestHashFilter policy_;
  	BlockBasedTableOptions table_options_;
  
  	FilterBlockTest()
  	{
  		table_options_.filter_policy.reset(new TestHashFilter());
  	}
  };
  
  TEST_F(FilterBlockTest, EmptyBuilder)
  {
  	BlockBasedFilterBlockBuilder builder(nullptr, table_options_);
  	BlockContents block(builder.Finish(), false, kNoCompression);
  	ASSERT_EQ("\\x00\\x00\\x00\\x00\\x0b", EscapeString(block.data));
  	BlockBasedFilterBlockReader reader(nullptr, table_options_, true,
  					   std::move(block), nullptr);
  	ASSERT_TRUE(reader.KeyMayMatch("foo", 0));
  	ASSERT_TRUE(reader.KeyMayMatch("foo", 100000));
  }
  
  TEST_F(FilterBlockTest, SingleChunk)
  {
  	BlockBasedFilterBlockBuilder builder(nullptr, table_options_);
  	builder.StartBlock(100);
  	builder.Add("foo");
  	builder.Add("bar");
  	builder.Add("box");
  	builder.StartBlock(200);
  	builder.Add("box");
  	builder.StartBlock(300);
  	builder.Add("hello");
  	BlockContents block(builder.Finish(), false, kNoCompression);
  	BlockBasedFilterBlockReader reader(nullptr, table_options_, true,
  					   std::move(block), nullptr);
  	ASSERT_TRUE(reader.KeyMayMatch("foo", 100));
  	ASSERT_TRUE(reader.KeyMayMatch("bar", 100));
  	ASSERT_TRUE(reader.KeyMayMatch("box", 100));
  	ASSERT_TRUE(reader.KeyMayMatch("hello", 100));
  	ASSERT_TRUE(reader.KeyMayMatch("foo", 100));
  	ASSERT_TRUE(!reader.KeyMayMatch("missing", 100));
  	ASSERT_TRUE(!reader.KeyMayMatch("other", 100));
  }
  
  TEST_F(FilterBlockTest, MultiChunk)
  {
  	BlockBasedFilterBlockBuilder builder(nullptr, table_options_);
  
  	// First filter
  	builder.StartBlock(0);
  	builder.Add("foo");
  	builder.StartBlock(2000);
  	builder.Add("bar");
  
  	// Second filter
  	builder.StartBlock(3100);
  	builder.Add("box");
  
  	// Third filter is empty
  
  	// Last filter
  	builder.StartBlock(9000);
  	builder.Add("box");
  	builder.Add("hello");
  
  	BlockContents block(builder.Finish(), false, kNoCompression);
  	BlockBasedFilterBlockReader reader(nullptr, table_options_, true,
  					   std::move(block), nullptr);
  
  	// Check first filter
  	ASSERT_TRUE(reader.KeyMayMatch("foo", 0));
  	ASSERT_TRUE(reader.KeyMayMatch("bar", 2000));
  	ASSERT_TRUE(!reader.KeyMayMatch("box", 0));
  	ASSERT_TRUE(!reader.KeyMayMatch("hello", 0));
  
  	// Check second filter
  	ASSERT_TRUE(reader.KeyMayMatch("box", 3100));
  	ASSERT_TRUE(!reader.KeyMayMatch("foo", 3100));
  	ASSERT_TRUE(!reader.KeyMayMatch("bar", 3100));
  	ASSERT_TRUE(!reader.KeyMayMatch("hello", 3100));
  
  	// Check third filter (empty)
  	ASSERT_TRUE(!reader.KeyMayMatch("foo", 4100));
  	ASSERT_TRUE(!reader.KeyMayMatch("bar", 4100));
  	ASSERT_TRUE(!reader.KeyMayMatch("box", 4100));
  	ASSERT_TRUE(!reader.KeyMayMatch("hello", 4100));
  
  	// Check last filter
  	ASSERT_TRUE(reader.KeyMayMatch("box", 9000));
  	ASSERT_TRUE(reader.KeyMayMatch("hello", 9000));
  	ASSERT_TRUE(!reader.KeyMayMatch("foo", 9000));
  	ASSERT_TRUE(!reader.KeyMayMatch("bar", 9000));
  }
  
  // Test for block based filter block
  // use new interface in FilterPolicy to create filter builder/reader
  class BlockBasedFilterBlockTest : public testing::Test {
      public:
  	BlockBasedTableOptions table_options_;
  
  	BlockBasedFilterBlockTest()
  	{
  		table_options_.filter_policy.reset(NewBloomFilterPolicy(10));
  	}
  
  	~BlockBasedFilterBlockTest()
  	{
  	}
  };
  
  TEST_F(BlockBasedFilterBlockTest, BlockBasedEmptyBuilder)
  {
  	FilterBlockBuilder *builder =
  		new BlockBasedFilterBlockBuilder(nullptr, table_options_);
  	BlockContents block(builder->Finish(), false, kNoCompression);
  	ASSERT_EQ("\\x00\\x00\\x00\\x00\\x0b", EscapeString(block.data));
  	FilterBlockReader *reader = new BlockBasedFilterBlockReader(
  		nullptr, table_options_, true, std::move(block), nullptr);
  	ASSERT_TRUE(reader->KeyMayMatch("foo", 0));
  	ASSERT_TRUE(reader->KeyMayMatch("foo", 100000));
  
  	delete builder;
  	delete reader;
  }
  
  TEST_F(BlockBasedFilterBlockTest, BlockBasedSingleChunk)
  {
  	FilterBlockBuilder *builder =
  		new BlockBasedFilterBlockBuilder(nullptr, table_options_);
  	builder->StartBlock(100);
  	builder->Add("foo");
  	builder->Add("bar");
  	builder->Add("box");
  	builder->StartBlock(200);
  	builder->Add("box");
  	builder->StartBlock(300);
  	builder->Add("hello");
  	BlockContents block(builder->Finish(), false, kNoCompression);
  	FilterBlockReader *reader = new BlockBasedFilterBlockReader(
  		nullptr, table_options_, true, std::move(block), nullptr);
  	ASSERT_TRUE(reader->KeyMayMatch("foo", 100));
  	ASSERT_TRUE(reader->KeyMayMatch("bar", 100));
  	ASSERT_TRUE(reader->KeyMayMatch("box", 100));
  	ASSERT_TRUE(reader->KeyMayMatch("hello", 100));
  	ASSERT_TRUE(reader->KeyMayMatch("foo", 100));
  	ASSERT_TRUE(!reader->KeyMayMatch("missing", 100));
  	ASSERT_TRUE(!reader->KeyMayMatch("other", 100));
  
  	delete builder;
  	delete reader;
  }
  
  TEST_F(BlockBasedFilterBlockTest, BlockBasedMultiChunk)
  {
  	FilterBlockBuilder *builder =
  		new BlockBasedFilterBlockBuilder(nullptr, table_options_);
  
  	// First filter
  	builder->StartBlock(0);
  	builder->Add("foo");
  	builder->StartBlock(2000);
  	builder->Add("bar");
  
  	// Second filter
  	builder->StartBlock(3100);
  	builder->Add("box");
  
  	// Third filter is empty
  
  	// Last filter
  	builder->StartBlock(9000);
  	builder->Add("box");
  	builder->Add("hello");
  
  	BlockContents block(builder->Finish(), false, kNoCompression);
  	FilterBlockReader *reader = new BlockBasedFilterBlockReader(
  		nullptr, table_options_, true, std::move(block), nullptr);
  
  	// Check first filter
  	ASSERT_TRUE(reader->KeyMayMatch("foo", 0));
  	ASSERT_TRUE(reader->KeyMayMatch("bar", 2000));
  	ASSERT_TRUE(!reader->KeyMayMatch("box", 0));
  	ASSERT_TRUE(!reader->KeyMayMatch("hello", 0));
  
  	// Check second filter
  	ASSERT_TRUE(reader->KeyMayMatch("box", 3100));
  	ASSERT_TRUE(!reader->KeyMayMatch("foo", 3100));
  	ASSERT_TRUE(!reader->KeyMayMatch("bar", 3100));
  	ASSERT_TRUE(!reader->KeyMayMatch("hello", 3100));
  
  	// Check third filter (empty)
  	ASSERT_TRUE(!reader->KeyMayMatch("foo", 4100));
  	ASSERT_TRUE(!reader->KeyMayMatch("bar", 4100));
  	ASSERT_TRUE(!reader->KeyMayMatch("box", 4100));
  	ASSERT_TRUE(!reader->KeyMayMatch("hello", 4100));
  
  	// Check last filter
  	ASSERT_TRUE(reader->KeyMayMatch("box", 9000));
  	ASSERT_TRUE(reader->KeyMayMatch("hello", 9000));
  	ASSERT_TRUE(!reader->KeyMayMatch("foo", 9000));
  	ASSERT_TRUE(!reader->KeyMayMatch("bar", 9000));
  
  	delete builder;
  	delete reader;
  }
  
  } // namespace rocksdb
  
  int main(int argc, char **argv)
  {
  	::testing::InitGoogleTest(&argc, argv);
  	return RUN_ALL_TESTS();
  }
  