From 114b5812f6283f2325fc31e186b26c6d76f9551a Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Thu, 29 Oct 2015 07:11:24 +0100 Subject: Prevector type --- src/test/prevector_tests.cpp | 217 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 217 insertions(+) create mode 100644 src/test/prevector_tests.cpp (limited to 'src/test/prevector_tests.cpp') diff --git a/src/test/prevector_tests.cpp b/src/test/prevector_tests.cpp new file mode 100644 index 000000000..01a45b540 --- /dev/null +++ b/src/test/prevector_tests.cpp @@ -0,0 +1,217 @@ +// Copyright (c) 2015 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include +#include "prevector.h" +#include "random.h" + +#include "serialize.h" +#include "streams.h" + +#include "test/test_bitcoin.h" + +#include + +BOOST_FIXTURE_TEST_SUITE(PrevectorTests, TestingSetup) + +template +class prevector_tester { + typedef std::vector realtype; + realtype real_vector; + + typedef prevector pretype; + pretype pre_vector; + + typedef typename pretype::size_type Size; + + void test() { + const pretype& const_pre_vector = pre_vector; + BOOST_CHECK_EQUAL(real_vector.size(), pre_vector.size()); + BOOST_CHECK_EQUAL(real_vector.empty(), pre_vector.empty()); + for (Size s = 0; s < real_vector.size(); s++) { + BOOST_CHECK(real_vector[s] == pre_vector[s]); + BOOST_CHECK(&(pre_vector[s]) == &(pre_vector.begin()[s])); + BOOST_CHECK(&(pre_vector[s]) == &*(pre_vector.begin() + s)); + BOOST_CHECK(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size())); + } + // BOOST_CHECK(realtype(pre_vector) == real_vector); + BOOST_CHECK(pretype(real_vector.begin(), real_vector.end()) == pre_vector); + BOOST_CHECK(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector); + size_t pos = 0; + BOOST_FOREACH(const T& v, pre_vector) { + BOOST_CHECK(v == real_vector[pos++]); + } + BOOST_REVERSE_FOREACH(const T& v, pre_vector) { + BOOST_CHECK(v == real_vector[--pos]); + } + BOOST_FOREACH(const T& v, const_pre_vector) { + BOOST_CHECK(v == real_vector[pos++]); + } + BOOST_REVERSE_FOREACH(const T& v, const_pre_vector) { + BOOST_CHECK(v == real_vector[--pos]); + } + CDataStream ss1(SER_DISK, 0); + CDataStream ss2(SER_DISK, 0); + ss1 << real_vector; + ss2 << pre_vector; + BOOST_CHECK_EQUAL(ss1.size(), ss2.size()); + for (Size s = 0; s < ss1.size(); s++) { + BOOST_CHECK_EQUAL(ss1[s], ss2[s]); + } + } + +public: + void resize(Size s) { + real_vector.resize(s); + BOOST_CHECK_EQUAL(real_vector.size(), s); + pre_vector.resize(s); + BOOST_CHECK_EQUAL(pre_vector.size(), s); + test(); + } + + void reserve(Size s) { + real_vector.reserve(s); + BOOST_CHECK(real_vector.capacity() >= s); + pre_vector.reserve(s); + BOOST_CHECK(pre_vector.capacity() >= s); + test(); + } + + void insert(Size position, const T& value) { + real_vector.insert(real_vector.begin() + position, value); + pre_vector.insert(pre_vector.begin() + position, value); + test(); + } + + void insert(Size position, Size count, const T& value) { + real_vector.insert(real_vector.begin() + position, count, value); + pre_vector.insert(pre_vector.begin() + position, count, value); + test(); + } + + template + void insert_range(Size position, I first, I last) { + real_vector.insert(real_vector.begin() + position, first, last); + pre_vector.insert(pre_vector.begin() + position, first, last); + test(); + } + + void erase(Size position) { + real_vector.erase(real_vector.begin() + position); + pre_vector.erase(pre_vector.begin() + position); + test(); + } + + void erase(Size first, Size last) { + real_vector.erase(real_vector.begin() + first, real_vector.begin() + last); + pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last); + test(); + } + + void update(Size pos, const T& value) { + real_vector[pos] = value; + pre_vector[pos] = value; + test(); + } + + void push_back(const T& value) { + real_vector.push_back(value); + pre_vector.push_back(value); + test(); + } + + void pop_back() { + real_vector.pop_back(); + pre_vector.pop_back(); + test(); + } + + void clear() { + real_vector.clear(); + pre_vector.clear(); + } + + void assign(Size n, const T& value) { + real_vector.assign(n, value); + pre_vector.assign(n, value); + } + + Size size() { + return real_vector.size(); + } + + Size capacity() { + return pre_vector.capacity(); + } + + void shrink_to_fit() { + pre_vector.shrink_to_fit(); + test(); + } +}; + +BOOST_AUTO_TEST_CASE(PrevectorTestInt) +{ + for (int j = 0; j < 64; j++) { + prevector_tester<8, int> test; + for (int i = 0; i < 2048; i++) { + int r = insecure_rand(); + if ((r % 4) == 0) { + test.insert(insecure_rand() % (test.size() + 1), insecure_rand()); + } + if (test.size() > 0 && ((r >> 2) % 4) == 1) { + test.erase(insecure_rand() % test.size()); + } + if (((r >> 4) % 8) == 2) { + int new_size = std::max(0, std::min(30, test.size() + (insecure_rand() % 5) - 2)); + test.resize(new_size); + } + if (((r >> 7) % 8) == 3) { + test.insert(insecure_rand() % (test.size() + 1), 1 + (insecure_rand() % 2), insecure_rand()); + } + if (((r >> 10) % 8) == 4) { + int del = std::min(test.size(), 1 + (insecure_rand() % 2)); + int beg = insecure_rand() % (test.size() + 1 - del); + test.erase(beg, beg + del); + } + if (((r >> 13) % 16) == 5) { + test.push_back(insecure_rand()); + } + if (test.size() > 0 && ((r >> 17) % 16) == 6) { + test.pop_back(); + } + if (((r >> 21) % 32) == 7) { + int values[4]; + int num = 1 + (insecure_rand() % 4); + for (int i = 0; i < num; i++) { + values[i] = insecure_rand(); + } + test.insert_range(insecure_rand() % (test.size() + 1), values, values + num); + } + if (((r >> 26) % 32) == 8) { + int del = std::min(test.size(), 1 + (insecure_rand() % 4)); + int beg = insecure_rand() % (test.size() + 1 - del); + test.erase(beg, beg + del); + } + r = insecure_rand(); + if (r % 32 == 9) { + test.reserve(insecure_rand() % 32); + } + if ((r >> 5) % 64 == 10) { + test.shrink_to_fit(); + } + if (test.size() > 0) { + test.update(insecure_rand() % test.size(), insecure_rand()); + } + if (((r >> 11) & 1024) == 11) { + test.clear(); + } + if (((r >> 21) & 512) == 12) { + test.assign(insecure_rand() % 32, insecure_rand()); + } + } + } +} + +BOOST_AUTO_TEST_SUITE_END() -- cgit v1.2.3 From 4ed41a2b611dfd328fe6f72312d6c596650f03f8 Mon Sep 17 00:00:00 2001 From: Kaz Wesley Date: Sat, 16 Apr 2016 06:49:38 -0700 Subject: test prevector::swap - add a swap operation to prevector tests (fails due to broken prevector::swap) - fix 2 prevector test operation conditions that were impossible --- src/test/prevector_tests.cpp | 15 +++++++++++++-- 1 file changed, 13 insertions(+), 2 deletions(-) (limited to 'src/test/prevector_tests.cpp') diff --git a/src/test/prevector_tests.cpp b/src/test/prevector_tests.cpp index 01a45b540..b39b90353 100644 --- a/src/test/prevector_tests.cpp +++ b/src/test/prevector_tests.cpp @@ -19,9 +19,11 @@ template class prevector_tester { typedef std::vector realtype; realtype real_vector; + realtype real_vector_alt; typedef prevector pretype; pretype pre_vector; + pretype pre_vector_alt; typedef typename pretype::size_type Size; @@ -149,6 +151,12 @@ public: pre_vector.shrink_to_fit(); test(); } + + void swap() { + real_vector.swap(real_vector_alt); + pre_vector.swap(pre_vector_alt); + test(); + } }; BOOST_AUTO_TEST_CASE(PrevectorTestInt) @@ -204,12 +212,15 @@ BOOST_AUTO_TEST_CASE(PrevectorTestInt) if (test.size() > 0) { test.update(insecure_rand() % test.size(), insecure_rand()); } - if (((r >> 11) & 1024) == 11) { + if (((r >> 11) % 1024) == 11) { test.clear(); } - if (((r >> 21) & 512) == 12) { + if (((r >> 21) % 512) == 12) { test.assign(insecure_rand() % 32, insecure_rand()); } + if (((r >> 15) % 64) == 3) { + test.swap(); + } } } } -- cgit v1.2.3 From c2715d3ab8d83be5bc256380b84d5467e85a4330 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Pavel=20Jan=C3=ADk?= Date: Tue, 7 Jun 2016 21:22:48 +0200 Subject: Do not shadow local variables --- src/test/prevector_tests.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/test/prevector_tests.cpp') diff --git a/src/test/prevector_tests.cpp b/src/test/prevector_tests.cpp index b39b90353..d1407c1da 100644 --- a/src/test/prevector_tests.cpp +++ b/src/test/prevector_tests.cpp @@ -192,8 +192,8 @@ BOOST_AUTO_TEST_CASE(PrevectorTestInt) if (((r >> 21) % 32) == 7) { int values[4]; int num = 1 + (insecure_rand() % 4); - for (int i = 0; i < num; i++) { - values[i] = insecure_rand(); + for (int k = 0; k < num; k++) { + values[k] = insecure_rand(); } test.insert_range(insecure_rand() % (test.size() + 1), values, values + num); } -- cgit v1.2.3 From f71d4a3786611d564e4c239099501daee989b170 Mon Sep 17 00:00:00 2001 From: Jeremy Rubin Date: Tue, 6 Sep 2016 16:19:25 -0400 Subject: Minimal fix to slow prevector tests as stopgap measure --- src/test/prevector_tests.cpp | 62 ++++++++++++++++++++++++++++++-------------- 1 file changed, 43 insertions(+), 19 deletions(-) (limited to 'src/test/prevector_tests.cpp') diff --git a/src/test/prevector_tests.cpp b/src/test/prevector_tests.cpp index d1407c1da..b8c45ca56 100644 --- a/src/test/prevector_tests.cpp +++ b/src/test/prevector_tests.cpp @@ -26,57 +26,70 @@ class prevector_tester { pretype pre_vector_alt; typedef typename pretype::size_type Size; + bool passed = true; + uint32_t insecure_rand_Rz_cache; + uint32_t insecure_rand_Rw_cache; + + template + void local_check_equal(A a, B b) + { + local_check(a == b); + } + void local_check(bool b) + { + passed &= b; + } void test() { const pretype& const_pre_vector = pre_vector; - BOOST_CHECK_EQUAL(real_vector.size(), pre_vector.size()); - BOOST_CHECK_EQUAL(real_vector.empty(), pre_vector.empty()); + local_check_equal(real_vector.size(), pre_vector.size()); + local_check_equal(real_vector.empty(), pre_vector.empty()); for (Size s = 0; s < real_vector.size(); s++) { - BOOST_CHECK(real_vector[s] == pre_vector[s]); - BOOST_CHECK(&(pre_vector[s]) == &(pre_vector.begin()[s])); - BOOST_CHECK(&(pre_vector[s]) == &*(pre_vector.begin() + s)); - BOOST_CHECK(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size())); + local_check(real_vector[s] == pre_vector[s]); + local_check(&(pre_vector[s]) == &(pre_vector.begin()[s])); + local_check(&(pre_vector[s]) == &*(pre_vector.begin() + s)); + local_check(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size())); } - // BOOST_CHECK(realtype(pre_vector) == real_vector); - BOOST_CHECK(pretype(real_vector.begin(), real_vector.end()) == pre_vector); - BOOST_CHECK(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector); + // local_check(realtype(pre_vector) == real_vector); + local_check(pretype(real_vector.begin(), real_vector.end()) == pre_vector); + local_check(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector); size_t pos = 0; BOOST_FOREACH(const T& v, pre_vector) { - BOOST_CHECK(v == real_vector[pos++]); + local_check(v == real_vector[pos++]); } BOOST_REVERSE_FOREACH(const T& v, pre_vector) { - BOOST_CHECK(v == real_vector[--pos]); + local_check(v == real_vector[--pos]); } BOOST_FOREACH(const T& v, const_pre_vector) { - BOOST_CHECK(v == real_vector[pos++]); + local_check(v == real_vector[pos++]); } BOOST_REVERSE_FOREACH(const T& v, const_pre_vector) { - BOOST_CHECK(v == real_vector[--pos]); + local_check(v == real_vector[--pos]); } CDataStream ss1(SER_DISK, 0); CDataStream ss2(SER_DISK, 0); ss1 << real_vector; ss2 << pre_vector; - BOOST_CHECK_EQUAL(ss1.size(), ss2.size()); + local_check_equal(ss1.size(), ss2.size()); for (Size s = 0; s < ss1.size(); s++) { - BOOST_CHECK_EQUAL(ss1[s], ss2[s]); + local_check_equal(ss1[s], ss2[s]); } } public: void resize(Size s) { real_vector.resize(s); - BOOST_CHECK_EQUAL(real_vector.size(), s); + local_check_equal(real_vector.size(), s); pre_vector.resize(s); - BOOST_CHECK_EQUAL(pre_vector.size(), s); + local_check_equal(pre_vector.size(), s); test(); } void reserve(Size s) { real_vector.reserve(s); - BOOST_CHECK(real_vector.capacity() >= s); + local_check(real_vector.capacity() >= s); pre_vector.reserve(s); - BOOST_CHECK(pre_vector.capacity() >= s); + local_check(pre_vector.capacity() >= s); test(); } @@ -157,6 +170,17 @@ public: pre_vector.swap(pre_vector_alt); test(); } + ~prevector_tester() { + BOOST_CHECK_MESSAGE(passed, "insecure_rand_Rz: " + << insecure_rand_Rz_cache + << ", insecure_rand_Rw: " + << insecure_rand_Rw_cache); + } + prevector_tester() { + seed_insecure_rand(); + insecure_rand_Rz_cache = insecure_rand_Rz; + insecure_rand_Rw_cache = insecure_rand_Rw; + } }; BOOST_AUTO_TEST_CASE(PrevectorTestInt) -- cgit v1.2.3 From 5eaaa83ac1f5eb525f93e2808fafd73f5ed97013 Mon Sep 17 00:00:00 2001 From: "Wladimir J. van der Laan" Date: Thu, 13 Oct 2016 16:19:20 +0200 Subject: Kill insecure_random and associated global state There are only a few uses of `insecure_random` outside the tests. This PR replaces uses of insecure_random (and its accompanying global state) in the core code with an FastRandomContext that is automatically seeded on creation. This is meant to be used for inner loops. The FastRandomContext can be in the outer scope, or the class itself, then rand32() is used inside the loop. Useful e.g. for pushing addresses in CNode or the fee rounding, or randomization for coin selection. As a context is created per purpose, thus it gets rid of cross-thread unprotected shared usage of a single set of globals, this should also get rid of the potential race conditions. - I'd say TxMempool::check is not called enough to warrant using a special fast random context, this is switched to GetRand() (open for discussion...) - The use of `insecure_rand` in ConnectThroughProxy has been replaced by an atomic integer counter. The only goal here is to have a different credentials pair for each connection to go on a different Tor circuit, it does not need to be random nor unpredictable. - To avoid having a FastRandomContext on every CNode, the context is passed into PushAddress as appropriate. There remains an insecure_random for test usage in `test_random.h`. --- src/test/prevector_tests.cpp | 14 ++++++-------- 1 file changed, 6 insertions(+), 8 deletions(-) (limited to 'src/test/prevector_tests.cpp') diff --git a/src/test/prevector_tests.cpp b/src/test/prevector_tests.cpp index b8c45ca56..6cad02e73 100644 --- a/src/test/prevector_tests.cpp +++ b/src/test/prevector_tests.cpp @@ -4,7 +4,7 @@ #include #include "prevector.h" -#include "random.h" +#include "test_random.h" #include "serialize.h" #include "streams.h" @@ -27,8 +27,7 @@ class prevector_tester { typedef typename pretype::size_type Size; bool passed = true; - uint32_t insecure_rand_Rz_cache; - uint32_t insecure_rand_Rw_cache; + FastRandomContext rand_cache; template @@ -171,15 +170,14 @@ public: test(); } ~prevector_tester() { - BOOST_CHECK_MESSAGE(passed, "insecure_rand_Rz: " - << insecure_rand_Rz_cache + BOOST_CHECK_MESSAGE(passed, "insecure_rand_Rz: " + << rand_cache.Rz << ", insecure_rand_Rw: " - << insecure_rand_Rw_cache); + << rand_cache.Rw); } prevector_tester() { seed_insecure_rand(); - insecure_rand_Rz_cache = insecure_rand_Rz; - insecure_rand_Rw_cache = insecure_rand_Rw; + rand_cache = insecure_rand_ctx; } }; -- cgit v1.2.3 From fa8278e845b6a80164e13a39f917a101fe14b10d Mon Sep 17 00:00:00 2001 From: MarcoFalke Date: Mon, 7 Nov 2016 15:04:57 +0100 Subject: test: Fix test_random includes --- src/test/prevector_tests.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/test/prevector_tests.cpp') diff --git a/src/test/prevector_tests.cpp b/src/test/prevector_tests.cpp index 6cad02e73..1e5de2021 100644 --- a/src/test/prevector_tests.cpp +++ b/src/test/prevector_tests.cpp @@ -4,12 +4,12 @@ #include #include "prevector.h" -#include "test_random.h" #include "serialize.h" #include "streams.h" #include "test/test_bitcoin.h" +#include "test/test_random.h" #include -- cgit v1.2.3 From 2ddfcfd2d67bc2bd8aa4682ceaba6a59614e54d1 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 13 Dec 2016 19:36:46 -0800 Subject: Make CScript (and prevector) c++11 movable. Such moves are used when reallocating vectors that contain them, for example. --- src/test/prevector_tests.cpp | 21 ++++++++++++++++++++- 1 file changed, 20 insertions(+), 1 deletion(-) (limited to 'src/test/prevector_tests.cpp') diff --git a/src/test/prevector_tests.cpp b/src/test/prevector_tests.cpp index 1e5de2021..1352ea722 100644 --- a/src/test/prevector_tests.cpp +++ b/src/test/prevector_tests.cpp @@ -169,6 +169,19 @@ public: pre_vector.swap(pre_vector_alt); test(); } + + void move() { + real_vector = std::move(real_vector_alt); + real_vector_alt.clear(); + pre_vector = std::move(pre_vector_alt); + pre_vector_alt.clear(); + } + + void copy() { + real_vector = real_vector_alt; + pre_vector = pre_vector_alt; + } + ~prevector_tester() { BOOST_CHECK_MESSAGE(passed, "insecure_rand_Rz: " << rand_cache.Rz @@ -240,9 +253,15 @@ BOOST_AUTO_TEST_CASE(PrevectorTestInt) if (((r >> 21) % 512) == 12) { test.assign(insecure_rand() % 32, insecure_rand()); } - if (((r >> 15) % 64) == 3) { + if (((r >> 15) % 8) == 3) { test.swap(); } + if (((r >> 15) % 16) == 8) { + test.copy(); + } + if (((r >> 15) % 32) == 18) { + test.move(); + } } } } -- cgit v1.2.3 From 27765b6403cece54320374b37afb01a0cfe571c3 Mon Sep 17 00:00:00 2001 From: isle2983 Date: Sat, 31 Dec 2016 11:01:21 -0700 Subject: Increment MIT Licence copyright header year on files modified in 2016 Edited via: $ contrib/devtools/copyright_header.py update . --- src/test/prevector_tests.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/test/prevector_tests.cpp') diff --git a/src/test/prevector_tests.cpp b/src/test/prevector_tests.cpp index 1352ea722..bd8a7819a 100644 --- a/src/test/prevector_tests.cpp +++ b/src/test/prevector_tests.cpp @@ -1,4 +1,4 @@ -// Copyright (c) 2015 The Bitcoin Core developers +// Copyright (c) 2015-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. -- cgit v1.2.3