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


abseil_cpp
Author(s):
autogenerated on Mon Feb 28 2022 21:31:18