simple_vector.cpp (10295B)
1 #include "libshit/container/simple_vector.hpp" 2 3 #include "libshit/doctest.hpp" 4 #include "libshit/platform.hpp" 5 6 #include <cstring> 7 #include <ostream> 8 #include <vector> 9 10 namespace Libshit::Test 11 { 12 TEST_SUITE_BEGIN("Libshit::SimpleVector"); 13 14 namespace 15 { 16 struct X 17 { 18 static inline int count = 0; 19 int i; 20 21 X() : i{} { ++count; } 22 X(int i) : i{i} { ++count; } 23 X(const X& o) : i{o.i} { ++count; } 24 ~X() { --count; } 25 26 X& operator=(const X&) noexcept = default; // shut up gcc 27 28 bool operator==(const X& o) const noexcept { return i == o.i; } 29 bool operator!=(const X& o) const noexcept { return i != o.i; } 30 }; 31 32 std::ostream& operator<<(std::ostream& os, const X& x) 33 { return os << "X{" << x.i << '}'; } 34 } 35 36 TEST_CASE_TEMPLATE("basic test", T, int, X, const int) 37 { 38 constexpr const bool is_const = std::is_const_v<T>; 39 using NoConst = std::remove_const_t<T>; 40 41 Libshit::SimpleVector<T> v; 42 CHECK(v.empty()); 43 CHECK(v.size() == 0); 44 CHECK(v.capacity() == 0); 45 46 SUBCASE("copy op=") 47 { 48 SUBCASE("empty") {} 49 SUBCASE("not empty") { v.push_back(1); } 50 Libshit::SimpleVector<T> v2{1,2,3}; 51 v = v2; 52 CHECK(!v.empty()); 53 CHECK(v.size() == 3); 54 CHECK(v.capacity() >= v.size()); 55 56 CHECK(v.size() == v2.size()); 57 CHECK(v == v2); 58 } 59 60 SUBCASE("move op=") 61 { 62 SUBCASE("empty") {} 63 SUBCASE("not empty") { v.push_back(1); } 64 v = Libshit::SimpleVector<T>{1,2,3}; 65 CHECK(!v.empty()); 66 CHECK(v.size() == 3); 67 CHECK(v.capacity() >= v.size()); 68 69 v = Libshit::SimpleVector<T>(); 70 CHECK(v.empty()); 71 CHECK(v.size() == 0); 72 73 v = Libshit::SimpleVector<T>(5, 1); 74 CHECK(!v.empty()); 75 CHECK(v.size() == 5); 76 CHECK(v.capacity() >= 5); 77 CHECK(v == Libshit::SimpleVector<T>{1,1,1,1,1}); 78 } 79 80 SUBCASE("assign n") 81 { 82 SUBCASE("empty") {} 83 SUBCASE("not empty") { v.push_back(1); } 84 v.assign(2, 3); 85 CHECK(!v.empty()); 86 CHECK(v.size() == 2); 87 CHECK(v == Libshit::SimpleVector<T>{3, 3}); 88 } 89 90 SUBCASE("assign iterator") 91 { 92 SUBCASE("empty") {} 93 SUBCASE("not empty") { v.push_back(1); } 94 std::vector<NoConst> v2{4,5,6}; 95 v.assign(v2.begin(), v2.end()); 96 CHECK(!v.empty()); 97 CHECK(v.size() == 3); 98 CHECK(v == Libshit::SimpleVector<T>{4, 5, 6}); 99 } 100 101 SUBCASE("assign initializer_list") 102 { 103 SUBCASE("empty") {} 104 SUBCASE("not empty") { v.push_back(1); } 105 v.assign({2, 7, 9, 2}); 106 CHECK(!v.empty()); 107 CHECK(v.size() == 4); 108 CHECK(v == Libshit::SimpleVector<T>{2, 7, 9, 2}); 109 } 110 111 SUBCASE("with data") 112 { 113 v = {0, 1, 2, 3}; 114 SUBCASE("simple accessors") 115 { 116 CHECK(v.at(1) == 1); 117 // that const cast would work even in non-const case, but test that 118 // assignment works normally when members are not const 119 if constexpr (is_const) const_cast<NoConst&>(v.at(1)) = 9; 120 else v.at(1) = 9; 121 CHECK(v.at(1) == 9); 122 CHECK(std::as_const(v).at(2) == 2); 123 CHECK(v[2] == 2); 124 if constexpr (is_const) const_cast<NoConst&>(v[2]) = 8; 125 else v[2] = 8; 126 CHECK(v[2] == 8); 127 CHECK(std::as_const(v)[2] == 8); 128 CHECK(v == Libshit::SimpleVector<T>{0, 9, 8, 3}); 129 130 CHECK_THROWS(v.at(4)); 131 CHECK_THROWS(std::as_const(v).at(1111)); 132 133 CHECK(v.front() == 0); 134 CHECK(std::as_const(v).front() == 0); 135 if constexpr (is_const) const_cast<NoConst&>(v.front()) = 5; 136 else v.front() = 5; 137 CHECK(v.back() == 3); 138 CHECK(std::as_const(v).back() == 3); 139 if constexpr (is_const) const_cast<NoConst&>(v.back()) = 6; 140 else v.back() = 6; 141 CHECK(v == Libshit::SimpleVector<T>{5, 9, 8, 6}); 142 } 143 144 SUBCASE("data") 145 { 146 CHECK(v.data()[0] == 0); 147 CHECK(v.data() == &v[0]); 148 CHECK(std::as_const(v).data() == &v[0]); 149 CHECK(v.pdata() == &v[0]); 150 CHECK(std::as_const(v).pdata() == &v[0]); 151 int dat[] = {0,1,2,3}; 152 CHECK(memcmp(v.data(), dat, 4*sizeof(int)) == 0); 153 } 154 155 SUBCASE("basic iterator") 156 { 157 static_assert(std::is_same_v<T*, decltype(v.begin())>); 158 CHECK(v.begin() == v.data()); 159 CHECK(v.end() == v.data() + 4); 160 CHECK(std::as_const(v).begin() == v.data()); 161 CHECK(std::as_const(v).end() == v.data() + 4); 162 CHECK(std::as_const(v).cbegin() == v.data()); 163 CHECK(std::as_const(v).cend() == v.data() + 4); 164 CHECK(std::vector<NoConst>{v.begin(), v.end()} == 165 std::vector<NoConst>{0,1,2,3}); 166 167 CHECK(v.rbegin() != v.rend()); 168 CHECK(std::vector<NoConst>{v.rbegin(), v.rend()} == 169 std::vector<NoConst>{3,2,1,0}); 170 171 CHECK(v.wbegin() == v.data()); 172 CHECK(v.wend() == v.data() + 4); 173 CHECK(std::as_const(v).wbegin() == v.data()); 174 CHECK(std::as_const(v).wend() == v.data() + 4); 175 } 176 177 SUBCASE("reserve") 178 { 179 REQUIRE(v.capacity() < 100); 180 v.reserve(128); 181 CHECK(v.size() == 4); 182 CHECK(v.capacity() >= 128); 183 184 v.shrink_to_fit(); 185 CHECK(v.size() == 4); 186 CHECK(v.capacity() == 4); 187 } 188 189 SUBCASE("reset") 190 { 191 v.reset(); 192 CHECK(v.size() == 0); 193 CHECK(v.capacity() == 0); 194 } 195 SUBCASE("clear") 196 { 197 v.clear(); 198 CHECK(v.size() == 0); 199 CHECK(v.capacity() > 0); 200 } 201 202 SUBCASE("insert with enough space") 203 { 204 v.reserve(v.size() + 4); 205 v.insert(v.begin(), 10); 206 v.insert(v.end(), 11); 207 v.insert(v.begin() + 2, 12); 208 CHECK(v == Libshit::SimpleVector<T>{10, 0, 12, 1, 2, 3, 11}); 209 } 210 211 SUBCASE("insert with resize begin") 212 { 213 v.shrink_to_fit(); CHECK(v.size() == v.capacity()); 214 v.insert(v.begin(), 10); 215 CHECK(v == Libshit::SimpleVector<T>{10, 0, 1, 2, 3}); 216 } 217 SUBCASE("insert with resize end") 218 { 219 v.shrink_to_fit(); CHECK(v.size() == v.capacity()); 220 v.insert(v.end(), 11); 221 CHECK(v == Libshit::SimpleVector<T>{0, 1, 2, 3, 11}); 222 } 223 SUBCASE("insert with resize middle") 224 { 225 v.shrink_to_fit(); CHECK(v.size() == v.capacity()); 226 v.insert(v.begin() + 2, 12); 227 CHECK(v == Libshit::SimpleVector<T>{0, 1, 12, 2, 3}); 228 } 229 230 SUBCASE("emplace") 231 { 232 v.emplace(v.begin(), 10); 233 v.emplace(v.end(), 11); 234 v.emplace(v.begin() + 2, 12); 235 CHECK(v == Libshit::SimpleVector<T>{10, 0, 12, 1, 2, 3, 11}); 236 } 237 238 SUBCASE("erase") 239 { 240 v.erase(v.end() - 1); 241 CHECK(v == Libshit::SimpleVector<T>{0, 1, 2}); 242 v.erase(v.begin()); 243 CHECK(v == Libshit::SimpleVector<T>{1, 2}); 244 245 v = {1,2,3,4,5}; 246 v.erase(v.begin() + 1); 247 CHECK(v == Libshit::SimpleVector<T>{1, 3, 4, 5}); 248 } 249 250 SUBCASE("erase range") 251 { 252 v.erase(v.begin(), v.end()); 253 CHECK(v.size() == 0); 254 255 v = {0,1,2,3,4}; 256 v.erase(v.begin(), v.begin()+2); 257 CHECK(v == Libshit::SimpleVector<T>{2, 3, 4}); 258 v.erase(v.begin() + 1, v.end()); 259 CHECK(v == Libshit::SimpleVector<T>{2}); 260 261 v = {0, 1, 2, 3, 4, 5}; 262 v.erase(v.begin()+1, v.begin()+4); 263 CHECK(v == Libshit::SimpleVector<T>{0, 4, 5}); 264 } 265 266 SUBCASE("unordered erase") 267 { 268 v.unordered_erase(v.begin() + 1); 269 CHECK(v == Libshit::SimpleVector<T>{0, 3, 2}); 270 271 v.unordered_erase(v.begin()); 272 CHECK(v == Libshit::SimpleVector<T>{2, 3}); 273 274 v.unordered_erase(v.begin() + 1); 275 CHECK(v == Libshit::SimpleVector<T>{2}); 276 } 277 278 SUBCASE("push_back/emplace_back/pop_back") 279 { 280 v.shrink_to_fit(); CHECK(v.size() == v.capacity()); 281 // one realloc push_back, one no alloc emplace_back 282 v.push_back(7); 283 v.emplace_back(8); 284 CHECK(v == Libshit::SimpleVector<T>{0, 1, 2, 3, 7, 8}); 285 v.pop_back(); 286 CHECK(v == Libshit::SimpleVector<T>{0, 1, 2, 3, 7}); 287 } 288 289 SUBCASE("resize") 290 { 291 v.resize(7); 292 CHECK(v == Libshit::SimpleVector<T>{0, 1, 2, 3, 0, 0, 0}); 293 CHECK(v.capacity() < 9); // will realloc 294 v.resize(9, 9); 295 CHECK(v == Libshit::SimpleVector<T>{0, 1, 2, 3, 0, 0, 0, 9, 9}); 296 CHECK(v.capacity() >= 10); // no realloc 297 v.resize(10, -1); 298 CHECK(v == Libshit::SimpleVector<T>{0, 1, 2, 3, 0, 0, 0, 9, 9, -1}); 299 v.resize(2, 42); 300 CHECK(v == Libshit::SimpleVector<T>{0, 1}); 301 } 302 303 SUBCASE("swap") 304 { 305 Libshit::SimpleVector<T> v2{-1, -2, -3}; 306 v.swap(v2); 307 CHECK(v == Libshit::SimpleVector<T>{-1, -2, -3}); 308 CHECK(v2 == Libshit::SimpleVector<T>{0, 1, 2, 3}); 309 } 310 311 SUBCASE("==") 312 { 313 Libshit::SimpleVector<T> v2{0, 1, 2, 3}; 314 CHECK(v == v2); 315 CHECK(!(v != v2)); 316 317 const_cast<std::remove_const_t<T>&>(v2[2]) = 7; 318 CHECK(v != v2); 319 CHECK(!(v == v2)); 320 321 v2 = {0, 1, 2, 3, 4}; 322 CHECK(v != v2); 323 CHECK(!(v == v2)); 324 } 325 } 326 } 327 328 TEST_CASE("uninitialized_resize") 329 { 330 Libshit::SimpleVector<int> v{10,11,12,13}; 331 v.resize(2); 332 v.uninitialized_resize(4); 333 CHECK(v[0] == 10); 334 CHECK(v[1] == 11); 335 // without this, valgrind should warn on the two last checks (uninitialized 336 // read) 337 Asan::Defined(&v[2], 2 * sizeof(int)); 338 // the actual read value is an implementation detail 339 CHECK(v[2] == (LIBSHIT_IS_DEBUG ? 0xdefeca7e : 12)); 340 CHECK(v[3] == (LIBSHIT_IS_DEBUG ? 0xdefeca7e : 13)); 341 } 342 343 // Under asan or valgrind, each commented line should generate an error 344 TEST_CASE("asan") 345 { 346 Libshit::SimpleVector<int> v(5); 347 v.reserve(10); 348 v.data()[4] = 1; 349 // v.data()[5] = 1; // NOK, size=5 350 // v.data()[7] = 1; // NOK, size=5 351 v.resize(3); 352 v.data()[2] = 1; 353 // v.data()[3] = 1; // NOK, size=3 354 // v.data()[4] = 1; // NOK, size=3 355 v.clear(); 356 // v.data()[0] = 1; // NOK, size=0 357 v.push_back(1); 358 v.data()[0] = 1; // OK, size=1 359 v.pop_back(); 360 // v.data()[0] = 1; // NOK, size=0 361 } 362 363 TEST_SUITE_END(); 364 } 365 366 TYPE_TO_STRING(Libshit::Test::X);