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 {
27   // Deliberately not explicit.
IFLTestValueart::IFLTestValue28   IFLTestValue(int v) : hook(), value(v) { }  // NOLINT(runtime/explicit)
29 
30   IntrusiveForwardListHook hook;
31   int value;
32 };
33 
operator ==(const IFLTestValue & lhs,const IFLTestValue & rhs)34 bool operator==(const IFLTestValue& lhs, const IFLTestValue& rhs) {
35   return lhs.value == rhs.value;
36 }
37 
operator <(const IFLTestValue & lhs,const IFLTestValue & rhs)38 bool operator<(const IFLTestValue& lhs, const IFLTestValue& rhs) {
39   return lhs.value < rhs.value;
40 }
41 
42 #define ASSERT_LISTS_EQUAL(expected, value)                                   \
43   do {                                                                        \
44     ASSERT_EQ(expected.empty(), value.empty());                               \
45     ASSERT_EQ(std::distance(expected.begin(), expected.end()),                \
46               std::distance(value.begin(), value.end()));                     \
47     ASSERT_TRUE(std::equal(expected.begin(), expected.end(), value.begin())); \
48   } while (false)
49 
TEST(IntrusiveForwardList,IteratorToConstIterator)50 TEST(IntrusiveForwardList, IteratorToConstIterator) {
51   IntrusiveForwardList<IFLTestValue> ifl;
52   IntrusiveForwardList<IFLTestValue>::iterator begin = ifl.begin();
53   IntrusiveForwardList<IFLTestValue>::const_iterator cbegin = ifl.cbegin();
54   IntrusiveForwardList<IFLTestValue>::const_iterator converted_begin = begin;
55   ASSERT_TRUE(converted_begin == cbegin);
56 }
57 
TEST(IntrusiveForwardList,IteratorOperators)58 TEST(IntrusiveForwardList, IteratorOperators) {
59   IntrusiveForwardList<IFLTestValue> ifl;
60   ASSERT_TRUE(ifl.begin() == ifl.cbegin());
61   ASSERT_FALSE(ifl.begin() != ifl.cbegin());
62   ASSERT_TRUE(ifl.end() == ifl.cend());
63   ASSERT_FALSE(ifl.end() != ifl.cend());
64 
65   ASSERT_TRUE(ifl.begin() == ifl.end());  // Empty.
66   ASSERT_FALSE(ifl.begin() != ifl.end());  // Empty.
67 
68   IFLTestValue value(1);
69   ifl.insert_after(ifl.cbefore_begin(), value);
70 
71   ASSERT_FALSE(ifl.begin() == ifl.end());  // Not empty.
72   ASSERT_TRUE(ifl.begin() != ifl.end());  // Not empty.
73 }
74 
TEST(IntrusiveForwardList,ConstructRange)75 TEST(IntrusiveForwardList, ConstructRange) {
76   std::forward_list<int> ref({ 1, 2, 7 });
77   std::vector<IFLTestValue> storage(ref.begin(), ref.end());
78   IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
79   ASSERT_LISTS_EQUAL(ref, ifl);
80 }
81 
TEST(IntrusiveForwardList,Assign)82 TEST(IntrusiveForwardList, Assign) {
83   std::forward_list<int> ref1({ 2, 8, 5 });
84   std::vector<IFLTestValue> storage1(ref1.begin(), ref1.end());
85   IntrusiveForwardList<IFLTestValue> ifl;
86   ifl.assign(storage1.begin(), storage1.end());
87   ASSERT_LISTS_EQUAL(ref1, ifl);
88   std::forward_list<int> ref2({ 7, 1, 3 });
89   std::vector<IFLTestValue> storage2(ref2.begin(), ref2.end());
90   ifl.assign(storage2.begin(), storage2.end());
91   ASSERT_LISTS_EQUAL(ref2, ifl);
92 }
93 
TEST(IntrusiveForwardList,PushPop)94 TEST(IntrusiveForwardList, PushPop) {
95   IFLTestValue value3(3);
96   IFLTestValue value7(7);
97   std::forward_list<int> ref;
98   IntrusiveForwardList<IFLTestValue> ifl;
99   ASSERT_LISTS_EQUAL(ref, ifl);
100   ref.push_front(3);
101   ifl.push_front(value3);
102   ASSERT_LISTS_EQUAL(ref, ifl);
103   ASSERT_EQ(3, ifl.front());
104   ref.push_front(7);
105   ifl.push_front(value7);
106   ASSERT_LISTS_EQUAL(ref, ifl);
107   ASSERT_EQ(7, ifl.front());
108   ref.pop_front();
109   ifl.pop_front();
110   ASSERT_LISTS_EQUAL(ref, ifl);
111   ASSERT_EQ(3, ifl.front());
112   ref.pop_front();
113   ifl.pop_front();
114   ASSERT_LISTS_EQUAL(ref, ifl);
115 }
116 
TEST(IntrusiveForwardList,InsertAfter1)117 TEST(IntrusiveForwardList, InsertAfter1) {
118   IFLTestValue value4(4);
119   IFLTestValue value8(8);
120   IFLTestValue value5(5);
121   IFLTestValue value3(3);
122   std::forward_list<int> ref;
123   IntrusiveForwardList<IFLTestValue> ifl;
124 
125   auto ref_it = ref.insert_after(ref.before_begin(), 4);
126   auto ifl_it = ifl.insert_after(ifl.before_begin(), value4);
127   ASSERT_LISTS_EQUAL(ref, ifl);
128   ASSERT_EQ(*ref_it, *ifl_it);
129   CHECK(ref_it == ref.begin());
130   ASSERT_TRUE(ifl_it == ifl.begin());
131 
132   ref_it = ref.insert_after(ref.begin(), 8);
133   ifl_it = ifl.insert_after(ifl.begin(), value8);
134   ASSERT_LISTS_EQUAL(ref, ifl);
135   ASSERT_EQ(*ref_it, *ifl_it);
136   CHECK(ref_it != ref.end());
137   ASSERT_TRUE(ifl_it != ifl.end());
138   CHECK(++ref_it == ref.end());
139   ASSERT_TRUE(++ifl_it == ifl.end());
140 
141   ref_it = ref.insert_after(ref.begin(), 5);
142   ifl_it = ifl.insert_after(ifl.begin(), value5);
143   ASSERT_LISTS_EQUAL(ref, ifl);
144   ASSERT_EQ(*ref_it, *ifl_it);
145 
146   ref_it = ref.insert_after(ref_it, 3);
147   ifl_it = ifl.insert_after(ifl_it, value3);
148   ASSERT_LISTS_EQUAL(ref, ifl);
149   ASSERT_EQ(*ref_it, *ifl_it);
150 }
151 
TEST(IntrusiveForwardList,InsertAfter2)152 TEST(IntrusiveForwardList, InsertAfter2) {
153   std::forward_list<int> ref;
154   IntrusiveForwardList<IFLTestValue> ifl;
155 
156   auto ref_it = ref.insert_after(ref.before_begin(), { 2, 8, 5 });
157   std::vector<IFLTestValue> storage1({ { 2 }, { 8 }, { 5 } });
158   auto ifl_it = ifl.insert_after(ifl.before_begin(), storage1.begin(), storage1.end());
159   ASSERT_LISTS_EQUAL(ref, ifl);
160   ASSERT_EQ(*ref_it, *ifl_it);
161 
162   std::vector<IFLTestValue> storage2({ { 7 }, { 2 } });
163   ref_it = ref.insert_after(ref.begin(), { 7, 2 });
164   ifl_it = ifl.insert_after(ifl.begin(), storage2.begin(), storage2.end());
165   ASSERT_LISTS_EQUAL(ref, ifl);
166   ASSERT_EQ(*ref_it, *ifl_it);
167 
168   std::vector<IFLTestValue> storage3({ { 1 }, { 3 }, { 4 }, { 9 } });
169   ref_it = ref.begin();
170   ifl_it = ifl.begin();
171   std::advance(ref_it, std::distance(ref.begin(), ref.end()) - 1);
172   std::advance(ifl_it, std::distance(ifl.begin(), ifl.end()) - 1);
173   ref_it = ref.insert_after(ref_it, { 1, 3, 4, 9 });
174   ifl_it = ifl.insert_after(ifl_it, storage3.begin(), storage3.end());
175   ASSERT_LISTS_EQUAL(ref, ifl);
176 }
177 
TEST(IntrusiveForwardList,EraseAfter1)178 TEST(IntrusiveForwardList, EraseAfter1) {
179   std::forward_list<int> ref({ 1, 2, 7, 4, 5 });
180   std::vector<IFLTestValue> storage(ref.begin(), ref.end());
181   IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
182   ASSERT_LISTS_EQUAL(ref, ifl);
183   CHECK_EQ(std::distance(ref.begin(), ref.end()), 5);
184 
185   auto ref_it = ref.begin();
186   auto ifl_it = ifl.begin();
187   std::advance(ref_it, 2);
188   std::advance(ifl_it, 2);
189   ref_it = ref.erase_after(ref_it);
190   ifl_it = ifl.erase_after(ifl_it);
191   ASSERT_LISTS_EQUAL(ref, ifl);
192   CHECK_EQ(std::distance(ref.begin(), ref.end()), 4);
193   CHECK(ref_it != ref.end());
194   ASSERT_TRUE(ifl_it != ifl.end());
195   CHECK(++ref_it == ref.end());
196   ASSERT_TRUE(++ifl_it == ifl.end());
197 
198   ref_it = ref.begin();
199   ifl_it = ifl.begin();
200   std::advance(ref_it, 2);
201   std::advance(ifl_it, 2);
202   ref_it = ref.erase_after(ref_it);
203   ifl_it = ifl.erase_after(ifl_it);
204   ASSERT_LISTS_EQUAL(ref, ifl);
205   CHECK_EQ(std::distance(ref.begin(), ref.end()), 3);
206   CHECK(ref_it == ref.end());
207   ASSERT_TRUE(ifl_it == ifl.end());
208 
209   ref_it = ref.erase_after(ref.begin());
210   ifl_it = ifl.erase_after(ifl.begin());
211   ASSERT_LISTS_EQUAL(ref, ifl);
212   CHECK_EQ(std::distance(ref.begin(), ref.end()), 2);
213   CHECK(ref_it != ref.end());
214   ASSERT_TRUE(ifl_it != ifl.end());
215   CHECK(++ref_it == ref.end());
216   ASSERT_TRUE(++ifl_it == ifl.end());
217 
218   ref_it = ref.erase_after(ref.before_begin());
219   ifl_it = ifl.erase_after(ifl.before_begin());
220   ASSERT_LISTS_EQUAL(ref, ifl);
221   CHECK_EQ(std::distance(ref.begin(), ref.end()), 1);
222   CHECK(ref_it == ref.begin());
223   ASSERT_TRUE(ifl_it == ifl.begin());
224 
225   ref_it = ref.erase_after(ref.before_begin());
226   ifl_it = ifl.erase_after(ifl.before_begin());
227   ASSERT_LISTS_EQUAL(ref, ifl);
228   CHECK_EQ(std::distance(ref.begin(), ref.end()), 0);
229   CHECK(ref_it == ref.begin());
230   ASSERT_TRUE(ifl_it == ifl.begin());
231 }
232 
TEST(IntrusiveForwardList,EraseAfter2)233 TEST(IntrusiveForwardList, EraseAfter2) {
234   std::forward_list<int> ref({ 1, 2, 7, 4, 5, 3, 2, 8, 9 });
235   std::vector<IFLTestValue> storage(ref.begin(), ref.end());
236   IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
237   ASSERT_LISTS_EQUAL(ref, ifl);
238   CHECK_EQ(std::distance(ref.begin(), ref.end()), 9);
239 
240   auto ref_it = ref.begin();
241   auto ifl_it = ifl.begin();
242   std::advance(ref_it, 3);
243   std::advance(ifl_it, 3);
244   ref_it = ref.erase_after(ref.begin(), ref_it);
245   ifl_it = ifl.erase_after(ifl.begin(), ifl_it);
246   ASSERT_LISTS_EQUAL(ref, ifl);
247   ASSERT_EQ(std::distance(ref.begin(), ref_it), std::distance(ifl.begin(), ifl_it));
248   CHECK_EQ(std::distance(ref.begin(), ref.end()), 7);
249 
250   ref_it = ref.erase_after(ref_it, ref.end());
251   ifl_it = ifl.erase_after(ifl_it, ifl.end());
252   ASSERT_LISTS_EQUAL(ref, ifl);
253   CHECK(ref_it == ref.end());
254   ASSERT_TRUE(ifl_it == ifl.end());
255   CHECK_EQ(std::distance(ref.begin(), ref.end()), 2);
256 
257   ref_it = ref.erase_after(ref.before_begin(), ref.end());
258   ifl_it = ifl.erase_after(ifl.before_begin(), ifl.end());
259   ASSERT_LISTS_EQUAL(ref, ifl);
260   CHECK(ref_it == ref.end());
261   ASSERT_TRUE(ifl_it == ifl.end());
262   CHECK_EQ(std::distance(ref.begin(), ref.end()), 0);
263 }
264 
TEST(IntrusiveForwardList,SwapClear)265 TEST(IntrusiveForwardList, SwapClear) {
266   std::forward_list<int> ref1({ 1, 2, 7 });
267   std::vector<IFLTestValue> storage1(ref1.begin(), ref1.end());
268   IntrusiveForwardList<IFLTestValue> ifl1(storage1.begin(), storage1.end());
269   std::forward_list<int> ref2({ 3, 8, 6 });
270   std::vector<IFLTestValue> storage2(ref2.begin(), ref2.end());
271   IntrusiveForwardList<IFLTestValue> ifl2(storage2.begin(), storage2.end());
272   ASSERT_LISTS_EQUAL(ref1, ifl1);
273   ASSERT_LISTS_EQUAL(ref2, ifl2);
274   ref1.swap(ref2);
275   ifl1.swap(ifl2);
276   ASSERT_LISTS_EQUAL(ref1, ifl1);
277   ASSERT_LISTS_EQUAL(ref2, ifl2);
278   ref1.clear();
279   ifl1.clear();
280   ASSERT_LISTS_EQUAL(ref1, ifl1);
281   ASSERT_LISTS_EQUAL(ref2, ifl2);
282   swap(ref1, ref2);
283   swap(ifl1, ifl2);
284   ASSERT_LISTS_EQUAL(ref1, ifl1);
285   ASSERT_LISTS_EQUAL(ref2, ifl2);
286   ref1.clear();
287   ifl1.clear();
288   ASSERT_LISTS_EQUAL(ref1, ifl1);
289   ASSERT_LISTS_EQUAL(ref2, ifl2);
290 }
291 
TEST(IntrusiveForwardList,SpliceAfter)292 TEST(IntrusiveForwardList, SpliceAfter) {
293   std::forward_list<int> ref1({ 3, 1, 2, 7, 4, 5, 4, 8, 7 });
294   std::forward_list<int> ref2;
295   std::vector<IFLTestValue> storage(ref1.begin(), ref1.end());
296   IntrusiveForwardList<IFLTestValue> ifl1(storage.begin(), storage.end());
297   IntrusiveForwardList<IFLTestValue> ifl2;
298   ASSERT_LISTS_EQUAL(ref1, ifl1);
299   ASSERT_LISTS_EQUAL(ref2, ifl2);
300 
301   // Move everything to ref2/ifl2.
302   ref2.splice_after(ref2.before_begin(), ref1);
303   ifl2.splice_after(ifl2.before_begin(), ifl1);
304   ASSERT_LISTS_EQUAL(ref1, ifl1);
305   ASSERT_LISTS_EQUAL(ref2, ifl2);
306 
307   // Move first element (3) to ref1/ifl1.
308   ref1.splice_after(ref1.before_begin(), ref2, ref2.before_begin());
309   ifl1.splice_after(ifl1.before_begin(), ifl2, ifl2.before_begin());
310   ASSERT_LISTS_EQUAL(ref1, ifl1);
311   ASSERT_LISTS_EQUAL(ref2, ifl2);
312 
313   // Move second element (2) to ref1/ifl1 after the first element (3).
314   ref1.splice_after(ref1.begin(), ref2, ref2.begin());
315   ifl1.splice_after(ifl1.begin(), ifl2, ifl2.begin());
316   ASSERT_LISTS_EQUAL(ref1, ifl1);
317   ASSERT_LISTS_EQUAL(ref2, ifl2);
318 
319   // Move everything from ref2/ifl2 between the 2 elements now in ref1/ifl1.
320   ref1.splice_after(ref1.begin(), ref2);
321   ifl1.splice_after(ifl1.begin(), ifl2);
322   ASSERT_LISTS_EQUAL(ref1, ifl1);
323   ASSERT_LISTS_EQUAL(ref2, ifl2);
324 
325   std::forward_list<int> check({ 3, 1, 7, 4, 5, 4, 8, 7, 2 });
326   ASSERT_LISTS_EQUAL(check, ifl1);
327   ASSERT_TRUE(ifl2.empty());
328 
329   // Empty splice_after().
330   ref2.splice_after(
331       ref2.before_begin(), ref1, ref1.before_begin(), ref1.begin());
332   ifl2.splice_after(ifl2.before_begin(), ifl1, ifl1.before_begin(), ifl1.begin());
333   ASSERT_LISTS_EQUAL(ref1, ifl1);
334   ASSERT_LISTS_EQUAL(ref2, ifl2);
335 
336   // Move { 1, 7 } to ref2/ifl2.
337   auto ref_it = ref1.begin();
338   auto ifl_it = ifl1.begin();
339   std::advance(ref_it, 3);
340   std::advance(ifl_it, 3);
341   ref2.splice_after(ref2.before_begin(), ref1, ref1.begin(), ref_it);
342   ifl2.splice_after(ifl2.before_begin(), ifl1, ifl1.begin(), ifl_it);
343   ASSERT_LISTS_EQUAL(ref1, ifl1);
344   ASSERT_LISTS_EQUAL(ref2, ifl2);
345 
346   // Move { 8, 7, 2 } to the beginning of ref1/ifl1.
347   ref_it = ref1.begin();
348   ifl_it = ifl1.begin();
349   std::advance(ref_it, 3);
350   std::advance(ifl_it, 3);
351   ref1.splice_after(ref1.before_begin(), ref1, ref_it, ref1.end());
352   ifl1.splice_after(ifl1.before_begin(), ifl1, ifl_it, ifl1.end());
353   ASSERT_LISTS_EQUAL(ref1, ifl1);
354 
355   check.assign({ 8, 7, 2, 3, 4, 5, 4 });
356   ASSERT_LISTS_EQUAL(check, ifl1);
357   check.assign({ 1, 7 });
358   ASSERT_LISTS_EQUAL(check, ifl2);
359 
360   // Move all but the first element to ref2/ifl2.
361   ref_it = ref2.begin();
362   ifl_it = ifl2.begin();
363   std::advance(ref_it, 1);
364   std::advance(ifl_it, 1);
365   ref2.splice_after(ref_it, ref1, ref1.begin(), ref1.end());
366   ifl2.splice_after(ifl_it, ifl1, ifl1.begin(), ifl1.end());
367   ASSERT_LISTS_EQUAL(ref1, ifl1);
368   ASSERT_LISTS_EQUAL(ref2, ifl2);
369 
370   check.assign({8});
371   ASSERT_LISTS_EQUAL(check, ifl1);
372 
373   // Move the first element of ref1/ifl1 to the beginning of ref1/ifl1 (do nothing).
374   ref1.splice_after(ref1.before_begin(), ref1, ref1.before_begin());
375   ifl1.splice_after(ifl1.before_begin(), ifl1, ifl1.before_begin());
376   ASSERT_LISTS_EQUAL(ref1, ifl1);
377   ASSERT_LISTS_EQUAL(check, ifl1);
378 
379   // Move the first element of ref2/ifl2 after itself (do nothing).
380   ref1.splice_after(ref1.begin(), ref1, ref1.before_begin());
381   ifl1.splice_after(ifl1.begin(), ifl1, ifl1.before_begin());
382   ASSERT_LISTS_EQUAL(ref1, ifl1);
383   ASSERT_LISTS_EQUAL(check, ifl1);
384 
385   check.assign({ 1, 7, 7, 2, 3, 4, 5, 4 });
386   ASSERT_LISTS_EQUAL(check, ifl2);
387 
388   // Move the first element of ref2/ifl2 to the beginning of ref2/ifl2 (do nothing).
389   ref2.splice_after(ref2.before_begin(), ref2, ref2.before_begin());
390   ifl2.splice_after(ifl2.before_begin(), ifl2, ifl2.before_begin());
391   ASSERT_LISTS_EQUAL(ref2, ifl2);
392   ASSERT_LISTS_EQUAL(check, ifl2);
393 
394   // Move the first element of ref2/ifl2 after itself (do nothing).
395   ref2.splice_after(ref2.begin(), ref2, ref2.before_begin());
396   ifl2.splice_after(ifl2.begin(), ifl2, ifl2.before_begin());
397   ASSERT_LISTS_EQUAL(ref2, ifl2);
398   ASSERT_LISTS_EQUAL(check, ifl2);
399 }
400 
TEST(IntrusiveForwardList,Remove)401 TEST(IntrusiveForwardList, Remove) {
402   std::forward_list<int> ref({ 3, 1, 2, 7, 4, 5, 4, 8, 7 });
403   std::vector<IFLTestValue> storage(ref.begin(), ref.end());
404   IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
405   ASSERT_LISTS_EQUAL(ref, ifl);
406   ref.remove(1);
407   ifl.remove(1);
408   ASSERT_LISTS_EQUAL(ref, ifl);
409   ref.remove(4);
410   ifl.remove(4);
411   ASSERT_LISTS_EQUAL(ref, ifl);
412   auto odd = [](IFLTestValue value) { return (value.value & 1) != 0; };  // NOLINT(readability/braces)
413   ref.remove_if(odd);
414   ifl.remove_if(odd);
415   ASSERT_LISTS_EQUAL(ref, ifl);
416   auto all = [](IFLTestValue value ATTRIBUTE_UNUSED) { return true; };  // NOLINT(readability/braces)
417   ref.remove_if(all);
418   ifl.remove_if(all);
419   ASSERT_LISTS_EQUAL(ref, ifl);
420 }
421 
TEST(IntrusiveForwardList,Unique)422 TEST(IntrusiveForwardList, Unique) {
423   std::forward_list<int> ref({ 3, 1, 1, 2, 3, 3, 7, 7, 4, 4, 5, 7 });
424   std::vector<IFLTestValue> storage(ref.begin(), ref.end());
425   IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
426   ASSERT_LISTS_EQUAL(ref, ifl);
427   ref.unique();
428   ifl.unique();
429   ASSERT_LISTS_EQUAL(ref, ifl);
430   std::forward_list<int> check({ 3, 1, 2, 3, 7, 4, 5, 7 });
431   ASSERT_LISTS_EQUAL(check, ifl);
432 
433   auto bin_pred = [](IFLTestValue lhs, IFLTestValue rhs) {
434     return (lhs.value & ~1) == (rhs.value & ~1);
435   };
436   ref.unique(bin_pred);
437   ifl.unique(bin_pred);
438   ASSERT_LISTS_EQUAL(ref, ifl);
439   check.assign({ 3, 1, 2, 7, 4, 7 });
440   ASSERT_LISTS_EQUAL(check, ifl);
441 }
442 
TEST(IntrusiveForwardList,Merge)443 TEST(IntrusiveForwardList, Merge) {
444   std::forward_list<int> ref1({ 1, 4, 8, 8, 12 });
445   std::vector<IFLTestValue> storage1(ref1.begin(), ref1.end());
446   IntrusiveForwardList<IFLTestValue> ifl1(storage1.begin(), storage1.end());
447   std::forward_list<int> ref2({ 3, 5, 6, 7, 9 });
448   std::vector<IFLTestValue> storage2(ref2.begin(), ref2.end());
449   IntrusiveForwardList<IFLTestValue> ifl2(storage2.begin(), storage2.end());
450   ASSERT_LISTS_EQUAL(ref1, ifl1);
451   ASSERT_LISTS_EQUAL(ref2, ifl2);
452   CHECK(std::is_sorted(ref1.begin(), ref1.end()));
453   CHECK(std::is_sorted(ref2.begin(), ref2.end()));
454   ref1.merge(ref2);
455   ifl1.merge(ifl2);
456   ASSERT_LISTS_EQUAL(ref1, ifl1);
457   ASSERT_LISTS_EQUAL(ref2, ifl2);
458   CHECK(ref2.empty());
459   std::forward_list<int> check({ 1, 3, 4, 5, 6, 7, 8, 8, 9, 12 });
460   ASSERT_LISTS_EQUAL(check, ifl1);
461 }
462 
TEST(IntrusiveForwardList,Sort1)463 TEST(IntrusiveForwardList, Sort1) {
464   std::forward_list<int> ref({ 2, 9, 8, 3, 7, 4, 1, 5, 3, 0 });
465   std::vector<IFLTestValue> storage(ref.begin(), ref.end());
466   IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
467   ASSERT_LISTS_EQUAL(ref, ifl);
468   CHECK(!std::is_sorted(ref.begin(), ref.end()));
469   ref.sort();
470   ifl.sort();
471   ASSERT_LISTS_EQUAL(ref, ifl);
472   std::forward_list<int> check({ 0, 1, 2, 3, 3, 4, 5, 7, 8, 9 });
473   ASSERT_LISTS_EQUAL(check, ifl);
474 }
475 
TEST(IntrusiveForwardList,Sort2)476 TEST(IntrusiveForwardList, Sort2) {
477   std::forward_list<int> ref({ 2, 9, 8, 3, 7, 4, 1, 5, 3, 0 });
478   std::vector<IFLTestValue> storage(ref.begin(), ref.end());
479   IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
480   ASSERT_LISTS_EQUAL(ref, ifl);
481   auto cmp = [](IFLTestValue lhs, IFLTestValue rhs) {
482     return (lhs.value & ~1) < (rhs.value & ~1);
483   };
484   CHECK(!std::is_sorted(ref.begin(), ref.end(), cmp));
485   ref.sort(cmp);
486   ifl.sort(cmp);
487   ASSERT_LISTS_EQUAL(ref, ifl);
488   std::forward_list<int> check({ 1, 0, 2, 3, 3, 4, 5, 7, 9, 8 });
489   ASSERT_LISTS_EQUAL(check, ifl);
490 }
491 
TEST(IntrusiveForwardList,Reverse)492 TEST(IntrusiveForwardList, Reverse) {
493   std::forward_list<int> ref({ 8, 3, 5, 4, 1, 3 });
494   std::vector<IFLTestValue> storage(ref.begin(), ref.end());
495   IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
496   ASSERT_LISTS_EQUAL(ref, ifl);
497   CHECK(!std::is_sorted(ref.begin(), ref.end()));
498   ref.reverse();
499   ifl.reverse();
500   ASSERT_LISTS_EQUAL(ref, ifl);
501   std::forward_list<int> check({ 3, 1, 4, 5, 3, 8 });
502   ASSERT_LISTS_EQUAL(check, ifl);
503 }
504 
505 }  // namespace art
506