655 lines · cpp
1//===- unittests/ADT/SimpleIListTest.cpp - simple_ilist unit tests --------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ADT/simple_ilist.h"10#include "llvm/ADT/STLExtras.h"11#include "gtest/gtest.h"12 13using namespace llvm;14 15namespace {16 17struct Node : ilist_node<Node> {};18bool operator<(const Node &L, const Node &R) { return &L < &R; }19bool makeFalse(const Node &, const Node &) { return false; }20 21struct deleteNode : std::default_delete<Node> {};22void doNothing(Node *) {}23 24TEST(SimpleIListTest, DefaultConstructor) {25 simple_ilist<Node> L;26 EXPECT_EQ(L.begin(), L.end());27 EXPECT_TRUE(L.empty());28 EXPECT_EQ(0u, L.size());29}30 31TEST(SimpleIListTest, pushPopFront) {32 simple_ilist<Node> L;33 Node A, B;34 L.push_front(B);35 L.push_front(A);36 EXPECT_EQ(&A, &L.front());37 EXPECT_EQ(&B, &L.back());38 EXPECT_FALSE(L.empty());39 EXPECT_EQ(2u, L.size());40 41 // Pop front and check the new front.42 L.pop_front();43 EXPECT_EQ(&B, &L.front());44 45 // Pop to empty.46 L.pop_front();47 EXPECT_TRUE(L.empty());48}49 50TEST(SimpleIListTest, pushPopBack) {51 simple_ilist<Node> L;52 Node A, B;53 L.push_back(A);54 L.push_back(B);55 EXPECT_EQ(&A, &L.front());56 EXPECT_EQ(&B, &L.back());57 EXPECT_FALSE(L.empty());58 EXPECT_EQ(2u, L.size());59 60 // Pop back and check the new front.61 L.pop_back();62 EXPECT_EQ(&A, &L.back());63 64 // Pop to empty.65 L.pop_back();66 EXPECT_TRUE(L.empty());67}68 69TEST(SimpleIListTest, swap) {70 simple_ilist<Node> L1, L2;71 Node A, B;72 L1.push_back(A);73 L1.push_back(B);74 L1.swap(L2);75 EXPECT_TRUE(L1.empty());76 EXPECT_EQ(0u, L1.size());77 EXPECT_EQ(&A, &L2.front());78 EXPECT_EQ(&B, &L2.back());79 EXPECT_FALSE(L2.empty());80 EXPECT_EQ(2u, L2.size());81}82 83TEST(SimpleIListTest, insertEraseAtEnd) {84 simple_ilist<Node> L;85 Node A, B;86 L.insert(L.end(), A);87 L.insert(L.end(), B);88 EXPECT_EQ(&A, &L.front());89 EXPECT_EQ(&B, &L.back());90 EXPECT_FALSE(L.empty());91 EXPECT_EQ(2u, L.size());92}93 94TEST(SimpleIListTest, insertAtBegin) {95 simple_ilist<Node> L;96 Node A, B;97 L.insert(L.begin(), B);98 L.insert(L.begin(), A);99 EXPECT_EQ(&A, &L.front());100 EXPECT_EQ(&B, &L.back());101 EXPECT_FALSE(L.empty());102 EXPECT_EQ(2u, L.size());103}104 105TEST(SimpleIListTest, remove) {106 simple_ilist<Node> L;107 Node A, B, C;108 L.push_back(A);109 L.push_back(B);110 L.push_back(C);111 EXPECT_EQ(&A, &L.front());112 EXPECT_EQ(&B, &*++L.begin());113 EXPECT_EQ(&C, &L.back());114 EXPECT_EQ(3u, L.size());115 116 L.remove(B);117 EXPECT_EQ(&A, &L.front());118 EXPECT_EQ(&C, &L.back());119 EXPECT_EQ(2u, L.size());120 121 L.remove(A);122 EXPECT_EQ(&C, &L.front());123 EXPECT_EQ(1u, L.size());124 125 L.remove(C);126 EXPECT_TRUE(L.empty());127}128 129TEST(SimpleIListTest, removeAndDispose) {130 simple_ilist<Node> L;131 Node A, C;132 Node *B = new Node;133 L.push_back(A);134 L.push_back(*B);135 L.push_back(C);136 EXPECT_EQ(&A, &L.front());137 EXPECT_EQ(B, &*++L.begin());138 EXPECT_EQ(&C, &L.back());139 EXPECT_EQ(3u, L.size());140 141 L.removeAndDispose(*B, deleteNode());142 EXPECT_EQ(&A, &L.front());143 EXPECT_EQ(&C, &L.back());144 EXPECT_EQ(2u, L.size());145}146 147TEST(SimpleIListTest, removeAndDisposeNullDeleter) {148 simple_ilist<Node> L;149 Node A, B, C;150 L.push_back(A);151 L.push_back(B);152 L.push_back(C);153 EXPECT_EQ(&A, &L.front());154 EXPECT_EQ(&B, &*++L.begin());155 EXPECT_EQ(&C, &L.back());156 EXPECT_EQ(3u, L.size());157 158 L.removeAndDispose(B, doNothing);159 EXPECT_EQ(&A, &L.front());160 EXPECT_EQ(&C, &L.back());161 EXPECT_EQ(2u, L.size());162}163 164TEST(SimpleIListTest, erase) {165 simple_ilist<Node> L;166 Node A, B, C;167 L.push_back(A);168 L.push_back(B);169 L.push_back(C);170 EXPECT_EQ(&A, &L.front());171 EXPECT_EQ(&B, &*++L.begin());172 EXPECT_EQ(&C, &L.back());173 EXPECT_EQ(3u, L.size());174 175 EXPECT_EQ(C.getIterator(), L.erase(B.getIterator()));176 EXPECT_EQ(&A, &L.front());177 EXPECT_EQ(&C, &L.back());178 EXPECT_EQ(2u, L.size());179}180 181TEST(SimpleIListTest, reverse_iterator) {182 simple_ilist<Node> L;183 Node A, B, C;184 L.push_back(A);185 L.push_back(B);186 L.push_back(C);187 188 auto ReverseIter = L.rbegin();189 EXPECT_EQ(C.getReverseIterator(), ReverseIter);190 ++ReverseIter;191 EXPECT_EQ(B.getReverseIterator(), ReverseIter);192 ++ReverseIter;193 EXPECT_EQ(A.getReverseIterator(), ReverseIter);194 ++ReverseIter;195 EXPECT_EQ(L.rend(), ReverseIter);196}197 198TEST(SimpleIListTest, eraseAndDispose) {199 simple_ilist<Node> L;200 Node A, C;201 Node *B = new Node;202 L.push_back(A);203 L.push_back(*B);204 L.push_back(C);205 EXPECT_EQ(&A, &L.front());206 EXPECT_EQ(B, &*++L.begin());207 EXPECT_EQ(&C, &L.back());208 EXPECT_EQ(3u, L.size());209 210 L.eraseAndDispose(B->getIterator(), deleteNode());211 EXPECT_EQ(&A, &L.front());212 EXPECT_EQ(&C, &L.back());213 EXPECT_EQ(2u, L.size());214}215 216TEST(SimpleIListTest, eraseAndDisposeNullDeleter) {217 simple_ilist<Node> L;218 Node A, B, C;219 L.push_back(A);220 L.push_back(B);221 L.push_back(C);222 EXPECT_EQ(&A, &L.front());223 EXPECT_EQ(&B, &*++L.begin());224 EXPECT_EQ(&C, &L.back());225 EXPECT_EQ(3u, L.size());226 227 L.eraseAndDispose(B.getIterator(), doNothing);228 EXPECT_EQ(&A, &L.front());229 EXPECT_EQ(&C, &L.back());230 EXPECT_EQ(2u, L.size());231}232 233TEST(SimpleIListTest, eraseRange) {234 simple_ilist<Node> L;235 Node A, B, C, D, E;236 L.push_back(A);237 L.push_back(B);238 L.push_back(C);239 L.push_back(D);240 L.push_back(E);241 auto I = L.begin();242 EXPECT_EQ(&A, &*I++);243 EXPECT_EQ(&B, &*I++);244 EXPECT_EQ(&C, &*I++);245 EXPECT_EQ(&D, &*I++);246 EXPECT_EQ(&E, &*I++);247 EXPECT_EQ(L.end(), I);248 EXPECT_EQ(5u, L.size());249 250 // Erase a range.251 EXPECT_EQ(E.getIterator(), L.erase(B.getIterator(), E.getIterator()));252 EXPECT_EQ(&A, &L.front());253 EXPECT_EQ(&E, &L.back());254 EXPECT_EQ(2u, L.size());255}256 257TEST(SimpleIListTest, eraseAndDisposeRange) {258 simple_ilist<Node> L;259 Node A, *B = new Node, *C = new Node, *D = new Node, E;260 L.push_back(A);261 L.push_back(*B);262 L.push_back(*C);263 L.push_back(*D);264 L.push_back(E);265 auto I = L.begin();266 EXPECT_EQ(&A, &*I++);267 EXPECT_EQ(B, &*I++);268 EXPECT_EQ(C, &*I++);269 EXPECT_EQ(D, &*I++);270 EXPECT_EQ(&E, &*I++);271 EXPECT_EQ(L.end(), I);272 EXPECT_EQ(5u, L.size());273 274 // Erase a range.275 EXPECT_EQ(E.getIterator(),276 L.eraseAndDispose(B->getIterator(), E.getIterator(), deleteNode()));277 EXPECT_EQ(&A, &L.front());278 EXPECT_EQ(&E, &L.back());279 EXPECT_EQ(2u, L.size());280}281 282TEST(SimpleIListTest, eraseAndDisposeRangeNullDeleter) {283 simple_ilist<Node> L;284 Node A, B, C, D, E;285 L.push_back(A);286 L.push_back(B);287 L.push_back(C);288 L.push_back(D);289 L.push_back(E);290 auto I = L.begin();291 EXPECT_EQ(&A, &*I++);292 EXPECT_EQ(&B, &*I++);293 EXPECT_EQ(&C, &*I++);294 EXPECT_EQ(&D, &*I++);295 EXPECT_EQ(&E, &*I++);296 EXPECT_EQ(L.end(), I);297 EXPECT_EQ(5u, L.size());298 299 // Erase a range.300 EXPECT_EQ(E.getIterator(),301 L.eraseAndDispose(B.getIterator(), E.getIterator(), doNothing));302 EXPECT_EQ(&A, &L.front());303 EXPECT_EQ(&E, &L.back());304 EXPECT_EQ(2u, L.size());305}306 307TEST(SimpleIListTest, clear) {308 simple_ilist<Node> L;309 Node A, B;310 L.push_back(A);311 L.push_back(B);312 L.clear();313 EXPECT_TRUE(L.empty());314 EXPECT_EQ(0u, L.size());315}316 317TEST(SimpleIListTest, clearAndDispose) {318 simple_ilist<Node> L;319 Node *A = new Node;320 Node *B = new Node;321 L.push_back(*A);322 L.push_back(*B);323 L.clearAndDispose(deleteNode());324 EXPECT_TRUE(L.empty());325 EXPECT_EQ(0u, L.size());326}327 328TEST(SimpleIListTest, clearAndDisposeNullDeleter) {329 simple_ilist<Node> L;330 Node A, B;331 L.push_back(A);332 L.push_back(B);333 L.clearAndDispose(doNothing);334 EXPECT_TRUE(L.empty());335 EXPECT_EQ(0u, L.size());336}337 338TEST(SimpleIListTest, spliceList) {339 simple_ilist<Node> L1, L2;340 Node A, B, C, D;341 342 // [A, D].343 L1.push_back(A);344 L1.push_back(D);345 346 // [B, C].347 L2.push_back(B);348 L2.push_back(C);349 350 // Splice in L2, giving [A, B, C, D].351 L1.splice(--L1.end(), L2);352 EXPECT_TRUE(L2.empty());353 EXPECT_EQ(4u, L1.size());354 auto I = L1.begin();355 EXPECT_EQ(&A, &*I++);356 EXPECT_EQ(&B, &*I++);357 EXPECT_EQ(&C, &*I++);358 EXPECT_EQ(&D, &*I++);359 EXPECT_EQ(L1.end(), I);360}361 362TEST(SimpleIListTest, spliceSingle) {363 simple_ilist<Node> L1, L2;364 Node A, B, C, D, E;365 366 // [A, C].367 L1.push_back(A);368 L1.push_back(C);369 370 // [D, B, E].371 L2.push_back(D);372 L2.push_back(B);373 L2.push_back(E);374 375 // Splice B from L2 to L1, giving [A, B, C] and [D, E].376 L1.splice(--L1.end(), L2, ++L2.begin());377 auto I = L1.begin();378 EXPECT_EQ(&A, &*I++);379 EXPECT_EQ(&B, &*I++);380 EXPECT_EQ(&C, &*I++);381 EXPECT_EQ(L1.end(), I);382 383 I = L2.begin();384 EXPECT_EQ(&D, &*I++);385 EXPECT_EQ(&E, &*I++);386 EXPECT_EQ(L2.end(), I);387}388 389TEST(SimpleIListTest, spliceRange) {390 simple_ilist<Node> L1, L2;391 Node A, B, C, D, E, F;392 393 // [A, D].394 L1.push_back(A);395 L1.push_back(D);396 397 // [E, B, C, F].398 L2.push_back(E);399 L2.push_back(B);400 L2.push_back(C);401 L2.push_back(F);402 403 // Splice B from L2 to L1, giving [A, B, C, D] and [E, F].404 L1.splice(--L1.end(), L2, ++L2.begin(), --L2.end());405 auto I = L1.begin();406 EXPECT_EQ(&A, &*I++);407 EXPECT_EQ(&B, &*I++);408 EXPECT_EQ(&C, &*I++);409 EXPECT_EQ(&D, &*I++);410 EXPECT_EQ(L1.end(), I);411 412 I = L2.begin();413 EXPECT_EQ(&E, &*I++);414 EXPECT_EQ(&F, &*I++);415 EXPECT_EQ(L2.end(), I);416}417 418TEST(SimpleIListTest, merge) {419 for (bool IsL1LHS : {false, true}) {420 simple_ilist<Node> L1, L2;421 Node Ns[10];422 423 // Fill L1.424 L1.push_back(Ns[0]);425 L1.push_back(Ns[3]);426 L1.push_back(Ns[4]);427 L1.push_back(Ns[8]);428 429 // Fill L2.430 L2.push_back(Ns[1]);431 L2.push_back(Ns[2]);432 L2.push_back(Ns[5]);433 L2.push_back(Ns[6]);434 L2.push_back(Ns[7]);435 L2.push_back(Ns[9]);436 437 // Check setup.438 EXPECT_EQ(4u, L1.size());439 EXPECT_EQ(6u, L2.size());440 EXPECT_TRUE(llvm::is_sorted(L1));441 EXPECT_TRUE(llvm::is_sorted(L2));442 443 // Merge.444 auto &LHS = IsL1LHS ? L1 : L2;445 auto &RHS = IsL1LHS ? L2 : L1;446 LHS.merge(RHS);447 EXPECT_TRUE(RHS.empty());448 EXPECT_FALSE(LHS.empty());449 EXPECT_TRUE(llvm::is_sorted(LHS));450 auto I = LHS.begin();451 for (Node &N : Ns)452 EXPECT_EQ(&N, &*I++);453 EXPECT_EQ(LHS.end(), I);454 }455}456 457TEST(SimpleIListTest, mergeIsStable) {458 simple_ilist<Node> L1, L2;459 Node Ns[5];460 461 auto setup = [&]() {462 EXPECT_TRUE(L1.empty());463 EXPECT_TRUE(L2.empty());464 465 // Fill L1.466 L1.push_back(Ns[0]);467 L1.push_back(Ns[3]);468 L1.push_back(Ns[4]);469 470 // Fill L2.471 L2.push_back(Ns[1]);472 L2.push_back(Ns[2]);473 474 // Check setup.475 EXPECT_EQ(3u, L1.size());476 EXPECT_EQ(2u, L2.size());477 EXPECT_TRUE(llvm::is_sorted(L1, makeFalse));478 EXPECT_TRUE(llvm::is_sorted(L2, makeFalse));479 };480 481 // Merge. Should be stable.482 setup();483 L1.merge(L2, makeFalse);484 EXPECT_TRUE(L2.empty());485 EXPECT_FALSE(L1.empty());486 EXPECT_TRUE(llvm::is_sorted(L1, makeFalse));487 auto I = L1.begin();488 EXPECT_EQ(&Ns[0], &*I++);489 EXPECT_EQ(&Ns[3], &*I++);490 EXPECT_EQ(&Ns[4], &*I++);491 EXPECT_EQ(&Ns[1], &*I++);492 EXPECT_EQ(&Ns[2], &*I++);493 EXPECT_EQ(L1.end(), I);494 495 // Merge the other way. Should be stable.496 L1.clear();497 setup();498 L2.merge(L1, makeFalse);499 EXPECT_TRUE(L1.empty());500 EXPECT_FALSE(L2.empty());501 EXPECT_TRUE(llvm::is_sorted(L2, makeFalse));502 I = L2.begin();503 EXPECT_EQ(&Ns[1], &*I++);504 EXPECT_EQ(&Ns[2], &*I++);505 EXPECT_EQ(&Ns[0], &*I++);506 EXPECT_EQ(&Ns[3], &*I++);507 EXPECT_EQ(&Ns[4], &*I++);508 EXPECT_EQ(L2.end(), I);509}510 511TEST(SimpleIListTest, mergeEmpty) {512 for (bool IsL1LHS : {false, true}) {513 simple_ilist<Node> L1, L2;514 Node Ns[4];515 516 // Fill L1.517 L1.push_back(Ns[0]);518 L1.push_back(Ns[1]);519 L1.push_back(Ns[2]);520 L1.push_back(Ns[3]);521 522 // Check setup.523 EXPECT_EQ(4u, L1.size());524 EXPECT_TRUE(L2.empty());525 EXPECT_TRUE(llvm::is_sorted(L1));526 527 // Merge.528 auto &LHS = IsL1LHS ? L1 : L2;529 auto &RHS = IsL1LHS ? L2 : L1;530 LHS.merge(RHS);531 EXPECT_TRUE(RHS.empty());532 EXPECT_FALSE(LHS.empty());533 EXPECT_TRUE(llvm::is_sorted(LHS));534 auto I = LHS.begin();535 for (Node &N : Ns)536 EXPECT_EQ(&N, &*I++);537 EXPECT_EQ(LHS.end(), I);538 }539}540 541TEST(SimpleIListTest, mergeBothEmpty) {542 simple_ilist<Node> L1, L2;543 L1.merge(L2);544 EXPECT_TRUE(L1.empty());545 EXPECT_TRUE(L2.empty());546}547 548TEST(SimpleIListTest, sort) {549 simple_ilist<Node> L;550 Node Ns[10];551 552 // Fill L.553 for (int I : {3, 4, 0, 8, 1, 2, 6, 7, 9, 5})554 L.push_back(Ns[I]);555 556 // Check setup.557 EXPECT_EQ(10u, L.size());558 EXPECT_FALSE(llvm::is_sorted(L));559 560 // Sort.561 L.sort();562 EXPECT_TRUE(llvm::is_sorted(L));563 auto I = L.begin();564 for (Node &N : Ns)565 EXPECT_EQ(&N, &*I++);566 EXPECT_EQ(L.end(), I);567}568 569TEST(SimpleIListTest, sortIsStable) {570 simple_ilist<Node> L;571 Node Ns[10];572 573 // Compare such that nodes are partitioned but not fully sorted.574 auto partition = [&](const Node &N) { return &N >= &Ns[5]; };575 auto compare = [&](const Node &L, const Node &R) {576 return partition(L) < partition(R);577 };578 579 // Fill L.580 for (int I : {3, 4, 7, 8, 1, 2, 6, 0, 9, 5})581 L.push_back(Ns[I]);582 583 // Check setup.584 EXPECT_EQ(10u, L.size());585 EXPECT_FALSE(llvm::is_sorted(L, compare));586 587 // Sort.588 L.sort(compare);589 EXPECT_TRUE(llvm::is_sorted(L, compare));590 auto I = L.begin();591 for (int O : {3, 4, 1, 2, 0})592 EXPECT_EQ(&Ns[O], &*I++);593 for (int O : {7, 8, 6, 9, 5})594 EXPECT_EQ(&Ns[O], &*I++);595 EXPECT_EQ(L.end(), I);596}597 598TEST(SimpleIListTest, sortEmpty) {599 simple_ilist<Node> L;600 L.sort();601}602 603struct Tag1 {};604struct Tag2 {};605 606struct DoubleNode : ilist_node<DoubleNode, ilist_tag<Tag1>>,607 ilist_node<DoubleNode, ilist_tag<Tag2>> {608 using Node1Type = ilist_node<DoubleNode, ilist_tag<Tag1>>;609 using Node2Type = ilist_node<DoubleNode, ilist_tag<Tag2>>;610 611 Node1Type::self_iterator getIterator1() { return Node1Type::getIterator(); }612 Node2Type::self_iterator getIterator2() { return Node2Type::getIterator(); }613 Node1Type::const_self_iterator getIterator1() const {614 return Node1Type::getIterator();615 }616 Node2Type::const_self_iterator getIterator2() const {617 return Node2Type::getIterator();618 }619};620using TaggedList1Type = simple_ilist<DoubleNode, ilist_tag<Tag1>>;621using TaggedList2Type = simple_ilist<DoubleNode, ilist_tag<Tag2>>;622 623TEST(SimpleIListTest, TaggedLists) {624 TaggedList1Type L1;625 TaggedList2Type L2;626 627 // Build the two lists, sharing a couple of nodes.628 DoubleNode Ns[10];629 int Order1[] = {0, 1, 2, 3, 4, 7, 9};630 int Order2[] = {2, 5, 6, 7, 8, 4, 9, 1};631 for (int I : Order1)632 L1.push_back(Ns[I]);633 for (int I : Order2)634 L2.push_back(Ns[I]);635 636 // Check that each list is correct.637 EXPECT_EQ(std::size(Order1), L1.size());638 auto I1 = L1.begin();639 for (int I : Order1) {640 EXPECT_EQ(Ns[I].getIterator1(), I1);641 EXPECT_EQ(&Ns[I], &*I1++);642 }643 EXPECT_EQ(L1.end(), I1);644 645 EXPECT_EQ(std::size(Order2), L2.size());646 auto I2 = L2.begin();647 for (int I : Order2) {648 EXPECT_EQ(Ns[I].getIterator2(), I2);649 EXPECT_EQ(&Ns[I], &*I2++);650 }651 EXPECT_EQ(L2.end(), I2);652}653 654} // end namespace655