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.
5 #include "leveldb/filter_policy.h"
7 #include "leveldb/slice.h"
13 static uint32_t BloomHash(const Slice& key) {
14 return Hash(key.data(), key.size(), 0xbc9f1d34);
17 class BloomFilterPolicy : public FilterPolicy {
23 explicit BloomFilterPolicy(int bits_per_key)
24 : bits_per_key_(bits_per_key) {
25 // We intentionally round down to reduce probing cost a little bit
26 k_ = static_cast<size_t>(bits_per_key * 0.69); // 0.69 =~ ln(2)
31 virtual const char* Name() const {
32 return "leveldb.BuiltinBloomFilter2";
35 virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const {
36 // Compute bloom filter size (in both bits and bytes)
37 size_t bits = n * bits_per_key_;
39 // For small n, we can see a very high false positive rate. Fix it
40 // by enforcing a minimum bloom filter length.
41 if (bits < 64) bits = 64;
43 size_t bytes = (bits + 7) / 8;
46 const size_t init_size = dst->size();
47 dst->resize(init_size + bytes, 0);
48 dst->push_back(static_cast<char>(k_)); // Remember # of probes in filter
49 char* array = &(*dst)[init_size];
50 for (size_t i = 0; i < n; i++) {
51 // Use double-hashing to generate a sequence of hash values.
52 // See analysis in [Kirsch,Mitzenmacher 2006].
53 uint32_t h = BloomHash(keys[i]);
54 const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits
55 for (size_t j = 0; j < k_; j++) {
56 const uint32_t bitpos = h % bits;
57 array[bitpos/8] |= (1 << (bitpos % 8));
63 virtual bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const {
64 const size_t len = bloom_filter.size();
65 if (len < 2) return false;
67 const char* array = bloom_filter.data();
68 const size_t bits = (len - 1) * 8;
70 // Use the encoded k so that we can read filters generated by
71 // bloom filters created using different parameters.
72 const size_t k = array[len-1];
74 // Reserved for potentially new encodings for short bloom filters.
75 // Consider it a match.
79 uint32_t h = BloomHash(key);
80 const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits
81 for (size_t j = 0; j < k; j++) {
82 const uint32_t bitpos = h % bits;
83 if ((array[bitpos/8] & (1 << (bitpos % 8))) == 0) return false;
91 const FilterPolicy* NewBloomFilterPolicy(int bits_per_key) {
92 return new BloomFilterPolicy(bits_per_key);
95 } // namespace leveldb