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) {
26 k_ =
static_cast<size_t>(bits_per_key * 0.69);
31 virtual const char* Name()
const {
32 return "leveldb.BuiltinBloomFilter";
35 virtual void CreateFilter(
const Slice* keys,
int n, std::string* dst)
const {
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_));
49 char* array = &(*dst)[init_size];
50 for (
size_t i = 0; i < n; i++) {
54 const uint32_t delta = (h >> 17) | (h << 15);
55 for (
size_t j = 0; j <
k_; j++) {
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;
72 const size_t k = array[len-1];
80 const uint32_t delta = (h >> 17) | (h << 15);
81 for (
size_t j = 0; j < k; j++) {
83 if ((array[bitpos/8] & (1 << (bitpos % 8))) == 0)
return false;
92 return new BloomFilterPolicy(bits_per_key);
uint32_t Hash(const char *data, size_t n, uint32_t seed)
const FilterPolicy * NewBloomFilterPolicy(int bits_per_key)