1 /*
2  * Copyright 2020 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include <ftl/small_vector.h>
18 #include <gtest/gtest.h>
19 
20 #include <algorithm>
21 #include <iterator>
22 #include <string>
23 #include <utility>
24 
25 using namespace std::string_literals;
26 
27 namespace android::test {
28 
29 using ftl::SmallVector;
30 
31 // Keep in sync with example usage in header file.
TEST(SmallVector,Example)32 TEST(SmallVector, Example) {
33   ftl::SmallVector<char, 3> vector;
34   EXPECT_TRUE(vector.empty());
35   EXPECT_FALSE(vector.dynamic());
36 
37   vector = {'a', 'b', 'c'};
38   EXPECT_EQ(vector.size(), 3u);
39   EXPECT_FALSE(vector.dynamic());
40 
41   vector.push_back('d');
42   EXPECT_TRUE(vector.dynamic());
43 
44   vector.unstable_erase(vector.begin());
45   EXPECT_EQ(vector, (ftl::SmallVector{'d', 'b', 'c'}));
46 
47   vector.pop_back();
48   EXPECT_EQ(vector.back(), 'b');
49   EXPECT_TRUE(vector.dynamic());
50 
51   const char array[] = "hi";
52   vector = ftl::SmallVector(array);
53   EXPECT_EQ(vector, (ftl::SmallVector{'h', 'i', '\0'}));
54   EXPECT_FALSE(vector.dynamic());
55 
56   ftl::SmallVector strings = ftl::init::list<std::string>("abc")("123456", 3u)(3u, '?');
57   ASSERT_EQ(strings.size(), 3u);
58   EXPECT_FALSE(strings.dynamic());
59 
60   EXPECT_EQ(strings[0], "abc");
61   EXPECT_EQ(strings[1], "123");
62   EXPECT_EQ(strings[2], "???");
63 }
64 
TEST(SmallVector,Construct)65 TEST(SmallVector, Construct) {
66   {
67     // Default constructor.
68     SmallVector<std::string, 2> vector;
69 
70     EXPECT_TRUE(vector.empty());
71     EXPECT_FALSE(vector.dynamic());
72   }
73   {
74     // Array constructor.
75     const float floats[] = {.1f, .2f, .3f};
76     SmallVector vector(floats);
77 
78     EXPECT_EQ(vector, (SmallVector{.1f, .2f, .3f}));
79     EXPECT_FALSE(vector.dynamic());
80   }
81   {
82     // Iterator constructor.
83     const char chars[] = "abcdef";
84     std::string string(chars);
85     SmallVector<char, sizeof(chars)> vector(string.begin(), string.end());
86 
87     EXPECT_STREQ(vector.begin(), chars);
88     EXPECT_FALSE(vector.dynamic());
89   }
90   {
91     // Variadic constructor with same types.
92     SmallVector vector = {1, 2, 3};
93 
94     static_assert(std::is_same_v<decltype(vector), SmallVector<int, 3>>);
95     EXPECT_EQ(vector, (SmallVector{1, 2, 3}));
96     EXPECT_FALSE(vector.dynamic());
97   }
98   {
99     // Variadic constructor with different types.
100     const auto copy = "quince"s;
101     auto move = "tart"s;
102     SmallVector vector = {copy, std::move(move)};
103 
104     static_assert(std::is_same_v<decltype(vector), SmallVector<std::string, 2>>);
105     EXPECT_EQ(vector, (SmallVector{"quince"s, "tart"s}));
106     EXPECT_FALSE(vector.dynamic());
107   }
108   {
109     // In-place constructor with same types.
110     SmallVector vector =
111         ftl::init::list<std::string>("redolent", 3u)("velveteen", 6u)("cakewalk", 4u);
112 
113     static_assert(std::is_same_v<decltype(vector), SmallVector<std::string, 3>>);
114     EXPECT_EQ(vector, (SmallVector{"red"s, "velvet"s, "cake"s}));
115     EXPECT_FALSE(vector.dynamic());
116   }
117   {
118     // In-place constructor with different types.
119     const auto copy = "red"s;
120     auto move = "velvet"s;
121     std::initializer_list<char> list = {'c', 'a', 'k', 'e'};
122     SmallVector vector = ftl::init::list<std::string>(copy.c_str())(std::move(move))(list);
123 
124     static_assert(std::is_same_v<decltype(vector), SmallVector<std::string, 3>>);
125     EXPECT_TRUE(move.empty());
126     EXPECT_EQ(vector, (SmallVector{"red"s, "velvet"s, "cake"s}));
127     EXPECT_FALSE(vector.dynamic());
128   }
129   {
130     // Conversion from StaticVector.
131     ftl::StaticVector doubles = {.1, .2, .3};
132     SmallVector vector = std::move(doubles);
133     EXPECT_TRUE(doubles.empty());
134 
135     static_assert(std::is_same_v<decltype(vector), SmallVector<double, 3>>);
136     EXPECT_EQ(vector, (SmallVector{.1, .2, .3}));
137     EXPECT_FALSE(vector.dynamic());
138   }
139 }
140 
TEST(SmallVector,String)141 TEST(SmallVector, String) {
142   SmallVector<char, 10> chars;
143   char c = 'a';
144   std::generate_n(std::back_inserter(chars), chars.max_size(), [&c] { return c++; });
145   chars.push_back('\0');
146 
147   EXPECT_TRUE(chars.dynamic());
148   EXPECT_EQ(chars.size(), 11u);
149   EXPECT_STREQ(chars.begin(), "abcdefghij");
150 
151   // Constructor takes iterator range.
152   const char numbers[] = "123456";
153   SmallVector<char, 10> string(std::begin(numbers), std::end(numbers));
154 
155   EXPECT_FALSE(string.dynamic());
156   EXPECT_STREQ(string.begin(), "123456");
157   EXPECT_EQ(string.size(), 7u);
158 
159   // Similar to emplace, but replaces rather than inserts.
160   string.replace(string.begin() + 5, '\0');
161   EXPECT_STREQ(string.begin(), "12345");
162 
163   swap(chars, string);
164 
165   EXPECT_STREQ(chars.begin(), "12345");
166   EXPECT_STREQ(string.begin(), "abcdefghij");
167 
168   EXPECT_FALSE(chars.dynamic());
169   EXPECT_TRUE(string.dynamic());
170 }
171 
TEST(SmallVector,CopyableElement)172 TEST(SmallVector, CopyableElement) {
173   struct Pair {
174     // Needed because std::vector does not use list initialization to emplace.
175     Pair(int a, int b) : a(a), b(b) {}
176 
177     const int a, b;
178     bool operator==(Pair p) const { return p.a == a && p.b == b; }
179   };
180 
181   SmallVector<Pair, 5> pairs;
182 
183   EXPECT_TRUE(pairs.empty());
184   EXPECT_EQ(pairs.max_size(), 5u);
185 
186   for (size_t i = 0; i < pairs.max_size(); ++i) {
187     EXPECT_EQ(pairs.size(), i);
188 
189     const int a = static_cast<int>(i) * 2;
190     EXPECT_EQ(pairs.emplace_back(a, a + 1), Pair(a, a + 1));
191   }
192 
193   EXPECT_EQ(pairs.size(), 5u);
194   EXPECT_FALSE(pairs.dynamic());
195 
196   // The vector is promoted when full.
197   EXPECT_EQ(pairs.emplace_back(10, 11), Pair(10, 11));
198   EXPECT_TRUE(pairs.dynamic());
199 
200   EXPECT_EQ(pairs, (SmallVector{Pair{0, 1}, Pair{2, 3}, Pair{4, 5}, Pair{6, 7}, Pair{8, 9},
201                                 Pair{10, 11}}));
202 
203   // Constructor takes at most N elements.
204   SmallVector<int, 6> sums = {0, 0, 0, 0, 0, 0};
205   EXPECT_FALSE(sums.dynamic());
206 
207   // Random-access iterators comply with standard.
208   std::transform(pairs.begin(), pairs.end(), sums.begin(), [](Pair p) { return p.a + p.b; });
209   EXPECT_EQ(sums, (SmallVector{1, 5, 9, 13, 17, 21}));
210 
211   sums.pop_back();
212   std::reverse(sums.begin(), sums.end());
213 
214   EXPECT_EQ(sums, (SmallVector{17, 13, 9, 5, 1}));
215 }
216 
TEST(SmallVector,MovableElement)217 TEST(SmallVector, MovableElement) {
218   // Construct std::string elements in place from per-element arguments.
219   SmallVector strings = ftl::init::list<std::string>()()()("cake")("velvet")("red")();
220   strings.pop_back();
221 
222   EXPECT_EQ(strings.max_size(), 7u);
223   EXPECT_EQ(strings.size(), 6u);
224 
225   // Erase "cake" and append a substring copy.
226   {
227     const auto it =
228         std::find_if(strings.begin(), strings.end(), [](const auto& s) { return !s.empty(); });
229     ASSERT_FALSE(it == strings.end());
230     EXPECT_EQ(*it, "cake");
231 
232     // Construct std::string from first 4 characters of string literal.
233     strings.unstable_erase(it);
234     EXPECT_EQ(strings.emplace_back("cakewalk", 4u), "cake"s);
235   }
236 
237   strings[1] = "quince"s;
238 
239   // Replace last empty string with "tart".
240   {
241     const auto rit = std::find(strings.rbegin(), strings.rend(), std::string());
242     ASSERT_FALSE(rit == strings.rend());
243 
244     std::initializer_list<char> list = {'t', 'a', 'r', 't'};
245     strings.replace(rit.base() - 1, list);
246   }
247 
248   strings.front().assign("pie");
249 
250   EXPECT_EQ(strings, (SmallVector{"pie"s, "quince"s, "tart"s, "red"s, "velvet"s, "cake"s}));
251 
252   strings.push_back("nougat");
253   strings.push_back("oreo");
254   EXPECT_TRUE(strings.dynamic());
255 
256   std::rotate(strings.begin(), strings.end() - 2, strings.end());
257 
258   EXPECT_EQ(strings, (SmallVector{"nougat"s, "oreo"s, "pie"s, "quince"s, "tart"s, "red"s, "velvet"s,
259                                   "cake"s}));
260 }
261 
TEST(SmallVector,Replace)262 TEST(SmallVector, Replace) {
263   // Replacing does not require a copy/move assignment operator.
264   struct Word {
265     explicit Word(std::string str) : str(std::move(str)) {}
266     const std::string str;
267 
268     bool operator==(const Word& other) const { return other.str == str; }
269   };
270 
271   SmallVector words = ftl::init::list<Word>("colored")("velour");
272 
273   // The replaced element can be referenced by the replacement.
274   {
275     const Word& word = words.replace(words.last(), words.back().str.substr(0, 3) + "vet");
276     EXPECT_EQ(word, Word("velvet"));
277   }
278 
279   // The vector is not promoted if replacing while full.
280   EXPECT_FALSE(words.dynamic());
281 
282   words.emplace_back("cake");
283   EXPECT_TRUE(words.dynamic());
284 
285   {
286     const Word& word = words.replace(words.begin(), words.front().str.substr(4));
287     EXPECT_EQ(word, Word("red"));
288   }
289 
290   EXPECT_EQ(words, (SmallVector{Word("red"), Word("velvet"), Word("cake")}));
291 }
292 
TEST(SmallVector,ReverseAppend)293 TEST(SmallVector, ReverseAppend) {
294   SmallVector strings = {"red"s, "velvet"s, "cake"s};
295   EXPECT_FALSE(strings.dynamic());
296 
297   auto rit = strings.rbegin();
298   while (rit != strings.rend()) {
299     // Iterator and reference are invalidated on insertion.
300     const auto i = std::distance(strings.begin(), rit.base());
301     std::string s = *rit;
302 
303     strings.push_back(std::move(s));
304     rit = std::make_reverse_iterator(strings.begin() + i) + 1;
305   }
306 
307   EXPECT_EQ(strings, (SmallVector{"red"s, "velvet"s, "cake"s, "cake"s, "velvet"s, "red"s}));
308   EXPECT_TRUE(strings.dynamic());
309 }
310 
TEST(SmallVector,Sort)311 TEST(SmallVector, Sort) {
312   SmallVector strings = ftl::init::list<std::string>("pie")("quince")("tart")("red")("velvet");
313   strings.push_back("cake"s);
314 
315   auto sorted = std::move(strings);
316   EXPECT_TRUE(strings.empty());
317 
318   EXPECT_TRUE(sorted.dynamic());
319   EXPECT_TRUE(strings.dynamic());
320 
321   std::sort(sorted.begin(), sorted.end());
322   EXPECT_EQ(sorted, (SmallVector{"cake"s, "pie"s, "quince"s, "red"s, "tart"s, "velvet"s}));
323 
324   // Constructor takes array reference.
325   {
326     const char* array[] = {"cake", "lie"};
327     strings = SmallVector(array);
328     EXPECT_FALSE(strings.dynamic());
329   }
330 
331   EXPECT_GT(sorted, strings);
332   swap(sorted, strings);
333   EXPECT_LT(sorted, strings);
334 
335   EXPECT_FALSE(sorted.dynamic());
336   EXPECT_TRUE(strings.dynamic());
337 
338   // Append remaining elements, such that "pie" is the only difference.
339   for (const char* str : {"quince", "red", "tart", "velvet"}) {
340     sorted.emplace_back(str);
341   }
342   EXPECT_TRUE(sorted.dynamic());
343 
344   EXPECT_NE(sorted, strings);
345 
346   // Replace second element with "pie".
347   const auto it = sorted.begin() + 1;
348   EXPECT_EQ(sorted.replace(it, 'p' + it->substr(1)), "pie");
349 
350   EXPECT_EQ(sorted, strings);
351 }
352 
353 namespace {
354 
355 struct DestroyCounts {
DestroyCountsandroid::test::__anonbde1e03a0410::DestroyCounts356   DestroyCounts(int& live, int& dead) : counts{live, dead} {}
DestroyCountsandroid::test::__anonbde1e03a0410::DestroyCounts357   DestroyCounts(const DestroyCounts& other) : counts(other.counts) {}
DestroyCountsandroid::test::__anonbde1e03a0410::DestroyCounts358   DestroyCounts(DestroyCounts&& other) : counts(other.counts) { other.alive = false; }
~DestroyCountsandroid::test::__anonbde1e03a0410::DestroyCounts359   ~DestroyCounts() { ++(alive ? counts.live : counts.dead); }
360 
361   struct {
362     int& live;
363     int& dead;
364   } counts;
365 
366   bool alive = true;
367 };
368 
swap(DestroyCounts & lhs,DestroyCounts & rhs)369 void swap(DestroyCounts& lhs, DestroyCounts& rhs) {
370   std::swap(lhs.alive, rhs.alive);
371 }
372 
373 }  // namespace
374 
TEST(SmallVector,Destroy)375 TEST(SmallVector, Destroy) {
376   int live = 0;
377   int dead = 0;
378 
379   { SmallVector<DestroyCounts, 3> counts; }
380   EXPECT_EQ(0, live);
381   EXPECT_EQ(0, dead);
382 
383   {
384     SmallVector<DestroyCounts, 3> counts;
385     counts.emplace_back(live, dead);
386     counts.emplace_back(live, dead);
387     counts.emplace_back(live, dead);
388 
389     EXPECT_FALSE(counts.dynamic());
390   }
391   EXPECT_EQ(3, live);
392   EXPECT_EQ(0, dead);
393 
394   live = 0;
395   {
396     SmallVector<DestroyCounts, 3> counts;
397     counts.emplace_back(live, dead);
398     counts.emplace_back(live, dead);
399     counts.emplace_back(live, dead);
400     counts.emplace_back(live, dead);
401 
402     EXPECT_TRUE(counts.dynamic());
403   }
404   EXPECT_EQ(4, live);
405   EXPECT_EQ(3, dead);
406 
407   live = dead = 0;
408   {
409     SmallVector<DestroyCounts, 2> counts;
410     counts.emplace_back(live, dead);
411     counts.emplace_back(live, dead);
412     counts.emplace_back(live, dead);
413 
414     auto copy = counts;
415     EXPECT_TRUE(copy.dynamic());
416   }
417   EXPECT_EQ(6, live);
418   EXPECT_EQ(2, dead);
419 
420   live = dead = 0;
421   {
422     SmallVector<DestroyCounts, 2> counts;
423     counts.emplace_back(live, dead);
424     counts.emplace_back(live, dead);
425     counts.emplace_back(live, dead);
426 
427     auto move = std::move(counts);
428     EXPECT_TRUE(move.dynamic());
429   }
430   EXPECT_EQ(3, live);
431   EXPECT_EQ(2, dead);
432 
433   live = dead = 0;
434   {
435     SmallVector<DestroyCounts, 2> counts1;
436     counts1.emplace_back(live, dead);
437     counts1.emplace_back(live, dead);
438     counts1.emplace_back(live, dead);
439 
440     EXPECT_TRUE(counts1.dynamic());
441     EXPECT_EQ(2, dead);
442     dead = 0;
443 
444     SmallVector<DestroyCounts, 2> counts2;
445     counts2.emplace_back(live, dead);
446 
447     EXPECT_FALSE(counts2.dynamic());
448 
449     swap(counts1, counts2);
450 
451     EXPECT_FALSE(counts1.dynamic());
452     EXPECT_TRUE(counts2.dynamic());
453 
454     EXPECT_EQ(0, live);
455     EXPECT_EQ(1, dead);
456 
457     dead = 0;
458   }
459   EXPECT_EQ(4, live);
460   EXPECT_EQ(0, dead);
461 }
462 
463 }  // namespace android::test
464