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