aboutsummaryrefslogtreecommitdiff
path: root/src/leveldb/util/bloom.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/leveldb/util/bloom.cc')
-rw-r--r--src/leveldb/util/bloom.cc27
1 files changed, 12 insertions, 15 deletions
diff --git a/src/leveldb/util/bloom.cc b/src/leveldb/util/bloom.cc
index bf3e4ca6e9..87547a7e62 100644
--- a/src/leveldb/util/bloom.cc
+++ b/src/leveldb/util/bloom.cc
@@ -15,24 +15,17 @@ static uint32_t BloomHash(const Slice& key) {
}
class BloomFilterPolicy : public FilterPolicy {
- private:
- size_t bits_per_key_;
- size_t k_;
-
public:
- explicit BloomFilterPolicy(int bits_per_key)
- : bits_per_key_(bits_per_key) {
+ explicit BloomFilterPolicy(int bits_per_key) : bits_per_key_(bits_per_key) {
// We intentionally round down to reduce probing cost a little bit
k_ = static_cast<size_t>(bits_per_key * 0.69); // 0.69 =~ ln(2)
if (k_ < 1) k_ = 1;
if (k_ > 30) k_ = 30;
}
- virtual const char* Name() const {
- return "leveldb.BuiltinBloomFilter2";
- }
+ const char* Name() const override { return "leveldb.BuiltinBloomFilter2"; }
- virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const {
+ void CreateFilter(const Slice* keys, int n, std::string* dst) const override {
// Compute bloom filter size (in both bits and bytes)
size_t bits = n * bits_per_key_;
@@ -54,13 +47,13 @@ class BloomFilterPolicy : public FilterPolicy {
const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits
for (size_t j = 0; j < k_; j++) {
const uint32_t bitpos = h % bits;
- array[bitpos/8] |= (1 << (bitpos % 8));
+ array[bitpos / 8] |= (1 << (bitpos % 8));
h += delta;
}
}
}
- virtual bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const {
+ bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const override {
const size_t len = bloom_filter.size();
if (len < 2) return false;
@@ -69,7 +62,7 @@ class BloomFilterPolicy : public FilterPolicy {
// Use the encoded k so that we can read filters generated by
// bloom filters created using different parameters.
- const size_t k = array[len-1];
+ const size_t k = array[len - 1];
if (k > 30) {
// Reserved for potentially new encodings for short bloom filters.
// Consider it a match.
@@ -80,13 +73,17 @@ class BloomFilterPolicy : public FilterPolicy {
const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits
for (size_t j = 0; j < k; j++) {
const uint32_t bitpos = h % bits;
- if ((array[bitpos/8] & (1 << (bitpos % 8))) == 0) return false;
+ if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0) return false;
h += delta;
}
return true;
}
+
+ private:
+ size_t bits_per_key_;
+ size_t k_;
};
-}
+} // namespace
const FilterPolicy* NewBloomFilterPolicy(int bits_per_key) {
return new BloomFilterPolicy(bits_per_key);