prevector_tests.cpp
1 // Copyright (c) 2015-present 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 <serialize.h> 7 #include <streams.h> 8 #include <test/util/random.h> 9 #include <test/util/setup_common.h> 10 11 #include <boost/test/unit_test.hpp> 12 13 #include <ranges> 14 #include <vector> 15 16 BOOST_FIXTURE_TEST_SUITE(prevector_tests, BasicTestingSetup) 17 18 template <unsigned int N, typename T> 19 class prevector_tester 20 { 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 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 { 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 : pre_vector | std::views::reverse) { 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 : const_pre_vector | std::views::reverse) { 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 { 83 real_vector.resize(s); 84 local_check_equal(real_vector.size(), s); 85 pre_vector.resize(s); 86 local_check_equal(pre_vector.size(), s); 87 test(); 88 } 89 90 void reserve(Size s) 91 { 92 real_vector.reserve(s); 93 local_check(real_vector.capacity() >= s); 94 pre_vector.reserve(s); 95 local_check(pre_vector.capacity() >= s); 96 test(); 97 } 98 99 void insert(Size position, const T& value) 100 { 101 real_vector.insert(real_vector.begin() + position, value); 102 pre_vector.insert(pre_vector.begin() + position, value); 103 test(); 104 } 105 106 void insert(Size position, Size count, const T& value) 107 { 108 real_vector.insert(real_vector.begin() + position, count, value); 109 pre_vector.insert(pre_vector.begin() + position, count, value); 110 test(); 111 } 112 113 template <typename I> 114 void insert_range(Size position, I first, I last) 115 { 116 real_vector.insert(real_vector.begin() + position, first, last); 117 pre_vector.insert(pre_vector.begin() + position, first, last); 118 test(); 119 } 120 121 void erase(Size position) 122 { 123 real_vector.erase(real_vector.begin() + position); 124 pre_vector.erase(pre_vector.begin() + position); 125 test(); 126 } 127 128 void erase(Size first, Size last) 129 { 130 real_vector.erase(real_vector.begin() + first, real_vector.begin() + last); 131 pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last); 132 test(); 133 } 134 135 void update(Size pos, const T& value) 136 { 137 real_vector[pos] = value; 138 pre_vector[pos] = value; 139 test(); 140 } 141 142 void push_back(const T& value) 143 { 144 real_vector.push_back(value); 145 pre_vector.push_back(value); 146 test(); 147 } 148 149 void pop_back() 150 { 151 real_vector.pop_back(); 152 pre_vector.pop_back(); 153 test(); 154 } 155 156 void clear() 157 { 158 real_vector.clear(); 159 pre_vector.clear(); 160 } 161 162 void assign(Size n, const T& value) 163 { 164 real_vector.assign(n, value); 165 pre_vector.assign(n, value); 166 } 167 168 Size size() const 169 { 170 return real_vector.size(); 171 } 172 173 Size capacity() const 174 { 175 return pre_vector.capacity(); 176 } 177 178 void shrink_to_fit() 179 { 180 pre_vector.shrink_to_fit(); 181 test(); 182 } 183 184 void swap() noexcept 185 { 186 real_vector.swap(real_vector_alt); 187 pre_vector.swap(pre_vector_alt); 188 test(); 189 } 190 191 void move() 192 { 193 real_vector = std::move(real_vector_alt); 194 real_vector_alt.clear(); 195 pre_vector = std::move(pre_vector_alt); 196 pre_vector_alt.clear(); 197 } 198 199 void copy() 200 { 201 real_vector = real_vector_alt; 202 pre_vector = pre_vector_alt; 203 } 204 205 void resize_uninitialized(realtype values) 206 { 207 size_t r = values.size(); 208 size_t s = real_vector.size() / 2; 209 if (real_vector.capacity() < s + r) { 210 real_vector.reserve(s + r); 211 } 212 real_vector.resize(s); 213 pre_vector.resize_uninitialized(s); 214 for (auto v : values) { 215 real_vector.push_back(v); 216 } 217 auto p = pre_vector.size(); 218 pre_vector.resize_uninitialized(p + r); 219 for (auto v : values) { 220 pre_vector[p] = v; 221 ++p; 222 } 223 test(); 224 } 225 226 ~prevector_tester() 227 { 228 BOOST_CHECK_MESSAGE(passed, "insecure_rand: " + rand_seed.ToString()); 229 } 230 231 prevector_tester(FastRandomContext& rng) 232 { 233 rand_seed = rng.rand256(); 234 rng.Reseed(rand_seed); 235 } 236 }; 237 238 BOOST_AUTO_TEST_CASE(PrevectorTestInt) 239 { 240 for (int j = 0; j < 64; j++) { 241 prevector_tester<8, int> test{m_rng}; 242 for (int i = 0; i < 2048; i++) { 243 if (m_rng.randbits(2) == 0) { 244 test.insert(m_rng.randrange(test.size() + 1), int(m_rng.rand32())); 245 } 246 if (test.size() > 0 && m_rng.randbits(2) == 1) { 247 test.erase(m_rng.randrange(test.size())); 248 } 249 if (m_rng.randbits(3) == 2) { 250 int new_size = std::max(0, std::min(30, (int)test.size() + (int)m_rng.randrange(5) - 2)); 251 test.resize(new_size); 252 } 253 if (m_rng.randbits(3) == 3) { 254 test.insert(m_rng.randrange(test.size() + 1), 1 + m_rng.randbool(), int(m_rng.rand32())); 255 } 256 if (m_rng.randbits(3) == 4) { 257 int del = std::min<int>(test.size(), 1 + (m_rng.randbool())); 258 int beg = m_rng.randrange(test.size() + 1 - del); 259 test.erase(beg, beg + del); 260 } 261 if (m_rng.randbits(4) == 5) { 262 test.push_back(int(m_rng.rand32())); 263 } 264 if (test.size() > 0 && m_rng.randbits(4) == 6) { 265 test.pop_back(); 266 } 267 if (m_rng.randbits(5) == 7) { 268 int values[4]; 269 int num = 1 + (m_rng.randbits(2)); 270 for (int k = 0; k < num; k++) { 271 values[k] = int(m_rng.rand32()); 272 } 273 test.insert_range(m_rng.randrange(test.size() + 1), values, values + num); 274 } 275 if (m_rng.randbits(5) == 8) { 276 int del = std::min<int>(test.size(), 1 + (m_rng.randbits(2))); 277 int beg = m_rng.randrange(test.size() + 1 - del); 278 test.erase(beg, beg + del); 279 } 280 if (m_rng.randbits(5) == 9) { 281 test.reserve(m_rng.randbits(5)); 282 } 283 if (m_rng.randbits(6) == 10) { 284 test.shrink_to_fit(); 285 } 286 if (test.size() > 0) { 287 test.update(m_rng.randrange(test.size()), int(m_rng.rand32())); 288 } 289 if (m_rng.randbits(10) == 11) { 290 test.clear(); 291 } 292 if (m_rng.randbits(9) == 12) { 293 test.assign(m_rng.randbits(5), int(m_rng.rand32())); 294 } 295 if (m_rng.randbits(3) == 3) { 296 test.swap(); 297 } 298 if (m_rng.randbits(4) == 8) { 299 test.copy(); 300 } 301 if (m_rng.randbits(5) == 18) { 302 test.move(); 303 } 304 if (m_rng.randbits(5) == 19) { 305 unsigned int num = 1 + (m_rng.randbits(4)); 306 std::vector<int> values(num); 307 for (int& v : values) { 308 v = int(m_rng.rand32()); 309 } 310 test.resize_uninitialized(values); 311 } 312 } 313 } 314 } 315 316 BOOST_AUTO_TEST_SUITE_END()