src/leveldb/table/filter_block.h

   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 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_