aboutsummaryrefslogtreecommitdiff
path: root/src/test
diff options
context:
space:
mode:
Diffstat (limited to 'src/test')
-rw-r--r--src/test/bloom_tests.cpp78
-rw-r--r--src/test/mruset_tests.cpp126
2 files changed, 132 insertions, 72 deletions
diff --git a/src/test/bloom_tests.cpp b/src/test/bloom_tests.cpp
index 73a146f05c..1bda8a7ea1 100644
--- a/src/test/bloom_tests.cpp
+++ b/src/test/bloom_tests.cpp
@@ -8,6 +8,7 @@
#include "clientversion.h"
#include "key.h"
#include "merkleblock.h"
+#include "random.h"
#include "serialize.h"
#include "streams.h"
#include "uint256.h"
@@ -459,4 +460,81 @@ BOOST_AUTO_TEST_CASE(merkle_block_4_test_update_none)
BOOST_CHECK(!filter.contains(COutPoint(uint256S("0x02981fa052f0481dbc5868f4fc2166035a10f27a03cfd2de67326471df5bc041"), 0)));
}
+static std::vector<unsigned char> RandomData()
+{
+ uint256 r = GetRandHash();
+ return std::vector<unsigned char>(r.begin(), r.end());
+}
+
+BOOST_AUTO_TEST_CASE(rolling_bloom)
+{
+ // last-100-entry, 1% false positive:
+ CRollingBloomFilter rb1(100, 0.01, 0);
+
+ // Overfill:
+ static const int DATASIZE=399;
+ std::vector<unsigned char> data[DATASIZE];
+ for (int i = 0; i < DATASIZE; i++) {
+ data[i] = RandomData();
+ rb1.insert(data[i]);
+ }
+ // Last 100 guaranteed to be remembered:
+ for (int i = 299; i < DATASIZE; i++) {
+ BOOST_CHECK(rb1.contains(data[i]));
+ }
+
+ // false positive rate is 1%, so we should get about 100 hits if
+ // testing 10,000 random keys. We get worst-case false positive
+ // behavior when the filter is as full as possible, which is
+ // when we've inserted one minus an integer multiple of nElement*2.
+ unsigned int nHits = 0;
+ for (int i = 0; i < 10000; i++) {
+ if (rb1.contains(RandomData()))
+ ++nHits;
+ }
+ // Run test_bitcoin with --log_level=message to see BOOST_TEST_MESSAGEs:
+ BOOST_TEST_MESSAGE("RollingBloomFilter got " << nHits << " false positives (~100 expected)");
+
+ // Insanely unlikely to get a fp count outside this range:
+ BOOST_CHECK(nHits > 25);
+ BOOST_CHECK(nHits < 175);
+
+ BOOST_CHECK(rb1.contains(data[DATASIZE-1]));
+ rb1.clear();
+ BOOST_CHECK(!rb1.contains(data[DATASIZE-1]));
+
+ // Now roll through data, make sure last 100 entries
+ // are always remembered:
+ for (int i = 0; i < DATASIZE; i++) {
+ if (i >= 100)
+ BOOST_CHECK(rb1.contains(data[i-100]));
+ rb1.insert(data[i]);
+ }
+
+ // Insert 999 more random entries:
+ for (int i = 0; i < 999; i++) {
+ rb1.insert(RandomData());
+ }
+ // Sanity check to make sure the filter isn't just filling up:
+ nHits = 0;
+ for (int i = 0; i < DATASIZE; i++) {
+ if (rb1.contains(data[i]))
+ ++nHits;
+ }
+ // Expect about 5 false positives, more than 100 means
+ // something is definitely broken.
+ BOOST_TEST_MESSAGE("RollingBloomFilter got " << nHits << " false positives (~5 expected)");
+ BOOST_CHECK(nHits < 100);
+
+ // last-1000-entry, 0.01% false positive:
+ CRollingBloomFilter rb2(1000, 0.001, 0);
+ for (int i = 0; i < DATASIZE; i++) {
+ rb2.insert(data[i]);
+ }
+ // ... room for all of them:
+ for (int i = 0; i < DATASIZE; i++) {
+ BOOST_CHECK(rb2.contains(data[i]));
+ }
+}
+
BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/mruset_tests.cpp b/src/test/mruset_tests.cpp
index bd4e9c1d38..2b68f8899e 100644
--- a/src/test/mruset_tests.cpp
+++ b/src/test/mruset_tests.cpp
@@ -17,83 +17,65 @@
using namespace std;
-class mrutester
-{
-private:
- mruset<int> mru;
- std::set<int> set;
-
-public:
- mrutester() { mru.max_size(MAX_SIZE); }
- int size() const { return set.size(); }
-
- void insert(int n)
- {
- mru.insert(n);
- set.insert(n);
- BOOST_CHECK(mru == set);
- }
-};
-
BOOST_FIXTURE_TEST_SUITE(mruset_tests, BasicTestingSetup)
-// Test that an mruset behaves like a set, as long as no more than MAX_SIZE elements are in it
-BOOST_AUTO_TEST_CASE(mruset_like_set)
-{
-
- for (int nTest=0; nTest<NUM_TESTS; nTest++)
- {
- mrutester tester;
- while (tester.size() < MAX_SIZE)
- tester.insert(GetRandInt(2 * MAX_SIZE));
- }
-
-}
-
-// Test that an mruset's size never exceeds its max_size
-BOOST_AUTO_TEST_CASE(mruset_limited_size)
+BOOST_AUTO_TEST_CASE(mruset_test)
{
- for (int nTest=0; nTest<NUM_TESTS; nTest++)
- {
- mruset<int> mru(MAX_SIZE);
- for (int nAction=0; nAction<3*MAX_SIZE; nAction++)
- {
- int n = GetRandInt(2 * MAX_SIZE);
- mru.insert(n);
- BOOST_CHECK(mru.size() <= MAX_SIZE);
+ // The mruset being tested.
+ mruset<int> mru(5000);
+
+ // Run the test 10 times.
+ for (int test = 0; test < 10; test++) {
+ // Reset mru.
+ mru.clear();
+
+ // A deque + set to simulate the mruset.
+ std::deque<int> rep;
+ std::set<int> all;
+
+ // Insert 10000 random integers below 15000.
+ for (int j=0; j<10000; j++) {
+ int add = GetRandInt(15000);
+ mru.insert(add);
+
+ // Add the number to rep/all as well.
+ if (all.count(add) == 0) {
+ all.insert(add);
+ rep.push_back(add);
+ if (all.size() == 5001) {
+ all.erase(rep.front());
+ rep.pop_front();
+ }
+ }
+
+ // Do a full comparison between mru and the simulated mru every 1000 and every 5001 elements.
+ if (j % 1000 == 0 || j % 5001 == 0) {
+ mruset<int> mru2 = mru; // Also try making a copy
+
+ // Check that all elements that should be in there, are in there.
+ BOOST_FOREACH(int x, rep) {
+ BOOST_CHECK(mru.count(x));
+ BOOST_CHECK(mru2.count(x));
+ }
+
+ // Check that all elements that are in there, should be in there.
+ BOOST_FOREACH(int x, mru) {
+ BOOST_CHECK(all.count(x));
+ }
+
+ // Check that all elements that are in there, should be in there.
+ BOOST_FOREACH(int x, mru2) {
+ BOOST_CHECK(all.count(x));
+ }
+
+ for (int t = 0; t < 10; t++) {
+ int r = GetRandInt(15000);
+ BOOST_CHECK(all.count(r) == mru.count(r));
+ BOOST_CHECK(all.count(r) == mru2.count(r));
+ }
+ }
}
}
}
-// 16-bit permutation function
-int static permute(int n)
-{
- // hexadecimals of pi; verified to be linearly independent
- static const int table[16] = {0x243F, 0x6A88, 0x85A3, 0x08D3, 0x1319, 0x8A2E, 0x0370, 0x7344,
- 0xA409, 0x3822, 0x299F, 0x31D0, 0x082E, 0xFA98, 0xEC4E, 0x6C89};
-
- int ret = 0;
- for (int bit=0; bit<16; bit++)
- if (n & (1<<bit))
- ret ^= table[bit];
-
- return ret;
-}
-
-// Test that an mruset acts like a moving window, if no duplicate elements are added
-BOOST_AUTO_TEST_CASE(mruset_window)
-{
- mruset<int> mru(MAX_SIZE);
- for (int n=0; n<10*MAX_SIZE; n++)
- {
- mru.insert(permute(n));
-
- set<int> tester;
- for (int m=max(0,n-MAX_SIZE+1); m<=n; m++)
- tester.insert(permute(m));
-
- BOOST_CHECK(mru == tester);
- }
-}
-
BOOST_AUTO_TEST_SUITE_END()
generated by cgit v1.2.3 (git 2.26.2) at 2024-08-20 05:10:29 +0000