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