table/filter_block.cc

   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
  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], static_cast<int>(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 <= static_cast<size_t>(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 }