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