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