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