src/test/prevector_tests.cpp

   1 // Copyright (c) 2015-2016 The Bitcoin Core developers
   2 // Distributed under the MIT software license, see the accompanying
   3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   4
   5 #include <vector>
   6 #include "prevector.h"
   7
   8 #include "reverse_iterator.h"
   9 #include "serialize.h"
  10 #include "streams.h"
  11
  12 #include "test/test_bitcoin.h"
  13
  14 #include <boost/test/unit_test.hpp>
  15
  16 BOOST_FIXTURE_TEST_SUITE(PrevectorTests, TestingSetup)
  17
  18 template<unsigned int N, typename T>
  19 class prevector_tester {
  20     typedef std::vector<T> realtype;
  21     realtype real_vector;
  22     realtype real_vector_alt;
  23
  24     typedef prevector<N, T> pretype;
  25     pretype pre_vector;
  26     pretype pre_vector_alt;
  27
  28     typedef typename pretype::size_type Size;
  29     bool passed = true;
  30     FastRandomContext rand_cache;
  31     uint256 rand_seed;
  32
  33
  34     template <typename A, typename B>
  35         void local_check_equal(A a, B b)
  36         {
  37             local_check(a == b);
  38         }
  39     void local_check(bool b)
  40     {
  41         passed &= b;
  42     }
  43     void test() {
  44         const pretype& const_pre_vector = pre_vector;
  45         local_check_equal(real_vector.size(), pre_vector.size());
  46         local_check_equal(real_vector.empty(), pre_vector.empty());
  47         for (Size s = 0; s < real_vector.size(); s++) {
  48              local_check(real_vector[s] == pre_vector[s]);
  49              local_check(&(pre_vector[s]) == &(pre_vector.begin()[s]));
  50              local_check(&(pre_vector[s]) == &*(pre_vector.begin() + s));
  51              local_check(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size()));
  52         }
  53         // local_check(realtype(pre_vector) == real_vector);
  54         local_check(pretype(real_vector.begin(), real_vector.end()) == pre_vector);
  55         local_check(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector);
  56         size_t pos = 0;
  57         for (const T& v : pre_vector) {
  58              local_check(v == real_vector[pos++]);
  59         }
  60         for (const T& v : reverse_iterate(pre_vector)) {
  61              local_check(v == real_vector[--pos]);
  62         }
  63         for (const T& v : const_pre_vector) {
  64              local_check(v == real_vector[pos++]);
  65         }
  66         for (const T& v : reverse_iterate(const_pre_vector)) {
  67              local_check(v == real_vector[--pos]);
  68         }
  69         CDataStream ss1(SER_DISK, 0);
  70         CDataStream ss2(SER_DISK, 0);
  71         ss1 << real_vector;
  72         ss2 << pre_vector;
  73         local_check_equal(ss1.size(), ss2.size());
  74         for (Size s = 0; s < ss1.size(); s++) {
  75             local_check_equal(ss1[s], ss2[s]);
  76         }
  77     }
  78
  79 public:
  80     void resize(Size s) {
  81         real_vector.resize(s);
  82         local_check_equal(real_vector.size(), s);
  83         pre_vector.resize(s);
  84         local_check_equal(pre_vector.size(), s);
  85         test();
  86     }
  87
  88     void reserve(Size s) {
  89         real_vector.reserve(s);
  90         local_check(real_vector.capacity() >= s);
  91         pre_vector.reserve(s);
  92         local_check(pre_vector.capacity() >= s);
  93         test();
  94     }
  95
  96     void insert(Size position, const T& value) {
  97         real_vector.insert(real_vector.begin() + position, value);
  98         pre_vector.insert(pre_vector.begin() + position, value);
  99         test();
 100     }
 101
 102     void insert(Size position, Size count, const T& value) {
 103         real_vector.insert(real_vector.begin() + position, count, value);
 104         pre_vector.insert(pre_vector.begin() + position, count, value);
 105         test();
 106     }
 107
 108     template<typename I>
 109     void insert_range(Size position, I first, I last) {
 110         real_vector.insert(real_vector.begin() + position, first, last);
 111         pre_vector.insert(pre_vector.begin() + position, first, last);
 112         test();
 113     }
 114
 115     void erase(Size position) {
 116         real_vector.erase(real_vector.begin() + position);
 117         pre_vector.erase(pre_vector.begin() + position);
 118         test();
 119     }
 120
 121     void erase(Size first, Size last) {
 122         real_vector.erase(real_vector.begin() + first, real_vector.begin() + last);
 123         pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last);
 124         test();
 125     }
 126
 127     void update(Size pos, const T& value) {
 128         real_vector[pos] = value;
 129         pre_vector[pos] = value;
 130         test();
 131     }
 132
 133     void push_back(const T& value) {
 134         real_vector.push_back(value);
 135         pre_vector.push_back(value);
 136         test();
 137     }
 138
 139     void pop_back() {
 140         real_vector.pop_back();
 141         pre_vector.pop_back();
 142         test();
 143     }
 144
 145     void clear() {
 146         real_vector.clear();
 147         pre_vector.clear();
 148     }
 149
 150     void assign(Size n, const T& value) {
 151         real_vector.assign(n, value);
 152         pre_vector.assign(n, value);
 153     }
 154
 155     Size size() const {
 156         return real_vector.size();
 157     }
 158
 159     Size capacity() const {
 160         return pre_vector.capacity();
 161     }
 162
 163     void shrink_to_fit() {
 164         pre_vector.shrink_to_fit();
 165         test();
 166     }
 167
 168     void swap() {
 169         real_vector.swap(real_vector_alt);
 170         pre_vector.swap(pre_vector_alt);
 171         test();
 172     }
 173
 174     void move() {
 175         real_vector = std::move(real_vector_alt);
 176         real_vector_alt.clear();
 177         pre_vector = std::move(pre_vector_alt);
 178         pre_vector_alt.clear();
 179     }
 180
 181     void copy() {
 182         real_vector = real_vector_alt;
 183         pre_vector = pre_vector_alt;
 184     }
 185
 186     ~prevector_tester() {
 187         BOOST_CHECK_MESSAGE(passed, "insecure_rand: " + rand_seed.ToString());
 188     }
 189
 190     prevector_tester() {
 191         SeedInsecureRand();
 192         rand_seed = insecure_rand_seed;
 193         rand_cache = insecure_rand_ctx;
 194     }
 195 };
 196
 197 BOOST_AUTO_TEST_CASE(PrevectorTestInt)
 198 {
 199     for (int j = 0; j < 64; j++) {
 200         prevector_tester<8, int> test;
 201         for (int i = 0; i < 2048; i++) {
 202             if (InsecureRandBits(2) == 0) {
 203                 test.insert(InsecureRandRange(test.size() + 1), InsecureRand32());
 204             }
 205             if (test.size() > 0 && InsecureRandBits(2) == 1) {
 206                 test.erase(InsecureRandRange(test.size()));
 207             }
 208             if (InsecureRandBits(3) == 2) {
 209                 int new_size = std::max<int>(0, std::min<int>(30, test.size() + (InsecureRandRange(5)) - 2));
 210                 test.resize(new_size);
 211             }
 212             if (InsecureRandBits(3) == 3) {
 213                 test.insert(InsecureRandRange(test.size() + 1), 1 + InsecureRandBool(), InsecureRand32());
 214             }
 215             if (InsecureRandBits(3) == 4) {
 216                 int del = std::min<int>(test.size(), 1 + (InsecureRandBool()));
 217                 int beg = InsecureRandRange(test.size() + 1 - del);
 218                 test.erase(beg, beg + del);
 219             }
 220             if (InsecureRandBits(4) == 5) {
 221                 test.push_back(InsecureRand32());
 222             }
 223             if (test.size() > 0 && InsecureRandBits(4) == 6) {
 224                 test.pop_back();
 225             }
 226             if (InsecureRandBits(5) == 7) {
 227                 int values[4];
 228                 int num = 1 + (InsecureRandBits(2));
 229                 for (int k = 0; k < num; k++) {
 230                     values[k] = InsecureRand32();
 231                 }
 232                 test.insert_range(InsecureRandRange(test.size() + 1), values, values + num);
 233             }
 234             if (InsecureRandBits(5) == 8) {
 235                 int del = std::min<int>(test.size(), 1 + (InsecureRandBits(2)));
 236                 int beg = InsecureRandRange(test.size() + 1 - del);
 237                 test.erase(beg, beg + del);
 238             }
 239             if (InsecureRandBits(5) == 9) {
 240                 test.reserve(InsecureRandBits(5));
 241             }
 242             if (InsecureRandBits(6) == 10) {
 243                 test.shrink_to_fit();
 244             }
 245             if (test.size() > 0) {
 246                 test.update(InsecureRandRange(test.size()), InsecureRand32());
 247             }
 248             if (InsecureRandBits(10) == 11) {
 249                 test.clear();
 250             }
 251             if (InsecureRandBits(9) == 12) {
 252                 test.assign(InsecureRandBits(5), InsecureRand32());
 253             }
 254             if (InsecureRandBits(3) == 3) {
 255                 test.swap();
 256             }
 257             if (InsecureRandBits(4) == 8) {
 258                 test.copy();
 259             }
 260             if (InsecureRandBits(5) == 18) {
 261                 test.move();
 262             }
 263         }
 264     }
 265 }
 266
 267 BOOST_AUTO_TEST_SUITE_END()