1 //===- unittests/ADT/IListIteratorTest.cpp - ilist_iterator 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 class Parent {};
17
18 struct Node : ilist_node<Node> {};
19 struct ParentNode : ilist_node<ParentNode, ilist_parent<Parent>> {};
20
TEST(IListIteratorTest,DefaultConstructor)21 TEST(IListIteratorTest, DefaultConstructor) {
22 simple_ilist<Node>::iterator I;
23 simple_ilist<Node>::reverse_iterator RI;
24 simple_ilist<Node>::const_iterator CI;
25 simple_ilist<Node>::const_reverse_iterator CRI;
26 EXPECT_EQ(nullptr, I.getNodePtr());
27 EXPECT_EQ(nullptr, CI.getNodePtr());
28 EXPECT_EQ(nullptr, RI.getNodePtr());
29 EXPECT_EQ(nullptr, CRI.getNodePtr());
30 EXPECT_EQ(I, I);
31 EXPECT_EQ(I, CI);
32 EXPECT_EQ(CI, I);
33 EXPECT_EQ(CI, CI);
34 EXPECT_EQ(RI, RI);
35 EXPECT_EQ(RI, CRI);
36 EXPECT_EQ(CRI, RI);
37 EXPECT_EQ(CRI, CRI);
38 EXPECT_EQ(I, RI.getReverse());
39 EXPECT_EQ(RI, I.getReverse());
40 }
41
TEST(IListIteratorTest,Empty)42 TEST(IListIteratorTest, Empty) {
43 simple_ilist<Node> L;
44
45 // Check iterators of L.
46 EXPECT_EQ(L.begin(), L.end());
47 EXPECT_EQ(L.rbegin(), L.rend());
48
49 // Reverse of end should be rend (since the sentinel sits on both sides).
50 EXPECT_EQ(L.end(), L.rend().getReverse());
51 EXPECT_EQ(L.rend(), L.end().getReverse());
52
53 // Iterators shouldn't match default constructors.
54 simple_ilist<Node>::iterator I;
55 simple_ilist<Node>::reverse_iterator RI;
56 EXPECT_NE(I, L.begin());
57 EXPECT_NE(I, L.end());
58 EXPECT_NE(RI, L.rbegin());
59 EXPECT_NE(RI, L.rend());
60 }
61
TEST(IListIteratorTest,OneNodeList)62 TEST(IListIteratorTest, OneNodeList) {
63 simple_ilist<Node> L;
64 Node A;
65 L.insert(L.end(), A);
66
67 // Check address of reference.
68 EXPECT_EQ(&A, &*L.begin());
69 EXPECT_EQ(&A, &*L.rbegin());
70
71 // Check that the handle matches.
72 EXPECT_EQ(L.rbegin().getNodePtr(), L.begin().getNodePtr());
73
74 // Check iteration.
75 EXPECT_EQ(L.end(), ++L.begin());
76 EXPECT_EQ(L.begin(), --L.end());
77 EXPECT_EQ(L.rend(), ++L.rbegin());
78 EXPECT_EQ(L.rbegin(), --L.rend());
79
80 // Check conversions.
81 EXPECT_EQ(L.rbegin(), L.begin().getReverse());
82 EXPECT_EQ(L.begin(), L.rbegin().getReverse());
83 }
84
TEST(IListIteratorTest,TwoNodeList)85 TEST(IListIteratorTest, TwoNodeList) {
86 simple_ilist<Node> L;
87 Node A, B;
88 L.insert(L.end(), A);
89 L.insert(L.end(), B);
90
91 // Check order.
92 EXPECT_EQ(&A, &*L.begin());
93 EXPECT_EQ(&B, &*++L.begin());
94 EXPECT_EQ(L.end(), ++++L.begin());
95 EXPECT_EQ(&B, &*L.rbegin());
96 EXPECT_EQ(&A, &*++L.rbegin());
97 EXPECT_EQ(L.rend(), ++++L.rbegin());
98
99 // Check conversions.
100 EXPECT_EQ(++L.rbegin(), L.begin().getReverse());
101 EXPECT_EQ(L.rbegin(), (++L.begin()).getReverse());
102 EXPECT_EQ(++L.begin(), L.rbegin().getReverse());
103 EXPECT_EQ(L.begin(), (++L.rbegin()).getReverse());
104 }
105
TEST(IListIteratorTest,CheckEraseForward)106 TEST(IListIteratorTest, CheckEraseForward) {
107 simple_ilist<Node> L;
108 Node A, B;
109 L.insert(L.end(), A);
110 L.insert(L.end(), B);
111
112 // Erase nodes.
113 auto I = L.begin();
114 EXPECT_EQ(&A, &*I);
115 L.remove(*I++);
116 EXPECT_EQ(&B, &*I);
117 L.remove(*I++);
118 EXPECT_EQ(L.end(), I);
119 }
120
TEST(IListIteratorTest,CheckEraseReverse)121 TEST(IListIteratorTest, CheckEraseReverse) {
122 simple_ilist<Node> L;
123 Node A, B;
124 L.insert(L.end(), A);
125 L.insert(L.end(), B);
126
127 // Erase nodes.
128 auto RI = L.rbegin();
129 EXPECT_EQ(&B, &*RI);
130 L.remove(*RI++);
131 EXPECT_EQ(&A, &*RI);
132 L.remove(*RI++);
133 EXPECT_EQ(L.rend(), RI);
134 }
135
TEST(IListIteratorTest,ReverseConstructor)136 TEST(IListIteratorTest, ReverseConstructor) {
137 simple_ilist<Node> L;
138 const simple_ilist<Node> &CL = L;
139 Node A, B;
140 L.insert(L.end(), A);
141 L.insert(L.end(), B);
142
143 // Save typing.
144 typedef simple_ilist<Node>::iterator iterator;
145 typedef simple_ilist<Node>::reverse_iterator reverse_iterator;
146 typedef simple_ilist<Node>::const_iterator const_iterator;
147 typedef simple_ilist<Node>::const_reverse_iterator const_reverse_iterator;
148
149 // Check conversion values.
150 EXPECT_EQ(L.begin(), iterator(L.rend()));
151 EXPECT_EQ(++L.begin(), iterator(++L.rbegin()));
152 EXPECT_EQ(L.end(), iterator(L.rbegin()));
153 EXPECT_EQ(L.rbegin(), reverse_iterator(L.end()));
154 EXPECT_EQ(++L.rbegin(), reverse_iterator(++L.begin()));
155 EXPECT_EQ(L.rend(), reverse_iterator(L.begin()));
156
157 // Check const iterator constructors.
158 EXPECT_EQ(CL.begin(), const_iterator(L.rend()));
159 EXPECT_EQ(CL.begin(), const_iterator(CL.rend()));
160 EXPECT_EQ(CL.rbegin(), const_reverse_iterator(L.end()));
161 EXPECT_EQ(CL.rbegin(), const_reverse_iterator(CL.end()));
162
163 // Confirm lack of implicit conversions.
164 static_assert(!std::is_convertible_v<iterator, reverse_iterator>,
165 "unexpected implicit conversion");
166 static_assert(!std::is_convertible_v<reverse_iterator, iterator>,
167 "unexpected implicit conversion");
168 static_assert(!std::is_convertible_v<const_iterator, const_reverse_iterator>,
169 "unexpected implicit conversion");
170 static_assert(!std::is_convertible_v<const_reverse_iterator, const_iterator>,
171 "unexpected implicit conversion");
172 }
173
TEST(IListIteratorTest,GetParent)174 TEST(IListIteratorTest, GetParent) {
175 simple_ilist<ParentNode, ilist_parent<Parent>> L;
176 Parent P;
177 ParentNode A;
178 const simple_ilist<ParentNode, ilist_parent<Parent>> &CL = L;
179
180 // Parents are not set automatically.
181 A.setParent(&P);
182 L.insert(L.end(), A);
183 L.end().getNodePtr()->setParent(&P);
184
185 // Check we can get the node parent from all iterators, including for the
186 // sentinel.
187 EXPECT_EQ(&P, L.begin().getNodeParent());
188 EXPECT_EQ(&P, L.end().getNodeParent());
189 EXPECT_EQ(&P, L.rbegin().getNodeParent());
190 EXPECT_EQ(&P, L.rend().getNodeParent());
191
192 using VarParentTy =
193 std::remove_pointer_t<decltype(L.begin().getNodeParent())>;
194 using ConstParentTy =
195 std::remove_pointer_t<decltype(CL.begin().getNodeParent())>;
196 static_assert(
197 std::is_const_v<ConstParentTy> &&
198 std::is_same_v<VarParentTy, std::remove_const_t<ConstParentTy>>,
199 "`getNodeParent() const` adds const to parent type");
200 }
201
202 } // end namespace
203