1 //===- unittests/ADT/SimpleIListTest.cpp - simple_ilist unit tests --------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "llvm/ADT/simple_ilist.h"
11 #include "gtest/gtest.h"
12 
13 using namespace llvm;
14 
15 namespace {
16 
17 struct Node : ilist_node<Node> {};
18 bool operator<(const Node &L, const Node &R) { return &L < &R; }
19 bool makeFalse(const Node &, const Node &) { return false; }
20 
21 struct deleteNode : std::default_delete<Node> {};
22 void doNothing(Node *) {}
23 
24 TEST(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 
31 TEST(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 
50 TEST(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 
69 TEST(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 
83 TEST(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 
94 TEST(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 
105 TEST(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 
129 TEST(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 
147 TEST(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 
164 TEST(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 
181 TEST(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 
198 TEST(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 
216 TEST(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 
233 TEST(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 
257 TEST(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 
282 TEST(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 
307 TEST(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 
317 TEST(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 
328 TEST(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 
338 TEST(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 
362 TEST(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 
389 TEST(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 
418 TEST(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(std::is_sorted(L1.begin(), L1.end()));
441     EXPECT_TRUE(std::is_sorted(L2.begin(), L2.end()));
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(std::is_sorted(LHS.begin(), LHS.end()));
450     auto I = LHS.begin();
451     for (Node &N : Ns)
452       EXPECT_EQ(&N, &*I++);
453     EXPECT_EQ(LHS.end(), I);
454   }
455 }
456 
457 TEST(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(std::is_sorted(L1.begin(), L1.end(), makeFalse));
478     EXPECT_TRUE(std::is_sorted(L2.begin(), L2.end(), 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(std::is_sorted(L1.begin(), L1.end(), 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(std::is_sorted(L2.begin(), L2.end(), 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 
511 TEST(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(std::is_sorted(L1.begin(), L1.end()));
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(std::is_sorted(LHS.begin(), LHS.end()));
534     auto I = LHS.begin();
535     for (Node &N : Ns)
536       EXPECT_EQ(&N, &*I++);
537     EXPECT_EQ(LHS.end(), I);
538   }
539 }
540 
541 TEST(SimpleIListTest, mergeBothEmpty) {
542   simple_ilist<Node> L1, L2;
543   L1.merge(L2);
544   EXPECT_TRUE(L1.empty());
545   EXPECT_TRUE(L2.empty());
546 }
547 
548 TEST(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(std::is_sorted(L.begin(), L.end()));
559 
560   // Sort.
561   L.sort();
562   EXPECT_TRUE(std::is_sorted(L.begin(), L.end()));
563   auto I = L.begin();
564   for (Node &N : Ns)
565     EXPECT_EQ(&N, &*I++);
566   EXPECT_EQ(L.end(), I);
567 }
568 
569 TEST(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(std::is_sorted(L.begin(), L.end(), compare));
586 
587   // Sort.
588   L.sort(compare);
589   EXPECT_TRUE(std::is_sorted(L.begin(), L.end(), 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 
598 TEST(SimpleIListTest, sortEmpty) {
599   simple_ilist<Node> L;
600   L.sort();
601 }
602 
603 struct Tag1 {};
604 struct Tag2 {};
605 
606 struct DoubleNode : ilist_node<DoubleNode, ilist_tag<Tag1>>,
607                     ilist_node<DoubleNode, ilist_tag<Tag2>> {
608   typedef ilist_node<DoubleNode, ilist_tag<Tag1>> Node1Type;
609   typedef ilist_node<DoubleNode, ilist_tag<Tag2>> Node2Type;
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 };
620 typedef simple_ilist<DoubleNode, ilist_tag<Tag1>> TaggedList1Type;
621 typedef simple_ilist<DoubleNode, ilist_tag<Tag2>> TaggedList2Type;
622 
623 TEST(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(sizeof(Order1) / sizeof(int), 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(sizeof(Order2) / sizeof(int), 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 namespace
655