stack_container_unittest.cc 5.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215
  1. // Copyright (c) 2012 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "base/containers/stack_container.h"
  5. #include <stddef.h>
  6. #include <algorithm>
  7. #include "base/memory/aligned_memory.h"
  8. #include "base/memory/raw_ptr.h"
  9. #include "base/memory/ref_counted.h"
  10. #include "build/build_config.h"
  11. #include "testing/gtest/include/gtest/gtest.h"
  12. namespace base {
  13. namespace {
  14. class Dummy : public RefCounted<Dummy> {
  15. public:
  16. explicit Dummy(int* alive) : alive_(alive) {
  17. ++*alive_;
  18. }
  19. private:
  20. friend class RefCounted<Dummy>;
  21. ~Dummy() {
  22. --*alive_;
  23. }
  24. const raw_ptr<int> alive_;
  25. };
  26. } // namespace
  27. TEST(StackContainer, Vector) {
  28. const int stack_size = 3;
  29. StackVector<int, stack_size> vect;
  30. const int* stack_buffer = &vect.stack_data().stack_buffer()[0];
  31. // The initial |stack_size| elements should appear in the stack buffer.
  32. EXPECT_EQ(static_cast<size_t>(stack_size), vect.container().capacity());
  33. for (int i = 0; i < stack_size; i++) {
  34. vect.container().push_back(i);
  35. EXPECT_EQ(stack_buffer, &vect.container()[0]);
  36. EXPECT_TRUE(vect.stack_data().used_stack_buffer_);
  37. }
  38. // Adding more elements should push the array onto the heap.
  39. for (int i = 0; i < stack_size; i++) {
  40. vect.container().push_back(i + stack_size);
  41. EXPECT_NE(stack_buffer, &vect.container()[0]);
  42. EXPECT_FALSE(vect.stack_data().used_stack_buffer_);
  43. }
  44. // The array should still be in order.
  45. for (int i = 0; i < stack_size * 2; i++)
  46. EXPECT_EQ(i, vect.container()[i]);
  47. // Resize to smaller. Our STL implementation won't reallocate in this case,
  48. // otherwise it might use our stack buffer. We reserve right after the resize
  49. // to guarantee it isn't using the stack buffer, even though it doesn't have
  50. // much data.
  51. vect.container().resize(stack_size);
  52. vect.container().reserve(stack_size * 2);
  53. EXPECT_FALSE(vect.stack_data().used_stack_buffer_);
  54. // Copying the small vector to another should use the same allocator and use
  55. // the now-unused stack buffer. GENERALLY CALLERS SHOULD NOT DO THIS since
  56. // they have to get the template types just right and it can cause errors.
  57. std::vector<int, StackAllocator<int, stack_size, std::allocator<int>>> other(
  58. vect.container());
  59. EXPECT_EQ(stack_buffer, &other.front());
  60. EXPECT_TRUE(vect.stack_data().used_stack_buffer_);
  61. for (int i = 0; i < stack_size; i++)
  62. EXPECT_EQ(i, other[i]);
  63. }
  64. TEST(StackContainer, VectorDoubleDelete) {
  65. // Regression testing for double-delete.
  66. typedef StackVector<scoped_refptr<Dummy>, 2> Vector;
  67. Vector vect;
  68. int alive = 0;
  69. scoped_refptr<Dummy> dummy(new Dummy(&alive));
  70. EXPECT_EQ(alive, 1);
  71. vect->push_back(dummy);
  72. EXPECT_EQ(alive, 1);
  73. Dummy* dummy_unref = dummy.get();
  74. dummy = nullptr;
  75. EXPECT_EQ(alive, 1);
  76. auto itr = std::find(vect->begin(), vect->end(), dummy_unref);
  77. EXPECT_EQ(itr->get(), dummy_unref);
  78. vect->erase(itr);
  79. EXPECT_EQ(alive, 0);
  80. // Shouldn't crash at exit.
  81. }
  82. namespace {
  83. template <size_t alignment>
  84. class AlignedData {
  85. public:
  86. AlignedData() { memset(data_, 0, alignment); }
  87. ~AlignedData() = default;
  88. alignas(alignment) char data_[alignment];
  89. };
  90. } // namespace
  91. TEST(StackContainer, BufferAlignment) {
  92. StackVector<wchar_t, 16> text;
  93. text->push_back(L'A');
  94. EXPECT_TRUE(IsAligned(&text[0], alignof(wchar_t)));
  95. StackVector<double, 1> doubles;
  96. doubles->push_back(0.0);
  97. EXPECT_TRUE(IsAligned(&doubles[0], alignof(double)));
  98. StackVector<AlignedData<16>, 1> aligned16;
  99. aligned16->push_back(AlignedData<16>());
  100. EXPECT_TRUE(IsAligned(&aligned16[0], 16));
  101. #if !defined(__GNUC__) || defined(ARCH_CPU_X86_FAMILY)
  102. // It seems that non-X86 gcc doesn't respect greater than 16 byte alignment.
  103. // See http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33721 for details.
  104. // TODO(sbc): Re-enable this if GCC starts respecting higher alignments.
  105. StackVector<AlignedData<256>, 1> aligned256;
  106. aligned256->push_back(AlignedData<256>());
  107. EXPECT_TRUE(IsAligned(&aligned256[0], 256));
  108. #endif
  109. }
  110. template class StackVector<int, 2>;
  111. template class StackVector<scoped_refptr<Dummy>, 2>;
  112. template <typename T, size_t size>
  113. void CheckStackVectorElements(const StackVector<T, size>& vec,
  114. std::initializer_list<T> expected) {
  115. auto expected_it = expected.begin();
  116. EXPECT_EQ(vec->size(), expected.size());
  117. for (T t : vec) {
  118. EXPECT_NE(expected.end(), expected_it);
  119. EXPECT_EQ(*expected_it, t);
  120. ++expected_it;
  121. }
  122. EXPECT_EQ(expected.end(), expected_it);
  123. }
  124. TEST(StackContainer, Iteration) {
  125. StackVector<int, 3> vect;
  126. vect->push_back(7);
  127. vect->push_back(11);
  128. CheckStackVectorElements(vect, {7, 11});
  129. for (int& i : vect) {
  130. ++i;
  131. }
  132. CheckStackVectorElements(vect, {8, 12});
  133. vect->push_back(13);
  134. CheckStackVectorElements(vect, {8, 12, 13});
  135. vect->resize(5);
  136. CheckStackVectorElements(vect, {8, 12, 13, 0, 0});
  137. vect->resize(1);
  138. CheckStackVectorElements(vect, {8});
  139. }
  140. namespace {
  141. struct Allocator : std::allocator<int> {
  142. using Base = std::allocator<int>;
  143. int* allocate(size_t n) {
  144. ++allocated;
  145. return Base::allocate(n);
  146. }
  147. void deallocate(int* p, size_t n) {
  148. ++deallocated;
  149. Base::deallocate(p, n);
  150. }
  151. static int allocated;
  152. static int deallocated;
  153. };
  154. int Allocator::allocated = 0;
  155. int Allocator::deallocated = 0;
  156. } // namespace
  157. TEST(StackContainer, CustomAllocator) {
  158. StackVector<int, 2, Allocator> v;
  159. EXPECT_EQ(0, Allocator::allocated);
  160. EXPECT_EQ(0, Allocator::deallocated);
  161. v->push_back(1);
  162. v->push_back(1);
  163. EXPECT_EQ(0, Allocator::allocated);
  164. v->push_back(1);
  165. EXPECT_EQ(1, Allocator::allocated);
  166. EXPECT_EQ(0, Allocator::deallocated);
  167. v->clear();
  168. // shrink_to_fit() makes sure to destroy empty backing store.
  169. v->shrink_to_fit();
  170. EXPECT_EQ(1, Allocator::deallocated);
  171. }
  172. } // namespace base