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
FilterBlockBuilder(const FilterPolicy * policy)18 FilterBlockBuilder::FilterBlockBuilder(const FilterPolicy* policy)
19 : policy_(policy) {}
20
StartBlock(uint64_t block_offset)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
AddKey(const Slice & key)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
Finish()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
GenerateFilter()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
FilterBlockReader(const FilterPolicy * policy,const Slice & contents)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
KeyMayMatch(uint64_t block_offset,const Slice & key)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