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