1 // Copyright 2021 The libgav1 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 // http://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 "src/utils/vector.h"
16
17 #include <memory>
18 #include <new>
19 #include <utility>
20
21 #include "gtest/gtest.h"
22 #include "src/utils/compiler_attributes.h"
23
24 #if LIBGAV1_MSAN
25 #include <sanitizer/msan_interface.h>
26 #endif
27
28 namespace libgav1 {
29 namespace {
30
31 class Foo {
32 public:
33 Foo() = default;
34
x() const35 int x() const { return x_; }
36
37 private:
38 int x_ = 38;
39 };
40
41 class Point {
42 public:
Point(int x,int y)43 Point(int x, int y) : x_(x), y_(y) {}
44
x() const45 int x() const { return x_; }
y() const46 int y() const { return y_; }
47
48 private:
49 int x_;
50 int y_;
51 };
52
TEST(VectorTest,NoCtor)53 TEST(VectorTest, NoCtor) {
54 VectorNoCtor<int> v;
55 EXPECT_TRUE(v.resize(100));
56 Vector<int> w;
57 EXPECT_TRUE(w.resize(100));
58
59 #if LIBGAV1_MSAN
60 // Use MemorySanitizer to check VectorNoCtor::resize() does not initialize
61 // the memory while Vector::resize() does.
62 //
63 // __msan_test_shadow(const void *x, uptr size) returns the offset of the
64 // first (at least partially) poisoned byte in the range, or -1 if the whole
65 // range is good.
66 for (size_t i = 0; i < 100; ++i) {
67 EXPECT_EQ(__msan_test_shadow(&v[i], sizeof(int)), 0);
68 EXPECT_EQ(__msan_test_shadow(&w[i], sizeof(int)), -1);
69 }
70 #endif
71 }
72
TEST(VectorTest,Constructor)73 TEST(VectorTest, Constructor) {
74 Vector<Foo> v;
75 EXPECT_TRUE(v.resize(100));
76 for (const Foo& foo : v) {
77 EXPECT_EQ(foo.x(), 38);
78 }
79 }
80
TEST(VectorTest,PushBack)81 TEST(VectorTest, PushBack) {
82 // Create a vector containing integers
83 Vector<int> v;
84 EXPECT_TRUE(v.reserve(8));
85 EXPECT_EQ(v.size(), 0);
86
87 EXPECT_TRUE(v.push_back(25));
88 EXPECT_EQ(v.size(), 1);
89 EXPECT_EQ(v[0], 25);
90
91 EXPECT_TRUE(v.push_back(13));
92 EXPECT_EQ(v.size(), 2);
93 EXPECT_EQ(v[0], 25);
94 EXPECT_EQ(v[1], 13);
95 }
96
TEST(VectorTest,PushBackUnchecked)97 TEST(VectorTest, PushBackUnchecked) {
98 Vector<std::unique_ptr<Point>> v;
99 EXPECT_TRUE(v.reserve(2));
100 EXPECT_EQ(v.size(), 0);
101
102 std::unique_ptr<Point> point(new (std::nothrow) Point(1, 2));
103 EXPECT_NE(point, nullptr);
104 v.push_back_unchecked(std::move(point));
105 EXPECT_EQ(v.size(), 1);
106 EXPECT_EQ(v[0]->x(), 1);
107 EXPECT_EQ(v[0]->y(), 2);
108
109 point.reset(new (std::nothrow) Point(3, 4));
110 EXPECT_NE(point, nullptr);
111 v.push_back_unchecked(std::move(point));
112 EXPECT_EQ(v.size(), 2);
113 EXPECT_EQ(v[0]->x(), 1);
114 EXPECT_EQ(v[0]->y(), 2);
115 EXPECT_EQ(v[1]->x(), 3);
116 EXPECT_EQ(v[1]->y(), 4);
117 }
118
TEST(VectorTest,EmplaceBack)119 TEST(VectorTest, EmplaceBack) {
120 Vector<Point> v;
121 EXPECT_EQ(v.size(), 0);
122
123 EXPECT_TRUE(v.emplace_back(1, 2));
124 EXPECT_EQ(v.size(), 1);
125 EXPECT_EQ(v[0].x(), 1);
126 EXPECT_EQ(v[0].y(), 2);
127
128 EXPECT_TRUE(v.emplace_back(3, 4));
129 EXPECT_EQ(v.size(), 2);
130 EXPECT_EQ(v[0].x(), 1);
131 EXPECT_EQ(v[0].y(), 2);
132 EXPECT_EQ(v[1].x(), 3);
133 EXPECT_EQ(v[1].y(), 4);
134 }
135
136 // Copy constructor and assignment are deleted, but move constructor and
137 // assignment are OK.
TEST(VectorTest,Move)138 TEST(VectorTest, Move) {
139 Vector<int> ints1;
140 EXPECT_TRUE(ints1.reserve(4));
141 EXPECT_TRUE(ints1.push_back(2));
142 EXPECT_TRUE(ints1.push_back(3));
143 EXPECT_TRUE(ints1.push_back(5));
144 EXPECT_TRUE(ints1.push_back(7));
145
146 // Move constructor.
147 Vector<int> ints2(std::move(ints1));
148 EXPECT_EQ(ints2.size(), 4);
149 EXPECT_EQ(ints2[0], 2);
150 EXPECT_EQ(ints2[1], 3);
151 EXPECT_EQ(ints2[2], 5);
152 EXPECT_EQ(ints2[3], 7);
153
154 // Move assignment.
155 Vector<int> ints3;
156 EXPECT_TRUE(ints3.reserve(1));
157 EXPECT_TRUE(ints3.push_back(11));
158 ints3 = std::move(ints2);
159 EXPECT_EQ(ints3.size(), 4);
160 EXPECT_EQ(ints3[0], 2);
161 EXPECT_EQ(ints3[1], 3);
162 EXPECT_EQ(ints3[2], 5);
163 EXPECT_EQ(ints3[3], 7);
164 }
165
TEST(VectorTest,Erase)166 TEST(VectorTest, Erase) {
167 Vector<int> ints;
168 EXPECT_TRUE(ints.reserve(4));
169 EXPECT_TRUE(ints.push_back(2));
170 EXPECT_TRUE(ints.push_back(3));
171 EXPECT_TRUE(ints.push_back(5));
172 EXPECT_TRUE(ints.push_back(7));
173
174 EXPECT_EQ(ints.size(), 4);
175 EXPECT_EQ(ints[0], 2);
176 EXPECT_EQ(ints[1], 3);
177 EXPECT_EQ(ints[2], 5);
178 EXPECT_EQ(ints[3], 7);
179
180 ints.erase(ints.begin());
181 EXPECT_EQ(ints.size(), 3);
182 EXPECT_EQ(ints[0], 3);
183 EXPECT_EQ(ints[1], 5);
184 EXPECT_EQ(ints[2], 7);
185 }
186
TEST(VectorTest,EraseNonTrivial)187 TEST(VectorTest, EraseNonTrivial) {
188 // A simple class that sets an int value to 0 in the destructor.
189 class Cleaner {
190 public:
191 explicit Cleaner(int* value) : value_(value) {}
192 ~Cleaner() { *value_ = 0; }
193
194 int value() const { return *value_; }
195
196 private:
197 int* value_;
198 };
199 int value1 = 100;
200 int value2 = 200;
201 Vector<std::unique_ptr<Cleaner>> v;
202 EXPECT_TRUE(v.reserve(2));
203 EXPECT_EQ(v.capacity(), 2);
204
205 std::unique_ptr<Cleaner> c(new (std::nothrow) Cleaner(&value1));
206 EXPECT_NE(c, nullptr);
207 EXPECT_TRUE(v.push_back(std::move(c)));
208 c.reset(new (std::nothrow) Cleaner(&value2));
209 EXPECT_NE(c, nullptr);
210 EXPECT_TRUE(v.push_back(std::move(c)));
211 EXPECT_EQ(v.size(), 2);
212 EXPECT_EQ(value1, 100);
213 EXPECT_EQ(value2, 200);
214
215 v.erase(v.begin());
216 EXPECT_EQ(v.size(), 1);
217 EXPECT_EQ(v.capacity(), 2);
218 EXPECT_EQ(value1, 0);
219 EXPECT_EQ(value2, 200);
220 EXPECT_EQ(v[0].get()->value(), value2);
221
222 EXPECT_TRUE(v.shrink_to_fit());
223 EXPECT_EQ(v.size(), 1);
224 EXPECT_EQ(v.capacity(), 1);
225 EXPECT_EQ(value2, 200);
226 EXPECT_EQ(v[0].get()->value(), value2);
227
228 v.clear();
229 EXPECT_TRUE(v.empty());
230 EXPECT_EQ(value2, 0);
231 }
232
233 } // namespace
234 } // namespace libgav1
235