Prevector type

5 files changed, 226 insertions, 9 deletions

diff --git a/src/test/miner_tests.cpp b/src/test/miner_tests.cpp
index 827525783a..d92b7ec62e 100644
--- a/src/test/miner_tests.cpp
+++ b/src/test/miner_tests.cpp
@@ -186,7 +186,7 @@ BOOST_AUTO_TEST_CASE(CreateNewBlock_validity)
     hash = tx.GetHash();
     mempool.addUnchecked(hash, CTxMemPoolEntry(tx, 11, GetTime(), 111.0, 11));
     tx.vin[0].prevout.hash = hash;
-    tx.vin[0].scriptSig = CScript() << (std::vector<unsigned char>)script;
+    tx.vin[0].scriptSig = CScript() << std::vector<unsigned char>(script.begin(), script.end());
     tx.vout[0].nValue -= 1000000;
     hash = tx.GetHash();
     mempool.addUnchecked(hash, CTxMemPoolEntry(tx, 11, GetTime(), 111.0, 11));
diff --git a/src/test/prevector_tests.cpp b/src/test/prevector_tests.cpp
new file mode 100644
index 0000000000..01a45b540d
--- /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 <vector>
+#include "prevector.h"
+#include "random.h"
+
+#include "serialize.h"
+#include "streams.h"
+
+#include "test/test_bitcoin.h"
+
+#include <boost/test/unit_test.hpp>
+
+BOOST_FIXTURE_TEST_SUITE(PrevectorTests, TestingSetup)
+
+template<unsigned int N, typename T>
+class prevector_tester {
+    typedef std::vector<T> realtype;
+    realtype real_vector;
+
+    typedef prevector<N, T> 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<typename I>
+    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<int>(0, std::min<int>(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<int>(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<int>(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()
diff --git a/src/test/script_P2SH_tests.cpp b/src/test/script_P2SH_tests.cpp
index 16c9a4a868..e36aca8dfa 100644
--- a/src/test/script_P2SH_tests.cpp
+++ b/src/test/script_P2SH_tests.cpp
@@ -25,7 +25,7 @@ using namespace std;
 static std::vector<unsigned char>
 Serialize(const CScript& s)
 {
-    std::vector<unsigned char> sSerialized(s);
+    std::vector<unsigned char> sSerialized(s.begin(), s.end());
     return sSerialized;
 }
 
@@ -339,8 +339,8 @@ BOOST_AUTO_TEST_CASE(AreInputsStandard)
     // SignSignature doesn't know how to sign these. We're
     // not testing validating signatures, so just create
     // dummy signatures that DO include the correct P2SH scripts:
-    txTo.vin[3].scriptSig << OP_11 << OP_11 << static_cast<vector<unsigned char> >(oneAndTwo);
-    txTo.vin[4].scriptSig << static_cast<vector<unsigned char> >(fifteenSigops);
+    txTo.vin[3].scriptSig << OP_11 << OP_11 << vector<unsigned char>(oneAndTwo.begin(), oneAndTwo.end());
+    txTo.vin[4].scriptSig << vector<unsigned char>(fifteenSigops.begin(), fifteenSigops.end());
 
     BOOST_CHECK(::AreInputsStandard(txTo, coins));
     // 22 P2SH sigops for all inputs (1 for vin[0], 6 for vin[3], 15 for vin[4]
@@ -362,7 +362,7 @@ BOOST_AUTO_TEST_CASE(AreInputsStandard)
     txToNonStd1.vin.resize(1);
     txToNonStd1.vin[0].prevout.n = 5;
     txToNonStd1.vin[0].prevout.hash = txFrom.GetHash();
-    txToNonStd1.vin[0].scriptSig << static_cast<vector<unsigned char> >(sixteenSigops);
+    txToNonStd1.vin[0].scriptSig << vector<unsigned char>(sixteenSigops.begin(), sixteenSigops.end());
 
     BOOST_CHECK(!::AreInputsStandard(txToNonStd1, coins));
     BOOST_CHECK_EQUAL(GetP2SHSigOpCount(txToNonStd1, coins), 16U);
@@ -374,7 +374,7 @@ BOOST_AUTO_TEST_CASE(AreInputsStandard)
     txToNonStd2.vin.resize(1);
     txToNonStd2.vin[0].prevout.n = 6;
     txToNonStd2.vin[0].prevout.hash = txFrom.GetHash();
-    txToNonStd2.vin[0].scriptSig << static_cast<vector<unsigned char> >(twentySigops);
+    txToNonStd2.vin[0].scriptSig << vector<unsigned char>(twentySigops.begin(), twentySigops.end());
 
     BOOST_CHECK(!::AreInputsStandard(txToNonStd2, coins));
     BOOST_CHECK_EQUAL(GetP2SHSigOpCount(txToNonStd2, coins), 20U);
diff --git a/src/test/script_tests.cpp b/src/test/script_tests.cpp
index 882f9eb199..0059e4a998 100644
--- a/src/test/script_tests.cpp
+++ b/src/test/script_tests.cpp
@@ -260,7 +260,7 @@ public:
 
     TestBuilder& PushRedeem()
     {
-        DoPush(static_cast<std::vector<unsigned char> >(scriptPubKey));
+        DoPush(std::vector<unsigned char>(scriptPubKey.begin(), scriptPubKey.end()));
         return *this;
     }
 
@@ -892,7 +892,7 @@ BOOST_AUTO_TEST_CASE(script_combineSigs)
     combined = CombineSignatures(scriptPubKey, txTo, 0, scriptSigCopy, scriptSig);
     BOOST_CHECK(combined == scriptSigCopy || combined == scriptSig);
     // dummy scriptSigCopy with placeholder, should always choose non-placeholder:
-    scriptSigCopy = CScript() << OP_0 << static_cast<vector<unsigned char> >(pkSingle);
+    scriptSigCopy = CScript() << OP_0 << vector<unsigned char>(pkSingle.begin(), pkSingle.end());
     combined = CombineSignatures(scriptPubKey, txTo, 0, scriptSigCopy, scriptSig);
     BOOST_CHECK(combined == scriptSig);
     combined = CombineSignatures(scriptPubKey, txTo, 0, scriptSig, scriptSigCopy);
diff --git a/src/test/sigopcount_tests.cpp b/src/test/sigopcount_tests.cpp
index b26fed99f2..ea2b9b795f 100644
--- a/src/test/sigopcount_tests.cpp
+++ b/src/test/sigopcount_tests.cpp
@@ -20,7 +20,7 @@ using namespace std;
 static std::vector<unsigned char>
 Serialize(const CScript& s)
 {
-    std::vector<unsigned char> sSerialized(s);
+    std::vector<unsigned char> sSerialized(s.begin(), s.end());
     return sSerialized;
 }