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
19namespace leveldb {
20
21class 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
29class 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
52class 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_
69