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 | |
10 | namespace 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 |
15 | static const size_t kFilterBaseLg = 11; |
16 | static const size_t kFilterBase = 1 << kFilterBaseLg; |
17 | |
18 | FilterBlockBuilder::FilterBlockBuilder(const FilterPolicy* policy) |
19 | : policy_(policy) {} |
20 | |
21 | void 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 | |
29 | void FilterBlockBuilder::AddKey(const Slice& key) { |
30 | Slice k = key; |
31 | start_.push_back(keys_.size()); |
32 | keys_.append(k.data(), k.size()); |
33 | } |
34 | |
35 | Slice 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 | |
51 | void 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 | |
77 | FilterBlockReader::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 | |
90 | bool 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 | |