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