Differential D5120 Diff 15929 src/test/bloom_tests.cpp

Changeset View

Standalone View

src/test/bloom_tests.cpp

Show First 20 Lines • Show All 1,114 Lines • ▼ Show 20 Lines	BOOST_AUTO_TEST_CASE(rolling_bloom) {
}		}

// false positive rate is 1%, so we should get about 100 hits if		// false positive rate is 1%, so we should get about 100 hits if
// testing 10,000 random keys. We get worst-case false positive		// testing 10,000 random keys. We get worst-case false positive
// behavior when the filter is as full as possible, which is		// behavior when the filter is as full as possible, which is
// when we've inserted one minus an integer multiple of nElement*2.		// when we've inserted one minus an integer multiple of nElement*2.
unsigned int nHits = 0;		unsigned int nHits = 0;
for (int i = 0; i < 10000; i++) {		for (int i = 0; i < 10000; i++) {
if (rb1.contains(RandomData())) ++nHits;		if (rb1.contains(RandomData())) {
		++nHits;
		}
}		}
// Expect about 100 hits		// Expect about 100 hits
BOOST_CHECK_EQUAL(nHits, 75);		BOOST_CHECK_EQUAL(nHits, 75);

BOOST_CHECK(rb1.contains(data[DATASIZE - 1]));		BOOST_CHECK(rb1.contains(data[DATASIZE - 1]));
rb1.reset();		rb1.reset();
BOOST_CHECK(!rb1.contains(data[DATASIZE - 1]));		BOOST_CHECK(!rb1.contains(data[DATASIZE - 1]));

// Now roll through data, make sure last 100 entries		// Now roll through data, make sure last 100 entries
// are always remembered:		// are always remembered:
for (int i = 0; i < DATASIZE; i++) {		for (int i = 0; i < DATASIZE; i++) {
if (i >= 100) BOOST_CHECK(rb1.contains(data[i - 100]));		if (i >= 100) {
		BOOST_CHECK(rb1.contains(data[i - 100]));
		}
rb1.insert(data[i]);		rb1.insert(data[i]);
BOOST_CHECK(rb1.contains(data[i]));		BOOST_CHECK(rb1.contains(data[i]));
}		}

// Insert 999 more random entries:		// Insert 999 more random entries:
for (int i = 0; i < 999; i++) {		for (int i = 0; i < 999; i++) {
std::vector<uint8_t> d = RandomData();		std::vector<uint8_t> d = RandomData();
rb1.insert(d);		rb1.insert(d);
BOOST_CHECK(rb1.contains(d));		BOOST_CHECK(rb1.contains(d));
}		}
// Sanity check to make sure the filter isn't just filling up:		// Sanity check to make sure the filter isn't just filling up:
nHits = 0;		nHits = 0;
for (int i = 0; i < DATASIZE; i++) {		for (int i = 0; i < DATASIZE; i++) {
if (rb1.contains(data[i])) ++nHits;		if (rb1.contains(data[i])) {
		++nHits;
		}
}		}
// Expect about 5 false positives		// Expect about 5 false positives
BOOST_CHECK_EQUAL(nHits, 6);		BOOST_CHECK_EQUAL(nHits, 6);

// last-1000-entry, 0.01% false positive:		// last-1000-entry, 0.01% false positive:
CRollingBloomFilter rb2(1000, 0.001);		CRollingBloomFilter rb2(1000, 0.001);
for (int i = 0; i < DATASIZE; i++) {		for (int i = 0; i < DATASIZE; i++) {
rb2.insert(data[i]);		rb2.insert(data[i]);
Show All 9 Lines