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