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 <cstddef>
13#include <cstdint>
14#include <string>
15#include <vector>
16
17#include "leveldb/slice.h"
18#include "util/hash.h"
19
20namespace leveldb {
21
22class FilterPolicy;
23
24// A FilterBlockBuilder is used to construct all of the filters for a
25// particular Table. It generates a single string which is stored as
26// a special block in the Table.
27//
28// The sequence of calls to FilterBlockBuilder must match the regexp:
29// (StartBlock AddKey*)* Finish
30class FilterBlockBuilder {
31 public:
32 explicit FilterBlockBuilder(const FilterPolicy*);
33
34 FilterBlockBuilder(const FilterBlockBuilder&) = delete;
35 FilterBlockBuilder& operator=(const FilterBlockBuilder&) = delete;
36
37 void StartBlock(uint64_t block_offset);
38 void AddKey(const Slice& key);
39 Slice Finish();
40
41 private:
42 void GenerateFilter();
43
44 const FilterPolicy* policy_;
45 std::string keys_; // Flattened key contents
46 std::vector<size_t> start_; // Starting index in keys_ of each key
47 std::string result_; // Filter data computed so far
48 std::vector<Slice> tmp_keys_; // policy_->CreateFilter() argument
49 std::vector<uint32_t> filter_offsets_;
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} // namespace leveldb
67
68#endif // STORAGE_LEVELDB_TABLE_FILTER_BLOCK_H_
69