1 /*
2 * Copyright (C) 2016 The Android Open Source Project
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 #include <algorithm>
18 #include <forward_list>
19 #include <type_traits>
20 #include <vector>
21
22 #include "gtest/gtest.h"
23 #include "intrusive_forward_list.h"
24
25 namespace art {
26
27 struct IFLTestValue : public IntrusiveForwardListNode<IFLTestValue> {
28 // Deliberately not explicit.
IFLTestValueart::IFLTestValue29 IFLTestValue(int v) : value(v) { } // NOLINT(runtime/explicit)
30
31 int value;
32 };
33 using IFLTestValueList = IntrusiveForwardList<IFLTestValue>;
34 using ConstIFLTestValueList = IntrusiveForwardList<const IFLTestValue>;
35
operator ==(const IFLTestValue & lhs,const IFLTestValue & rhs)36 bool operator==(const IFLTestValue& lhs, const IFLTestValue& rhs) {
37 return lhs.value == rhs.value;
38 }
39
operator <(const IFLTestValue & lhs,const IFLTestValue & rhs)40 bool operator<(const IFLTestValue& lhs, const IFLTestValue& rhs) {
41 return lhs.value < rhs.value;
42 }
43
44 struct IFLTestValue2 {
45 // Deliberately not explicit.
IFLTestValue2art::IFLTestValue246 IFLTestValue2(int v) : hook(), value(v) { } // NOLINT(runtime/explicit)
47
48 IntrusiveForwardListHook hook;
49 int value;
50 };
51 using IFLTestValue2List =
52 IntrusiveForwardList<IFLTestValue2, IntrusiveForwardListMemberHookTraits<IFLTestValue2>>;
53
operator ==(const IFLTestValue2 & lhs,const IFLTestValue2 & rhs)54 bool operator==(const IFLTestValue2& lhs, const IFLTestValue2& rhs) {
55 return lhs.value == rhs.value;
56 }
57
operator <(const IFLTestValue2 & lhs,const IFLTestValue2 & rhs)58 bool operator<(const IFLTestValue2& lhs, const IFLTestValue2& rhs) {
59 return lhs.value < rhs.value;
60 }
61
62 #define ASSERT_LISTS_EQUAL(expected, value) \
63 do { \
64 ASSERT_EQ((expected).empty(), (value).empty()); \
65 ASSERT_EQ(std::distance((expected).begin(), (expected).end()), \
66 std::distance((value).begin(), (value).end())); \
67 ASSERT_TRUE(std::equal((expected).begin(), (expected).end(), (value).begin())); \
68 } while (false)
69
70 class IntrusiveForwardListTest : public testing::Test {
71 public:
72 template <typename ListType>
73 void IteratorToConstIterator();
74
75 template <typename ListType>
76 void IteratorOperators();
77
78 template <typename ListType>
79 void ConstructRange();
80
81 template <typename ListType>
82 void Assign();
83
84 template <typename ListType>
85 void PushPop();
86
87 template <typename ListType>
88 void InsertAfter1();
89
90 template <typename ListType>
91 void InsertAfter2();
92
93 template <typename ListType>
94 void EraseAfter1();
95
96 template <typename ListType>
97 void EraseAfter2();
98
99 template <typename ListType>
100 void SwapClear();
101
102 template <typename ListType>
103 void SpliceAfter();
104
105 template <typename ListType>
106 void Remove();
107
108 template <typename ListType>
109 void Unique();
110
111 template <typename ListType>
112 void Merge();
113
114 template <typename ListType>
115 void Sort1();
116
117 template <typename ListType>
118 void Sort2();
119
120 template <typename ListType>
121 void Reverse();
122
123 template <typename ListType>
124 void ModifyValue();
125 };
126
127 template <typename ListType>
IteratorToConstIterator()128 void IntrusiveForwardListTest::IteratorToConstIterator() {
129 ListType ifl;
130 typename ListType::iterator begin = ifl.begin();
131 typename ListType::const_iterator cbegin = ifl.cbegin();
132 typename ListType::const_iterator converted_begin = begin;
133 ASSERT_TRUE(converted_begin == cbegin);
134 }
135
TEST_F(IntrusiveForwardListTest,IteratorToConstIterator)136 TEST_F(IntrusiveForwardListTest, IteratorToConstIterator) {
137 IteratorToConstIterator<IFLTestValueList>();
138 IteratorToConstIterator<ConstIFLTestValueList>();
139 IteratorToConstIterator<IFLTestValue2List>();
140 }
141
142 template <typename ListType>
IteratorOperators()143 void IntrusiveForwardListTest::IteratorOperators() {
144 using ValueType = typename ListType::value_type;
145 ListType ifl;
146 ASSERT_TRUE(ifl.begin() == ifl.cbegin());
147 ASSERT_FALSE(ifl.begin() != ifl.cbegin());
148 ASSERT_TRUE(ifl.end() == ifl.cend());
149 ASSERT_FALSE(ifl.end() != ifl.cend());
150
151 ASSERT_TRUE(ifl.begin() == ifl.end()); // Empty.
152 ASSERT_FALSE(ifl.begin() != ifl.end()); // Empty.
153
154 ValueType value(1);
155 ifl.insert_after(ifl.cbefore_begin(), value);
156
157 ASSERT_FALSE(ifl.begin() == ifl.end()); // Not empty.
158 ASSERT_TRUE(ifl.begin() != ifl.end()); // Not empty.
159 }
160
TEST_F(IntrusiveForwardListTest,IteratorOperators)161 TEST_F(IntrusiveForwardListTest, IteratorOperators) {
162 IteratorOperators<IFLTestValueList>();
163 IteratorOperators<ConstIFLTestValueList>();
164 IteratorOperators<IFLTestValue2List>();
165 }
166
167 template <typename ListType>
ConstructRange()168 void IntrusiveForwardListTest::ConstructRange() {
169 using ValueType = typename ListType::value_type;
170 std::forward_list<int> ref({ 1, 2, 7 });
171 std::vector<std::remove_const_t<ValueType>> storage(ref.begin(), ref.end());
172 ListType ifl(storage.begin(), storage.end());
173 ASSERT_LISTS_EQUAL(ref, ifl);
174 }
175
TEST_F(IntrusiveForwardListTest,ConstructRange)176 TEST_F(IntrusiveForwardListTest, ConstructRange) {
177 ConstructRange<IFLTestValueList>();
178 ConstructRange<ConstIFLTestValueList>();
179 ConstructRange<IFLTestValue2List>();
180 }
181
182 template <typename ListType>
Assign()183 void IntrusiveForwardListTest::Assign() {
184 using ValueType = typename ListType::value_type;
185 std::forward_list<int> ref1({ 2, 8, 5 });
186 std::vector<std::remove_const_t<ValueType>> storage1(ref1.begin(), ref1.end());
187 ListType ifl;
188 ifl.assign(storage1.begin(), storage1.end());
189 ASSERT_LISTS_EQUAL(ref1, ifl);
190 std::forward_list<int> ref2({ 7, 1, 3 });
191 std::vector<std::remove_const_t<ValueType>> storage2(ref2.begin(), ref2.end());
192 ifl.assign(storage2.begin(), storage2.end());
193 ASSERT_LISTS_EQUAL(ref2, ifl);
194 }
195
TEST_F(IntrusiveForwardListTest,Assign)196 TEST_F(IntrusiveForwardListTest, Assign) {
197 Assign<IFLTestValueList>();
198 Assign<ConstIFLTestValueList>();
199 Assign<IFLTestValue2List>();
200 }
201
202 template <typename ListType>
PushPop()203 void IntrusiveForwardListTest::PushPop() {
204 using ValueType = typename ListType::value_type;
205 ValueType value3(3);
206 ValueType value7(7);
207 std::forward_list<int> ref;
208 ListType ifl;
209 ASSERT_LISTS_EQUAL(ref, ifl);
210 ref.push_front(3);
211 ifl.push_front(value3);
212 ASSERT_LISTS_EQUAL(ref, ifl);
213 ASSERT_EQ(3, ifl.front());
214 ref.push_front(7);
215 ifl.push_front(value7);
216 ASSERT_LISTS_EQUAL(ref, ifl);
217 ASSERT_EQ(7, ifl.front());
218 ref.pop_front();
219 ifl.pop_front();
220 ASSERT_LISTS_EQUAL(ref, ifl);
221 ASSERT_EQ(3, ifl.front());
222 ref.pop_front();
223 ifl.pop_front();
224 ASSERT_LISTS_EQUAL(ref, ifl);
225 }
226
TEST_F(IntrusiveForwardListTest,PushPop)227 TEST_F(IntrusiveForwardListTest, PushPop) {
228 PushPop<IFLTestValueList>();
229 PushPop<ConstIFLTestValueList>();
230 PushPop<IFLTestValue2List>();
231 }
232
233 template <typename ListType>
InsertAfter1()234 void IntrusiveForwardListTest::InsertAfter1() {
235 using ValueType = typename ListType::value_type;
236 ValueType value4(4);
237 ValueType value8(8);
238 ValueType value5(5);
239 ValueType value3(3);
240 std::forward_list<int> ref;
241 ListType ifl;
242
243 auto ref_it = ref.insert_after(ref.before_begin(), 4);
244 auto ifl_it = ifl.insert_after(ifl.before_begin(), value4);
245 ASSERT_LISTS_EQUAL(ref, ifl);
246 ASSERT_EQ(*ref_it, *ifl_it);
247 CHECK(ref_it == ref.begin());
248 ASSERT_TRUE(ifl_it == ifl.begin());
249
250 ref_it = ref.insert_after(ref.begin(), 8);
251 ifl_it = ifl.insert_after(ifl.begin(), value8);
252 ASSERT_LISTS_EQUAL(ref, ifl);
253 ASSERT_EQ(*ref_it, *ifl_it);
254 CHECK(ref_it != ref.end());
255 ASSERT_TRUE(ifl_it != ifl.end());
256 CHECK(++ref_it == ref.end());
257 ASSERT_TRUE(++ifl_it == ifl.end());
258
259 ref_it = ref.insert_after(ref.begin(), 5);
260 ifl_it = ifl.insert_after(ifl.begin(), value5);
261 ASSERT_LISTS_EQUAL(ref, ifl);
262 ASSERT_EQ(*ref_it, *ifl_it);
263
264 ref_it = ref.insert_after(ref_it, 3);
265 ifl_it = ifl.insert_after(ifl_it, value3);
266 ASSERT_LISTS_EQUAL(ref, ifl);
267 ASSERT_EQ(*ref_it, *ifl_it);
268 }
269
TEST_F(IntrusiveForwardListTest,InsertAfter1)270 TEST_F(IntrusiveForwardListTest, InsertAfter1) {
271 InsertAfter1<IFLTestValueList>();
272 InsertAfter1<ConstIFLTestValueList>();
273 InsertAfter1<IFLTestValue2List>();
274 }
275
276 template <typename ListType>
InsertAfter2()277 void IntrusiveForwardListTest::InsertAfter2() {
278 using ValueType = typename ListType::value_type;
279 std::forward_list<int> ref;
280 ListType ifl;
281
282 auto ref_it = ref.insert_after(ref.before_begin(), { 2, 8, 5 });
283 std::vector<std::remove_const_t<ValueType>> storage1({ { 2 }, { 8 }, { 5 } });
284 auto ifl_it = ifl.insert_after(ifl.before_begin(), storage1.begin(), storage1.end());
285 ASSERT_LISTS_EQUAL(ref, ifl);
286 ASSERT_EQ(*ref_it, *ifl_it);
287
288 std::vector<std::remove_const_t<ValueType>> storage2({ { 7 }, { 2 } });
289 ref_it = ref.insert_after(ref.begin(), { 7, 2 });
290 ifl_it = ifl.insert_after(ifl.begin(), storage2.begin(), storage2.end());
291 ASSERT_LISTS_EQUAL(ref, ifl);
292 ASSERT_EQ(*ref_it, *ifl_it);
293
294 std::vector<std::remove_const_t<ValueType>> storage3({ { 1 }, { 3 }, { 4 }, { 9 } });
295 ref_it = ref.begin();
296 ifl_it = ifl.begin();
297 std::advance(ref_it, std::distance(ref.begin(), ref.end()) - 1);
298 std::advance(ifl_it, std::distance(ifl.begin(), ifl.end()) - 1);
299 ref_it = ref.insert_after(ref_it, { 1, 3, 4, 9 });
300 ifl_it = ifl.insert_after(ifl_it, storage3.begin(), storage3.end());
301 ASSERT_LISTS_EQUAL(ref, ifl);
302 }
303
TEST_F(IntrusiveForwardListTest,InsertAfter2)304 TEST_F(IntrusiveForwardListTest, InsertAfter2) {
305 InsertAfter2<IFLTestValueList>();
306 InsertAfter2<ConstIFLTestValueList>();
307 InsertAfter2<IFLTestValue2List>();
308 }
309
310 template <typename ListType>
EraseAfter1()311 void IntrusiveForwardListTest::EraseAfter1() {
312 using ValueType = typename ListType::value_type;
313 std::forward_list<int> ref({ 1, 2, 7, 4, 5 });
314 std::vector<std::remove_const_t<ValueType>> storage(ref.begin(), ref.end());
315 ListType ifl(storage.begin(), storage.end());
316 ASSERT_LISTS_EQUAL(ref, ifl);
317 CHECK_EQ(std::distance(ref.begin(), ref.end()), 5);
318
319 auto ref_it = ref.begin();
320 auto ifl_it = ifl.begin();
321 std::advance(ref_it, 2);
322 std::advance(ifl_it, 2);
323 ref_it = ref.erase_after(ref_it);
324 ifl_it = ifl.erase_after(ifl_it);
325 ASSERT_LISTS_EQUAL(ref, ifl);
326 CHECK_EQ(std::distance(ref.begin(), ref.end()), 4);
327 CHECK(ref_it != ref.end());
328 ASSERT_TRUE(ifl_it != ifl.end());
329 CHECK(++ref_it == ref.end());
330 ASSERT_TRUE(++ifl_it == ifl.end());
331
332 ref_it = ref.begin();
333 ifl_it = ifl.begin();
334 std::advance(ref_it, 2);
335 std::advance(ifl_it, 2);
336 ref_it = ref.erase_after(ref_it);
337 ifl_it = ifl.erase_after(ifl_it);
338 ASSERT_LISTS_EQUAL(ref, ifl);
339 CHECK_EQ(std::distance(ref.begin(), ref.end()), 3);
340 CHECK(ref_it == ref.end());
341 ASSERT_TRUE(ifl_it == ifl.end());
342
343 ref_it = ref.erase_after(ref.begin());
344 ifl_it = ifl.erase_after(ifl.begin());
345 ASSERT_LISTS_EQUAL(ref, ifl);
346 CHECK_EQ(std::distance(ref.begin(), ref.end()), 2);
347 CHECK(ref_it != ref.end());
348 ASSERT_TRUE(ifl_it != ifl.end());
349 CHECK(++ref_it == ref.end());
350 ASSERT_TRUE(++ifl_it == ifl.end());
351
352 ref_it = ref.erase_after(ref.before_begin());
353 ifl_it = ifl.erase_after(ifl.before_begin());
354 ASSERT_LISTS_EQUAL(ref, ifl);
355 CHECK_EQ(std::distance(ref.begin(), ref.end()), 1);
356 CHECK(ref_it == ref.begin());
357 ASSERT_TRUE(ifl_it == ifl.begin());
358
359 ref_it = ref.erase_after(ref.before_begin());
360 ifl_it = ifl.erase_after(ifl.before_begin());
361 ASSERT_LISTS_EQUAL(ref, ifl);
362 CHECK_EQ(std::distance(ref.begin(), ref.end()), 0);
363 CHECK(ref_it == ref.begin());
364 ASSERT_TRUE(ifl_it == ifl.begin());
365 }
366
TEST_F(IntrusiveForwardListTest,EraseAfter1)367 TEST_F(IntrusiveForwardListTest, EraseAfter1) {
368 EraseAfter1<IFLTestValueList>();
369 EraseAfter1<ConstIFLTestValueList>();
370 EraseAfter1<IFLTestValue2List>();
371 }
372
373 template <typename ListType>
EraseAfter2()374 void IntrusiveForwardListTest::EraseAfter2() {
375 using ValueType = typename ListType::value_type;
376 std::forward_list<int> ref({ 1, 2, 7, 4, 5, 3, 2, 8, 9 });
377 std::vector<std::remove_const_t<ValueType>> storage(ref.begin(), ref.end());
378 ListType ifl(storage.begin(), storage.end());
379 ASSERT_LISTS_EQUAL(ref, ifl);
380 CHECK_EQ(std::distance(ref.begin(), ref.end()), 9);
381
382 auto ref_it = ref.begin();
383 auto ifl_it = ifl.begin();
384 std::advance(ref_it, 3);
385 std::advance(ifl_it, 3);
386 ref_it = ref.erase_after(ref.begin(), ref_it);
387 ifl_it = ifl.erase_after(ifl.begin(), ifl_it);
388 ASSERT_LISTS_EQUAL(ref, ifl);
389 ASSERT_EQ(std::distance(ref.begin(), ref_it), std::distance(ifl.begin(), ifl_it));
390 CHECK_EQ(std::distance(ref.begin(), ref.end()), 7);
391
392 ref_it = ref.erase_after(ref_it, ref.end());
393 ifl_it = ifl.erase_after(ifl_it, ifl.end());
394 ASSERT_LISTS_EQUAL(ref, ifl);
395 CHECK(ref_it == ref.end());
396 ASSERT_TRUE(ifl_it == ifl.end());
397 CHECK_EQ(std::distance(ref.begin(), ref.end()), 2);
398
399 ref_it = ref.erase_after(ref.before_begin(), ref.end());
400 ifl_it = ifl.erase_after(ifl.before_begin(), ifl.end());
401 ASSERT_LISTS_EQUAL(ref, ifl);
402 CHECK(ref_it == ref.end());
403 ASSERT_TRUE(ifl_it == ifl.end());
404 CHECK_EQ(std::distance(ref.begin(), ref.end()), 0);
405 }
406
TEST_F(IntrusiveForwardListTest,EraseAfter2)407 TEST_F(IntrusiveForwardListTest, EraseAfter2) {
408 EraseAfter2<IFLTestValueList>();
409 EraseAfter2<ConstIFLTestValueList>();
410 EraseAfter2<IFLTestValue2List>();
411 }
412
413 template <typename ListType>
SwapClear()414 void IntrusiveForwardListTest::SwapClear() {
415 using ValueType = typename ListType::value_type;
416 std::forward_list<int> ref1({ 1, 2, 7 });
417 std::vector<std::remove_const_t<ValueType>> storage1(ref1.begin(), ref1.end());
418 ListType ifl1(storage1.begin(), storage1.end());
419 std::forward_list<int> ref2({ 3, 8, 6 });
420 std::vector<std::remove_const_t<ValueType>> storage2(ref2.begin(), ref2.end());
421 ListType ifl2(storage2.begin(), storage2.end());
422 ASSERT_LISTS_EQUAL(ref1, ifl1);
423 ASSERT_LISTS_EQUAL(ref2, ifl2);
424 ref1.swap(ref2);
425 ifl1.swap(ifl2);
426 ASSERT_LISTS_EQUAL(ref1, ifl1);
427 ASSERT_LISTS_EQUAL(ref2, ifl2);
428 ref1.clear();
429 ifl1.clear();
430 ASSERT_LISTS_EQUAL(ref1, ifl1);
431 ASSERT_LISTS_EQUAL(ref2, ifl2);
432 swap(ref1, ref2);
433 swap(ifl1, ifl2);
434 ASSERT_LISTS_EQUAL(ref1, ifl1);
435 ASSERT_LISTS_EQUAL(ref2, ifl2);
436 ref1.clear();
437 ifl1.clear();
438 ASSERT_LISTS_EQUAL(ref1, ifl1);
439 ASSERT_LISTS_EQUAL(ref2, ifl2);
440 }
441
TEST_F(IntrusiveForwardListTest,SwapClear)442 TEST_F(IntrusiveForwardListTest, SwapClear) {
443 SwapClear<IFLTestValueList>();
444 SwapClear<ConstIFLTestValueList>();
445 SwapClear<IFLTestValue2List>();
446 }
447
448 template <typename ListType>
SpliceAfter()449 void IntrusiveForwardListTest::SpliceAfter() {
450 using ValueType = typename ListType::value_type;
451 std::forward_list<int> ref1({ 3, 1, 2, 7, 4, 5, 4, 8, 7 });
452 std::forward_list<int> ref2;
453 std::vector<std::remove_const_t<ValueType>> storage(ref1.begin(), ref1.end());
454 ListType ifl1(storage.begin(), storage.end());
455 ListType ifl2;
456 ASSERT_LISTS_EQUAL(ref1, ifl1);
457 ASSERT_LISTS_EQUAL(ref2, ifl2);
458
459 // Move everything to ref2/ifl2.
460 ref2.splice_after(ref2.before_begin(), ref1);
461 ifl2.splice_after(ifl2.before_begin(), ifl1);
462 ASSERT_LISTS_EQUAL(ref1, ifl1);
463 ASSERT_LISTS_EQUAL(ref2, ifl2);
464
465 // Move first element (3) to ref1/ifl1.
466 ref1.splice_after(ref1.before_begin(), ref2, ref2.before_begin());
467 ifl1.splice_after(ifl1.before_begin(), ifl2, ifl2.before_begin());
468 ASSERT_LISTS_EQUAL(ref1, ifl1);
469 ASSERT_LISTS_EQUAL(ref2, ifl2);
470
471 // Move second element (2) to ref1/ifl1 after the first element (3).
472 ref1.splice_after(ref1.begin(), ref2, ref2.begin());
473 ifl1.splice_after(ifl1.begin(), ifl2, ifl2.begin());
474 ASSERT_LISTS_EQUAL(ref1, ifl1);
475 ASSERT_LISTS_EQUAL(ref2, ifl2);
476
477 // Move everything from ref2/ifl2 between the 2 elements now in ref1/ifl1.
478 ref1.splice_after(ref1.begin(), ref2);
479 ifl1.splice_after(ifl1.begin(), ifl2);
480 ASSERT_LISTS_EQUAL(ref1, ifl1);
481 ASSERT_LISTS_EQUAL(ref2, ifl2);
482
483 std::forward_list<int> check({ 3, 1, 7, 4, 5, 4, 8, 7, 2 });
484 ASSERT_LISTS_EQUAL(check, ifl1);
485 ASSERT_TRUE(ifl2.empty());
486
487 // Empty splice_after().
488 ref2.splice_after(
489 ref2.before_begin(), ref1, ref1.before_begin(), ref1.begin());
490 ifl2.splice_after(ifl2.before_begin(), ifl1, ifl1.before_begin(), ifl1.begin());
491 ASSERT_LISTS_EQUAL(ref1, ifl1);
492 ASSERT_LISTS_EQUAL(ref2, ifl2);
493
494 // Move { 1, 7 } to ref2/ifl2.
495 auto ref_it = ref1.begin();
496 auto ifl_it = ifl1.begin();
497 std::advance(ref_it, 3);
498 std::advance(ifl_it, 3);
499 ref2.splice_after(ref2.before_begin(), ref1, ref1.begin(), ref_it);
500 ifl2.splice_after(ifl2.before_begin(), ifl1, ifl1.begin(), ifl_it);
501 ASSERT_LISTS_EQUAL(ref1, ifl1);
502 ASSERT_LISTS_EQUAL(ref2, ifl2);
503
504 // Move { 8, 7, 2 } to the beginning of ref1/ifl1.
505 ref_it = ref1.begin();
506 ifl_it = ifl1.begin();
507 std::advance(ref_it, 3);
508 std::advance(ifl_it, 3);
509 ref1.splice_after(ref1.before_begin(), ref1, ref_it, ref1.end());
510 ifl1.splice_after(ifl1.before_begin(), ifl1, ifl_it, ifl1.end());
511 ASSERT_LISTS_EQUAL(ref1, ifl1);
512
513 check.assign({ 8, 7, 2, 3, 4, 5, 4 });
514 ASSERT_LISTS_EQUAL(check, ifl1);
515 check.assign({ 1, 7 });
516 ASSERT_LISTS_EQUAL(check, ifl2);
517
518 // Move all but the first element to ref2/ifl2.
519 ref_it = ref2.begin();
520 ifl_it = ifl2.begin();
521 std::advance(ref_it, 1);
522 std::advance(ifl_it, 1);
523 ref2.splice_after(ref_it, ref1, ref1.begin(), ref1.end());
524 ifl2.splice_after(ifl_it, ifl1, ifl1.begin(), ifl1.end());
525 ASSERT_LISTS_EQUAL(ref1, ifl1);
526 ASSERT_LISTS_EQUAL(ref2, ifl2);
527
528 check.assign({8});
529 ASSERT_LISTS_EQUAL(check, ifl1);
530
531 // Move the first element of ref1/ifl1 to the beginning of ref1/ifl1 (do nothing).
532 ref1.splice_after(ref1.before_begin(), ref1, ref1.before_begin());
533 ifl1.splice_after(ifl1.before_begin(), ifl1, ifl1.before_begin());
534 ASSERT_LISTS_EQUAL(ref1, ifl1);
535 ASSERT_LISTS_EQUAL(check, ifl1);
536
537 // Move the first element of ref2/ifl2 after itself (do nothing).
538 ref1.splice_after(ref1.begin(), ref1, ref1.before_begin());
539 ifl1.splice_after(ifl1.begin(), ifl1, ifl1.before_begin());
540 ASSERT_LISTS_EQUAL(ref1, ifl1);
541 ASSERT_LISTS_EQUAL(check, ifl1);
542
543 check.assign({ 1, 7, 7, 2, 3, 4, 5, 4 });
544 ASSERT_LISTS_EQUAL(check, ifl2);
545
546 // Move the first element of ref2/ifl2 to the beginning of ref2/ifl2 (do nothing).
547 ref2.splice_after(ref2.before_begin(), ref2, ref2.before_begin());
548 ifl2.splice_after(ifl2.before_begin(), ifl2, ifl2.before_begin());
549 ASSERT_LISTS_EQUAL(ref2, ifl2);
550 ASSERT_LISTS_EQUAL(check, ifl2);
551
552 // Move the first element of ref2/ifl2 after itself (do nothing).
553 ref2.splice_after(ref2.begin(), ref2, ref2.before_begin());
554 ifl2.splice_after(ifl2.begin(), ifl2, ifl2.before_begin());
555 ASSERT_LISTS_EQUAL(ref2, ifl2);
556 ASSERT_LISTS_EQUAL(check, ifl2);
557 }
558
TEST_F(IntrusiveForwardListTest,SpliceAfter)559 TEST_F(IntrusiveForwardListTest, SpliceAfter) {
560 SpliceAfter<IFLTestValueList>();
561 SpliceAfter<ConstIFLTestValueList>();
562 SpliceAfter<IFLTestValue2List>();
563 }
564
565 template <typename ListType>
Remove()566 void IntrusiveForwardListTest::Remove() {
567 using ValueType = typename ListType::value_type;
568 std::forward_list<int> ref({ 3, 1, 2, 7, 4, 5, 4, 8, 7 });
569 std::vector<std::remove_const_t<ValueType>> storage(ref.begin(), ref.end());
570 ListType ifl(storage.begin(), storage.end());
571 ASSERT_LISTS_EQUAL(ref, ifl);
572 ref.remove(1);
573 ifl.remove(1);
574 ASSERT_LISTS_EQUAL(ref, ifl);
575 ref.remove(4);
576 ifl.remove(4);
577 ASSERT_LISTS_EQUAL(ref, ifl);
578 auto odd = [](ValueType value) { return (value.value & 1) != 0; };
579 ref.remove_if(odd);
580 ifl.remove_if(odd);
581 ASSERT_LISTS_EQUAL(ref, ifl);
582 auto all = []([[maybe_unused]] ValueType value) { return true; };
583 ref.remove_if(all);
584 ifl.remove_if(all);
585 ASSERT_LISTS_EQUAL(ref, ifl);
586 }
587
TEST_F(IntrusiveForwardListTest,Remove)588 TEST_F(IntrusiveForwardListTest, Remove) {
589 Remove<IFLTestValueList>();
590 Remove<ConstIFLTestValueList>();
591 Remove<IFLTestValue2List>();
592 }
593
594 template <typename ListType>
Unique()595 void IntrusiveForwardListTest::Unique() {
596 using ValueType = typename ListType::value_type;
597 std::forward_list<int> ref({ 3, 1, 1, 2, 3, 3, 7, 7, 4, 4, 5, 7 });
598 std::vector<std::remove_const_t<ValueType>> storage(ref.begin(), ref.end());
599 ListType ifl(storage.begin(), storage.end());
600 ASSERT_LISTS_EQUAL(ref, ifl);
601 ref.unique();
602 ifl.unique();
603 ASSERT_LISTS_EQUAL(ref, ifl);
604 std::forward_list<int> check({ 3, 1, 2, 3, 7, 4, 5, 7 });
605 ASSERT_LISTS_EQUAL(check, ifl);
606
607 auto bin_pred = [](const ValueType& lhs, const ValueType& rhs) {
608 return (lhs.value & ~1) == (rhs.value & ~1);
609 };
610 ref.unique(bin_pred);
611 ifl.unique(bin_pred);
612 ASSERT_LISTS_EQUAL(ref, ifl);
613 check.assign({ 3, 1, 2, 7, 4, 7 });
614 ASSERT_LISTS_EQUAL(check, ifl);
615 }
616
TEST_F(IntrusiveForwardListTest,Unique)617 TEST_F(IntrusiveForwardListTest, Unique) {
618 Unique<IFLTestValueList>();
619 Unique<ConstIFLTestValueList>();
620 Unique<IFLTestValue2List>();
621 }
622
623 template <typename ListType>
Merge()624 void IntrusiveForwardListTest::Merge() {
625 using ValueType = typename ListType::value_type;
626 std::forward_list<int> ref1({ 1, 4, 8, 8, 12 });
627 std::vector<std::remove_const_t<ValueType>> storage1(ref1.begin(), ref1.end());
628 ListType ifl1(storage1.begin(), storage1.end());
629 std::forward_list<int> ref2({ 3, 5, 6, 7, 9 });
630 std::vector<std::remove_const_t<ValueType>> storage2(ref2.begin(), ref2.end());
631 ListType ifl2(storage2.begin(), storage2.end());
632 ASSERT_LISTS_EQUAL(ref1, ifl1);
633 ASSERT_LISTS_EQUAL(ref2, ifl2);
634 CHECK(std::is_sorted(ref1.begin(), ref1.end()));
635 CHECK(std::is_sorted(ref2.begin(), ref2.end()));
636 ref1.merge(ref2);
637 ifl1.merge(ifl2);
638 ASSERT_LISTS_EQUAL(ref1, ifl1);
639 ASSERT_LISTS_EQUAL(ref2, ifl2);
640 CHECK(ref2.empty());
641 std::forward_list<int> check({ 1, 3, 4, 5, 6, 7, 8, 8, 9, 12 });
642 ASSERT_LISTS_EQUAL(check, ifl1);
643 }
644
TEST_F(IntrusiveForwardListTest,Merge)645 TEST_F(IntrusiveForwardListTest, Merge) {
646 Merge<IFLTestValueList>();
647 Merge<ConstIFLTestValueList>();
648 Merge<IFLTestValue2List>();
649 }
650
651 template <typename ListType>
Sort1()652 void IntrusiveForwardListTest::Sort1() {
653 using ValueType = typename ListType::value_type;
654 std::forward_list<int> ref({ 2, 9, 8, 3, 7, 4, 1, 5, 3, 0 });
655 std::vector<std::remove_const_t<ValueType>> storage(ref.begin(), ref.end());
656 ListType ifl(storage.begin(), storage.end());
657 ASSERT_LISTS_EQUAL(ref, ifl);
658 CHECK(!std::is_sorted(ref.begin(), ref.end()));
659 ref.sort();
660 ifl.sort();
661 ASSERT_LISTS_EQUAL(ref, ifl);
662 std::forward_list<int> check({ 0, 1, 2, 3, 3, 4, 5, 7, 8, 9 });
663 ASSERT_LISTS_EQUAL(check, ifl);
664 }
665
TEST_F(IntrusiveForwardListTest,Sort1)666 TEST_F(IntrusiveForwardListTest, Sort1) {
667 Sort1<IFLTestValueList>();
668 Sort1<ConstIFLTestValueList>();
669 Sort1<IFLTestValue2List>();
670 }
671
672 template <typename ListType>
Sort2()673 void IntrusiveForwardListTest::Sort2() {
674 using ValueType = typename ListType::value_type;
675 std::forward_list<int> ref({ 2, 9, 8, 3, 7, 4, 1, 5, 3, 0 });
676 std::vector<std::remove_const_t<ValueType>> storage(ref.begin(), ref.end());
677 ListType ifl(storage.begin(), storage.end());
678 ASSERT_LISTS_EQUAL(ref, ifl);
679 auto cmp = [](const ValueType& lhs, const ValueType& rhs) {
680 return (lhs.value & ~1) < (rhs.value & ~1);
681 };
682 CHECK(!std::is_sorted(ref.begin(), ref.end(), cmp));
683 ref.sort(cmp);
684 ifl.sort(cmp);
685 ASSERT_LISTS_EQUAL(ref, ifl);
686 std::forward_list<int> check({ 1, 0, 2, 3, 3, 4, 5, 7, 9, 8 });
687 ASSERT_LISTS_EQUAL(check, ifl);
688 }
689
TEST_F(IntrusiveForwardListTest,Sort2)690 TEST_F(IntrusiveForwardListTest, Sort2) {
691 Sort2<IFLTestValueList>();
692 Sort2<ConstIFLTestValueList>();
693 Sort2<IFLTestValue2List>();
694 }
695
696 template <typename ListType>
Reverse()697 void IntrusiveForwardListTest::Reverse() {
698 using ValueType = typename ListType::value_type;
699 std::forward_list<int> ref({ 8, 3, 5, 4, 1, 3 });
700 std::vector<std::remove_const_t<ValueType>> storage(ref.begin(), ref.end());
701 ListType ifl(storage.begin(), storage.end());
702 ASSERT_LISTS_EQUAL(ref, ifl);
703 CHECK(!std::is_sorted(ref.begin(), ref.end()));
704 ref.reverse();
705 ifl.reverse();
706 ASSERT_LISTS_EQUAL(ref, ifl);
707 std::forward_list<int> check({ 3, 1, 4, 5, 3, 8 });
708 ASSERT_LISTS_EQUAL(check, ifl);
709 }
710
TEST_F(IntrusiveForwardListTest,Reverse)711 TEST_F(IntrusiveForwardListTest, Reverse) {
712 Reverse<IFLTestValueList>();
713 Reverse<ConstIFLTestValueList>();
714 Reverse<IFLTestValue2List>();
715 }
716
717 template <typename ListType>
ModifyValue()718 void IntrusiveForwardListTest::ModifyValue() {
719 using ValueType = typename ListType::value_type;
720 std::forward_list<int> ref({ 3, 7, 42 });
721 std::vector<std::remove_const_t<ValueType>> storage(ref.begin(), ref.end());
722 ListType ifl(storage.begin(), storage.end());
723 ASSERT_LISTS_EQUAL(ref, ifl);
724
725 auto add1 = [](const ValueType& value) { return value.value + 1; };
726 std::transform(ref.begin(), ref.end(), ref.begin(), add1);
727 std::transform(ifl.begin(), ifl.end(), ifl.begin(), add1);
728 ASSERT_LISTS_EQUAL(ref, ifl);
729 }
730
TEST_F(IntrusiveForwardListTest,ModifyValue)731 TEST_F(IntrusiveForwardListTest, ModifyValue) {
732 ModifyValue<IFLTestValueList>();
733 // Does not compile with ConstIFLTestValueList because LHS of the assignment is const.
734 // ModifyValue<ConstIFLTestValueList>();
735 static_assert(std::is_const_v<ConstIFLTestValueList::iterator::value_type>);
736 ModifyValue<IFLTestValue2List>();
737 }
738
739 struct Tag1;
740 struct Tag2;
741 struct TwoListsValue : public IntrusiveForwardListNode<TwoListsValue, Tag1>,
742 public IntrusiveForwardListNode<TwoListsValue, Tag2> {
743 // Deliberately not explicit.
TwoListsValueart::TwoListsValue744 TwoListsValue(int v) : value(v) { } // NOLINT(runtime/explicit)
745
746 int value;
747 };
748 using FirstList =
749 IntrusiveForwardList<TwoListsValue, IntrusiveForwardListBaseHookTraits<TwoListsValue, Tag1>>;
750 using SecondList =
751 IntrusiveForwardList<TwoListsValue, IntrusiveForwardListBaseHookTraits<TwoListsValue, Tag2>>;
752
operator ==(const TwoListsValue & lhs,const TwoListsValue & rhs)753 bool operator==(const TwoListsValue& lhs, const TwoListsValue& rhs) {
754 return lhs.value == rhs.value;
755 }
756
TEST_F(IntrusiveForwardListTest,TwoLists)757 TEST_F(IntrusiveForwardListTest, TwoLists) {
758 // Test that a value can be in two lists at the same time and the hooks do not interfere.
759 std::vector<TwoListsValue> storage({ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }); // storage[i] = i
760
761 std::vector<int> order1({ 3, 1, 7, 2, 8, 9, 4, 0, 6, 5 });
762 FirstList list1;
763 auto pos1 = list1.before_begin();
764 for (size_t idx : order1) {
765 pos1 = list1.insert_after(pos1, storage[idx]);
766 }
767
768 std::vector<int> order2({ 8, 5, 1, 6, 7, 2, 9, 3, 0, 4 });
769 SecondList list2;
770 auto pos2 = list2.before_begin();
771 for (size_t idx : order2) {
772 pos2 = list2.insert_after(pos2, storage[idx]);
773 }
774
775 // Using `storage[i] = i`, we can easily compare that nodes of each list are in the right order.
776 ASSERT_LISTS_EQUAL(order1, list1);
777 ASSERT_LISTS_EQUAL(order2, list2);
778 }
779
780 } // namespace art
781