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 "llvm/ADT/STLExtras.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(Node&: B); |
35 | L.push_front(Node&: 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(Node&: A); |
54 | L.push_back(Node&: 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(Node&: A); |
73 | L1.push_back(Node&: B); |
74 | L1.swap(X&: 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(I: L.end(), Node&: A); |
87 | L.insert(I: L.end(), Node&: 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(I: L.begin(), Node&: B); |
98 | L.insert(I: L.begin(), Node&: 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(Node&: A); |
109 | L.push_back(Node&: B); |
110 | L.push_back(Node&: 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(N&: B); |
117 | EXPECT_EQ(&A, &L.front()); |
118 | EXPECT_EQ(&C, &L.back()); |
119 | EXPECT_EQ(2u, L.size()); |
120 | |
121 | L.remove(N&: A); |
122 | EXPECT_EQ(&C, &L.front()); |
123 | EXPECT_EQ(1u, L.size()); |
124 | |
125 | L.remove(N&: 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(Node&: A); |
134 | L.push_back(Node&: *B); |
135 | L.push_back(Node&: 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(N&: *B, dispose: 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(Node&: A); |
151 | L.push_back(Node&: B); |
152 | L.push_back(Node&: 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(N&: B, dispose: 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(Node&: A); |
168 | L.push_back(Node&: B); |
169 | L.push_back(Node&: 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(Node&: A); |
185 | L.push_back(Node&: B); |
186 | L.push_back(Node&: 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(Node&: A); |
203 | L.push_back(Node&: *B); |
204 | L.push_back(Node&: 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(I: B->getIterator(), dispose: 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(Node&: A); |
220 | L.push_back(Node&: B); |
221 | L.push_back(Node&: 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(I: B.getIterator(), dispose: 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(Node&: A); |
237 | L.push_back(Node&: B); |
238 | L.push_back(Node&: C); |
239 | L.push_back(Node&: D); |
240 | L.push_back(Node&: 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(Node&: A); |
261 | L.push_back(Node&: *B); |
262 | L.push_back(Node&: *C); |
263 | L.push_back(Node&: *D); |
264 | L.push_back(Node&: 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(Node&: A); |
286 | L.push_back(Node&: B); |
287 | L.push_back(Node&: C); |
288 | L.push_back(Node&: D); |
289 | L.push_back(Node&: 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(Node&: A); |
311 | L.push_back(Node&: 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(Node&: *A); |
322 | L.push_back(Node&: *B); |
323 | L.clearAndDispose(dispose: 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(Node&: A); |
332 | L.push_back(Node&: B); |
333 | L.clearAndDispose(dispose: 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(Node&: A); |
344 | L1.push_back(Node&: D); |
345 | |
346 | // [B, C]. |
347 | L2.push_back(Node&: B); |
348 | L2.push_back(Node&: C); |
349 | |
350 | // Splice in L2, giving [A, B, C, D]. |
351 | L1.splice(I: --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(Node&: A); |
368 | L1.push_back(Node&: C); |
369 | |
370 | // [D, B, E]. |
371 | L2.push_back(Node&: D); |
372 | L2.push_back(Node&: B); |
373 | L2.push_back(Node&: E); |
374 | |
375 | // Splice B from L2 to L1, giving [A, B, C] and [D, E]. |
376 | L1.splice(I: --L1.end(), L2, Node: ++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(Node&: A); |
395 | L1.push_back(Node&: D); |
396 | |
397 | // [E, B, C, F]. |
398 | L2.push_back(Node&: E); |
399 | L2.push_back(Node&: B); |
400 | L2.push_back(Node&: C); |
401 | L2.push_back(Node&: F); |
402 | |
403 | // Splice B from L2 to L1, giving [A, B, C, D] and [E, F]. |
404 | L1.splice(I: --L1.end(), L2, First: ++L2.begin(), Last: --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(Node&: Ns[0]); |
425 | L1.push_back(Node&: Ns[3]); |
426 | L1.push_back(Node&: Ns[4]); |
427 | L1.push_back(Node&: Ns[8]); |
428 | |
429 | // Fill L2. |
430 | L2.push_back(Node&: Ns[1]); |
431 | L2.push_back(Node&: Ns[2]); |
432 | L2.push_back(Node&: Ns[5]); |
433 | L2.push_back(Node&: Ns[6]); |
434 | L2.push_back(Node&: Ns[7]); |
435 | L2.push_back(Node&: Ns[9]); |
436 | |
437 | // Check setup. |
438 | EXPECT_EQ(4u, L1.size()); |
439 | EXPECT_EQ(6u, L2.size()); |
440 | EXPECT_TRUE(llvm::is_sorted(L1)); |
441 | EXPECT_TRUE(llvm::is_sorted(L2)); |
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(llvm::is_sorted(LHS)); |
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(Node&: Ns[0]); |
467 | L1.push_back(Node&: Ns[3]); |
468 | L1.push_back(Node&: Ns[4]); |
469 | |
470 | // Fill L2. |
471 | L2.push_back(Node&: Ns[1]); |
472 | L2.push_back(Node&: Ns[2]); |
473 | |
474 | // Check setup. |
475 | EXPECT_EQ(3u, L1.size()); |
476 | EXPECT_EQ(2u, L2.size()); |
477 | EXPECT_TRUE(llvm::is_sorted(L1, makeFalse)); |
478 | EXPECT_TRUE(llvm::is_sorted(L2, makeFalse)); |
479 | }; |
480 | |
481 | // Merge. Should be stable. |
482 | setup(); |
483 | L1.merge(RHS&: L2, comp: makeFalse); |
484 | EXPECT_TRUE(L2.empty()); |
485 | EXPECT_FALSE(L1.empty()); |
486 | EXPECT_TRUE(llvm::is_sorted(L1, 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(RHS&: L1, comp: makeFalse); |
499 | EXPECT_TRUE(L1.empty()); |
500 | EXPECT_FALSE(L2.empty()); |
501 | EXPECT_TRUE(llvm::is_sorted(L2, 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(Node&: Ns[0]); |
518 | L1.push_back(Node&: Ns[1]); |
519 | L1.push_back(Node&: Ns[2]); |
520 | L1.push_back(Node&: Ns[3]); |
521 | |
522 | // Check setup. |
523 | EXPECT_EQ(4u, L1.size()); |
524 | EXPECT_TRUE(L2.empty()); |
525 | EXPECT_TRUE(llvm::is_sorted(L1)); |
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(llvm::is_sorted(LHS)); |
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(RHS&: 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(Node&: Ns[I]); |
555 | |
556 | // Check setup. |
557 | EXPECT_EQ(10u, L.size()); |
558 | EXPECT_FALSE(llvm::is_sorted(L)); |
559 | |
560 | // Sort. |
561 | L.sort(); |
562 | EXPECT_TRUE(llvm::is_sorted(L)); |
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(Node&: Ns[I]); |
582 | |
583 | // Check setup. |
584 | EXPECT_EQ(10u, L.size()); |
585 | EXPECT_FALSE(llvm::is_sorted(L, compare)); |
586 | |
587 | // Sort. |
588 | L.sort(comp: compare); |
589 | EXPECT_TRUE(llvm::is_sorted(L, 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(Node&: Ns[I]); |
633 | for (int I : Order2) |
634 | L2.push_back(Node&: Ns[I]); |
635 | |
636 | // Check that each list is correct. |
637 | EXPECT_EQ(std::size(Order1), 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(std::size(Order2), 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 | |