Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -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 | |
Dominik Laskowski | 5444fc8 | 2020-11-24 13:41:10 -0800 | [diff] [blame] | 17 | #include <ftl/small_vector.h> |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 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. |
| 32 | TEST(SmallVector, Example) { |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 33 | ftl::SmallVector<char, 3> vector; |
| 34 | EXPECT_TRUE(vector.empty()); |
| 35 | EXPECT_FALSE(vector.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 36 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 37 | vector = {'a', 'b', 'c'}; |
| 38 | EXPECT_EQ(vector.size(), 3u); |
| 39 | EXPECT_FALSE(vector.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 40 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 41 | vector.push_back('d'); |
| 42 | EXPECT_TRUE(vector.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 43 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 44 | vector.unstable_erase(vector.begin()); |
| 45 | EXPECT_EQ(vector, (ftl::SmallVector{'d', 'b', 'c'})); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 46 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 47 | vector.pop_back(); |
| 48 | EXPECT_EQ(vector.back(), 'b'); |
| 49 | EXPECT_TRUE(vector.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 50 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 51 | const char array[] = "hi"; |
| 52 | vector = ftl::SmallVector(array); |
| 53 | EXPECT_EQ(vector, (ftl::SmallVector{'h', 'i', '\0'})); |
| 54 | EXPECT_FALSE(vector.dynamic()); |
Dominik Laskowski | ccd50a4 | 2020-10-30 19:56:38 -0700 | [diff] [blame] | 55 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 56 | ftl::SmallVector strings = ftl::init::list<std::string>("abc")("123456", 3u)(3u, '?'); |
| 57 | ASSERT_EQ(strings.size(), 3u); |
| 58 | EXPECT_FALSE(strings.dynamic()); |
Dominik Laskowski | ccd50a4 | 2020-10-30 19:56:38 -0700 | [diff] [blame] | 59 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 60 | EXPECT_EQ(strings[0], "abc"); |
| 61 | EXPECT_EQ(strings[1], "123"); |
| 62 | EXPECT_EQ(strings[2], "???"); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 63 | } |
| 64 | |
| 65 | TEST(SmallVector, Construct) { |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 66 | { |
| 67 | // Default constructor. |
| 68 | SmallVector<std::string, 2> vector; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 69 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 77 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 86 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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}; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 93 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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)}; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 103 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 112 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 123 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 134 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 139 | } |
| 140 | |
| 141 | TEST(SmallVector, String) { |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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'); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 146 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 147 | EXPECT_TRUE(chars.dynamic()); |
| 148 | EXPECT_EQ(chars.size(), 11u); |
| 149 | EXPECT_STREQ(chars.begin(), "abcdefghij"); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 150 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 151 | // Constructor takes iterator range. |
| 152 | const char numbers[] = "123456"; |
| 153 | SmallVector<char, 10> string(std::begin(numbers), std::end(numbers)); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 154 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 155 | EXPECT_FALSE(string.dynamic()); |
| 156 | EXPECT_STREQ(string.begin(), "123456"); |
| 157 | EXPECT_EQ(string.size(), 7u); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 158 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 159 | // Similar to emplace, but replaces rather than inserts. |
| 160 | string.replace(string.begin() + 5, '\0'); |
| 161 | EXPECT_STREQ(string.begin(), "12345"); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 162 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 163 | swap(chars, string); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 164 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 165 | EXPECT_STREQ(chars.begin(), "12345"); |
| 166 | EXPECT_STREQ(string.begin(), "abcdefghij"); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 167 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 168 | EXPECT_FALSE(chars.dynamic()); |
| 169 | EXPECT_TRUE(string.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 170 | } |
| 171 | |
| 172 | TEST(SmallVector, CopyableElement) { |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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) {} |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 176 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 177 | const int a, b; |
| 178 | bool operator==(Pair p) const { return p.a == a && p.b == b; } |
| 179 | }; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 180 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 181 | SmallVector<Pair, 5> pairs; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 182 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 183 | EXPECT_TRUE(pairs.empty()); |
| 184 | EXPECT_EQ(pairs.max_size(), 5u); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 185 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 186 | for (size_t i = 0; i < pairs.max_size(); ++i) { |
| 187 | EXPECT_EQ(pairs.size(), i); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 188 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 189 | const int a = static_cast<int>(i) * 2; |
| 190 | EXPECT_EQ(pairs.emplace_back(a, a + 1), Pair(a, a + 1)); |
| 191 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 192 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 193 | EXPECT_EQ(pairs.size(), 5u); |
| 194 | EXPECT_FALSE(pairs.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 195 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 196 | // The vector is promoted when full. |
| 197 | EXPECT_EQ(pairs.emplace_back(10, 11), Pair(10, 11)); |
| 198 | EXPECT_TRUE(pairs.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 199 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 200 | EXPECT_EQ(pairs, (SmallVector{Pair{0, 1}, Pair{2, 3}, Pair{4, 5}, Pair{6, 7}, Pair{8, 9}, |
| 201 | Pair{10, 11}})); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 202 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 203 | // Constructor takes at most N elements. |
| 204 | SmallVector<int, 6> sums = {0, 0, 0, 0, 0, 0}; |
| 205 | EXPECT_FALSE(sums.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 206 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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})); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 210 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 211 | sums.pop_back(); |
| 212 | std::reverse(sums.begin(), sums.end()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 213 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 214 | EXPECT_EQ(sums, (SmallVector{17, 13, 9, 5, 1})); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 215 | } |
| 216 | |
| 217 | TEST(SmallVector, MovableElement) { |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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(); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 221 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 222 | EXPECT_EQ(strings.max_size(), 7u); |
| 223 | EXPECT_EQ(strings.size(), 6u); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 224 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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"); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 231 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 236 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 237 | strings[1] = "quince"s; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 238 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 243 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 244 | std::initializer_list<char> list = {'t', 'a', 'r', 't'}; |
| 245 | strings.replace(rit.base() - 1, list); |
| 246 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 247 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 248 | strings.front().assign("pie"); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 249 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 250 | EXPECT_EQ(strings, (SmallVector{"pie"s, "quince"s, "tart"s, "red"s, "velvet"s, "cake"s})); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 251 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 252 | strings.push_back("nougat"); |
| 253 | strings.push_back("oreo"); |
| 254 | EXPECT_TRUE(strings.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 255 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 256 | std::rotate(strings.begin(), strings.end() - 2, strings.end()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 257 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 258 | EXPECT_EQ(strings, (SmallVector{"nougat"s, "oreo"s, "pie"s, "quince"s, "tart"s, "red"s, "velvet"s, |
| 259 | "cake"s})); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 260 | } |
| 261 | |
| 262 | TEST(SmallVector, Replace) { |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 267 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 268 | bool operator==(const Word& other) const { return other.str == str; } |
| 269 | }; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 270 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 271 | SmallVector words = ftl::init::list<Word>("colored")("velour"); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 272 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 278 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 279 | // The vector is not promoted if replacing while full. |
| 280 | EXPECT_FALSE(words.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 281 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 282 | words.emplace_back("cake"); |
| 283 | EXPECT_TRUE(words.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 284 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 285 | { |
| 286 | const Word& word = words.replace(words.begin(), words.front().str.substr(4)); |
| 287 | EXPECT_EQ(word, Word("red")); |
| 288 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 289 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 290 | EXPECT_EQ(words, (SmallVector{Word("red"), Word("velvet"), Word("cake")})); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 291 | } |
| 292 | |
| 293 | TEST(SmallVector, ReverseAppend) { |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 294 | SmallVector strings = {"red"s, "velvet"s, "cake"s}; |
| 295 | EXPECT_FALSE(strings.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 296 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 302 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 303 | strings.push_back(std::move(s)); |
| 304 | rit = std::make_reverse_iterator(strings.begin() + i) + 1; |
| 305 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 306 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 307 | EXPECT_EQ(strings, (SmallVector{"red"s, "velvet"s, "cake"s, "cake"s, "velvet"s, "red"s})); |
| 308 | EXPECT_TRUE(strings.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 309 | } |
| 310 | |
| 311 | TEST(SmallVector, Sort) { |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 312 | SmallVector strings = ftl::init::list<std::string>("pie")("quince")("tart")("red")("velvet"); |
| 313 | strings.push_back("cake"s); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 314 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 315 | auto sorted = std::move(strings); |
| 316 | EXPECT_TRUE(strings.empty()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 317 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 318 | EXPECT_TRUE(sorted.dynamic()); |
| 319 | EXPECT_TRUE(strings.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 320 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 321 | std::sort(sorted.begin(), sorted.end()); |
| 322 | EXPECT_EQ(sorted, (SmallVector{"cake"s, "pie"s, "quince"s, "red"s, "tart"s, "velvet"s})); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 323 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 324 | // Constructor takes array reference. |
| 325 | { |
| 326 | const char* array[] = {"cake", "lie"}; |
| 327 | strings = SmallVector(array); |
| 328 | EXPECT_FALSE(strings.dynamic()); |
| 329 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 330 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 331 | EXPECT_GT(sorted, strings); |
| 332 | swap(sorted, strings); |
| 333 | EXPECT_LT(sorted, strings); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 334 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 335 | EXPECT_FALSE(sorted.dynamic()); |
| 336 | EXPECT_TRUE(strings.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 337 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 343 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 344 | EXPECT_NE(sorted, strings); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 345 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 346 | // Replace second element with "pie". |
| 347 | const auto it = sorted.begin() + 1; |
| 348 | EXPECT_EQ(sorted.replace(it, 'p' + it->substr(1)), "pie"); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 349 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 350 | EXPECT_EQ(sorted, strings); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 351 | } |
| 352 | |
| 353 | namespace { |
| 354 | |
| 355 | struct DestroyCounts { |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 356 | DestroyCounts(int& live, int& dead) : counts{live, dead} {} |
| 357 | DestroyCounts(const DestroyCounts& other) : counts(other.counts) {} |
| 358 | DestroyCounts(DestroyCounts&& other) : counts(other.counts) { other.alive = false; } |
| 359 | ~DestroyCounts() { ++(alive ? counts.live : counts.dead); } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 360 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 361 | struct { |
| 362 | int& live; |
| 363 | int& dead; |
| 364 | } counts; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 365 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 366 | bool alive = true; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 367 | }; |
| 368 | |
| 369 | void swap(DestroyCounts& lhs, DestroyCounts& rhs) { |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 370 | std::swap(lhs.alive, rhs.alive); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 371 | } |
| 372 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 373 | } // namespace |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 374 | |
| 375 | TEST(SmallVector, Destroy) { |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 376 | int live = 0; |
| 377 | int dead = 0; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 378 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 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 | |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 454 | EXPECT_EQ(0, live); |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 455 | EXPECT_EQ(1, dead); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 456 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 457 | dead = 0; |
| 458 | } |
| 459 | EXPECT_EQ(4, live); |
| 460 | EXPECT_EQ(0, dead); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 461 | } |
| 462 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 463 | } // namespace android::test |