filter_block.cc raw

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