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 "util/coding.h"
8 #include "util/logging.h"
9 #include "util/testharness.h"
10 #include "util/testutil.h"
14 static const int kVerbose = 1;
16 static Slice Key(int i, char* buffer) {
17 EncodeFixed32(buffer, i);
18 return Slice(buffer, sizeof(uint32_t));
23 const FilterPolicy* policy_;
25 std::vector<std::string> keys_;
28 BloomTest() : policy_(NewBloomFilterPolicy(10)) { }
39 void Add(const Slice& s) {
40 keys_.push_back(s.ToString());
44 std::vector<Slice> key_slices;
45 for (size_t i = 0; i < keys_.size(); i++) {
46 key_slices.push_back(Slice(keys_[i]));
49 policy_->CreateFilter(&key_slices[0], key_slices.size(), &filter_);
51 if (kVerbose >= 2) DumpFilter();
54 size_t FilterSize() const {
55 return filter_.size();
59 fprintf(stderr, "F(");
60 for (size_t i = 0; i+1 < filter_.size(); i++) {
61 const unsigned int c = static_cast<unsigned int>(filter_[i]);
62 for (int j = 0; j < 8; j++) {
63 fprintf(stderr, "%c", (c & (1 <<j)) ? '1' : '.');
66 fprintf(stderr, ")\n");
69 bool Matches(const Slice& s) {
73 return policy_->KeyMayMatch(s, filter_);
76 double FalsePositiveRate() {
77 char buffer[sizeof(int)];
79 for (int i = 0; i < 10000; i++) {
80 if (Matches(Key(i + 1000000000, buffer))) {
84 return result / 10000.0;
88 TEST(BloomTest, EmptyFilter) {
89 ASSERT_TRUE(! Matches("hello"));
90 ASSERT_TRUE(! Matches("world"));
93 TEST(BloomTest, Small) {
96 ASSERT_TRUE(Matches("hello"));
97 ASSERT_TRUE(Matches("world"));
98 ASSERT_TRUE(! Matches("x"));
99 ASSERT_TRUE(! Matches("foo"));
102 static int NextLength(int length) {
105 } else if (length < 100) {
107 } else if (length < 1000) {
115 TEST(BloomTest, VaryingLengths) {
116 char buffer[sizeof(int)];
118 // Count number of filters that significantly exceed the false positive rate
119 int mediocre_filters = 0;
120 int good_filters = 0;
122 for (int length = 1; length <= 10000; length = NextLength(length)) {
124 for (int i = 0; i < length; i++) {
129 ASSERT_LE(FilterSize(), (length * 10 / 8) + 40) << length;
131 // All added keys must match
132 for (int i = 0; i < length; i++) {
133 ASSERT_TRUE(Matches(Key(i, buffer)))
134 << "Length " << length << "; key " << i;
137 // Check false positive rate
138 double rate = FalsePositiveRate();
140 fprintf(stderr, "False positives: %5.2f%% @ length = %6d ; bytes = %6d\n",
141 rate*100.0, length, static_cast<int>(FilterSize()));
143 ASSERT_LE(rate, 0.02); // Must not be over 2%
144 if (rate > 0.0125) mediocre_filters++; // Allowed, but not too often
148 fprintf(stderr, "Filters: %d good, %d mediocre\n",
149 good_filters, mediocre_filters);
151 ASSERT_LE(mediocre_filters, good_filters/5);
154 // Different bits-per-byte
156 } // namespace leveldb
158 int main(int argc, char** argv) {
159 return leveldb::test::RunAllTests();