1 // Copyright 2024 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "base/containers/heap_array.h"
6
7 #include <stdint.h>
8
9 #include <algorithm>
10 #include <type_traits>
11
12 #include "base/containers/span.h"
13 #include "base/memory/raw_ptr_exclusion.h"
14 #include "testing/gtest/include/gtest/gtest.h"
15
16 namespace base {
17
18 namespace {
19
20 class DestructCounter {
21 public:
22 DestructCounter() = default;
~DestructCounter()23 ~DestructCounter() {
24 if (where_) {
25 (*where_)++;
26 }
27 }
28
set_where(size_t * where)29 void set_where(size_t* where) { where_ = where; }
30
31 private:
32 // RAW_PTR_EXCLUSION: Stack location only.
33 RAW_PTR_EXCLUSION size_t* where_ = nullptr;
34 };
35
CStyleInvoker(void (* cb)(void *),void * arg)36 extern "C" void CStyleInvoker(void (*cb)(void*), void* arg) {
37 (*cb)(arg);
38 }
39
40 } // namespace
41
TEST(HeapArray,DefaultConstructor)42 TEST(HeapArray, DefaultConstructor) {
43 HeapArray<uint32_t> vec;
44 EXPECT_TRUE(vec.empty());
45 EXPECT_EQ(vec.size(), 0u);
46 EXPECT_EQ(vec.data(), nullptr);
47 }
48
TEST(HeapArray,WithSizeZero)49 TEST(HeapArray, WithSizeZero) {
50 auto vec = HeapArray<uint32_t>::WithSize(0u);
51 EXPECT_EQ(vec.size(), 0u);
52 EXPECT_EQ(vec.data(), nullptr);
53 }
54
TEST(HeapArray,WithSizeNonZero)55 TEST(HeapArray, WithSizeNonZero) {
56 auto vec = HeapArray<uint32_t>::WithSize(2u);
57 EXPECT_EQ(vec.size(), 2u);
58 EXPECT_NE(vec.data(), nullptr);
59 }
60
TEST(HeapArray,FromOwningPointer)61 TEST(HeapArray, FromOwningPointer) {
62 auto vec = UNSAFE_BUFFERS(
63 HeapArray<uint32_t>::FromOwningPointer(new uint32_t[3], 3u));
64 EXPECT_EQ(vec.size(), 3u);
65 EXPECT_NE(vec.data(), nullptr);
66 }
67
TEST(HeapArray,MoveConstructor)68 TEST(HeapArray, MoveConstructor) {
69 auto that = HeapArray<uint32_t>::WithSize(2u);
70 base::HeapArray<uint32_t> vec(std::move(that));
71 EXPECT_EQ(vec.size(), 2u);
72 EXPECT_NE(vec.data(), nullptr);
73 EXPECT_EQ(that.size(), 0u);
74 EXPECT_EQ(that.data(), nullptr);
75 }
76
TEST(HeapArray,MoveAssign)77 TEST(HeapArray, MoveAssign) {
78 auto that = HeapArray<uint32_t>::WithSize(2u);
79 auto vec = HeapArray<uint32_t>::WithSize(4u);
80 vec = std::move(that);
81 EXPECT_EQ(vec.size(), 2u);
82 EXPECT_NE(vec.data(), nullptr);
83 EXPECT_EQ(that.size(), 0u);
84 EXPECT_EQ(that.data(), nullptr);
85 }
86
TEST(HeapArray,DataAndIndex)87 TEST(HeapArray, DataAndIndex) {
88 HeapArray<uint32_t> empty;
89 EXPECT_EQ(nullptr, empty.data());
90
91 auto vec = HeapArray<uint32_t>::WithSize(2u);
92 vec[0] = 100u;
93 vec[1] = 101u;
94 EXPECT_EQ(vec.data()[0], 100u);
95 EXPECT_EQ(vec.data()[1], 101u);
96 }
97
TEST(HeapArray,IteratorAndIndex)98 TEST(HeapArray, IteratorAndIndex) {
99 const HeapArray<uint32_t> empty;
100 static_assert(
101 std::is_const_v<std::remove_reference_t<decltype(*empty.begin())>>);
102 static_assert(
103 std::is_const_v<std::remove_reference_t<decltype(*empty.end())>>);
104 EXPECT_EQ(empty.begin(), empty.end());
105
106 auto vec = HeapArray<uint32_t>::WithSize(2u);
107 static_assert(
108 !std::is_const_v<std::remove_reference_t<decltype(*vec.begin())>>);
109 static_assert(
110 !std::is_const_v<std::remove_reference_t<decltype(*vec.end())>>);
111 vec[0] = 100u;
112 vec[1] = 101u;
113 uint32_t expected = 100;
114 for (auto i : vec) {
115 EXPECT_EQ(i, expected);
116 ++expected;
117 }
118 EXPECT_EQ(expected, 102u);
119 }
120
TEST(HeapArrayDeathTest,BadIndex)121 TEST(HeapArrayDeathTest, BadIndex) {
122 auto vec = HeapArray<uint32_t>::WithSize(2u);
123 EXPECT_DEATH_IF_SUPPORTED(vec[2], "");
124 }
125
TEST(HeapArray,AsSpan)126 TEST(HeapArray, AsSpan) {
127 {
128 auto vec = HeapArray<uint32_t>::WithSize(2u);
129 auto s = vec.as_span();
130 static_assert(std::same_as<decltype(s), span<uint32_t>>);
131 EXPECT_EQ(s.size(), 2u);
132 EXPECT_EQ(s.data(), vec.data());
133 }
134 {
135 const auto vec = HeapArray<uint32_t>::WithSize(2u);
136 auto s = vec.as_span();
137 static_assert(std::same_as<decltype(s), span<const uint32_t>>);
138 EXPECT_EQ(s.size(), 2u);
139 EXPECT_EQ(s.data(), vec.data());
140 }
141 }
142
TEST(HeapArray,Subspan)143 TEST(HeapArray, Subspan) {
144 auto vec = HeapArray<uint32_t>::WithSize(4u);
145 for (size_t i = 0; i < vec.size(); ++i) {
146 vec[i] = i;
147 }
148 span<uint32_t> empty = vec.subspan(2, 0);
149 EXPECT_TRUE(empty.empty());
150
151 span<uint32_t> first = vec.subspan(0, 1);
152 EXPECT_EQ(first.size(), 1u);
153 EXPECT_EQ(first[0], 0u);
154
155 span<uint32_t> mids = vec.subspan(1, 2);
156 EXPECT_EQ(mids.size(), 2u);
157 EXPECT_EQ(mids[0], 1u);
158 EXPECT_EQ(mids[1], 2u);
159
160 span<uint32_t> rest = vec.subspan(3);
161 EXPECT_EQ(rest.size(), 1u);
162 EXPECT_EQ(rest[0], 3u);
163 }
164
TEST(HeapArray,First)165 TEST(HeapArray, First) {
166 auto vec = HeapArray<uint32_t>::WithSize(4u);
167 for (size_t i = 0; i < vec.size(); ++i) {
168 vec[i] = i;
169 }
170 span<uint32_t> empty = vec.first(0u);
171 EXPECT_TRUE(empty.empty());
172
173 span<uint32_t> some = vec.first(2u);
174 EXPECT_EQ(some.size(), 2u);
175 EXPECT_EQ(some[0], 0u);
176 EXPECT_EQ(some[1], 1u);
177 }
178
TEST(HeapArray,Last)179 TEST(HeapArray, Last) {
180 auto vec = HeapArray<uint32_t>::WithSize(4u);
181 for (size_t i = 0; i < vec.size(); ++i) {
182 vec[i] = i;
183 }
184 span<uint32_t> empty = vec.first(0u);
185 EXPECT_TRUE(empty.empty());
186
187 span<uint32_t> some = vec.first(2u);
188 EXPECT_EQ(some.size(), 2u);
189 EXPECT_EQ(some[0], 0u);
190 EXPECT_EQ(some[1], 1u);
191 }
192
TEST(HeapArray,Init)193 TEST(HeapArray, Init) {
194 auto vec = HeapArray<uint32_t>::WithSize(200);
195 EXPECT_EQ(0u, vec[0]);
196 EXPECT_EQ(0u, vec[199]);
197
198 uint32_t accumulator = 0;
199 for (auto i : vec) {
200 accumulator |= i;
201 }
202 EXPECT_EQ(0u, accumulator);
203 }
204
TEST(HeapArray,Uninit)205 TEST(HeapArray, Uninit) {
206 auto vec = HeapArray<uint32_t>::Uninit(4);
207 vec[0] = 100u;
208 vec[1] = 101u;
209 EXPECT_EQ(100u, vec[0]);
210 EXPECT_EQ(101u, vec[1]);
211 #if defined(MEMORY_SANITIZER)
212 // TODO(tsepez): figure out how to get a msan crash here.
213 // volatile uint32_t* x = vec.data() + 2;
214 // EXPECT_DEATH(*x, "");
215 #endif
216 }
217
TEST(HeapArray,Fill)218 TEST(HeapArray, Fill) {
219 auto vec = HeapArray<uint32_t>::Uninit(4);
220 std::ranges::fill(vec, 0x76543210);
221 EXPECT_EQ(0x76543210u, vec[0]);
222 EXPECT_EQ(0x76543210u, vec[1]);
223 EXPECT_EQ(0x76543210u, vec[2]);
224 EXPECT_EQ(0x76543210u, vec[3]);
225 }
226
TEST(HeapArray,CopiedFrom)227 TEST(HeapArray, CopiedFrom) {
228 span<uint32_t> empty_span;
229 auto empty_vec = HeapArray<uint32_t>::CopiedFrom(empty_span);
230 EXPECT_EQ(0u, empty_vec.size());
231
232 const uint32_t kData[] = {1000u, 1001u};
233 auto vec = HeapArray<uint32_t>::CopiedFrom(kData);
234 ASSERT_EQ(2u, vec.size());
235 EXPECT_EQ(1000u, vec[0]);
236 EXPECT_EQ(1001u, vec[1]);
237 }
238
TEST(HeapArray,RunsDestructor)239 TEST(HeapArray, RunsDestructor) {
240 size_t count = 0;
241 {
242 auto vec = HeapArray<DestructCounter>::WithSize(2);
243 vec[0].set_where(&count);
244 vec[1].set_where(&count);
245 EXPECT_EQ(count, 0u);
246 }
247 EXPECT_EQ(count, 2u);
248 }
249
TEST(HeapArray,CopyFrom)250 TEST(HeapArray, CopyFrom) {
251 HeapArray<uint32_t> empty;
252 HeapArray<uint32_t> something = HeapArray<uint32_t>::Uninit(2);
253 HeapArray<uint32_t> other = HeapArray<uint32_t>::Uninit(2);
254 const uint32_t kStuff[] = {1000u, 1001u};
255
256 empty.copy_from(span<uint32_t>()); // Should not check.
257 something.copy_from(kStuff);
258 EXPECT_EQ(1000u, something[0]);
259 EXPECT_EQ(1001u, something[1]);
260
261 other.copy_from(something);
262 EXPECT_EQ(1000u, other[0]);
263 EXPECT_EQ(1001u, other[1]);
264 }
265
TEST(HeapArray,Leak)266 TEST(HeapArray, Leak) {
267 size_t count = 0;
268 span<DestructCounter> leaked;
269 {
270 auto vec = HeapArray<DestructCounter>::WithSize(2);
271 vec[0].set_where(&count);
272 vec[1].set_where(&count);
273
274 auto* data = vec.data();
275 leaked = std::move(vec).leak();
276 ASSERT_EQ(data, leaked.data());
277 EXPECT_EQ(count, 0u);
278 }
279 EXPECT_EQ(count, 0u);
280 CStyleInvoker(HeapArray<DestructCounter>::DeleteLeakedData, leaked.data());
281 EXPECT_EQ(count, 2u);
282 }
283
284 } // namespace base
285