fixed_array_test.cc
Go to the documentation of this file.
00001 // Copyright 2017 The Abseil Authors.
00002 //
00003 // Licensed under the Apache License, Version 2.0 (the "License");
00004 // you may not use this file except in compliance with the License.
00005 // You may obtain a copy of the License at
00006 //
00007 //      https://www.apache.org/licenses/LICENSE-2.0
00008 //
00009 // Unless required by applicable law or agreed to in writing, software
00010 // distributed under the License is distributed on an "AS IS" BASIS,
00011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00012 // See the License for the specific language governing permissions and
00013 // limitations under the License.
00014 
00015 #include "absl/container/fixed_array.h"
00016 
00017 #include <stdio.h>
00018 #include <cstring>
00019 #include <list>
00020 #include <memory>
00021 #include <numeric>
00022 #include <scoped_allocator>
00023 #include <stdexcept>
00024 #include <string>
00025 #include <vector>
00026 
00027 #include "gmock/gmock.h"
00028 #include "gtest/gtest.h"
00029 #include "absl/base/internal/exception_testing.h"
00030 #include "absl/hash/hash_testing.h"
00031 #include "absl/memory/memory.h"
00032 
00033 using ::testing::ElementsAreArray;
00034 
00035 namespace {
00036 
00037 // Helper routine to determine if a absl::FixedArray used stack allocation.
00038 template <typename ArrayType>
00039 static bool IsOnStack(const ArrayType& a) {
00040   return a.size() <= ArrayType::inline_elements;
00041 }
00042 
00043 class ConstructionTester {
00044  public:
00045   ConstructionTester()
00046       : self_ptr_(this),
00047         value_(0) {
00048     constructions++;
00049   }
00050   ~ConstructionTester() {
00051     assert(self_ptr_ == this);
00052     self_ptr_ = nullptr;
00053     destructions++;
00054   }
00055 
00056   // These are incremented as elements are constructed and destructed so we can
00057   // be sure all elements are properly cleaned up.
00058   static int constructions;
00059   static int destructions;
00060 
00061   void CheckConstructed() {
00062     assert(self_ptr_ == this);
00063   }
00064 
00065   void set(int value) { value_ = value; }
00066   int get() { return value_; }
00067 
00068  private:
00069   // self_ptr_ should always point to 'this' -- that's how we can be sure the
00070   // constructor has been called.
00071   ConstructionTester* self_ptr_;
00072   int value_;
00073 };
00074 
00075 int ConstructionTester::constructions = 0;
00076 int ConstructionTester::destructions = 0;
00077 
00078 // ThreeInts will initialize its three ints to the value stored in
00079 // ThreeInts::counter. The constructor increments counter so that each object
00080 // in an array of ThreeInts will have different values.
00081 class ThreeInts {
00082  public:
00083   ThreeInts() {
00084     x_ = counter;
00085     y_ = counter;
00086     z_ = counter;
00087     ++counter;
00088   }
00089 
00090   static int counter;
00091 
00092   int x_, y_, z_;
00093 };
00094 
00095 int ThreeInts::counter = 0;
00096 
00097 TEST(FixedArrayTest, CopyCtor) {
00098   absl::FixedArray<int, 10> on_stack(5);
00099   std::iota(on_stack.begin(), on_stack.end(), 0);
00100   absl::FixedArray<int, 10> stack_copy = on_stack;
00101   EXPECT_THAT(stack_copy, ElementsAreArray(on_stack));
00102   EXPECT_TRUE(IsOnStack(stack_copy));
00103 
00104   absl::FixedArray<int, 10> allocated(15);
00105   std::iota(allocated.begin(), allocated.end(), 0);
00106   absl::FixedArray<int, 10> alloced_copy = allocated;
00107   EXPECT_THAT(alloced_copy, ElementsAreArray(allocated));
00108   EXPECT_FALSE(IsOnStack(alloced_copy));
00109 }
00110 
00111 TEST(FixedArrayTest, MoveCtor) {
00112   absl::FixedArray<std::unique_ptr<int>, 10> on_stack(5);
00113   for (int i = 0; i < 5; ++i) {
00114     on_stack[i] = absl::make_unique<int>(i);
00115   }
00116 
00117   absl::FixedArray<std::unique_ptr<int>, 10> stack_copy = std::move(on_stack);
00118   for (int i = 0; i < 5; ++i) EXPECT_EQ(*(stack_copy[i]), i);
00119   EXPECT_EQ(stack_copy.size(), on_stack.size());
00120 
00121   absl::FixedArray<std::unique_ptr<int>, 10> allocated(15);
00122   for (int i = 0; i < 15; ++i) {
00123     allocated[i] = absl::make_unique<int>(i);
00124   }
00125 
00126   absl::FixedArray<std::unique_ptr<int>, 10> alloced_copy =
00127       std::move(allocated);
00128   for (int i = 0; i < 15; ++i) EXPECT_EQ(*(alloced_copy[i]), i);
00129   EXPECT_EQ(allocated.size(), alloced_copy.size());
00130 }
00131 
00132 TEST(FixedArrayTest, SmallObjects) {
00133   // Small object arrays
00134   {
00135     // Short arrays should be on the stack
00136     absl::FixedArray<int> array(4);
00137     EXPECT_TRUE(IsOnStack(array));
00138   }
00139 
00140   {
00141     // Large arrays should be on the heap
00142     absl::FixedArray<int> array(1048576);
00143     EXPECT_FALSE(IsOnStack(array));
00144   }
00145 
00146   {
00147     // Arrays of <= default size should be on the stack
00148     absl::FixedArray<int, 100> array(100);
00149     EXPECT_TRUE(IsOnStack(array));
00150   }
00151 
00152   {
00153     // Arrays of > default size should be on the heap
00154     absl::FixedArray<int, 100> array(101);
00155     EXPECT_FALSE(IsOnStack(array));
00156   }
00157 
00158   {
00159     // Arrays with different size elements should use approximately
00160     // same amount of stack space
00161     absl::FixedArray<int> array1(0);
00162     absl::FixedArray<char> array2(0);
00163     EXPECT_LE(sizeof(array1), sizeof(array2)+100);
00164     EXPECT_LE(sizeof(array2), sizeof(array1)+100);
00165   }
00166 
00167   {
00168     // Ensure that vectors are properly constructed inside a fixed array.
00169     absl::FixedArray<std::vector<int> > array(2);
00170     EXPECT_EQ(0, array[0].size());
00171     EXPECT_EQ(0, array[1].size());
00172   }
00173 
00174   {
00175     // Regardless of absl::FixedArray implementation, check that a type with a
00176     // low alignment requirement and a non power-of-two size is initialized
00177     // correctly.
00178     ThreeInts::counter = 1;
00179     absl::FixedArray<ThreeInts> array(2);
00180     EXPECT_EQ(1, array[0].x_);
00181     EXPECT_EQ(1, array[0].y_);
00182     EXPECT_EQ(1, array[0].z_);
00183     EXPECT_EQ(2, array[1].x_);
00184     EXPECT_EQ(2, array[1].y_);
00185     EXPECT_EQ(2, array[1].z_);
00186   }
00187 }
00188 
00189 TEST(FixedArrayTest, AtThrows) {
00190   absl::FixedArray<int> a = {1, 2, 3};
00191   EXPECT_EQ(a.at(2), 3);
00192   ABSL_BASE_INTERNAL_EXPECT_FAIL(a.at(3), std::out_of_range,
00193                                  "failed bounds check");
00194 }
00195 
00196 TEST(FixedArrayRelationalsTest, EqualArrays) {
00197   for (int i = 0; i < 10; ++i) {
00198     absl::FixedArray<int, 5> a1(i);
00199     std::iota(a1.begin(), a1.end(), 0);
00200     absl::FixedArray<int, 5> a2(a1.begin(), a1.end());
00201 
00202     EXPECT_TRUE(a1 == a2);
00203     EXPECT_FALSE(a1 != a2);
00204     EXPECT_TRUE(a2 == a1);
00205     EXPECT_FALSE(a2 != a1);
00206     EXPECT_FALSE(a1 < a2);
00207     EXPECT_FALSE(a1 > a2);
00208     EXPECT_FALSE(a2 < a1);
00209     EXPECT_FALSE(a2 > a1);
00210     EXPECT_TRUE(a1 <= a2);
00211     EXPECT_TRUE(a1 >= a2);
00212     EXPECT_TRUE(a2 <= a1);
00213     EXPECT_TRUE(a2 >= a1);
00214   }
00215 }
00216 
00217 TEST(FixedArrayRelationalsTest, UnequalArrays) {
00218   for (int i = 1; i < 10; ++i) {
00219     absl::FixedArray<int, 5> a1(i);
00220     std::iota(a1.begin(), a1.end(), 0);
00221     absl::FixedArray<int, 5> a2(a1.begin(), a1.end());
00222     --a2[i / 2];
00223 
00224     EXPECT_FALSE(a1 == a2);
00225     EXPECT_TRUE(a1 != a2);
00226     EXPECT_FALSE(a2 == a1);
00227     EXPECT_TRUE(a2 != a1);
00228     EXPECT_FALSE(a1 < a2);
00229     EXPECT_TRUE(a1 > a2);
00230     EXPECT_TRUE(a2 < a1);
00231     EXPECT_FALSE(a2 > a1);
00232     EXPECT_FALSE(a1 <= a2);
00233     EXPECT_TRUE(a1 >= a2);
00234     EXPECT_TRUE(a2 <= a1);
00235     EXPECT_FALSE(a2 >= a1);
00236   }
00237 }
00238 
00239 template <int stack_elements>
00240 static void TestArray(int n) {
00241   SCOPED_TRACE(n);
00242   SCOPED_TRACE(stack_elements);
00243   ConstructionTester::constructions = 0;
00244   ConstructionTester::destructions = 0;
00245   {
00246     absl::FixedArray<ConstructionTester, stack_elements> array(n);
00247 
00248     EXPECT_THAT(array.size(), n);
00249     EXPECT_THAT(array.memsize(), sizeof(ConstructionTester) * n);
00250     EXPECT_THAT(array.begin() + n, array.end());
00251 
00252     // Check that all elements were constructed
00253     for (int i = 0; i < n; i++) {
00254       array[i].CheckConstructed();
00255     }
00256     // Check that no other elements were constructed
00257     EXPECT_THAT(ConstructionTester::constructions, n);
00258 
00259     // Test operator[]
00260     for (int i = 0; i < n; i++) {
00261       array[i].set(i);
00262     }
00263     for (int i = 0; i < n; i++) {
00264       EXPECT_THAT(array[i].get(), i);
00265       EXPECT_THAT(array.data()[i].get(), i);
00266     }
00267 
00268     // Test data()
00269     for (int i = 0; i < n; i++) {
00270       array.data()[i].set(i + 1);
00271     }
00272     for (int i = 0; i < n; i++) {
00273       EXPECT_THAT(array[i].get(), i+1);
00274       EXPECT_THAT(array.data()[i].get(), i+1);
00275     }
00276   }  // Close scope containing 'array'.
00277 
00278   // Check that all constructed elements were destructed.
00279   EXPECT_EQ(ConstructionTester::constructions,
00280             ConstructionTester::destructions);
00281 }
00282 
00283 template <int elements_per_inner_array, int inline_elements>
00284 static void TestArrayOfArrays(int n) {
00285   SCOPED_TRACE(n);
00286   SCOPED_TRACE(inline_elements);
00287   SCOPED_TRACE(elements_per_inner_array);
00288   ConstructionTester::constructions = 0;
00289   ConstructionTester::destructions = 0;
00290   {
00291     using InnerArray = ConstructionTester[elements_per_inner_array];
00292     // Heap-allocate the FixedArray to avoid blowing the stack frame.
00293     auto array_ptr =
00294         absl::make_unique<absl::FixedArray<InnerArray, inline_elements>>(n);
00295     auto& array = *array_ptr;
00296 
00297     ASSERT_EQ(array.size(), n);
00298     ASSERT_EQ(array.memsize(),
00299              sizeof(ConstructionTester) * elements_per_inner_array * n);
00300     ASSERT_EQ(array.begin() + n, array.end());
00301 
00302     // Check that all elements were constructed
00303     for (int i = 0; i < n; i++) {
00304       for (int j = 0; j < elements_per_inner_array; j++) {
00305         (array[i])[j].CheckConstructed();
00306       }
00307     }
00308     // Check that no other elements were constructed
00309     ASSERT_EQ(ConstructionTester::constructions, n * elements_per_inner_array);
00310 
00311     // Test operator[]
00312     for (int i = 0; i < n; i++) {
00313       for (int j = 0; j < elements_per_inner_array; j++) {
00314         (array[i])[j].set(i * elements_per_inner_array + j);
00315       }
00316     }
00317     for (int i = 0; i < n; i++) {
00318       for (int j = 0; j < elements_per_inner_array; j++) {
00319         ASSERT_EQ((array[i])[j].get(),  i * elements_per_inner_array + j);
00320         ASSERT_EQ((array.data()[i])[j].get(), i * elements_per_inner_array + j);
00321       }
00322     }
00323 
00324     // Test data()
00325     for (int i = 0; i < n; i++) {
00326       for (int j = 0; j < elements_per_inner_array; j++) {
00327         (array.data()[i])[j].set((i + 1) * elements_per_inner_array + j);
00328       }
00329     }
00330     for (int i = 0; i < n; i++) {
00331       for (int j = 0; j < elements_per_inner_array; j++) {
00332         ASSERT_EQ((array[i])[j].get(),
00333                   (i + 1) * elements_per_inner_array + j);
00334         ASSERT_EQ((array.data()[i])[j].get(),
00335                   (i + 1) * elements_per_inner_array + j);
00336       }
00337     }
00338   }  // Close scope containing 'array'.
00339 
00340   // Check that all constructed elements were destructed.
00341   EXPECT_EQ(ConstructionTester::constructions,
00342             ConstructionTester::destructions);
00343 }
00344 
00345 TEST(IteratorConstructorTest, NonInline) {
00346   int const kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
00347   absl::FixedArray<int, ABSL_ARRAYSIZE(kInput) - 1> const fixed(
00348       kInput, kInput + ABSL_ARRAYSIZE(kInput));
00349   ASSERT_EQ(ABSL_ARRAYSIZE(kInput), fixed.size());
00350   for (size_t i = 0; i < ABSL_ARRAYSIZE(kInput); ++i) {
00351     ASSERT_EQ(kInput[i], fixed[i]);
00352   }
00353 }
00354 
00355 TEST(IteratorConstructorTest, Inline) {
00356   int const kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
00357   absl::FixedArray<int, ABSL_ARRAYSIZE(kInput)> const fixed(
00358       kInput, kInput + ABSL_ARRAYSIZE(kInput));
00359   ASSERT_EQ(ABSL_ARRAYSIZE(kInput), fixed.size());
00360   for (size_t i = 0; i < ABSL_ARRAYSIZE(kInput); ++i) {
00361     ASSERT_EQ(kInput[i], fixed[i]);
00362   }
00363 }
00364 
00365 TEST(IteratorConstructorTest, NonPod) {
00366   char const* kInput[] =
00367       { "red", "orange", "yellow", "green", "blue", "indigo", "violet" };
00368   absl::FixedArray<std::string> const fixed(kInput,
00369                                             kInput + ABSL_ARRAYSIZE(kInput));
00370   ASSERT_EQ(ABSL_ARRAYSIZE(kInput), fixed.size());
00371   for (size_t i = 0; i < ABSL_ARRAYSIZE(kInput); ++i) {
00372     ASSERT_EQ(kInput[i], fixed[i]);
00373   }
00374 }
00375 
00376 TEST(IteratorConstructorTest, FromEmptyVector) {
00377   std::vector<int> const empty;
00378   absl::FixedArray<int> const fixed(empty.begin(), empty.end());
00379   EXPECT_EQ(0, fixed.size());
00380   EXPECT_EQ(empty.size(), fixed.size());
00381 }
00382 
00383 TEST(IteratorConstructorTest, FromNonEmptyVector) {
00384   int const kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
00385   std::vector<int> const items(kInput, kInput + ABSL_ARRAYSIZE(kInput));
00386   absl::FixedArray<int> const fixed(items.begin(), items.end());
00387   ASSERT_EQ(items.size(), fixed.size());
00388   for (size_t i = 0; i < items.size(); ++i) {
00389     ASSERT_EQ(items[i], fixed[i]);
00390   }
00391 }
00392 
00393 TEST(IteratorConstructorTest, FromBidirectionalIteratorRange) {
00394   int const kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
00395   std::list<int> const items(kInput, kInput + ABSL_ARRAYSIZE(kInput));
00396   absl::FixedArray<int> const fixed(items.begin(), items.end());
00397   EXPECT_THAT(fixed, testing::ElementsAreArray(kInput));
00398 }
00399 
00400 TEST(InitListConstructorTest, InitListConstruction) {
00401   absl::FixedArray<int> fixed = {1, 2, 3};
00402   EXPECT_THAT(fixed, testing::ElementsAreArray({1, 2, 3}));
00403 }
00404 
00405 TEST(FillConstructorTest, NonEmptyArrays) {
00406   absl::FixedArray<int> stack_array(4, 1);
00407   EXPECT_THAT(stack_array, testing::ElementsAreArray({1, 1, 1, 1}));
00408 
00409   absl::FixedArray<int, 0> heap_array(4, 1);
00410   EXPECT_THAT(stack_array, testing::ElementsAreArray({1, 1, 1, 1}));
00411 }
00412 
00413 TEST(FillConstructorTest, EmptyArray) {
00414   absl::FixedArray<int> empty_fill(0, 1);
00415   absl::FixedArray<int> empty_size(0);
00416   EXPECT_EQ(empty_fill, empty_size);
00417 }
00418 
00419 TEST(FillConstructorTest, NotTriviallyCopyable) {
00420   std::string str = "abcd";
00421   absl::FixedArray<std::string> strings = {str, str, str, str};
00422 
00423   absl::FixedArray<std::string> array(4, str);
00424   EXPECT_EQ(array, strings);
00425 }
00426 
00427 TEST(FillConstructorTest, Disambiguation) {
00428   absl::FixedArray<size_t> a(1, 2);
00429   EXPECT_THAT(a, testing::ElementsAre(2));
00430 }
00431 
00432 TEST(FixedArrayTest, ManySizedArrays) {
00433   std::vector<int> sizes;
00434   for (int i = 1; i < 100; i++) sizes.push_back(i);
00435   for (int i = 100; i <= 1000; i += 100) sizes.push_back(i);
00436   for (int n : sizes) {
00437     TestArray<0>(n);
00438     TestArray<1>(n);
00439     TestArray<64>(n);
00440     TestArray<1000>(n);
00441   }
00442 }
00443 
00444 TEST(FixedArrayTest, ManySizedArraysOfArraysOf1) {
00445   for (int n = 1; n < 1000; n++) {
00446     ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 0>(n)));
00447     ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 1>(n)));
00448     ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 64>(n)));
00449     ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 1000>(n)));
00450   }
00451 }
00452 
00453 TEST(FixedArrayTest, ManySizedArraysOfArraysOf2) {
00454   for (int n = 1; n < 1000; n++) {
00455     TestArrayOfArrays<2, 0>(n);
00456     TestArrayOfArrays<2, 1>(n);
00457     TestArrayOfArrays<2, 64>(n);
00458     TestArrayOfArrays<2, 1000>(n);
00459   }
00460 }
00461 
00462 // If value_type is put inside of a struct container,
00463 // we might evoke this error in a hardened build unless data() is carefully
00464 // written, so check on that.
00465 //     error: call to int __builtin___sprintf_chk(etc...)
00466 //     will always overflow destination buffer [-Werror]
00467 TEST(FixedArrayTest, AvoidParanoidDiagnostics) {
00468   absl::FixedArray<char, 32> buf(32);
00469   sprintf(buf.data(), "foo");  // NOLINT(runtime/printf)
00470 }
00471 
00472 TEST(FixedArrayTest, TooBigInlinedSpace) {
00473   struct TooBig {
00474     char c[1 << 20];
00475   };  // too big for even one on the stack
00476 
00477   // Simulate the data members of absl::FixedArray, a pointer and a size_t.
00478   struct Data {
00479     TooBig* p;
00480     size_t size;
00481   };
00482 
00483   // Make sure TooBig objects are not inlined for 0 or default size.
00484   static_assert(sizeof(absl::FixedArray<TooBig, 0>) == sizeof(Data),
00485                 "0-sized absl::FixedArray should have same size as Data.");
00486   static_assert(alignof(absl::FixedArray<TooBig, 0>) == alignof(Data),
00487                 "0-sized absl::FixedArray should have same alignment as Data.");
00488   static_assert(sizeof(absl::FixedArray<TooBig>) == sizeof(Data),
00489                 "default-sized absl::FixedArray should have same size as Data");
00490   static_assert(
00491       alignof(absl::FixedArray<TooBig>) == alignof(Data),
00492       "default-sized absl::FixedArray should have same alignment as Data.");
00493 }
00494 
00495 // PickyDelete EXPECTs its class-scope deallocation funcs are unused.
00496 struct PickyDelete {
00497   PickyDelete() {}
00498   ~PickyDelete() {}
00499   void operator delete(void* p) {
00500     EXPECT_TRUE(false) << __FUNCTION__;
00501     ::operator delete(p);
00502   }
00503   void operator delete[](void* p) {
00504     EXPECT_TRUE(false) << __FUNCTION__;
00505     ::operator delete[](p);
00506   }
00507 };
00508 
00509 TEST(FixedArrayTest, UsesGlobalAlloc) { absl::FixedArray<PickyDelete, 0> a(5); }
00510 
00511 
00512 TEST(FixedArrayTest, Data) {
00513   static const int kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
00514   absl::FixedArray<int> fa(std::begin(kInput), std::end(kInput));
00515   EXPECT_EQ(fa.data(), &*fa.begin());
00516   EXPECT_EQ(fa.data(), &fa[0]);
00517 
00518   const absl::FixedArray<int>& cfa = fa;
00519   EXPECT_EQ(cfa.data(), &*cfa.begin());
00520   EXPECT_EQ(cfa.data(), &cfa[0]);
00521 }
00522 
00523 TEST(FixedArrayTest, Empty) {
00524   absl::FixedArray<int> empty(0);
00525   absl::FixedArray<int> inline_filled(1);
00526   absl::FixedArray<int, 0> heap_filled(1);
00527   EXPECT_TRUE(empty.empty());
00528   EXPECT_FALSE(inline_filled.empty());
00529   EXPECT_FALSE(heap_filled.empty());
00530 }
00531 
00532 TEST(FixedArrayTest, FrontAndBack) {
00533   absl::FixedArray<int, 3 * sizeof(int)> inlined = {1, 2, 3};
00534   EXPECT_EQ(inlined.front(), 1);
00535   EXPECT_EQ(inlined.back(), 3);
00536 
00537   absl::FixedArray<int, 0> allocated = {1, 2, 3};
00538   EXPECT_EQ(allocated.front(), 1);
00539   EXPECT_EQ(allocated.back(), 3);
00540 
00541   absl::FixedArray<int> one_element = {1};
00542   EXPECT_EQ(one_element.front(), one_element.back());
00543 }
00544 
00545 TEST(FixedArrayTest, ReverseIteratorInlined) {
00546   absl::FixedArray<int, 5 * sizeof(int)> a = {0, 1, 2, 3, 4};
00547 
00548   int counter = 5;
00549   for (absl::FixedArray<int>::reverse_iterator iter = a.rbegin();
00550        iter != a.rend(); ++iter) {
00551     counter--;
00552     EXPECT_EQ(counter, *iter);
00553   }
00554   EXPECT_EQ(counter, 0);
00555 
00556   counter = 5;
00557   for (absl::FixedArray<int>::const_reverse_iterator iter = a.rbegin();
00558        iter != a.rend(); ++iter) {
00559     counter--;
00560     EXPECT_EQ(counter, *iter);
00561   }
00562   EXPECT_EQ(counter, 0);
00563 
00564   counter = 5;
00565   for (auto iter = a.crbegin(); iter != a.crend(); ++iter) {
00566     counter--;
00567     EXPECT_EQ(counter, *iter);
00568   }
00569   EXPECT_EQ(counter, 0);
00570 }
00571 
00572 TEST(FixedArrayTest, ReverseIteratorAllocated) {
00573   absl::FixedArray<int, 0> a = {0, 1, 2, 3, 4};
00574 
00575   int counter = 5;
00576   for (absl::FixedArray<int>::reverse_iterator iter = a.rbegin();
00577        iter != a.rend(); ++iter) {
00578     counter--;
00579     EXPECT_EQ(counter, *iter);
00580   }
00581   EXPECT_EQ(counter, 0);
00582 
00583   counter = 5;
00584   for (absl::FixedArray<int>::const_reverse_iterator iter = a.rbegin();
00585        iter != a.rend(); ++iter) {
00586     counter--;
00587     EXPECT_EQ(counter, *iter);
00588   }
00589   EXPECT_EQ(counter, 0);
00590 
00591   counter = 5;
00592   for (auto iter = a.crbegin(); iter != a.crend(); ++iter) {
00593     counter--;
00594     EXPECT_EQ(counter, *iter);
00595   }
00596   EXPECT_EQ(counter, 0);
00597 }
00598 
00599 TEST(FixedArrayTest, Fill) {
00600   absl::FixedArray<int, 5 * sizeof(int)> inlined(5);
00601   int fill_val = 42;
00602   inlined.fill(fill_val);
00603   for (int i : inlined) EXPECT_EQ(i, fill_val);
00604 
00605   absl::FixedArray<int, 0> allocated(5);
00606   allocated.fill(fill_val);
00607   for (int i : allocated) EXPECT_EQ(i, fill_val);
00608 
00609   // It doesn't do anything, just make sure this compiles.
00610   absl::FixedArray<int> empty(0);
00611   empty.fill(fill_val);
00612 }
00613 
00614 // TODO(johnsoncj): Investigate InlinedStorage default initialization in GCC 4.x
00615 #ifndef __GNUC__
00616 TEST(FixedArrayTest, DefaultCtorDoesNotValueInit) {
00617   using T = char;
00618   constexpr auto capacity = 10;
00619   using FixedArrType = absl::FixedArray<T, capacity>;
00620   using FixedArrBuffType =
00621       absl::aligned_storage_t<sizeof(FixedArrType), alignof(FixedArrType)>;
00622   constexpr auto scrubbed_bits = 0x95;
00623   constexpr auto length = capacity / 2;
00624 
00625   FixedArrBuffType buff;
00626   std::memset(std::addressof(buff), scrubbed_bits, sizeof(FixedArrBuffType));
00627 
00628   FixedArrType* arr =
00629       ::new (static_cast<void*>(std::addressof(buff))) FixedArrType(length);
00630   EXPECT_THAT(*arr, testing::Each(scrubbed_bits));
00631   arr->~FixedArrType();
00632 }
00633 #endif  // __GNUC__
00634 
00635 // This is a stateful allocator, but the state lives outside of the
00636 // allocator (in whatever test is using the allocator). This is odd
00637 // but helps in tests where the allocator is propagated into nested
00638 // containers - that chain of allocators uses the same state and is
00639 // thus easier to query for aggregate allocation information.
00640 template <typename T>
00641 class CountingAllocator : public std::allocator<T> {
00642  public:
00643   using Alloc = std::allocator<T>;
00644   using pointer = typename Alloc::pointer;
00645   using size_type = typename Alloc::size_type;
00646 
00647   CountingAllocator() : bytes_used_(nullptr), instance_count_(nullptr) {}
00648   explicit CountingAllocator(int64_t* b)
00649       : bytes_used_(b), instance_count_(nullptr) {}
00650   CountingAllocator(int64_t* b, int64_t* a)
00651       : bytes_used_(b), instance_count_(a) {}
00652 
00653   template <typename U>
00654   explicit CountingAllocator(const CountingAllocator<U>& x)
00655       : Alloc(x),
00656         bytes_used_(x.bytes_used_),
00657         instance_count_(x.instance_count_) {}
00658 
00659   pointer allocate(size_type n, const void* const hint = nullptr) {
00660     assert(bytes_used_ != nullptr);
00661     *bytes_used_ += n * sizeof(T);
00662     return Alloc::allocate(n, hint);
00663   }
00664 
00665   void deallocate(pointer p, size_type n) {
00666     Alloc::deallocate(p, n);
00667     assert(bytes_used_ != nullptr);
00668     *bytes_used_ -= n * sizeof(T);
00669   }
00670 
00671   template <typename... Args>
00672   void construct(pointer p, Args&&... args) {
00673     Alloc::construct(p, absl::forward<Args>(args)...);
00674     if (instance_count_) {
00675       *instance_count_ += 1;
00676     }
00677   }
00678 
00679   void destroy(pointer p) {
00680     Alloc::destroy(p);
00681     if (instance_count_) {
00682       *instance_count_ -= 1;
00683     }
00684   }
00685 
00686   template <typename U>
00687   class rebind {
00688    public:
00689     using other = CountingAllocator<U>;
00690   };
00691 
00692   int64_t* bytes_used_;
00693   int64_t* instance_count_;
00694 };
00695 
00696 TEST(AllocatorSupportTest, CountInlineAllocations) {
00697   constexpr size_t inlined_size = 4;
00698   using Alloc = CountingAllocator<int>;
00699   using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>;
00700 
00701   int64_t allocated = 0;
00702   int64_t active_instances = 0;
00703 
00704   {
00705     const int ia[] = {0, 1, 2, 3, 4, 5, 6, 7};
00706 
00707     Alloc alloc(&allocated, &active_instances);
00708 
00709     AllocFxdArr arr(ia, ia + inlined_size, alloc);
00710     static_cast<void>(arr);
00711   }
00712 
00713   EXPECT_EQ(allocated, 0);
00714   EXPECT_EQ(active_instances, 0);
00715 }
00716 
00717 TEST(AllocatorSupportTest, CountOutoflineAllocations) {
00718   constexpr size_t inlined_size = 4;
00719   using Alloc = CountingAllocator<int>;
00720   using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>;
00721 
00722   int64_t allocated = 0;
00723   int64_t active_instances = 0;
00724 
00725   {
00726     const int ia[] = {0, 1, 2, 3, 4, 5, 6, 7};
00727     Alloc alloc(&allocated, &active_instances);
00728 
00729     AllocFxdArr arr(ia, ia + ABSL_ARRAYSIZE(ia), alloc);
00730 
00731     EXPECT_EQ(allocated, arr.size() * sizeof(int));
00732     static_cast<void>(arr);
00733   }
00734 
00735   EXPECT_EQ(active_instances, 0);
00736 }
00737 
00738 TEST(AllocatorSupportTest, CountCopyInlineAllocations) {
00739   constexpr size_t inlined_size = 4;
00740   using Alloc = CountingAllocator<int>;
00741   using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>;
00742 
00743   int64_t allocated1 = 0;
00744   int64_t allocated2 = 0;
00745   int64_t active_instances = 0;
00746   Alloc alloc(&allocated1, &active_instances);
00747   Alloc alloc2(&allocated2, &active_instances);
00748 
00749   {
00750     int initial_value = 1;
00751 
00752     AllocFxdArr arr1(inlined_size / 2, initial_value, alloc);
00753 
00754     EXPECT_EQ(allocated1, 0);
00755 
00756     AllocFxdArr arr2(arr1, alloc2);
00757 
00758     EXPECT_EQ(allocated2, 0);
00759     static_cast<void>(arr1);
00760     static_cast<void>(arr2);
00761   }
00762 
00763   EXPECT_EQ(active_instances, 0);
00764 }
00765 
00766 TEST(AllocatorSupportTest, CountCopyOutoflineAllocations) {
00767   constexpr size_t inlined_size = 4;
00768   using Alloc = CountingAllocator<int>;
00769   using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>;
00770 
00771   int64_t allocated1 = 0;
00772   int64_t allocated2 = 0;
00773   int64_t active_instances = 0;
00774   Alloc alloc(&allocated1, &active_instances);
00775   Alloc alloc2(&allocated2, &active_instances);
00776 
00777   {
00778     int initial_value = 1;
00779 
00780     AllocFxdArr arr1(inlined_size * 2, initial_value, alloc);
00781 
00782     EXPECT_EQ(allocated1, arr1.size() * sizeof(int));
00783 
00784     AllocFxdArr arr2(arr1, alloc2);
00785 
00786     EXPECT_EQ(allocated2, inlined_size * 2 * sizeof(int));
00787     static_cast<void>(arr1);
00788     static_cast<void>(arr2);
00789   }
00790 
00791   EXPECT_EQ(active_instances, 0);
00792 }
00793 
00794 TEST(AllocatorSupportTest, SizeValAllocConstructor) {
00795   using testing::AllOf;
00796   using testing::Each;
00797   using testing::SizeIs;
00798 
00799   constexpr size_t inlined_size = 4;
00800   using Alloc = CountingAllocator<int>;
00801   using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>;
00802 
00803   {
00804     auto len = inlined_size / 2;
00805     auto val = 0;
00806     int64_t allocated = 0;
00807     AllocFxdArr arr(len, val, Alloc(&allocated));
00808 
00809     EXPECT_EQ(allocated, 0);
00810     EXPECT_THAT(arr, AllOf(SizeIs(len), Each(0)));
00811   }
00812 
00813   {
00814     auto len = inlined_size * 2;
00815     auto val = 0;
00816     int64_t allocated = 0;
00817     AllocFxdArr arr(len, val, Alloc(&allocated));
00818 
00819     EXPECT_EQ(allocated, len * sizeof(int));
00820     EXPECT_THAT(arr, AllOf(SizeIs(len), Each(0)));
00821   }
00822 }
00823 
00824 #ifdef ADDRESS_SANITIZER
00825 TEST(FixedArrayTest, AddressSanitizerAnnotations1) {
00826   absl::FixedArray<int, 32> a(10);
00827   int *raw = a.data();
00828   raw[0] = 0;
00829   raw[9] = 0;
00830   EXPECT_DEATH(raw[-2] = 0, "container-overflow");
00831   EXPECT_DEATH(raw[-1] = 0, "container-overflow");
00832   EXPECT_DEATH(raw[10] = 0, "container-overflow");
00833   EXPECT_DEATH(raw[31] = 0, "container-overflow");
00834 }
00835 
00836 TEST(FixedArrayTest, AddressSanitizerAnnotations2) {
00837   absl::FixedArray<char, 17> a(12);
00838   char *raw = a.data();
00839   raw[0] = 0;
00840   raw[11] = 0;
00841   EXPECT_DEATH(raw[-7] = 0, "container-overflow");
00842   EXPECT_DEATH(raw[-1] = 0, "container-overflow");
00843   EXPECT_DEATH(raw[12] = 0, "container-overflow");
00844   EXPECT_DEATH(raw[17] = 0, "container-overflow");
00845 }
00846 
00847 TEST(FixedArrayTest, AddressSanitizerAnnotations3) {
00848   absl::FixedArray<uint64_t, 20> a(20);
00849   uint64_t *raw = a.data();
00850   raw[0] = 0;
00851   raw[19] = 0;
00852   EXPECT_DEATH(raw[-1] = 0, "container-overflow");
00853   EXPECT_DEATH(raw[20] = 0, "container-overflow");
00854 }
00855 
00856 TEST(FixedArrayTest, AddressSanitizerAnnotations4) {
00857   absl::FixedArray<ThreeInts> a(10);
00858   ThreeInts *raw = a.data();
00859   raw[0] = ThreeInts();
00860   raw[9] = ThreeInts();
00861   // Note: raw[-1] is pointing to 12 bytes before the container range. However,
00862   // there is only a 8-byte red zone before the container range, so we only
00863   // access the last 4 bytes of the struct to make sure it stays within the red
00864   // zone.
00865   EXPECT_DEATH(raw[-1].z_ = 0, "container-overflow");
00866   EXPECT_DEATH(raw[10] = ThreeInts(), "container-overflow");
00867   // The actual size of storage is kDefaultBytes=256, 21*12 = 252,
00868   // so reading raw[21] should still trigger the correct warning.
00869   EXPECT_DEATH(raw[21] = ThreeInts(), "container-overflow");
00870 }
00871 #endif  // ADDRESS_SANITIZER
00872 
00873 TEST(FixedArrayTest, AbslHashValueWorks) {
00874   using V = absl::FixedArray<int>;
00875   std::vector<V> cases;
00876 
00877   // Generate a variety of vectors some of these are small enough for the inline
00878   // space but are stored out of line.
00879   for (int i = 0; i < 10; ++i) {
00880     V v(i);
00881     for (int j = 0; j < i; ++j) {
00882       v[j] = j;
00883     }
00884     cases.push_back(v);
00885   }
00886 
00887   EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(cases));
00888 }
00889 
00890 }  // namespace


abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:42:14