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 "leveldb/filter_policy.h"
#       6                 :            : 
#       7                 :            : #include "leveldb/slice.h"
#       8                 :            : #include "util/hash.h"
#       9                 :            : 
#      10                 :            : namespace leveldb {
#      11                 :            : 
#      12                 :            : namespace {
#      13                 :    3579565 : static uint32_t BloomHash(const Slice& key) {
#      14                 :    3579565 :   return Hash(key.data(), key.size(), 0xbc9f1d34);
#      15                 :    3579565 : }
#      16                 :            : 
#      17                 :            : class BloomFilterPolicy : public FilterPolicy {
#      18                 :            :  public:
#      19                 :       2193 :   explicit BloomFilterPolicy(int bits_per_key) : bits_per_key_(bits_per_key) {
#      20                 :            :     // We intentionally round down to reduce probing cost a little bit
#      21                 :       2193 :     k_ = static_cast<size_t>(bits_per_key * 0.69);  // 0.69 =~ ln(2)
#      22         [ -  + ]:       2193 :     if (k_ < 1) k_ = 1;
#      23         [ -  + ]:       2193 :     if (k_ > 30) k_ = 30;
#      24                 :       2193 :   }
#      25                 :            : 
#      26                 :       3000 :   const char* Name() const override { return "leveldb.BuiltinBloomFilter2"; }
#      27                 :            : 
#      28                 :       4648 :   void CreateFilter(const Slice* keys, int n, std::string* dst) const override {
#      29                 :            :     // Compute bloom filter size (in both bits and bytes)
#      30                 :       4648 :     size_t bits = n * bits_per_key_;
#      31                 :            : 
#      32                 :            :     // For small n, we can see a very high false positive rate.  Fix it
#      33                 :            :     // by enforcing a minimum bloom filter length.
#      34         [ +  + ]:       4648 :     if (bits < 64) bits = 64;
#      35                 :            : 
#      36                 :       4648 :     size_t bytes = (bits + 7) / 8;
#      37                 :       4648 :     bits = bytes * 8;
#      38                 :            : 
#      39                 :       4648 :     const size_t init_size = dst->size();
#      40                 :       4648 :     dst->resize(init_size + bytes, 0);
#      41                 :       4648 :     dst->push_back(static_cast<char>(k_));  // Remember # of probes in filter
#      42                 :       4648 :     char* array = &(*dst)[init_size];
#      43         [ +  + ]:     201265 :     for (int i = 0; i < n; i++) {
#      44                 :            :       // Use double-hashing to generate a sequence of hash values.
#      45                 :            :       // See analysis in [Kirsch,Mitzenmacher 2006].
#      46                 :     196617 :       uint32_t h = BloomHash(keys[i]);
#      47                 :     196617 :       const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
#      48         [ +  + ]:    1376319 :       for (size_t j = 0; j < k_; j++) {
#      49                 :    1179702 :         const uint32_t bitpos = h % bits;
#      50                 :    1179702 :         array[bitpos / 8] |= (1 << (bitpos % 8));
#      51                 :    1179702 :         h += delta;
#      52                 :    1179702 :       }
#      53                 :     196617 :     }
#      54                 :       4648 :   }
#      55                 :            : 
#      56                 :    3382960 :   bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const override {
#      57                 :    3382960 :     const size_t len = bloom_filter.size();
#      58         [ -  + ]:    3382960 :     if (len < 2) return false;
#      59                 :            : 
#      60                 :    3382960 :     const char* array = bloom_filter.data();
#      61                 :    3382960 :     const size_t bits = (len - 1) * 8;
#      62                 :            : 
#      63                 :            :     // Use the encoded k so that we can read filters generated by
#      64                 :            :     // bloom filters created using different parameters.
#      65                 :    3382960 :     const size_t k = array[len - 1];
#      66         [ -  + ]:    3382960 :     if (k > 30) {
#      67                 :            :       // Reserved for potentially new encodings for short bloom filters.
#      68                 :            :       // Consider it a match.
#      69                 :          0 :       return true;
#      70                 :          0 :     }
#      71                 :            : 
#      72                 :    3382960 :     uint32_t h = BloomHash(key);
#      73                 :    3382960 :     const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
#      74         [ +  + ]:    4552060 :     for (size_t j = 0; j < k; j++) {
#      75                 :    4450781 :       const uint32_t bitpos = h % bits;
#      76         [ +  + ]:    4450781 :       if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0) return false;
#      77                 :    1169100 :       h += delta;
#      78                 :    1169100 :     }
#      79                 :     101279 :     return true;
#      80                 :    3382960 :   }
#      81                 :            : 
#      82                 :            :  private:
#      83                 :            :   size_t bits_per_key_;
#      84                 :            :   size_t k_;
#      85                 :            : };
#      86                 :            : }  // namespace
#      87                 :            : 
#      88                 :       2193 : const FilterPolicy* NewBloomFilterPolicy(int bits_per_key) {
#      89                 :       2193 :   return new BloomFilterPolicy(bits_per_key);
#      90                 :       2193 : }
#      91                 :            : 
#      92                 :            : }  // namespace leveldb