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