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 "serialize.h"
   9 #include "streams.h"
  10
  11 #include "test/test_bitcoin.h"
  12 #include "test/test_random.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
  32
  33     template <typename A, typename B>
  34         void local_check_equal(A a, B b)
  35         {
  36             local_check(a == b);
  37         }
  38     void local_check(bool b)
  39     {
  40         passed &= b;
  41     }
  42     void test() {
  43         const pretype& const_pre_vector = pre_vector;
  44         local_check_equal(real_vector.size(), pre_vector.size());
  45         local_check_equal(real_vector.empty(), pre_vector.empty());
  46         for (Size s = 0; s < real_vector.size(); s++) {
  47              local_check(real_vector[s] == pre_vector[s]);
  48              local_check(&(pre_vector[s]) == &(pre_vector.begin()[s]));
  49              local_check(&(pre_vector[s]) == &*(pre_vector.begin() + s));
  50              local_check(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size()));
  51         }
  52         // local_check(realtype(pre_vector) == real_vector);
  53         local_check(pretype(real_vector.begin(), real_vector.end()) == pre_vector);
  54         local_check(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector);
  55         size_t pos = 0;
  56         BOOST_FOREACH(const T& v, pre_vector) {
  57              local_check(v == real_vector[pos++]);
  58         }
  59         BOOST_REVERSE_FOREACH(const T& v, pre_vector) {
  60              local_check(v == real_vector[--pos]);
  61         }
  62         BOOST_FOREACH(const T& v, const_pre_vector) {
  63              local_check(v == real_vector[pos++]);
  64         }
  65         BOOST_REVERSE_FOREACH(const T& v, const_pre_vector) {
  66              local_check(v == real_vector[--pos]);
  67         }
  68         CDataStream ss1(SER_DISK, 0);
  69         CDataStream ss2(SER_DISK, 0);
  70         ss1 << real_vector;
  71         ss2 << pre_vector;
  72         local_check_equal(ss1.size(), ss2.size());
  73         for (Size s = 0; s < ss1.size(); s++) {
  74             local_check_equal(ss1[s], ss2[s]);
  75         }
  76     }
  77
  78 public:
  79     void resize(Size s) {
  80         real_vector.resize(s);
  81         local_check_equal(real_vector.size(), s);
  82         pre_vector.resize(s);
  83         local_check_equal(pre_vector.size(), s);
  84         test();
  85     }
  86
  87     void reserve(Size s) {
  88         real_vector.reserve(s);
  89         local_check(real_vector.capacity() >= s);
  90         pre_vector.reserve(s);
  91         local_check(pre_vector.capacity() >= s);
  92         test();
  93     }
  94
  95     void insert(Size position, const T& value) {
  96         real_vector.insert(real_vector.begin() + position, value);
  97         pre_vector.insert(pre_vector.begin() + position, value);
  98         test();
  99     }
 100
 101     void insert(Size position, Size count, const T& value) {
 102         real_vector.insert(real_vector.begin() + position, count, value);
 103         pre_vector.insert(pre_vector.begin() + position, count, value);
 104         test();
 105     }
 106
 107     template<typename I>
 108     void insert_range(Size position, I first, I last) {
 109         real_vector.insert(real_vector.begin() + position, first, last);
 110         pre_vector.insert(pre_vector.begin() + position, first, last);
 111         test();
 112     }
 113
 114     void erase(Size position) {
 115         real_vector.erase(real_vector.begin() + position);
 116         pre_vector.erase(pre_vector.begin() + position);
 117         test();
 118     }
 119
 120     void erase(Size first, Size last) {
 121         real_vector.erase(real_vector.begin() + first, real_vector.begin() + last);
 122         pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last);
 123         test();
 124     }
 125
 126     void update(Size pos, const T& value) {
 127         real_vector[pos] = value;
 128         pre_vector[pos] = value;
 129         test();
 130     }
 131
 132     void push_back(const T& value) {
 133         real_vector.push_back(value);
 134         pre_vector.push_back(value);
 135         test();
 136     }
 137
 138     void pop_back() {
 139         real_vector.pop_back();
 140         pre_vector.pop_back();
 141         test();
 142     }
 143
 144     void clear() {
 145         real_vector.clear();
 146         pre_vector.clear();
 147     }
 148
 149     void assign(Size n, const T& value) {
 150         real_vector.assign(n, value);
 151         pre_vector.assign(n, value);
 152     }
 153
 154     Size size() {
 155         return real_vector.size();
 156     }
 157
 158     Size capacity() {
 159         return pre_vector.capacity();
 160     }
 161
 162     void shrink_to_fit() {
 163         pre_vector.shrink_to_fit();
 164         test();
 165     }
 166
 167     void swap() {
 168         real_vector.swap(real_vector_alt);
 169         pre_vector.swap(pre_vector_alt);
 170         test();
 171     }
 172
 173     void move() {
 174         real_vector = std::move(real_vector_alt);
 175         real_vector_alt.clear();
 176         pre_vector = std::move(pre_vector_alt);
 177         pre_vector_alt.clear();
 178     }
 179
 180     void copy() {
 181         real_vector = real_vector_alt;
 182         pre_vector = pre_vector_alt;
 183     }
 184
 185     ~prevector_tester() {
 186         BOOST_CHECK_MESSAGE(passed, "insecure_rand_Rz: "
 187                 << rand_cache.Rz
 188                 << ", insecure_rand_Rw: "
 189                 << rand_cache.Rw);
 190     }
 191     prevector_tester() {
 192         seed_insecure_rand();
 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             int r = insecure_rand();
 203             if ((r % 4) == 0) {
 204                 test.insert(insecure_rand() % (test.size() + 1), insecure_rand());
 205             }
 206             if (test.size() > 0 && ((r >> 2) % 4) == 1) {
 207                 test.erase(insecure_rand() % test.size());
 208             }
 209             if (((r >> 4) % 8) == 2) {
 210                 int new_size = std::max<int>(0, std::min<int>(30, test.size() + (insecure_rand() % 5) - 2));
 211                 test.resize(new_size);
 212             }
 213             if (((r >> 7) % 8) == 3) {
 214                 test.insert(insecure_rand() % (test.size() + 1), 1 + (insecure_rand() % 2), insecure_rand());
 215             }
 216             if (((r >> 10) % 8) == 4) {
 217                 int del = std::min<int>(test.size(), 1 + (insecure_rand() % 2));
 218                 int beg = insecure_rand() % (test.size() + 1 - del);
 219                 test.erase(beg, beg + del);
 220             }
 221             if (((r >> 13) % 16) == 5) {
 222                 test.push_back(insecure_rand());
 223             }
 224             if (test.size() > 0 && ((r >> 17) % 16) == 6) {
 225                 test.pop_back();
 226             }
 227             if (((r >> 21) % 32) == 7) {
 228                 int values[4];
 229                 int num = 1 + (insecure_rand() % 4);
 230                 for (int k = 0; k < num; k++) {
 231                     values[k] = insecure_rand();
 232                 }
 233                 test.insert_range(insecure_rand() % (test.size() + 1), values, values + num);
 234             }
 235             if (((r >> 26) % 32) == 8) {
 236                 int del = std::min<int>(test.size(), 1 + (insecure_rand() % 4));
 237                 int beg = insecure_rand() % (test.size() + 1 - del);
 238                 test.erase(beg, beg + del);
 239             }
 240             r = insecure_rand();
 241             if (r % 32 == 9) {
 242                 test.reserve(insecure_rand() % 32);
 243             }
 244             if ((r >> 5) % 64 == 10) {
 245                 test.shrink_to_fit();
 246             }
 247             if (test.size() > 0) {
 248                 test.update(insecure_rand() % test.size(), insecure_rand());
 249             }
 250             if (((r >> 11) % 1024) == 11) {
 251                 test.clear();
 252             }
 253             if (((r >> 21) % 512) == 12) {
 254                 test.assign(insecure_rand() % 32, insecure_rand());
 255             }
 256             if (((r >> 15) % 8) == 3) {
 257                 test.swap();
 258             }
 259             if (((r >> 15) % 16) == 8) {
 260                 test.copy();
 261             }
 262             if (((r >> 15) % 32) == 18) {
 263                 test.move();
 264             }
 265         }
 266     }
 267 }
 268
 269 BOOST_AUTO_TEST_SUITE_END()