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#include "table/filter_block.h"
6
7#include "leveldb/filter_policy.h"
8#include "util/coding.h"
9
10namespace leveldb {
11
12// See doc/table_format.md for an explanation of the filter block format.
13
14// Generate new filter every 2KB of data
15static const size_t kFilterBaseLg = 11;
16static const size_t kFilterBase = 1 << kFilterBaseLg;
17
18FilterBlockBuilder::FilterBlockBuilder(const FilterPolicy* policy)
19    : policy_(policy) {}
20
21void FilterBlockBuilder::StartBlock(uint64_t block_offset) {
22  uint64_t filter_index = (block_offset / kFilterBase);
23  assert(filter_index >= filter_offsets_.size());
24  while (filter_index > filter_offsets_.size()) {
25    GenerateFilter();
26  }
27}
28
29void FilterBlockBuilder::AddKey(const Slice& key) {
30  Slice k = key;
31  start_.push_back(keys_.size());
32  keys_.append(k.data(), k.size());
33}
34
35Slice FilterBlockBuilder::Finish() {
36  if (!start_.empty()) {
37    GenerateFilter();
38  }
39
40  // Append array of per-filter offsets
41  const uint32_t array_offset = result_.size();
42  for (size_t i = 0; i < filter_offsets_.size(); i++) {
43    PutFixed32(&result_, filter_offsets_[i]);
44  }
45
46  PutFixed32(&result_, array_offset);
47  result_.push_back(kFilterBaseLg);  // Save encoding parameter in result
48  return Slice(result_);
49}
50
51void FilterBlockBuilder::GenerateFilter() {
52  const size_t num_keys = start_.size();
53  if (num_keys == 0) {
54    // Fast path if there are no keys for this filter
55    filter_offsets_.push_back(result_.size());
56    return;
57  }
58
59  // Make list of keys from flattened key structure
60  start_.push_back(keys_.size());  // Simplify length computation
61  tmp_keys_.resize(num_keys);
62  for (size_t i = 0; i < num_keys; i++) {
63    const char* base = keys_.data() + start_[i];
64    size_t length = start_[i + 1] - start_[i];
65    tmp_keys_[i] = Slice(base, length);
66  }
67
68  // Generate filter for current set of keys and append to result_.
69  filter_offsets_.push_back(result_.size());
70  policy_->CreateFilter(&tmp_keys_[0], static_cast<int>(num_keys), &result_);
71
72  tmp_keys_.clear();
73  keys_.clear();
74  start_.clear();
75}
76
77FilterBlockReader::FilterBlockReader(const FilterPolicy* policy,
78                                     const Slice& contents)
79    : policy_(policy), data_(nullptr), offset_(nullptr), num_(0), base_lg_(0) {
80  size_t n = contents.size();
81  if (n < 5) return;  // 1 byte for base_lg_ and 4 for start of offset array
82  base_lg_ = contents[n - 1];
83  uint32_t last_word = DecodeFixed32(contents.data() + n - 5);
84  if (last_word > n - 5) return;
85  data_ = contents.data();
86  offset_ = data_ + last_word;
87  num_ = (n - 5 - last_word) / 4;
88}
89
90bool FilterBlockReader::KeyMayMatch(uint64_t block_offset, const Slice& key) {
91  uint64_t index = block_offset >> base_lg_;
92  if (index < num_) {
93    uint32_t start = DecodeFixed32(offset_ + index * 4);
94    uint32_t limit = DecodeFixed32(offset_ + index * 4 + 4);
95    if (start <= limit && limit <= static_cast<size_t>(offset_ - data_)) {
96      Slice filter = Slice(data_ + start, limit - start);
97      return policy_->KeyMayMatch(key, filter);
98    } else if (start == limit) {
99      // Empty filters do not match any keys
100      return false;
101    }
102  }
103  return true;  // Errors are treated as potential matches
104}
105
106}  // namespace leveldb
107