Line data    Source code

       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             : // A filter block is stored near the end of a Table file.  It contains
       6             : // filters (e.g., bloom filters) for all data blocks in the table combined
       7             : // into a single filter block.
       8             : 
       9             : #ifndef STORAGE_LEVELDB_TABLE_FILTER_BLOCK_H_
      10             : #define STORAGE_LEVELDB_TABLE_FILTER_BLOCK_H_
      11             : 
      12             : #include <stddef.h>
      13             : #include <stdint.h>
      14             : #include <string>
      15             : #include <vector>
      16             : #include "leveldb/slice.h"
      17             : #include "util/hash.h"
      18             : 
      19             : namespace leveldb {
      20             : 
      21             : class FilterPolicy;
      22             : 
      23             : // A FilterBlockBuilder is used to construct all of the filters for a
      24             : // particular Table.  It generates a single string which is stored as
      25             : // a special block in the Table.
      26             : //
      27             : // The sequence of calls to FilterBlockBuilder must match the regexp:
      28             : //      (StartBlock AddKey*)* Finish
      29         732 : class FilterBlockBuilder {
      30             :  public:
      31             :   explicit FilterBlockBuilder(const FilterPolicy*);
      32             : 
      33             :   void StartBlock(uint64_t block_offset);
      34             :   void AddKey(const Slice& key);
      35             :   Slice Finish();
      36             : 
      37             :  private:
      38             :   void GenerateFilter();
      39             : 
      40             :   const FilterPolicy* policy_;
      41             :   std::string keys_;              // Flattened key contents
      42             :   std::vector<size_t> start_;     // Starting index in keys_ of each key
      43             :   std::string result_;            // Filter data computed so far
      44             :   std::vector<Slice> tmp_keys_;   // policy_->CreateFilter() argument
      45             :   std::vector<uint32_t> filter_offsets_;
      46             : 
      47             :   // No copying allowed
      48             :   FilterBlockBuilder(const FilterBlockBuilder&);
      49             :   void operator=(const FilterBlockBuilder&);
      50             : };
      51             : 
      52             : class FilterBlockReader {
      53             :  public:
      54             :  // REQUIRES: "contents" and *policy must stay live while *this is live.
      55             :   FilterBlockReader(const FilterPolicy* policy, const Slice& contents);
      56             :   bool KeyMayMatch(uint64_t block_offset, const Slice& key);
      57             : 
      58             :  private:
      59             :   const FilterPolicy* policy_;
      60             :   const char* data_;    // Pointer to filter data (at block-start)
      61             :   const char* offset_;  // Pointer to beginning of offset array (at block-end)
      62             :   size_t num_;          // Number of entries in offset array
      63             :   size_t base_lg_;      // Encoding parameter (see kFilterBaseLg in .cc file)
      64             : };
      65             : 
      66             : }
      67             : 
      68             : #endif  // STORAGE_LEVELDB_TABLE_FILTER_BLOCK_H_