jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice, this
9 * list of conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
21 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
22 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
23 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include <AK/TestSuite.h>
28
29#include <AK/String.h>
30#include <AK/NonnullOwnPtrVector.h>
31#include <AK/OwnPtr.h>
32#include <AK/Vector.h>
33
34TEST_CASE(construct)
35{
36 EXPECT(Vector<int>().is_empty());
37 EXPECT(Vector<int>().size() == 0);
38}
39
40TEST_CASE(ints)
41{
42 Vector<int> ints;
43 ints.append(1);
44 ints.append(2);
45 ints.append(3);
46 EXPECT_EQ(ints.size(), 3u);
47 EXPECT_EQ(ints.take_last(), 3);
48 EXPECT_EQ(ints.size(), 2u);
49 EXPECT_EQ(ints.take_last(), 2);
50 EXPECT_EQ(ints.size(), 1u);
51 EXPECT_EQ(ints.take_last(), 1);
52 EXPECT_EQ(ints.size(), 0u);
53
54 ints.clear();
55 EXPECT_EQ(ints.size(), 0u);
56}
57
58TEST_CASE(strings)
59{
60 Vector<String> strings;
61 strings.append("ABC");
62 strings.append("DEF");
63
64 int loop_counter = 0;
65 for (const String& string : strings) {
66 EXPECT(!string.is_null());
67 EXPECT(!string.is_empty());
68 ++loop_counter;
69 }
70
71 loop_counter = 0;
72 for (auto& string : (const_cast<const Vector<String>&>(strings))) {
73 EXPECT(!string.is_null());
74 EXPECT(!string.is_empty());
75 ++loop_counter;
76 }
77 EXPECT_EQ(loop_counter, 2);
78}
79
80TEST_CASE(strings_insert_ordered)
81{
82 Vector<String> strings;
83 strings.append("abc");
84 strings.append("def");
85 strings.append("ghi");
86
87 strings.insert_before_matching("f-g", [](auto& entry) {
88 return "f-g" < entry;
89 });
90
91 EXPECT_EQ(strings[0], "abc");
92 EXPECT_EQ(strings[1], "def");
93 EXPECT_EQ(strings[2], "f-g");
94 EXPECT_EQ(strings[3], "ghi");
95}
96
97TEST_CASE(prepend_vector)
98{
99 Vector<int> ints;
100 ints.append(1);
101 ints.append(2);
102 ints.append(3);
103
104 Vector<int> more_ints;
105 more_ints.append(4);
106 more_ints.append(5);
107 more_ints.append(6);
108
109 ints.prepend(move(more_ints));
110
111 EXPECT_EQ(ints.size(), 6u);
112 EXPECT_EQ(more_ints.size(), 0u);
113
114 EXPECT_EQ(ints[0], 4);
115 EXPECT_EQ(ints[1], 5);
116 EXPECT_EQ(ints[2], 6);
117 EXPECT_EQ(ints[3], 1);
118 EXPECT_EQ(ints[4], 2);
119 EXPECT_EQ(ints[5], 3);
120
121 ints.prepend(move(more_ints));
122 EXPECT_EQ(ints.size(), 6u);
123 EXPECT_EQ(more_ints.size(), 0u);
124
125 more_ints.prepend(move(ints));
126 EXPECT_EQ(more_ints.size(), 6u);
127 EXPECT_EQ(ints.size(), 0u);
128}
129
130TEST_CASE(prepend_vector_object)
131{
132 struct SubObject {
133 SubObject(int v)
134 : value(v)
135 {
136 }
137 int value { 0 };
138 };
139 struct Object {
140 Object(NonnullOwnPtr<SubObject>&& a_subobject)
141 : subobject(move(a_subobject))
142 {
143 }
144 OwnPtr<SubObject> subobject;
145 };
146
147 Vector<Object> objects;
148 objects.empend(make<SubObject>(1));
149 objects.empend(make<SubObject>(2));
150 objects.empend(make<SubObject>(3));
151
152 EXPECT_EQ(objects.size(), 3u);
153
154 Vector<Object> more_objects;
155 more_objects.empend(make<SubObject>(4));
156 more_objects.empend(make<SubObject>(5));
157 more_objects.empend(make<SubObject>(6));
158 EXPECT_EQ(more_objects.size(), 3u);
159
160 objects.prepend(move(more_objects));
161 EXPECT_EQ(more_objects.size(), 0u);
162 EXPECT_EQ(objects.size(), 6u);
163
164 EXPECT_EQ(objects[0].subobject->value, 4);
165 EXPECT_EQ(objects[1].subobject->value, 5);
166 EXPECT_EQ(objects[2].subobject->value, 6);
167 EXPECT_EQ(objects[3].subobject->value, 1);
168 EXPECT_EQ(objects[4].subobject->value, 2);
169 EXPECT_EQ(objects[5].subobject->value, 3);
170}
171
172TEST_CASE(vector_compare)
173{
174 Vector<int> ints;
175 Vector<int> same_ints;
176
177 for (int i = 0; i < 1000; ++i) {
178 ints.append(i);
179 same_ints.append(i);
180 }
181
182 EXPECT_EQ(ints.size(), 1000u);
183 EXPECT_EQ(ints, same_ints);
184
185 Vector<String> strings;
186 Vector<String> same_strings;
187
188 for (int i = 0; i < 1000; ++i) {
189 strings.append(String::number(i));
190 same_strings.append(String::number(i));
191 }
192
193 EXPECT_EQ(strings.size(), 1000u);
194 EXPECT_EQ(strings, same_strings);
195}
196
197TEST_CASE(grow_past_inline_capacity)
198{
199 auto make_vector = [] {
200 Vector<String, 16> strings;
201 for (int i = 0; i < 32; ++i) {
202 strings.append(String::number(i));
203 }
204 return strings;
205 };
206
207 auto strings = make_vector();
208
209 EXPECT_EQ(strings.size(), 32u);
210 EXPECT_EQ(strings[31], "31");
211
212 strings.clear();
213 EXPECT_EQ(strings.size(), 0u);
214 EXPECT_EQ(strings.capacity(), 16u);
215
216 strings = make_vector();
217
218 strings.clear_with_capacity();
219 EXPECT_EQ(strings.size(), 0u);
220 EXPECT(strings.capacity() >= 32u);
221}
222
223BENCHMARK_CASE(vector_append_trivial)
224{
225 // This should be super fast thanks to Vector using memmove.
226 Vector<int> ints;
227 for (int i = 0; i < 1000000; ++i) {
228 ints.append(i);
229 }
230 for (int i = 0; i < 100; ++i) {
231 Vector<int> tmp;
232 tmp.append(ints);
233 EXPECT_EQ(tmp.size(), 1000000u);
234 }
235}
236
237BENCHMARK_CASE(vector_remove_trivial)
238{
239 // This should be super fast thanks to Vector using memmove.
240 Vector<int> ints;
241 for (int i = 0; i < 10000; ++i) {
242 ints.append(i);
243 }
244 while (!ints.is_empty()) {
245 ints.remove(0);
246 }
247 EXPECT_EQ(ints.size(), 0u);
248}
249
250TEST_CASE(vector_remove)
251{
252 Vector<int> ints;
253 ints.append(1);
254 ints.append(2);
255 ints.append(3);
256 ints.append(4);
257 ints.append(5);
258
259 ints.remove(1);
260 EXPECT_EQ(ints.size(), 4u);
261 EXPECT_EQ(ints[0], 1);
262 EXPECT_EQ(ints[1], 3);
263 EXPECT_EQ(ints[2], 4);
264 EXPECT_EQ(ints[3], 5);
265
266 ints.remove(0);
267 EXPECT_EQ(ints.size(), 3u);
268 EXPECT_EQ(ints[0], 3);
269 EXPECT_EQ(ints[1], 4);
270 EXPECT_EQ(ints[2], 5);
271
272 ints.take_last();
273 EXPECT_EQ(ints.size(), 2u);
274 EXPECT_EQ(ints[0], 3);
275 EXPECT_EQ(ints[1], 4);
276
277 ints.take_first();
278 EXPECT_EQ(ints.size(), 1u);
279 EXPECT_EQ(ints[0], 4);
280}
281
282TEST_CASE(nonnullownptrvector)
283{
284 struct Object {
285 String string;
286 };
287 NonnullOwnPtrVector<Object> objects;
288
289 objects.append(make<Object>());
290 EXPECT_EQ(objects.size(), 1u);
291
292 OwnPtr<Object> o = make<Object>();
293 objects.append(o.release_nonnull());
294 EXPECT(o == nullptr);
295 EXPECT_EQ(objects.size(), 2u);
296}
297
298TEST_CASE(insert_trivial)
299{
300 Vector<int> ints;
301 ints.append(0);
302 ints.append(10);
303 ints.append(20);
304 ints.append(30);
305 ints.append(40);
306 ints.insert(2, 15);
307 EXPECT_EQ(ints.size(), 6u);
308 EXPECT_EQ(ints[0], 0);
309 EXPECT_EQ(ints[1], 10);
310 EXPECT_EQ(ints[2], 15);
311 EXPECT_EQ(ints[3], 20);
312 EXPECT_EQ(ints[4], 30);
313 EXPECT_EQ(ints[5], 40);
314}
315
316TEST_MAIN(Vector)