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