fixed_array_test.cc (26414B)
1 // Copyright 2019 The Abseil Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include "absl/container/fixed_array.h" 16 17 #include <stdio.h> 18 19 #include <cstring> 20 #include <forward_list> 21 #include <list> 22 #include <memory> 23 #include <numeric> 24 #include <scoped_allocator> 25 #include <stdexcept> 26 #include <string> 27 #include <utility> 28 #include <vector> 29 30 #include "gmock/gmock.h" 31 #include "gtest/gtest.h" 32 #include "absl/base/config.h" 33 #include "absl/base/internal/exception_testing.h" 34 #include "absl/base/internal/iterator_traits_test_helper.h" 35 #include "absl/base/options.h" 36 #include "absl/container/internal/test_allocator.h" 37 #include "absl/hash/hash_testing.h" 38 #include "absl/memory/memory.h" 39 40 using ::testing::ElementsAreArray; 41 42 namespace { 43 44 // Helper routine to determine if a absl::FixedArray used stack allocation. 45 template <typename ArrayType> 46 static bool IsOnStack(const ArrayType& a) { 47 return a.size() <= ArrayType::inline_elements; 48 } 49 50 class ConstructionTester { 51 public: 52 ConstructionTester() : self_ptr_(this), value_(0) { constructions++; } 53 ~ConstructionTester() { 54 assert(self_ptr_ == this); 55 self_ptr_ = nullptr; 56 destructions++; 57 } 58 59 // These are incremented as elements are constructed and destructed so we can 60 // be sure all elements are properly cleaned up. 61 static int constructions; 62 static int destructions; 63 64 void CheckConstructed() { assert(self_ptr_ == this); } 65 66 void set(int value) { value_ = value; } 67 int get() { return value_; } 68 69 private: 70 // self_ptr_ should always point to 'this' -- that's how we can be sure the 71 // constructor has been called. 72 ConstructionTester* self_ptr_; 73 int value_; 74 }; 75 76 int ConstructionTester::constructions = 0; 77 int ConstructionTester::destructions = 0; 78 79 // ThreeInts will initialize its three ints to the value stored in 80 // ThreeInts::counter. The constructor increments counter so that each object 81 // in an array of ThreeInts will have different values. 82 class ThreeInts { 83 public: 84 ThreeInts() { 85 x_ = counter; 86 y_ = counter; 87 z_ = counter; 88 ++counter; 89 } 90 91 static int counter; 92 93 int x_, y_, z_; 94 }; 95 96 int ThreeInts::counter = 0; 97 98 TEST(FixedArrayTest, CopyCtor) { 99 absl::FixedArray<int, 10> on_stack(5); 100 std::iota(on_stack.begin(), on_stack.end(), 0); 101 absl::FixedArray<int, 10> stack_copy = on_stack; 102 EXPECT_THAT(stack_copy, ElementsAreArray(on_stack)); 103 EXPECT_TRUE(IsOnStack(stack_copy)); 104 105 absl::FixedArray<int, 10> allocated(15); 106 std::iota(allocated.begin(), allocated.end(), 0); 107 absl::FixedArray<int, 10> alloced_copy = allocated; 108 EXPECT_THAT(alloced_copy, ElementsAreArray(allocated)); 109 EXPECT_FALSE(IsOnStack(alloced_copy)); 110 } 111 112 TEST(FixedArrayTest, MoveCtor) { 113 absl::FixedArray<std::unique_ptr<int>, 10> on_stack(5); 114 for (int i = 0; i < 5; ++i) { 115 on_stack[i] = absl::make_unique<int>(i); 116 } 117 118 absl::FixedArray<std::unique_ptr<int>, 10> stack_copy = std::move(on_stack); 119 for (int i = 0; i < 5; ++i) EXPECT_EQ(*(stack_copy[i]), i); 120 EXPECT_EQ(stack_copy.size(), on_stack.size()); 121 122 absl::FixedArray<std::unique_ptr<int>, 10> allocated(15); 123 for (int i = 0; i < 15; ++i) { 124 allocated[i] = absl::make_unique<int>(i); 125 } 126 127 absl::FixedArray<std::unique_ptr<int>, 10> alloced_copy = 128 std::move(allocated); 129 for (int i = 0; i < 15; ++i) EXPECT_EQ(*(alloced_copy[i]), i); 130 EXPECT_EQ(allocated.size(), alloced_copy.size()); 131 } 132 133 TEST(FixedArrayTest, SmallObjects) { 134 // Small object arrays 135 { 136 // Short arrays should be on the stack 137 absl::FixedArray<int> array(4); 138 EXPECT_TRUE(IsOnStack(array)); 139 } 140 141 { 142 // Large arrays should be on the heap 143 absl::FixedArray<int> array(1048576); 144 EXPECT_FALSE(IsOnStack(array)); 145 } 146 147 { 148 // Arrays of <= default size should be on the stack 149 absl::FixedArray<int, 100> array(100); 150 EXPECT_TRUE(IsOnStack(array)); 151 } 152 153 { 154 // Arrays of > default size should be on the heap 155 absl::FixedArray<int, 100> array(101); 156 EXPECT_FALSE(IsOnStack(array)); 157 } 158 159 { 160 // Arrays with different size elements should use approximately 161 // same amount of stack space 162 absl::FixedArray<int> array1(0); 163 absl::FixedArray<char> array2(0); 164 EXPECT_LE(sizeof(array1), sizeof(array2) + 100); 165 EXPECT_LE(sizeof(array2), sizeof(array1) + 100); 166 } 167 168 { 169 // Ensure that vectors are properly constructed inside a fixed array. 170 absl::FixedArray<std::vector<int>> array(2); 171 EXPECT_EQ(0, array[0].size()); 172 EXPECT_EQ(0, array[1].size()); 173 } 174 175 { 176 // Regardless of absl::FixedArray implementation, check that a type with a 177 // low alignment requirement and a non power-of-two size is initialized 178 // correctly. 179 ThreeInts::counter = 1; 180 absl::FixedArray<ThreeInts> array(2); 181 EXPECT_EQ(1, array[0].x_); 182 EXPECT_EQ(1, array[0].y_); 183 EXPECT_EQ(1, array[0].z_); 184 EXPECT_EQ(2, array[1].x_); 185 EXPECT_EQ(2, array[1].y_); 186 EXPECT_EQ(2, array[1].z_); 187 } 188 } 189 190 TEST(FixedArrayTest, AtThrows) { 191 absl::FixedArray<int> a = {1, 2, 3}; 192 EXPECT_EQ(a.at(2), 3); 193 ABSL_BASE_INTERNAL_EXPECT_FAIL(a.at(3), std::out_of_range, 194 "failed bounds check"); 195 } 196 197 TEST(FixedArrayTest, Hardened) { 198 #if !defined(NDEBUG) || ABSL_OPTION_HARDENED 199 absl::FixedArray<int> a = {1, 2, 3}; 200 EXPECT_EQ(a[2], 3); 201 EXPECT_DEATH_IF_SUPPORTED(a[3], ""); 202 EXPECT_DEATH_IF_SUPPORTED(a[-1], ""); 203 204 absl::FixedArray<int> empty(0); 205 EXPECT_DEATH_IF_SUPPORTED(empty[0], ""); 206 EXPECT_DEATH_IF_SUPPORTED(empty[-1], ""); 207 EXPECT_DEATH_IF_SUPPORTED(empty.front(), ""); 208 EXPECT_DEATH_IF_SUPPORTED(empty.back(), ""); 209 #endif 210 } 211 212 TEST(FixedArrayRelationalsTest, EqualArrays) { 213 for (int i = 0; i < 10; ++i) { 214 absl::FixedArray<int, 5> a1(i); 215 std::iota(a1.begin(), a1.end(), 0); 216 absl::FixedArray<int, 5> a2(a1.begin(), a1.end()); 217 218 EXPECT_TRUE(a1 == a2); 219 EXPECT_FALSE(a1 != a2); 220 EXPECT_TRUE(a2 == a1); 221 EXPECT_FALSE(a2 != a1); 222 EXPECT_FALSE(a1 < a2); 223 EXPECT_FALSE(a1 > a2); 224 EXPECT_FALSE(a2 < a1); 225 EXPECT_FALSE(a2 > a1); 226 EXPECT_TRUE(a1 <= a2); 227 EXPECT_TRUE(a1 >= a2); 228 EXPECT_TRUE(a2 <= a1); 229 EXPECT_TRUE(a2 >= a1); 230 } 231 } 232 233 TEST(FixedArrayRelationalsTest, UnequalArrays) { 234 for (int i = 1; i < 10; ++i) { 235 absl::FixedArray<int, 5> a1(i); 236 std::iota(a1.begin(), a1.end(), 0); 237 absl::FixedArray<int, 5> a2(a1.begin(), a1.end()); 238 --a2[i / 2]; 239 240 EXPECT_FALSE(a1 == a2); 241 EXPECT_TRUE(a1 != a2); 242 EXPECT_FALSE(a2 == a1); 243 EXPECT_TRUE(a2 != a1); 244 EXPECT_FALSE(a1 < a2); 245 EXPECT_TRUE(a1 > a2); 246 EXPECT_TRUE(a2 < a1); 247 EXPECT_FALSE(a2 > a1); 248 EXPECT_FALSE(a1 <= a2); 249 EXPECT_TRUE(a1 >= a2); 250 EXPECT_TRUE(a2 <= a1); 251 EXPECT_FALSE(a2 >= a1); 252 } 253 } 254 255 template <int stack_elements> 256 static void TestArray(int n) { 257 SCOPED_TRACE(n); 258 SCOPED_TRACE(stack_elements); 259 ConstructionTester::constructions = 0; 260 ConstructionTester::destructions = 0; 261 { 262 absl::FixedArray<ConstructionTester, stack_elements> array(n); 263 264 EXPECT_THAT(array.size(), n); 265 EXPECT_THAT(array.memsize(), sizeof(ConstructionTester) * n); 266 EXPECT_THAT(array.begin() + n, array.end()); 267 268 // Check that all elements were constructed 269 for (int i = 0; i < n; i++) { 270 array[i].CheckConstructed(); 271 } 272 // Check that no other elements were constructed 273 EXPECT_THAT(ConstructionTester::constructions, n); 274 275 // Test operator[] 276 for (int i = 0; i < n; i++) { 277 array[i].set(i); 278 } 279 for (int i = 0; i < n; i++) { 280 EXPECT_THAT(array[i].get(), i); 281 EXPECT_THAT(array.data()[i].get(), i); 282 } 283 284 // Test data() 285 for (int i = 0; i < n; i++) { 286 array.data()[i].set(i + 1); 287 } 288 for (int i = 0; i < n; i++) { 289 EXPECT_THAT(array[i].get(), i + 1); 290 EXPECT_THAT(array.data()[i].get(), i + 1); 291 } 292 } // Close scope containing 'array'. 293 294 // Check that all constructed elements were destructed. 295 EXPECT_EQ(ConstructionTester::constructions, 296 ConstructionTester::destructions); 297 } 298 299 template <int elements_per_inner_array, int inline_elements> 300 static void TestArrayOfArrays(int n) { 301 SCOPED_TRACE(n); 302 SCOPED_TRACE(inline_elements); 303 SCOPED_TRACE(elements_per_inner_array); 304 ConstructionTester::constructions = 0; 305 ConstructionTester::destructions = 0; 306 { 307 using InnerArray = ConstructionTester[elements_per_inner_array]; 308 // Heap-allocate the FixedArray to avoid blowing the stack frame. 309 auto array_ptr = 310 absl::make_unique<absl::FixedArray<InnerArray, inline_elements>>(n); 311 auto& array = *array_ptr; 312 313 ASSERT_EQ(array.size(), n); 314 ASSERT_EQ(array.memsize(), 315 sizeof(ConstructionTester) * elements_per_inner_array * n); 316 ASSERT_EQ(array.begin() + n, array.end()); 317 318 // Check that all elements were constructed 319 for (int i = 0; i < n; i++) { 320 for (int j = 0; j < elements_per_inner_array; j++) { 321 (array[i])[j].CheckConstructed(); 322 } 323 } 324 // Check that no other elements were constructed 325 ASSERT_EQ(ConstructionTester::constructions, n * elements_per_inner_array); 326 327 // Test operator[] 328 for (int i = 0; i < n; i++) { 329 for (int j = 0; j < elements_per_inner_array; j++) { 330 (array[i])[j].set(i * elements_per_inner_array + j); 331 } 332 } 333 for (int i = 0; i < n; i++) { 334 for (int j = 0; j < elements_per_inner_array; j++) { 335 ASSERT_EQ((array[i])[j].get(), i * elements_per_inner_array + j); 336 ASSERT_EQ((array.data()[i])[j].get(), i * elements_per_inner_array + j); 337 } 338 } 339 340 // Test data() 341 for (int i = 0; i < n; i++) { 342 for (int j = 0; j < elements_per_inner_array; j++) { 343 (array.data()[i])[j].set((i + 1) * elements_per_inner_array + j); 344 } 345 } 346 for (int i = 0; i < n; i++) { 347 for (int j = 0; j < elements_per_inner_array; j++) { 348 ASSERT_EQ((array[i])[j].get(), (i + 1) * elements_per_inner_array + j); 349 ASSERT_EQ((array.data()[i])[j].get(), 350 (i + 1) * elements_per_inner_array + j); 351 } 352 } 353 } // Close scope containing 'array'. 354 355 // Check that all constructed elements were destructed. 356 EXPECT_EQ(ConstructionTester::constructions, 357 ConstructionTester::destructions); 358 } 359 360 TEST(IteratorConstructorTest, NonInline) { 361 int const kInput[] = {2, 3, 5, 7, 11, 13, 17}; 362 absl::FixedArray<int, ABSL_ARRAYSIZE(kInput) - 1> const fixed( 363 kInput, kInput + ABSL_ARRAYSIZE(kInput)); 364 ASSERT_EQ(ABSL_ARRAYSIZE(kInput), fixed.size()); 365 for (size_t i = 0; i < ABSL_ARRAYSIZE(kInput); ++i) { 366 ASSERT_EQ(kInput[i], fixed[i]); 367 } 368 } 369 370 TEST(IteratorConstructorTest, Inline) { 371 int const kInput[] = {2, 3, 5, 7, 11, 13, 17}; 372 absl::FixedArray<int, ABSL_ARRAYSIZE(kInput)> const fixed( 373 kInput, kInput + ABSL_ARRAYSIZE(kInput)); 374 ASSERT_EQ(ABSL_ARRAYSIZE(kInput), fixed.size()); 375 for (size_t i = 0; i < ABSL_ARRAYSIZE(kInput); ++i) { 376 ASSERT_EQ(kInput[i], fixed[i]); 377 } 378 } 379 380 TEST(IteratorConstructorTest, NonPod) { 381 char const* kInput[] = {"red", "orange", "yellow", "green", 382 "blue", "indigo", "violet"}; 383 absl::FixedArray<std::string> const fixed(kInput, 384 kInput + ABSL_ARRAYSIZE(kInput)); 385 ASSERT_EQ(ABSL_ARRAYSIZE(kInput), fixed.size()); 386 for (size_t i = 0; i < ABSL_ARRAYSIZE(kInput); ++i) { 387 ASSERT_EQ(kInput[i], fixed[i]); 388 } 389 } 390 391 TEST(IteratorConstructorTest, FromEmptyVector) { 392 std::vector<int> const empty; 393 absl::FixedArray<int> const fixed(empty.begin(), empty.end()); 394 EXPECT_EQ(0, fixed.size()); 395 EXPECT_EQ(empty.size(), fixed.size()); 396 } 397 398 TEST(IteratorConstructorTest, FromNonEmptyVector) { 399 int const kInput[] = {2, 3, 5, 7, 11, 13, 17}; 400 std::vector<int> const items(kInput, kInput + ABSL_ARRAYSIZE(kInput)); 401 absl::FixedArray<int> const fixed(items.begin(), items.end()); 402 ASSERT_EQ(items.size(), fixed.size()); 403 for (size_t i = 0; i < items.size(); ++i) { 404 ASSERT_EQ(items[i], fixed[i]); 405 } 406 } 407 408 TEST(IteratorConstructorTest, FromBidirectionalIteratorRange) { 409 int const kInput[] = {2, 3, 5, 7, 11, 13, 17}; 410 std::list<int> const items(kInput, kInput + ABSL_ARRAYSIZE(kInput)); 411 absl::FixedArray<int> const fixed(items.begin(), items.end()); 412 EXPECT_THAT(fixed, testing::ElementsAreArray(kInput)); 413 } 414 415 TEST(IteratorConstructorTest, FromCpp20ForwardIteratorRange) { 416 std::forward_list<int> const kUnzippedInput = {2, 3, 5, 7, 11, 13, 17}; 417 absl::base_internal::Cpp20ForwardZipIterator< 418 std::forward_list<int>::const_iterator> const 419 begin(std::begin(kUnzippedInput), std::begin(kUnzippedInput)); 420 absl::base_internal:: 421 Cpp20ForwardZipIterator<std::forward_list<int>::const_iterator> const end( 422 std::end(kUnzippedInput), std::end(kUnzippedInput)); 423 424 std::forward_list<std::pair<int, int>> const items(begin, end); 425 absl::FixedArray<std::pair<int, int>> const fixed(begin, end); 426 EXPECT_THAT(fixed, testing::ElementsAreArray(items)); 427 } 428 429 TEST(InitListConstructorTest, InitListConstruction) { 430 absl::FixedArray<int> fixed = {1, 2, 3}; 431 EXPECT_THAT(fixed, testing::ElementsAreArray({1, 2, 3})); 432 } 433 434 TEST(FillConstructorTest, NonEmptyArrays) { 435 absl::FixedArray<int> stack_array(4, 1); 436 EXPECT_THAT(stack_array, testing::ElementsAreArray({1, 1, 1, 1})); 437 438 absl::FixedArray<int, 0> heap_array(4, 1); 439 EXPECT_THAT(heap_array, testing::ElementsAreArray({1, 1, 1, 1})); 440 } 441 442 TEST(FillConstructorTest, EmptyArray) { 443 absl::FixedArray<int> empty_fill(0, 1); 444 absl::FixedArray<int> empty_size(0); 445 EXPECT_EQ(empty_fill, empty_size); 446 } 447 448 TEST(FillConstructorTest, NotTriviallyCopyable) { 449 std::string str = "abcd"; 450 absl::FixedArray<std::string> strings = {str, str, str, str}; 451 452 absl::FixedArray<std::string> array(4, str); 453 EXPECT_EQ(array, strings); 454 } 455 456 TEST(FillConstructorTest, Disambiguation) { 457 absl::FixedArray<size_t> a(1, 2); 458 EXPECT_THAT(a, testing::ElementsAre(2)); 459 } 460 461 TEST(FixedArrayTest, ManySizedArrays) { 462 std::vector<int> sizes; 463 for (int i = 1; i < 100; i++) sizes.push_back(i); 464 for (int i = 100; i <= 1000; i += 100) sizes.push_back(i); 465 for (int n : sizes) { 466 TestArray<0>(n); 467 TestArray<1>(n); 468 TestArray<64>(n); 469 TestArray<1000>(n); 470 } 471 } 472 473 TEST(FixedArrayTest, ManySizedArraysOfArraysOf1) { 474 for (int n = 1; n < 1000; n++) { 475 ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 0>(n))); 476 ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 1>(n))); 477 ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 64>(n))); 478 ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 1000>(n))); 479 } 480 } 481 482 TEST(FixedArrayTest, ManySizedArraysOfArraysOf2) { 483 for (int n = 1; n < 1000; n++) { 484 TestArrayOfArrays<2, 0>(n); 485 TestArrayOfArrays<2, 1>(n); 486 TestArrayOfArrays<2, 64>(n); 487 TestArrayOfArrays<2, 1000>(n); 488 } 489 } 490 491 // If value_type is put inside of a struct container, 492 // we might evoke this error in a hardened build unless data() is carefully 493 // written, so check on that. 494 // error: call to int __builtin___sprintf_chk(etc...) 495 // will always overflow destination buffer [-Werror] 496 TEST(FixedArrayTest, AvoidParanoidDiagnostics) { 497 absl::FixedArray<char, 32> buf(32); 498 sprintf(buf.data(), "foo"); // NOLINT(runtime/printf) 499 } 500 501 TEST(FixedArrayTest, TooBigInlinedSpace) { 502 struct TooBig { 503 char c[1 << 20]; 504 }; // too big for even one on the stack 505 506 // Simulate the data members of absl::FixedArray, a pointer and a size_t. 507 struct Data { 508 TooBig* p; 509 size_t size; 510 }; 511 512 // Make sure TooBig objects are not inlined for 0 or default size. 513 static_assert(sizeof(absl::FixedArray<TooBig, 0>) == sizeof(Data), 514 "0-sized absl::FixedArray should have same size as Data."); 515 static_assert(alignof(absl::FixedArray<TooBig, 0>) == alignof(Data), 516 "0-sized absl::FixedArray should have same alignment as Data."); 517 static_assert(sizeof(absl::FixedArray<TooBig>) == sizeof(Data), 518 "default-sized absl::FixedArray should have same size as Data"); 519 static_assert( 520 alignof(absl::FixedArray<TooBig>) == alignof(Data), 521 "default-sized absl::FixedArray should have same alignment as Data."); 522 } 523 524 // PickyDelete EXPECTs its class-scope deallocation funcs are unused. 525 struct PickyDelete { 526 PickyDelete() {} 527 ~PickyDelete() {} 528 void operator delete(void* p) { 529 EXPECT_TRUE(false) << __FUNCTION__; 530 ::operator delete(p); 531 } 532 void operator delete[](void* p) { 533 EXPECT_TRUE(false) << __FUNCTION__; 534 ::operator delete[](p); 535 } 536 }; 537 538 TEST(FixedArrayTest, UsesGlobalAlloc) { 539 absl::FixedArray<PickyDelete, 0> a(5); 540 EXPECT_EQ(a.size(), 5); 541 } 542 543 TEST(FixedArrayTest, Data) { 544 static const int kInput[] = {2, 3, 5, 7, 11, 13, 17}; 545 absl::FixedArray<int> fa(std::begin(kInput), std::end(kInput)); 546 EXPECT_EQ(fa.data(), &*fa.begin()); 547 EXPECT_EQ(fa.data(), &fa[0]); 548 549 const absl::FixedArray<int>& cfa = fa; 550 EXPECT_EQ(cfa.data(), &*cfa.begin()); 551 EXPECT_EQ(cfa.data(), &cfa[0]); 552 } 553 554 TEST(FixedArrayTest, Empty) { 555 absl::FixedArray<int> empty(0); 556 absl::FixedArray<int> inline_filled(1); 557 absl::FixedArray<int, 0> heap_filled(1); 558 EXPECT_TRUE(empty.empty()); 559 EXPECT_FALSE(inline_filled.empty()); 560 EXPECT_FALSE(heap_filled.empty()); 561 } 562 563 TEST(FixedArrayTest, FrontAndBack) { 564 absl::FixedArray<int, 3 * sizeof(int)> inlined = {1, 2, 3}; 565 EXPECT_EQ(inlined.front(), 1); 566 EXPECT_EQ(inlined.back(), 3); 567 568 absl::FixedArray<int, 0> allocated = {1, 2, 3}; 569 EXPECT_EQ(allocated.front(), 1); 570 EXPECT_EQ(allocated.back(), 3); 571 572 absl::FixedArray<int> one_element = {1}; 573 EXPECT_EQ(one_element.front(), one_element.back()); 574 } 575 576 TEST(FixedArrayTest, ReverseIteratorInlined) { 577 absl::FixedArray<int, 5 * sizeof(int)> a = {0, 1, 2, 3, 4}; 578 579 int counter = 5; 580 for (absl::FixedArray<int>::reverse_iterator iter = a.rbegin(); 581 iter != a.rend(); ++iter) { 582 counter--; 583 EXPECT_EQ(counter, *iter); 584 } 585 EXPECT_EQ(counter, 0); 586 587 counter = 5; 588 for (absl::FixedArray<int>::const_reverse_iterator iter = a.rbegin(); 589 iter != a.rend(); ++iter) { 590 counter--; 591 EXPECT_EQ(counter, *iter); 592 } 593 EXPECT_EQ(counter, 0); 594 595 counter = 5; 596 for (auto iter = a.crbegin(); iter != a.crend(); ++iter) { 597 counter--; 598 EXPECT_EQ(counter, *iter); 599 } 600 EXPECT_EQ(counter, 0); 601 } 602 603 TEST(FixedArrayTest, ReverseIteratorAllocated) { 604 absl::FixedArray<int, 0> a = {0, 1, 2, 3, 4}; 605 606 int counter = 5; 607 for (absl::FixedArray<int>::reverse_iterator iter = a.rbegin(); 608 iter != a.rend(); ++iter) { 609 counter--; 610 EXPECT_EQ(counter, *iter); 611 } 612 EXPECT_EQ(counter, 0); 613 614 counter = 5; 615 for (absl::FixedArray<int>::const_reverse_iterator iter = a.rbegin(); 616 iter != a.rend(); ++iter) { 617 counter--; 618 EXPECT_EQ(counter, *iter); 619 } 620 EXPECT_EQ(counter, 0); 621 622 counter = 5; 623 for (auto iter = a.crbegin(); iter != a.crend(); ++iter) { 624 counter--; 625 EXPECT_EQ(counter, *iter); 626 } 627 EXPECT_EQ(counter, 0); 628 } 629 630 TEST(FixedArrayTest, Fill) { 631 absl::FixedArray<int, 5 * sizeof(int)> inlined(5); 632 int fill_val = 42; 633 inlined.fill(fill_val); 634 for (int i : inlined) EXPECT_EQ(i, fill_val); 635 636 absl::FixedArray<int, 0> allocated(5); 637 allocated.fill(fill_val); 638 for (int i : allocated) EXPECT_EQ(i, fill_val); 639 640 // It doesn't do anything, just make sure this compiles. 641 absl::FixedArray<int> empty(0); 642 empty.fill(fill_val); 643 } 644 645 #ifndef __GNUC__ 646 TEST(FixedArrayTest, DefaultCtorDoesNotValueInit) { 647 using T = char; 648 constexpr auto capacity = 10; 649 using FixedArrType = absl::FixedArray<T, capacity>; 650 constexpr auto scrubbed_bits = 0x95; 651 constexpr auto length = capacity / 2; 652 653 alignas(FixedArrType) unsigned char buff[sizeof(FixedArrType)]; 654 std::memset(std::addressof(buff), scrubbed_bits, sizeof(FixedArrType)); 655 656 FixedArrType* arr = 657 ::new (static_cast<void*>(std::addressof(buff))) FixedArrType(length); 658 EXPECT_THAT(*arr, testing::Each(scrubbed_bits)); 659 arr->~FixedArrType(); 660 } 661 #endif // __GNUC__ 662 663 TEST(AllocatorSupportTest, CountInlineAllocations) { 664 constexpr size_t inlined_size = 4; 665 using Alloc = absl::container_internal::CountingAllocator<int>; 666 using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>; 667 668 int64_t allocated = 0; 669 int64_t active_instances = 0; 670 671 { 672 const int ia[] = {0, 1, 2, 3, 4, 5, 6, 7}; 673 674 Alloc alloc(&allocated, &active_instances); 675 676 AllocFxdArr arr(ia, ia + inlined_size, alloc); 677 static_cast<void>(arr); 678 } 679 680 EXPECT_EQ(allocated, 0); 681 EXPECT_EQ(active_instances, 0); 682 } 683 684 TEST(AllocatorSupportTest, CountOutoflineAllocations) { 685 constexpr size_t inlined_size = 4; 686 using Alloc = absl::container_internal::CountingAllocator<int>; 687 using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>; 688 689 int64_t allocated = 0; 690 int64_t active_instances = 0; 691 692 { 693 const int ia[] = {0, 1, 2, 3, 4, 5, 6, 7}; 694 Alloc alloc(&allocated, &active_instances); 695 696 AllocFxdArr arr(ia, ia + ABSL_ARRAYSIZE(ia), alloc); 697 698 EXPECT_EQ(allocated, arr.size() * sizeof(int)); 699 static_cast<void>(arr); 700 } 701 702 EXPECT_EQ(active_instances, 0); 703 } 704 705 TEST(AllocatorSupportTest, CountCopyInlineAllocations) { 706 constexpr size_t inlined_size = 4; 707 using Alloc = absl::container_internal::CountingAllocator<int>; 708 using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>; 709 710 int64_t allocated1 = 0; 711 int64_t allocated2 = 0; 712 int64_t active_instances = 0; 713 Alloc alloc(&allocated1, &active_instances); 714 Alloc alloc2(&allocated2, &active_instances); 715 716 { 717 int initial_value = 1; 718 719 AllocFxdArr arr1(inlined_size / 2, initial_value, alloc); 720 721 EXPECT_EQ(allocated1, 0); 722 723 AllocFxdArr arr2(arr1, alloc2); 724 725 EXPECT_EQ(allocated2, 0); 726 static_cast<void>(arr1); 727 static_cast<void>(arr2); 728 } 729 730 EXPECT_EQ(active_instances, 0); 731 } 732 733 TEST(AllocatorSupportTest, CountCopyOutoflineAllocations) { 734 constexpr size_t inlined_size = 4; 735 using Alloc = absl::container_internal::CountingAllocator<int>; 736 using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>; 737 738 int64_t allocated1 = 0; 739 int64_t allocated2 = 0; 740 int64_t active_instances = 0; 741 Alloc alloc(&allocated1, &active_instances); 742 Alloc alloc2(&allocated2, &active_instances); 743 744 { 745 int initial_value = 1; 746 747 AllocFxdArr arr1(inlined_size * 2, initial_value, alloc); 748 749 EXPECT_EQ(allocated1, arr1.size() * sizeof(int)); 750 751 AllocFxdArr arr2(arr1, alloc2); 752 753 EXPECT_EQ(allocated2, inlined_size * 2 * sizeof(int)); 754 static_cast<void>(arr1); 755 static_cast<void>(arr2); 756 } 757 758 EXPECT_EQ(active_instances, 0); 759 } 760 761 TEST(AllocatorSupportTest, SizeValAllocConstructor) { 762 using testing::AllOf; 763 using testing::Each; 764 using testing::SizeIs; 765 766 constexpr size_t inlined_size = 4; 767 using Alloc = absl::container_internal::CountingAllocator<int>; 768 using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>; 769 770 { 771 auto len = inlined_size / 2; 772 auto val = 0; 773 int64_t allocated = 0; 774 AllocFxdArr arr(len, val, Alloc(&allocated)); 775 776 EXPECT_EQ(allocated, 0); 777 EXPECT_THAT(arr, AllOf(SizeIs(len), Each(0))); 778 } 779 780 { 781 auto len = inlined_size * 2; 782 auto val = 0; 783 int64_t allocated = 0; 784 AllocFxdArr arr(len, val, Alloc(&allocated)); 785 786 EXPECT_EQ(allocated, len * sizeof(int)); 787 EXPECT_THAT(arr, AllOf(SizeIs(len), Each(0))); 788 } 789 } 790 791 TEST(AllocatorSupportTest, PropagatesStatefulAllocator) { 792 constexpr size_t inlined_size = 4; 793 using Alloc = absl::container_internal::CountingAllocator<int>; 794 using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>; 795 796 auto len = inlined_size * 2; 797 auto val = 0; 798 int64_t allocated = 0; 799 AllocFxdArr arr(len, val, Alloc(&allocated)); 800 801 EXPECT_EQ(allocated, len * sizeof(int)); 802 803 AllocFxdArr copy = arr; 804 EXPECT_EQ(allocated, len * sizeof(int) * 2); 805 EXPECT_EQ(copy, arr); 806 } 807 808 #ifdef ABSL_HAVE_ADDRESS_SANITIZER 809 TEST(FixedArrayTest, AddressSanitizerAnnotations1) { 810 absl::FixedArray<int, 32> a(10); 811 int* raw = a.data(); 812 raw[0] = 0; 813 raw[9] = 0; 814 EXPECT_DEATH_IF_SUPPORTED(raw[-2] = 0, "container-overflow"); 815 EXPECT_DEATH_IF_SUPPORTED(raw[-1] = 0, "container-overflow"); 816 EXPECT_DEATH_IF_SUPPORTED(raw[10] = 0, "container-overflow"); 817 EXPECT_DEATH_IF_SUPPORTED(raw[31] = 0, "container-overflow"); 818 } 819 820 TEST(FixedArrayTest, AddressSanitizerAnnotations2) { 821 absl::FixedArray<char, 17> a(12); 822 char* raw = a.data(); 823 raw[0] = 0; 824 raw[11] = 0; 825 EXPECT_DEATH_IF_SUPPORTED(raw[-7] = 0, "container-overflow"); 826 EXPECT_DEATH_IF_SUPPORTED(raw[-1] = 0, "container-overflow"); 827 EXPECT_DEATH_IF_SUPPORTED(raw[12] = 0, "container-overflow"); 828 EXPECT_DEATH_IF_SUPPORTED(raw[17] = 0, "container-overflow"); 829 } 830 831 TEST(FixedArrayTest, AddressSanitizerAnnotations3) { 832 absl::FixedArray<uint64_t, 20> a(20); 833 uint64_t* raw = a.data(); 834 raw[0] = 0; 835 raw[19] = 0; 836 EXPECT_DEATH_IF_SUPPORTED(raw[-1] = 0, "container-overflow"); 837 EXPECT_DEATH_IF_SUPPORTED(raw[20] = 0, "container-overflow"); 838 } 839 840 TEST(FixedArrayTest, AddressSanitizerAnnotations4) { 841 absl::FixedArray<ThreeInts> a(10); 842 ThreeInts* raw = a.data(); 843 raw[0] = ThreeInts(); 844 raw[9] = ThreeInts(); 845 // Note: raw[-1] is pointing to 12 bytes before the container range. However, 846 // there is only a 8-byte red zone before the container range, so we only 847 // access the last 4 bytes of the struct to make sure it stays within the red 848 // zone. 849 EXPECT_DEATH_IF_SUPPORTED(raw[-1].z_ = 0, "container-overflow"); 850 EXPECT_DEATH_IF_SUPPORTED(raw[10] = ThreeInts(), "container-overflow"); 851 // The actual size of storage is kDefaultBytes=256, 21*12 = 252, 852 // so reading raw[21] should still trigger the correct warning. 853 EXPECT_DEATH_IF_SUPPORTED(raw[21] = ThreeInts(), "container-overflow"); 854 } 855 #endif // ABSL_HAVE_ADDRESS_SANITIZER 856 857 TEST(FixedArrayTest, AbslHashValueWorks) { 858 using V = absl::FixedArray<int>; 859 std::vector<V> cases; 860 861 // Generate a variety of vectors some of these are small enough for the inline 862 // space but are stored out of line. 863 for (int i = 0; i < 10; ++i) { 864 V v(i); 865 for (int j = 0; j < i; ++j) { 866 v[j] = j; 867 } 868 cases.push_back(v); 869 } 870 871 EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(cases)); 872 } 873 874 } // namespace