14 static const int kVerbose = 1;
16 static Slice
Key(
int i,
char* buffer) {
18 return Slice(buffer,
sizeof(
uint32_t));
44 std::vector<Slice> key_slices;
45 for (
size_t i = 0; i < keys_.size(); i++) {
46 key_slices.push_back(
Slice(keys_[i]));
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");
77 char buffer[
sizeof(int)];
79 for (
int i = 0; i < 10000; i++) {
84 return result / 10000.0;
102 static int NextLength(
int length) {
105 }
else if (length < 100) {
107 }
else if (length < 1000) {
116 char buffer[
sizeof(int)];
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;
132 for (
int i = 0; i < length; i++) {
134 <<
"Length " << length <<
"; key " << i;
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()));
144 if (rate > 0.0125) mediocre_filters++;
148 fprintf(stderr,
"Filters: %d good, %d mediocre\n",
149 good_filters, mediocre_filters);
151 ASSERT_LE(mediocre_filters, good_filters/5);
158 int main(
int argc,
char** argv) {
void EncodeFixed32(char *buf, uint32_t value)
size_t FilterSize() const
bool Matches(const Slice &s)
double FalsePositiveRate()
TEST(CorruptionTest, Recovery)
const FilterPolicy * NewBloomFilterPolicy(int bits_per_key)
int main(int argc, char **argv)
std::vector< std::string > keys_
virtual void CreateFilter(const Slice *keys, int n, std::string *dst) const =0
const FilterPolicy * policy_
std::string ToString() const
virtual bool KeyMayMatch(const Slice &key, const Slice &filter) const =0