199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// Copyright (c) 2012 The LevelDB Authors. All rights reserved. 299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// Use of this source code is governed by a BSD-style license that can be 399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// found in the LICENSE file. See the AUTHORS file for names of contributors. 499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#include "table/filter_block.h" 699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#include "leveldb/filter_policy.h" 899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#include "util/coding.h" 999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 1099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comnamespace leveldb { 1199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 1299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// See doc/table_format.txt for an explanation of the filter block format. 1399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 1499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// Generate new filter every 2KB of data 1599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comstatic const size_t kFilterBaseLg = 11; 1699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comstatic const size_t kFilterBase = 1 << kFilterBaseLg; 1799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 1899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comFilterBlockBuilder::FilterBlockBuilder(const FilterPolicy* policy) 1999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com : policy_(policy) { 2099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com} 2199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 2299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comvoid FilterBlockBuilder::StartBlock(uint64_t block_offset) { 2399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com uint64_t filter_index = (block_offset / kFilterBase); 2499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com assert(filter_index >= filter_offsets_.size()); 2599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com while (filter_index > filter_offsets_.size()) { 2699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com GenerateFilter(); 2799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 2899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com} 2999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 3099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comvoid FilterBlockBuilder::AddKey(const Slice& key) { 3199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com Slice k = key; 3299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com start_.push_back(keys_.size()); 3399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com keys_.append(k.data(), k.size()); 3499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com} 3599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 3699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comSlice FilterBlockBuilder::Finish() { 3799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (!start_.empty()) { 3899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com GenerateFilter(); 3999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 4099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 4199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com // Append array of per-filter offsets 4299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com const uint32_t array_offset = result_.size(); 4399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com for (size_t i = 0; i < filter_offsets_.size(); i++) { 4499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com PutFixed32(&result_, filter_offsets_[i]); 4599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 4699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 4799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com PutFixed32(&result_, array_offset); 4899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com result_.push_back(kFilterBaseLg); // Save encoding parameter in result 4999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com return Slice(result_); 5099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com} 5199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 5299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comvoid FilterBlockBuilder::GenerateFilter() { 5399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com const size_t num_keys = start_.size(); 5499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (num_keys == 0) { 5599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com // Fast path if there are no keys for this filter 5699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com filter_offsets_.push_back(result_.size()); 5799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com return; 5899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 5999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 6099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com // Make list of keys from flattened key structure 6199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com start_.push_back(keys_.size()); // Simplify length computation 6299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com tmp_keys_.resize(num_keys); 6399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com for (size_t i = 0; i < num_keys; i++) { 6499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com const char* base = keys_.data() + start_[i]; 6599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com size_t length = start_[i+1] - start_[i]; 6699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com tmp_keys_[i] = Slice(base, length); 6799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 6899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 6999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com // Generate filter for current set of keys and append to result_. 7099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com filter_offsets_.push_back(result_.size()); 7199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com policy_->CreateFilter(&tmp_keys_[0], num_keys, &result_); 7299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 7399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com tmp_keys_.clear(); 7499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com keys_.clear(); 7599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com start_.clear(); 7699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com} 7799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 7899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comFilterBlockReader::FilterBlockReader(const FilterPolicy* policy, 7999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com const Slice& contents) 8099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com : policy_(policy), 8199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com data_(NULL), 8299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com offset_(NULL), 8399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com num_(0), 8499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com base_lg_(0) { 8599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com size_t n = contents.size(); 8699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (n < 5) return; // 1 byte for base_lg_ and 4 for start of offset array 8799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com base_lg_ = contents[n-1]; 8899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com uint32_t last_word = DecodeFixed32(contents.data() + n - 5); 8999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (last_word > n - 5) return; 9099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com data_ = contents.data(); 9199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com offset_ = data_ + last_word; 9299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com num_ = (n - 5 - last_word) / 4; 9399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com} 9499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 9599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.combool FilterBlockReader::KeyMayMatch(uint64_t block_offset, const Slice& key) { 9699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com uint64_t index = block_offset >> base_lg_; 9799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (index < num_) { 9899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com uint32_t start = DecodeFixed32(offset_ + index*4); 9999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com uint32_t limit = DecodeFixed32(offset_ + index*4 + 4); 10099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (start <= limit && limit <= (offset_ - data_)) { 10199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com Slice filter = Slice(data_ + start, limit - start); 10299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com return policy_->KeyMayMatch(key, filter); 10399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } else if (start == limit) { 10499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com // Empty filters do not match any keys 10599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com return false; 10699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 10799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 10899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com return true; // Errors are treated as potential matches 10999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com} 11099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 11199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com} 112