1 | /** |
2 | * Copyright (c) Glow Contributors. See CONTRIBUTORS file. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | |
17 | // This file tests the basic functionality of the float16 type. |
18 | // This is by no mean a test to show the IEEE 754 compliance! |
19 | |
20 | #include "glow/Base/TaggedList.h" |
21 | #include "gtest/gtest.h" |
22 | |
23 | #include <iterator> |
24 | |
25 | using namespace glow; |
26 | |
27 | namespace { |
28 | class Node : public TaggedListNode<Node> { |
29 | public: |
30 | Node(int id) : id(id) {} |
31 | int id; |
32 | int adds = 0; |
33 | }; |
34 | } // namespace |
35 | |
36 | struct ListTraits : TaggedListTraits<Node> { |
37 | void addNodeToList(Node *node) { node->adds++; } |
38 | void removeNodeFromList(Node *node) { node->adds--; } |
39 | }; |
40 | |
41 | using List = TaggedList<Node, ListTraits>; |
42 | |
43 | TEST(TaggedList, empty) { |
44 | List ls; |
45 | EXPECT_TRUE(ls.empty()); |
46 | EXPECT_EQ(ls.size(), 0); |
47 | EXPECT_TRUE(ls.begin() == ls.end()); |
48 | EXPECT_FALSE(ls.begin() != ls.end()); |
49 | } |
50 | |
51 | TEST(TaggedList, empty_const) { |
52 | const List ls; |
53 | EXPECT_TRUE(ls.empty()); |
54 | EXPECT_EQ(ls.size(), 0); |
55 | EXPECT_TRUE(ls.begin() == ls.end()); |
56 | EXPECT_FALSE(ls.begin() != ls.end()); |
57 | } |
58 | |
59 | TEST(TaggedList, insert) { |
60 | List ls; |
61 | Node n7(7); |
62 | auto ins = ls.insert(ls.end(), &n7); |
63 | |
64 | EXPECT_EQ(ls.size(), 1); |
65 | EXPECT_FALSE(ls.empty()); |
66 | EXPECT_TRUE(ls.begin() == ins); |
67 | EXPECT_FALSE(ls.begin() != ins); |
68 | EXPECT_TRUE(ins != ls.end()); |
69 | EXPECT_FALSE(ins == ls.end()); |
70 | EXPECT_TRUE(&*ins == &n7); |
71 | EXPECT_EQ(ins->id, 7); |
72 | |
73 | // Trait callback. |
74 | EXPECT_EQ(n7.adds, 1); |
75 | |
76 | // Insert before a real elem: [n8 n7] |
77 | Node n8(8); |
78 | auto in2 = ls.insert(ins, &n8); |
79 | EXPECT_EQ(ls.size(), 2); |
80 | EXPECT_TRUE(&*in2 == &n8); |
81 | EXPECT_TRUE(ls.begin() == in2); |
82 | EXPECT_TRUE(ls.begin() != ins); |
83 | EXPECT_EQ(ins->id, 7); |
84 | EXPECT_EQ(in2->id, 8); |
85 | |
86 | // Insert in the middle: [n8 n9 n7] |
87 | Node n9(9); |
88 | auto in3 = ls.insert(ins, &n9); |
89 | EXPECT_TRUE(ls.begin() != in3); |
90 | EXPECT_TRUE(ls.end() != in3); |
91 | EXPECT_EQ(in3->id, 9); |
92 | |
93 | // Iterate over the list in both directions. |
94 | auto i = ls.begin(); |
95 | EXPECT_EQ(i->id, 8); |
96 | ++i; |
97 | EXPECT_EQ(i++->id, 9); |
98 | EXPECT_EQ(i->id, 7); |
99 | ++i; |
100 | EXPECT_TRUE(i == ls.end()); |
101 | EXPECT_EQ((--i)->id, 7); |
102 | --i; |
103 | EXPECT_EQ((i--)->id, 9); |
104 | EXPECT_EQ(i->id, 8); |
105 | EXPECT_TRUE(i == ls.begin()); |
106 | |
107 | // Same, with const_iterator. |
108 | { |
109 | const auto &cls = ls; |
110 | auto i = cls.begin(); |
111 | EXPECT_EQ(i->id, 8); |
112 | ++i; |
113 | EXPECT_EQ(i++->id, 9); |
114 | EXPECT_EQ(i->id, 7); |
115 | ++i; |
116 | EXPECT_TRUE(i == cls.end()); |
117 | EXPECT_EQ((--i)->id, 7); |
118 | --i; |
119 | EXPECT_EQ((i--)->id, 9); |
120 | EXPECT_EQ(i->id, 8); |
121 | EXPECT_TRUE(i == cls.begin()); |
122 | } |
123 | |
124 | // Destructor crashes trying to delete stack nodes. |
125 | ls.clearAndLeakNodesUnsafely(); |
126 | } |
127 | |
128 | TEST(TaggedList, remove) { |
129 | List ls; |
130 | Node n1(1), n2(2), n3(3); |
131 | auto i1 = ls.insert(ls.end(), &n1); |
132 | ls.insert(ls.end(), &n2); |
133 | auto i3 = ls.insert(ls.end(), &n3); |
134 | EXPECT_EQ(ls.size(), 3); |
135 | EXPECT_EQ(n1.adds, 1); |
136 | EXPECT_EQ(n2.adds, 1); |
137 | EXPECT_EQ(n3.adds, 1); |
138 | EXPECT_TRUE(n1.inTaggedList()); |
139 | |
140 | // Remove from the middle. |
141 | EXPECT_EQ(ls.remove(n2.getIterator()), &n2); |
142 | EXPECT_EQ(ls.size(), std::distance(ls.begin(), ls.end())); |
143 | EXPECT_EQ(n1.adds, 1); |
144 | EXPECT_EQ(n2.adds, 0); |
145 | EXPECT_EQ(n3.adds, 1); |
146 | |
147 | // Remove from back. |
148 | EXPECT_EQ(ls.remove(i3), &n3); |
149 | EXPECT_EQ(ls.size(), std::distance(ls.begin(), ls.end())); |
150 | EXPECT_EQ(n1.adds, 1); |
151 | EXPECT_EQ(n2.adds, 0); |
152 | EXPECT_EQ(n3.adds, 0); |
153 | |
154 | // Remove from front. |
155 | EXPECT_EQ(ls.remove(i1), &n1); |
156 | EXPECT_EQ(ls.size(), std::distance(ls.begin(), ls.end())); |
157 | EXPECT_EQ(n1.adds, 0); |
158 | EXPECT_EQ(n2.adds, 0); |
159 | EXPECT_EQ(n3.adds, 0); |
160 | EXPECT_FALSE(n1.inTaggedList()); |
161 | |
162 | EXPECT_TRUE(ls.empty()); |
163 | } |
164 | |
165 | TEST(TaggedList, reinsert) { |
166 | List ls; |
167 | Node n1(1); |
168 | |
169 | EXPECT_FALSE(n1.inTaggedList()); |
170 | ls.push_back(&n1); |
171 | EXPECT_TRUE(n1.inTaggedList()); |
172 | ls.remove(&n1); |
173 | EXPECT_FALSE(n1.inTaggedList()); |
174 | ls.push_back(&n1); |
175 | EXPECT_TRUE(n1.inTaggedList()); |
176 | ls.remove(&n1); |
177 | } |
178 | |
179 | TEST(TaggedList, reverse_iterator) { |
180 | List ls; |
181 | Node n1(1), n2(2), n3(3); |
182 | ls.push_front(&n1); |
183 | ls.push_back(&n2); |
184 | ls.push_back(&n3); |
185 | |
186 | EXPECT_EQ(ls.size(), std::distance(ls.rbegin(), ls.rend())); |
187 | |
188 | auto i = ls.rbegin(); |
189 | EXPECT_EQ(i->id, 3); |
190 | ++i; |
191 | EXPECT_EQ(i->id, 2); |
192 | i++; |
193 | EXPECT_EQ(i->id, 1); |
194 | EXPECT_TRUE(++i == ls.rend()); |
195 | |
196 | EXPECT_EQ((--i)->id, 1); |
197 | EXPECT_EQ((i--)->id, 1); |
198 | EXPECT_EQ(i->id, 2); |
199 | --i; |
200 | EXPECT_EQ(i->id, 3); |
201 | EXPECT_TRUE(i == ls.rbegin()); |
202 | |
203 | // Same, with const_reverse_iterator. |
204 | { |
205 | const auto &cls = ls; |
206 | auto i = cls.rbegin(); |
207 | EXPECT_EQ(i->id, 3); |
208 | ++i; |
209 | EXPECT_EQ(i->id, 2); |
210 | i++; |
211 | EXPECT_EQ(i->id, 1); |
212 | EXPECT_TRUE(++i == cls.rend()); |
213 | |
214 | EXPECT_EQ((--i)->id, 1); |
215 | EXPECT_EQ((i--)->id, 1); |
216 | EXPECT_EQ(i->id, 2); |
217 | --i; |
218 | EXPECT_EQ(i->id, 3); |
219 | EXPECT_TRUE(i == cls.rbegin()); |
220 | } |
221 | |
222 | ls.clearAndLeakNodesUnsafely(); |
223 | } |
224 | |
225 | TEST(TaggedList, clearAndLeakNodesUnsafely) { |
226 | List ls; |
227 | Node n1(1), n2(2), n3(3); |
228 | ls.insert(ls.end(), &n1); |
229 | ls.insert(ls.end(), &n2); |
230 | ls.insert(ls.end(), &n3); |
231 | |
232 | EXPECT_EQ(ls.size(), 3); |
233 | EXPECT_EQ(n1.adds, 1); |
234 | EXPECT_EQ(n2.adds, 1); |
235 | EXPECT_EQ(n3.adds, 1); |
236 | |
237 | ls.clearAndLeakNodesUnsafely(); |
238 | |
239 | EXPECT_TRUE(ls.begin() == ls.end()); |
240 | EXPECT_EQ(ls.size(), 0); |
241 | EXPECT_EQ(n1.adds, 1); |
242 | EXPECT_EQ(n2.adds, 1); |
243 | EXPECT_EQ(n3.adds, 1); |
244 | } |
245 | |
246 | TEST(TaggedList, clear) { |
247 | List ls; |
248 | Node *n1 = new Node(1); |
249 | Node *n2 = new Node(2); |
250 | Node *n3 = new Node(3); |
251 | ls.insert(ls.end(), n1); |
252 | ls.insert(ls.end(), n2); |
253 | ls.insert(ls.end(), n3); |
254 | |
255 | EXPECT_EQ(ls.size(), 3); |
256 | EXPECT_EQ(n1->adds, 1); |
257 | EXPECT_EQ(n2->adds, 1); |
258 | EXPECT_EQ(n3->adds, 1); |
259 | |
260 | ls.clear(); |
261 | |
262 | EXPECT_TRUE(ls.empty()); |
263 | EXPECT_TRUE(ls.begin() == ls.end()); |
264 | } |
265 | |
266 | TEST(TaggedList, pop) { |
267 | List ls; |
268 | ls.push_front(new Node(1)); |
269 | ls.push_back(new Node(2)); |
270 | ls.pop_back(); |
271 | EXPECT_EQ(ls.front().id, 1); |
272 | EXPECT_EQ(ls.back().id, 1); |
273 | ls.pop_front(); |
274 | EXPECT_TRUE(ls.empty()); |
275 | EXPECT_TRUE(ls.begin() == ls.end()); |
276 | } |
277 | |
278 | TEST(TaggedList, inequality) { |
279 | List ls; |
280 | |
281 | EXPECT_FALSE(ls.begin() < ls.begin()); |
282 | EXPECT_TRUE(ls.begin() <= ls.begin()); |
283 | EXPECT_FALSE(ls.begin() > ls.begin()); |
284 | EXPECT_TRUE(ls.begin() >= ls.begin()); |
285 | |
286 | ls.push_front(new Node(1)); |
287 | ls.push_back(new Node(2)); |
288 | |
289 | auto i1 = ls.begin(); |
290 | auto i2 = ls.back().getIterator(); |
291 | |
292 | EXPECT_TRUE(i1 < i2); |
293 | EXPECT_TRUE(i1 <= i2); |
294 | EXPECT_FALSE(i1 > i2); |
295 | EXPECT_FALSE(i1 >= i2); |
296 | EXPECT_FALSE(i2 < i1); |
297 | EXPECT_FALSE(i2 <= i1); |
298 | EXPECT_TRUE(i2 > i1); |
299 | EXPECT_TRUE(i2 >= i1); |
300 | |
301 | EXPECT_TRUE(i1 < ls.end()); |
302 | EXPECT_TRUE(i1 <= ls.end()); |
303 | EXPECT_FALSE(i1 > ls.end()); |
304 | EXPECT_FALSE(i1 >= ls.end()); |
305 | EXPECT_FALSE(ls.end() < i1); |
306 | EXPECT_FALSE(ls.end() <= i1); |
307 | EXPECT_TRUE(ls.end() > i1); |
308 | EXPECT_TRUE(ls.end() >= i1); |
309 | |
310 | // Same thing for reverse iterators. |
311 | auto r1 = ls.rbegin(); |
312 | auto r2 = ls.front().getReverseIterator(); |
313 | |
314 | EXPECT_TRUE(r1 < r2); |
315 | EXPECT_TRUE(r1 <= r2); |
316 | EXPECT_FALSE(r1 > r2); |
317 | EXPECT_FALSE(r1 >= r2); |
318 | EXPECT_FALSE(r2 < r1); |
319 | EXPECT_FALSE(r2 <= r1); |
320 | EXPECT_TRUE(r2 > r1); |
321 | EXPECT_TRUE(r2 >= r1); |
322 | |
323 | EXPECT_TRUE(r1 < ls.rend()); |
324 | EXPECT_TRUE(r1 <= ls.rend()); |
325 | EXPECT_FALSE(r1 > ls.rend()); |
326 | EXPECT_FALSE(r1 >= ls.rend()); |
327 | EXPECT_FALSE(ls.rend() < r1); |
328 | EXPECT_FALSE(ls.rend() <= r1); |
329 | EXPECT_TRUE(ls.rend() > r1); |
330 | EXPECT_TRUE(ls.rend() >= r1); |
331 | } |
332 | |
333 | TEST(TaggedList, sequencing) { |
334 | List ls; |
335 | |
336 | for (unsigned i = 0; i < 10000; i++) |
337 | ls.push_back(new Node(i)); |
338 | |
339 | // Verify iterator ordering forwards and backwards. |
340 | for (auto i1 = ls.begin(); i1 != ls.end();) { |
341 | auto i0 = i1++; |
342 | EXPECT_TRUE(i0 < i1); |
343 | } |
344 | for (auto i1 = ls.rbegin(); i1 != ls.rend();) { |
345 | auto i0 = i1++; |
346 | EXPECT_TRUE(i0 < i1); |
347 | } |
348 | |
349 | Node &middle = ls.front(); |
350 | for (unsigned i = 0; i < 10000; i++) |
351 | ls.push_front(new Node(i + 10000)); |
352 | |
353 | for (auto i1 = ls.begin(); i1 != ls.end();) { |
354 | auto i0 = i1++; |
355 | EXPECT_TRUE(i0 < i1); |
356 | } |
357 | for (auto i1 = ls.rbegin(); i1 != ls.rend();) { |
358 | auto i0 = i1++; |
359 | EXPECT_TRUE(i0 < i1); |
360 | } |
361 | |
362 | for (unsigned i = 0; i < 10000; i++) |
363 | ls.insert(middle.getIterator(), new Node(i + 20000)); |
364 | |
365 | for (auto i1 = ls.begin(); i1 != ls.end();) { |
366 | auto i0 = i1++; |
367 | EXPECT_TRUE(i0 < i1); |
368 | } |
369 | for (auto i1 = ls.rbegin(); i1 != ls.rend();) { |
370 | auto i0 = i1++; |
371 | EXPECT_TRUE(i0 < i1); |
372 | } |
373 | } |
374 | |