#include "rocksdb/filter_policy.h"
#include "rocksdb/slice.h"
#include "util/hash.h"
namespace
rocksdb {
namespace
{
class
BloomFilterPolicy :
public
FilterPolicy {
private
:
size_t
bits_per_key_;
size_t
k_;
uint32_t (*hash_func_)(
const
Slice& key);
void
initialize() {
k_ =
static_cast
<
size_t
>(bits_per_key_ * 0.69);
if
(k_ < 1) k_ = 1;
if
(k_ > 30) k_ = 30;
}
public
:
explicit
BloomFilterPolicy(
int
bits_per_key,
uint32_t (*hash_func)(
const
Slice& key))
: bits_per_key_(bits_per_key), hash_func_(hash_func) {
initialize();
}
explicit
BloomFilterPolicy(
int
bits_per_key)
: bits_per_key_(bits_per_key) {
hash_func_ = BloomHash;
initialize();
}
virtual
const
char
* Name()
const
{
return
"rocksdb.BuiltinBloomFilter"
;
}
virtual
void
CreateFilter(
const
Slice* keys,
int
n, std::string* dst)
const
{
size_t
bits = n * bits_per_key_;
if
(bits < 64) bits = 64;
size_t
bytes = (bits + 7) / 8;
bits = bytes * 8;
const
size_t
init_size = dst->size();
dst->resize(init_size + bytes, 0);
dst->push_back(
static_cast
<
char
>(k_));
char
* array = &(*dst)[init_size];
for
(
size_t
i = 0; i < (
size_t
)n; i++) {
uint32_t h = hash_func_(keys[i]);
const
uint32_t delta = (h >> 17) | (h << 15);
for
(
size_t
j = 0; j < k_; j++) {
const
uint32_t bitpos = h % bits;
array[bitpos/8] |= (1 << (bitpos % 8));
h += delta;
}
}
}
virtual
bool
KeyMayMatch(
const
Slice& key,
const
Slice& bloom_filter)
const
{
const
size_t
len = bloom_filter.size();
if
(len < 2)
return
false
;
const
char
* array = bloom_filter.data();
const
size_t
bits = (len - 1) * 8;
const
size_t
k = array[len-1];
if
(k > 30) {
return
true
;
}
uint32_t h = hash_func_(key);
const
uint32_t delta = (h >> 17) | (h << 15);
for
(
size_t
j = 0; j < k; j++) {
const
uint32_t bitpos = h % bits;
if
((array[bitpos/8] & (1 << (bitpos % 8))) == 0)
return
false
;
h += delta;
}
return
true
;
}
};
}
const
FilterPolicy* NewBloomFilterPolicy(
int
bits_per_key) {
return
new
BloomFilterPolicy(bits_per_key);
}
}