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