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