Dominik Laskowski | 6fdf114 | 2020-10-07 12:09:09 -0700 | [diff] [blame^] | 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/StaticVector.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::StaticVector; |
| 30 | |
| 31 | // Keep in sync with example usage in header file. |
| 32 | TEST(StaticVector, Example) { |
| 33 | ftl::StaticVector<char, 3> vector; |
| 34 | EXPECT_TRUE(vector.empty()); |
| 35 | |
| 36 | vector = {'a', 'b'}; |
| 37 | EXPECT_EQ(vector.size(), 2u); |
| 38 | |
| 39 | vector.push_back('c'); |
| 40 | EXPECT_TRUE(vector.full()); |
| 41 | |
| 42 | EXPECT_FALSE(vector.push_back('d')); |
| 43 | EXPECT_EQ(vector.size(), 3u); |
| 44 | |
| 45 | vector.unstable_erase(vector.begin()); |
| 46 | EXPECT_EQ(vector, (ftl::StaticVector{'c', 'b'})); |
| 47 | |
| 48 | vector.pop_back(); |
| 49 | EXPECT_EQ(vector.back(), 'c'); |
| 50 | |
| 51 | const char array[] = "hi"; |
| 52 | vector = ftl::StaticVector(array); |
| 53 | EXPECT_EQ(vector, (ftl::StaticVector{'h', 'i', '\0'})); |
| 54 | } |
| 55 | |
| 56 | TEST(StaticVector, Construct) { |
| 57 | { |
| 58 | // Default constructor. |
| 59 | StaticVector<std::string, 2> vector; |
| 60 | EXPECT_TRUE(vector.empty()); |
| 61 | } |
| 62 | { |
| 63 | // Array constructor. |
| 64 | const float kFloats[] = {.1f, .2f, .3f}; |
| 65 | StaticVector vector(kFloats); |
| 66 | EXPECT_EQ(vector, (StaticVector{.1f, .2f, .3f})); |
| 67 | } |
| 68 | { |
| 69 | // Iterator constructor. |
| 70 | const char chars[] = "abcdef"; |
| 71 | std::string string(chars); |
| 72 | StaticVector<char, sizeof(chars)> vector(string.begin(), string.end()); |
| 73 | |
| 74 | EXPECT_STREQ(vector.begin(), chars); |
| 75 | } |
| 76 | { |
| 77 | // Variadic constructor with same types. |
| 78 | StaticVector vector = {1, 2, 3}; |
| 79 | |
| 80 | static_assert(std::is_same_v<decltype(vector), StaticVector<int, 3>>); |
| 81 | EXPECT_EQ(vector, (StaticVector{1, 2, 3})); |
| 82 | } |
| 83 | { |
| 84 | // Variadic constructor with different types. |
| 85 | const auto copy = "quince"s; |
| 86 | auto move = "tart"s; |
| 87 | StaticVector vector = {copy, std::move(move)}; |
| 88 | |
| 89 | static_assert(std::is_same_v<decltype(vector), StaticVector<std::string, 2>>); |
| 90 | EXPECT_EQ(vector, (StaticVector{"quince"s, "tart"s})); |
| 91 | } |
| 92 | { |
| 93 | // In-place constructor with same types. |
| 94 | StaticVector vector(std::in_place_type<std::string>, "red", "velvet", "cake"); |
| 95 | |
| 96 | static_assert(std::is_same_v<decltype(vector), StaticVector<std::string, 3>>); |
| 97 | EXPECT_EQ(vector, (StaticVector{"red"s, "velvet"s, "cake"s})); |
| 98 | } |
| 99 | { |
| 100 | // In-place constructor with different types. |
| 101 | const auto copy = "red"s; |
| 102 | auto move = "velvet"s; |
| 103 | std::initializer_list<char> list = {'c', 'a', 'k', 'e'}; |
| 104 | StaticVector vector(std::in_place_type<std::string>, copy.c_str(), std::move(move), list); |
| 105 | |
| 106 | static_assert(std::is_same_v<decltype(vector), StaticVector<std::string, 3>>); |
| 107 | EXPECT_EQ(vector, (StaticVector{"red"s, "velvet"s, "cake"s})); |
| 108 | } |
| 109 | } |
| 110 | |
| 111 | TEST(StaticVector, String) { |
| 112 | StaticVector<char, 10> chars; |
| 113 | char c = 'a'; |
| 114 | std::generate_n(std::back_inserter(chars), chars.max_size(), [&c] { return c++; }); |
| 115 | chars.back() = '\0'; |
| 116 | |
| 117 | EXPECT_STREQ(chars.begin(), "abcdefghi"); |
| 118 | |
| 119 | // Constructor takes iterator range. |
| 120 | const char kString[] = "123456"; |
| 121 | StaticVector<char, 10> string(std::begin(kString), std::end(kString)); |
| 122 | |
| 123 | EXPECT_STREQ(string.begin(), "123456"); |
| 124 | EXPECT_EQ(string.size(), 7u); |
| 125 | |
| 126 | // Similar to emplace, but replaces rather than inserts. |
| 127 | const auto it = string.replace(string.begin() + 5, '\0'); |
| 128 | EXPECT_NE(it, string.end()); |
| 129 | EXPECT_STREQ(string.begin(), "12345"); |
| 130 | |
| 131 | swap(chars, string); |
| 132 | |
| 133 | EXPECT_STREQ(chars.begin(), "12345"); |
| 134 | EXPECT_STREQ(string.begin(), "abcdefghi"); |
| 135 | } |
| 136 | |
| 137 | TEST(StaticVector, CopyableElement) { |
| 138 | struct Pair { |
| 139 | const int a, b; |
| 140 | bool operator==(Pair p) const { return p.a == a && p.b == b; } |
| 141 | }; |
| 142 | |
| 143 | StaticVector<Pair, 5> pairs; |
| 144 | |
| 145 | EXPECT_TRUE(pairs.empty()); |
| 146 | EXPECT_EQ(pairs.max_size(), 5u); |
| 147 | |
| 148 | for (size_t i = 0; i < pairs.max_size(); ++i) { |
| 149 | EXPECT_EQ(pairs.size(), i); |
| 150 | |
| 151 | const int a = static_cast<int>(i) * 2; |
| 152 | const auto it = pairs.emplace_back(a, a + 1); |
| 153 | ASSERT_NE(it, pairs.end()); |
| 154 | EXPECT_EQ(*it, (Pair{a, a + 1})); |
| 155 | } |
| 156 | |
| 157 | EXPECT_TRUE(pairs.full()); |
| 158 | EXPECT_EQ(pairs.size(), 5u); |
| 159 | |
| 160 | // Insertion fails if the vector is full. |
| 161 | const auto it = pairs.emplace_back(10, 11); |
| 162 | EXPECT_EQ(it, pairs.end()); |
| 163 | |
| 164 | EXPECT_EQ(pairs, (StaticVector{Pair{0, 1}, Pair{2, 3}, Pair{4, 5}, Pair{6, 7}, Pair{8, 9}})); |
| 165 | |
| 166 | // Constructor takes at most N elements. |
| 167 | StaticVector<int, 6> sums = {0, 0, 0, 0, 0, -1}; |
| 168 | EXPECT_TRUE(sums.full()); |
| 169 | |
| 170 | // Random-access iterators comply with standard. |
| 171 | std::transform(pairs.begin(), pairs.end(), sums.begin(), [](Pair p) { return p.a + p.b; }); |
| 172 | EXPECT_EQ(sums, (StaticVector{1, 5, 9, 13, 17, -1})); |
| 173 | |
| 174 | sums.pop_back(); |
| 175 | std::reverse(sums.begin(), sums.end()); |
| 176 | |
| 177 | EXPECT_EQ(sums, (StaticVector{17, 13, 9, 5, 1})); |
| 178 | } |
| 179 | |
| 180 | TEST(StaticVector, MovableElement) { |
| 181 | // Construct std::string elements in-place from C-style strings. Without std::in_place_type, the |
| 182 | // element type would be deduced from the first element, i.e. const char*. |
| 183 | StaticVector strings(std::in_place_type<std::string>, "", "", "", "cake", "velvet", "red", ""); |
| 184 | strings.pop_back(); |
| 185 | |
| 186 | EXPECT_EQ(strings.max_size(), 7u); |
| 187 | EXPECT_EQ(strings.size(), 6u); |
| 188 | |
| 189 | // Erase "cake" and append a substring copy. |
| 190 | { |
| 191 | auto it = std::find_if(strings.begin(), strings.end(), |
| 192 | [](const auto& s) { return !s.empty(); }); |
| 193 | ASSERT_FALSE(it == strings.end()); |
| 194 | EXPECT_EQ(*it, "cake"); |
| 195 | |
| 196 | strings.unstable_erase(it); |
| 197 | |
| 198 | // Construct std::string from first 4 characters of C-style string. |
| 199 | it = strings.emplace_back("cakewalk", 4u); |
| 200 | ASSERT_NE(it, strings.end()); |
| 201 | EXPECT_EQ(*it, "cake"s); |
| 202 | } |
| 203 | |
| 204 | strings[1] = "quince"s; |
| 205 | |
| 206 | // Replace last empty string with "tart". |
| 207 | { |
| 208 | const auto rit = std::find(strings.rbegin(), strings.rend(), std::string()); |
| 209 | ASSERT_FALSE(rit == strings.rend()); |
| 210 | |
| 211 | std::initializer_list<char> list = {'t', 'a', 'r', 't'}; |
| 212 | const auto it = strings.replace(rit.base() - 1, list); |
| 213 | EXPECT_NE(it, strings.end()); |
| 214 | } |
| 215 | |
| 216 | strings.front().assign("pie"); |
| 217 | |
| 218 | EXPECT_EQ(strings, (StaticVector{"pie"s, "quince"s, "tart"s, "red"s, "velvet"s, "cake"s})); |
| 219 | } |
| 220 | |
| 221 | TEST(StaticVector, ReverseTruncate) { |
| 222 | StaticVector<std::string, 10> strings("pie", "quince", "tart", "red", "velvet", "cake"); |
| 223 | EXPECT_FALSE(strings.full()); |
| 224 | |
| 225 | for (auto it = strings.begin(); it != strings.end(); ++it) { |
| 226 | strings.replace(it, strings.back()); |
| 227 | strings.pop_back(); |
| 228 | } |
| 229 | |
| 230 | EXPECT_EQ(strings, (StaticVector{"cake"s, "velvet"s, "red"s})); |
| 231 | } |
| 232 | |
| 233 | TEST(StaticVector, Sort) { |
| 234 | StaticVector<std::string, 7> strings("pie", "quince", "tart", "red", "velvet", "cake"); |
| 235 | EXPECT_FALSE(strings.full()); |
| 236 | |
| 237 | auto sorted = std::move(strings); |
| 238 | EXPECT_TRUE(strings.empty()); |
| 239 | |
| 240 | std::sort(sorted.begin(), sorted.end()); |
| 241 | EXPECT_EQ(sorted, (StaticVector{"cake"s, "pie"s, "quince"s, "red"s, "tart"s, "velvet"s})); |
| 242 | |
| 243 | // Constructor takes array reference. |
| 244 | { |
| 245 | const char* kStrings[] = {"cake", "lie"}; |
| 246 | strings = StaticVector(kStrings); |
| 247 | } |
| 248 | |
| 249 | EXPECT_GT(sorted, strings); |
| 250 | swap(sorted, strings); |
| 251 | EXPECT_LT(sorted, strings); |
| 252 | |
| 253 | // Append remaining elements, such that "pie" is the only difference. |
| 254 | sorted.replace(sorted.end(), "quince"); |
| 255 | for (const char* str : {"red", "tart", "velvet"}) sorted.emplace_back(str); |
| 256 | |
| 257 | EXPECT_NE(sorted, strings); |
| 258 | |
| 259 | sorted.replace(sorted.begin() + 1, "pie"); |
| 260 | EXPECT_EQ(sorted, strings); |
| 261 | } |
| 262 | |
| 263 | namespace { |
| 264 | |
| 265 | struct DestroyCounts { |
| 266 | DestroyCounts(int& live, int& dead) : counts{live, dead} {} |
| 267 | DestroyCounts(const DestroyCounts& other) : counts(other.counts) {} |
| 268 | DestroyCounts(DestroyCounts&& other) : counts(other.counts) { other.alive = false; } |
| 269 | ~DestroyCounts() { ++(alive ? counts.live : counts.dead); } |
| 270 | |
| 271 | struct { |
| 272 | int& live; |
| 273 | int& dead; |
| 274 | } counts; |
| 275 | |
| 276 | bool alive = true; |
| 277 | }; |
| 278 | |
| 279 | void swap(DestroyCounts& lhs, DestroyCounts& rhs) { |
| 280 | std::swap(lhs.alive, rhs.alive); |
| 281 | } |
| 282 | |
| 283 | } // namespace |
| 284 | |
| 285 | TEST(StaticVector, Destroy) { |
| 286 | int live = 0; |
| 287 | int dead = 0; |
| 288 | |
| 289 | { StaticVector<DestroyCounts, 5> counts; } |
| 290 | EXPECT_EQ(0, live); |
| 291 | EXPECT_EQ(0, dead); |
| 292 | |
| 293 | { |
| 294 | StaticVector<DestroyCounts, 5> counts; |
| 295 | counts.emplace_back(live, dead); |
| 296 | counts.emplace_back(live, dead); |
| 297 | counts.emplace_back(live, dead); |
| 298 | } |
| 299 | EXPECT_EQ(3, live); |
| 300 | EXPECT_EQ(0, dead); |
| 301 | |
| 302 | live = 0; |
| 303 | { |
| 304 | StaticVector<DestroyCounts, 5> counts; |
| 305 | counts.emplace_back(live, dead); |
| 306 | counts.emplace_back(live, dead); |
| 307 | counts.emplace_back(live, dead); |
| 308 | |
| 309 | auto copy = counts; |
| 310 | } |
| 311 | EXPECT_EQ(6, live); |
| 312 | EXPECT_EQ(0, dead); |
| 313 | |
| 314 | live = 0; |
| 315 | { |
| 316 | StaticVector<DestroyCounts, 5> counts; |
| 317 | counts.emplace_back(live, dead); |
| 318 | counts.emplace_back(live, dead); |
| 319 | counts.emplace_back(live, dead); |
| 320 | |
| 321 | auto move = std::move(counts); |
| 322 | } |
| 323 | EXPECT_EQ(3, live); |
| 324 | EXPECT_EQ(3, dead); |
| 325 | |
| 326 | live = dead = 0; |
| 327 | { |
| 328 | StaticVector<DestroyCounts, 5> counts1; |
| 329 | counts1.emplace_back(live, dead); |
| 330 | counts1.emplace_back(live, dead); |
| 331 | counts1.emplace_back(live, dead); |
| 332 | |
| 333 | StaticVector<DestroyCounts, 5> counts2; |
| 334 | counts2.emplace_back(live, dead); |
| 335 | |
| 336 | swap(counts1, counts2); |
| 337 | |
| 338 | EXPECT_EQ(0, live); |
| 339 | EXPECT_EQ(2, dead); |
| 340 | |
| 341 | dead = 0; |
| 342 | } |
| 343 | EXPECT_EQ(4, live); |
| 344 | EXPECT_EQ(0, dead); |
| 345 | } |
| 346 | |
| 347 | } // namespace android::test |