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