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