Inside Bitcoin

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