1 //===- unittests/ADT/IListBaseTest.cpp - ilist_base 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/ilist_base.h"
11 #include "gtest/gtest.h"
12 
13 using namespace llvm;
14 
15 namespace {
16 
17 // Test fixture.
18 template <typename T> class IListBaseTest : public ::testing::Test {};
19 
20 // Test variants with the same test.
21 typedef ::testing::Types<ilist_base<false>, ilist_base<true>>
22     IListBaseTestTypes;
23 TYPED_TEST_CASE(IListBaseTest, IListBaseTestTypes);
24 
25 TYPED_TEST(IListBaseTest, insertBeforeImpl) {
26   typedef TypeParam list_base_type;
27   typedef typename list_base_type::node_base_type node_base_type;
28 
29   node_base_type S, A, B;
30 
31   // [S] <-> [S]
32   S.setPrev(&S);
33   S.setNext(&S);
34 
35   // [S] <-> A <-> [S]
36   list_base_type::insertBeforeImpl(S, A);
37   EXPECT_EQ(&A, S.getPrev());
38   EXPECT_EQ(&S, A.getPrev());
39   EXPECT_EQ(&A, S.getNext());
40   EXPECT_EQ(&S, A.getNext());
41 
42   // [S] <-> A <-> B <-> [S]
43   list_base_type::insertBeforeImpl(S, B);
44   EXPECT_EQ(&B, S.getPrev());
45   EXPECT_EQ(&A, B.getPrev());
46   EXPECT_EQ(&S, A.getPrev());
47   EXPECT_EQ(&A, S.getNext());
48   EXPECT_EQ(&B, A.getNext());
49   EXPECT_EQ(&S, B.getNext());
50 }
51 
52 TYPED_TEST(IListBaseTest, removeImpl) {
53   typedef TypeParam list_base_type;
54   typedef typename list_base_type::node_base_type node_base_type;
55 
56   node_base_type S, A, B;
57 
58   // [S] <-> A <-> B <-> [S]
59   S.setPrev(&S);
60   S.setNext(&S);
61   list_base_type::insertBeforeImpl(S, A);
62   list_base_type::insertBeforeImpl(S, B);
63 
64   // [S] <-> B <-> [S]
65   list_base_type::removeImpl(A);
66   EXPECT_EQ(&B, S.getPrev());
67   EXPECT_EQ(&S, B.getPrev());
68   EXPECT_EQ(&B, S.getNext());
69   EXPECT_EQ(&S, B.getNext());
70   EXPECT_EQ(nullptr, A.getPrev());
71   EXPECT_EQ(nullptr, A.getNext());
72 
73   // [S] <-> [S]
74   list_base_type::removeImpl(B);
75   EXPECT_EQ(&S, S.getPrev());
76   EXPECT_EQ(&S, S.getNext());
77   EXPECT_EQ(nullptr, B.getPrev());
78   EXPECT_EQ(nullptr, B.getNext());
79 }
80 
81 TYPED_TEST(IListBaseTest, removeRangeImpl) {
82   typedef TypeParam list_base_type;
83   typedef typename list_base_type::node_base_type node_base_type;
84 
85   node_base_type S, A, B, C, D;
86 
87   // [S] <-> A <-> B <-> C <-> D <-> [S]
88   S.setPrev(&S);
89   S.setNext(&S);
90   list_base_type::insertBeforeImpl(S, A);
91   list_base_type::insertBeforeImpl(S, B);
92   list_base_type::insertBeforeImpl(S, C);
93   list_base_type::insertBeforeImpl(S, D);
94 
95   // [S] <-> A <-> D <-> [S]
96   list_base_type::removeRangeImpl(B, D);
97   EXPECT_EQ(&D, S.getPrev());
98   EXPECT_EQ(&A, D.getPrev());
99   EXPECT_EQ(&S, A.getPrev());
100   EXPECT_EQ(&A, S.getNext());
101   EXPECT_EQ(&D, A.getNext());
102   EXPECT_EQ(&S, D.getNext());
103   EXPECT_EQ(nullptr, B.getPrev());
104   EXPECT_EQ(nullptr, C.getNext());
105 }
106 
107 TYPED_TEST(IListBaseTest, removeRangeImplAllButSentinel) {
108   typedef TypeParam list_base_type;
109   typedef typename list_base_type::node_base_type node_base_type;
110 
111   node_base_type S, A, B;
112 
113   // [S] <-> A <-> B <-> [S]
114   S.setPrev(&S);
115   S.setNext(&S);
116   list_base_type::insertBeforeImpl(S, A);
117   list_base_type::insertBeforeImpl(S, B);
118 
119   // [S] <-> [S]
120   list_base_type::removeRangeImpl(A, S);
121   EXPECT_EQ(&S, S.getPrev());
122   EXPECT_EQ(&S, S.getNext());
123   EXPECT_EQ(nullptr, A.getPrev());
124   EXPECT_EQ(nullptr, B.getNext());
125 }
126 
127 TYPED_TEST(IListBaseTest, transferBeforeImpl) {
128   typedef TypeParam list_base_type;
129   typedef typename list_base_type::node_base_type node_base_type;
130 
131   node_base_type S1, S2, A, B, C, D, E;
132 
133   // [S1] <-> A <-> B <-> C <-> [S1]
134   S1.setPrev(&S1);
135   S1.setNext(&S1);
136   list_base_type::insertBeforeImpl(S1, A);
137   list_base_type::insertBeforeImpl(S1, B);
138   list_base_type::insertBeforeImpl(S1, C);
139 
140   // [S2] <-> D <-> E <-> [S2]
141   S2.setPrev(&S2);
142   S2.setNext(&S2);
143   list_base_type::insertBeforeImpl(S2, D);
144   list_base_type::insertBeforeImpl(S2, E);
145 
146   // [S1] <-> C <-> [S1]
147   list_base_type::transferBeforeImpl(D, A, C);
148   EXPECT_EQ(&C, S1.getPrev());
149   EXPECT_EQ(&S1, C.getPrev());
150   EXPECT_EQ(&C, S1.getNext());
151   EXPECT_EQ(&S1, C.getNext());
152 
153   // [S2] <-> A <-> B <-> D <-> E <-> [S2]
154   EXPECT_EQ(&E, S2.getPrev());
155   EXPECT_EQ(&D, E.getPrev());
156   EXPECT_EQ(&B, D.getPrev());
157   EXPECT_EQ(&A, B.getPrev());
158   EXPECT_EQ(&S2, A.getPrev());
159   EXPECT_EQ(&A, S2.getNext());
160   EXPECT_EQ(&B, A.getNext());
161   EXPECT_EQ(&D, B.getNext());
162   EXPECT_EQ(&E, D.getNext());
163   EXPECT_EQ(&S2, E.getNext());
164 }
165 
166 } // end namespace
167