aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorPieter Wuille <pieter.wuille@gmail.com>2014-06-29 15:26:58 +0200
committerPieter Wuille <pieter.wuille@gmail.com>2014-06-29 21:51:55 +0200
commit236982c2b6de619f0744c9c17ea7208b64a4afb3 (patch)
treea8b8c2de488fbe6b4dd23dd2f95e6d2ec3c5c708 /src
parentc9a0918330f31dcb1d5e86b56af63c3f521d3cf2 (diff)
Add skiplist unit tests
Diffstat (limited to 'src')
-rw-r--r--src/Makefile.test.include1
-rw-r--r--src/test/skiplist_tests.cpp45
2 files changed, 46 insertions, 0 deletions
diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index 4dab1773f4..8685452c7b 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -47,6 +47,7 @@ BITCOIN_TESTS =\
test/script_tests.cpp \
test/serialize_tests.cpp \
test/sigopcount_tests.cpp \
+ test/skiplist_tests.cpp \
test/test_bitcoin.cpp \
test/transaction_tests.cpp \
test/uint256_tests.cpp \
diff --git a/src/test/skiplist_tests.cpp b/src/test/skiplist_tests.cpp
new file mode 100644
index 0000000000..ea301685c9
--- /dev/null
+++ b/src/test/skiplist_tests.cpp
@@ -0,0 +1,45 @@
+// Copyright (c) 2014 The Bitcoin Core developers
+// Distributed under the MIT/X11 software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <boost/test/unit_test.hpp>
+#include <vector>
+#include "main.h"
+#include "util.h"
+
+
+#define SKIPLIST_LENGTH 300000
+
+BOOST_AUTO_TEST_SUITE(skiplist_tests)
+
+BOOST_AUTO_TEST_CASE(skiplist_test)
+{
+ std::vector<CBlockIndex> vIndex(SKIPLIST_LENGTH);
+
+ for (int i=0; i<SKIPLIST_LENGTH; i++) {
+ vIndex[i].nHeight = i;
+ vIndex[i].pprev = (i == 0) ? NULL : &vIndex[i - 1];
+ vIndex[i].BuildSkip();
+ }
+
+ for (int i=0; i<SKIPLIST_LENGTH; i++) {
+ if (i > 0) {
+ BOOST_CHECK(vIndex[i].pskip == &vIndex[vIndex[i].pskip->nHeight]);
+ BOOST_CHECK(vIndex[i].pskip->nHeight < i);
+ } else {
+ BOOST_CHECK(vIndex[i].pskip == NULL);
+ }
+ }
+
+ for (int i=0; i < 1000; i++) {
+ int from = insecure_rand() % (SKIPLIST_LENGTH - 1);
+ int to = insecure_rand() % (from + 1);
+
+ BOOST_CHECK(vIndex[SKIPLIST_LENGTH - 1].GetAncestor(from) == &vIndex[from]);
+ BOOST_CHECK(vIndex[from].GetAncestor(to) == &vIndex[to]);
+ BOOST_CHECK(vIndex[from].GetAncestor(0) == &vIndex[0]);
+ }
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+