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 24namespace art { 25 26struct IFLTestValue { 27 // Deliberately not explicit. 28 IFLTestValue(int v) : hook(), value(v) { } // NOLINT(runtime/explicit) 29 30 IntrusiveForwardListHook hook; 31 int value; 32}; 33 34bool operator==(const IFLTestValue& lhs, const IFLTestValue& rhs) { 35 return lhs.value == rhs.value; 36} 37 38bool 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 50TEST(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 58TEST(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 75TEST(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 82TEST(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 94TEST(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 117TEST(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 152TEST(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 178TEST(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 233TEST(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 265TEST(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 292TEST(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 401TEST(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 422TEST(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 443TEST(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 463TEST(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 476TEST(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 492TEST(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