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                 :     2587795 : static uint32_t BloomHash(const Slice& key) {
      14                 :     2587795 :   return Hash(key.data(), key.size(), 0xbc9f1d34);
      15                 :             : }
      16                 :             : 
      17                 :             : class BloomFilterPolicy : public FilterPolicy {
      18                 :             :  public:
      19         [ -  + ]:        2854 :   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                 :        2854 :     k_ = static_cast<size_t>(bits_per_key * 0.69);  // 0.69 =~ ln(2)
      22         [ -  + ]:        2854 :     if (k_ < 1) k_ = 1;
      23         [ -  + ]:        2854 :     if (k_ > 30) k_ = 30;
      24                 :        2854 :   }
      25                 :             : 
      26                 :        6172 :   const char* Name() const override { return "leveldb.BuiltinBloomFilter2"; }
      27                 :             : 
      28                 :       10347 :   void CreateFilter(const Slice* keys, int n, std::string* dst) const override {
      29                 :             :     // Compute bloom filter size (in both bits and bytes)
      30                 :       10347 :     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         [ +  + ]:       10347 :     if (bits < 64) bits = 64;
      35                 :             : 
      36                 :       10347 :     size_t bytes = (bits + 7) / 8;
      37                 :       10347 :     bits = bytes * 8;
      38                 :             : 
      39         [ -  + ]:       10347 :     const size_t init_size = dst->size();
      40                 :       10347 :     dst->resize(init_size + bytes, 0);
      41                 :       10347 :     dst->push_back(static_cast<char>(k_));  // Remember # of probes in filter
      42                 :       10347 :     char* array = &(*dst)[init_size];
      43         [ +  + ]:      381315 :     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                 :      370968 :       uint32_t h = BloomHash(keys[i]);
      47                 :      370968 :       const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
      48         [ +  + ]:     2596776 :       for (size_t j = 0; j < k_; j++) {
      49                 :     2225808 :         const uint32_t bitpos = h % bits;
      50                 :     2225808 :         array[bitpos / 8] |= (1 << (bitpos % 8));
      51                 :     2225808 :         h += delta;
      52                 :             :       }
      53                 :             :     }
      54                 :       10347 :   }
      55                 :             : 
      56                 :     2216827 :   bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const override {
      57         [ +  - ]:     2216827 :     const size_t len = bloom_filter.size();
      58         [ +  - ]:     2216827 :     if (len < 2) return false;
      59                 :             : 
      60         [ +  - ]:     2216827 :     const char* array = bloom_filter.data();
      61                 :     2216827 :     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                 :     2216827 :     const size_t k = array[len - 1];
      66         [ +  - ]:     2216827 :     if (k > 30) {
      67                 :             :       // Reserved for potentially new encodings for short bloom filters.
      68                 :             :       // Consider it a match.
      69                 :             :       return true;
      70                 :             :     }
      71                 :             : 
      72                 :     2216827 :     uint32_t h = BloomHash(key);
      73                 :     2216827 :     const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
      74         [ +  + ]:     3594450 :     for (size_t j = 0; j < k; j++) {
      75                 :     3499744 :       const uint32_t bitpos = h % bits;
      76         [ +  + ]:     3499744 :       if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0) return false;
      77                 :     1377623 :       h += delta;
      78                 :             :     }
      79                 :             :     return true;
      80                 :             :   }
      81                 :             : 
      82                 :             :  private:
      83                 :             :   size_t bits_per_key_;
      84                 :             :   size_t k_;
      85                 :             : };
      86                 :             : }  // namespace
      87                 :             : 
      88                 :        2854 : const FilterPolicy* NewBloomFilterPolicy(int bits_per_key) {
      89                 :        2854 :   return new BloomFilterPolicy(bits_per_key);
      90                 :             : }
      91                 :             : 
      92                 :             : }  // namespace leveldb