third_party/pigweed/repo/pw_containers/vector_test.cc

   1 // Copyright 2020 The Pigweed Authors
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
   4 // use this file except in compliance with the License. You may obtain a copy of
   5 // the License at
   6 //
   7 //     https://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  12 // License for the specific language governing permissions and limitations under
  13 // the License.
  14
  15 #include "pw_containers/vector.h"
  16
  17 #include <cstddef>
  18 #include <vector>
  19
  20 #include "gtest/gtest.h"
  21
  22 namespace pw {
  23 namespace {
  24
  25 // Since pw::Vector<T, N> downcasts to a pw::Vector<T, 0>, ensure that the
  26 // alignment doesn't change.
  27 static_assert(alignof(Vector<std::max_align_t, 0>) ==
  28               alignof(Vector<std::max_align_t, 1>));
  29
  30 struct CopyOnly {
  31   explicit CopyOnly(int val) : value(val) {}
  32
  33   CopyOnly(const CopyOnly& other) { value = other.value; }
  34
  35   CopyOnly& operator=(const CopyOnly& other) {
  36     value = other.value;
  37     return *this;
  38   }
  39
  40   CopyOnly(CopyOnly&&) = delete;
  41
  42   int value;
  43 };
  44
  45 struct MoveOnly {
  46   explicit MoveOnly(int val) : value(val) {}
  47
  48   MoveOnly(const MoveOnly&) = delete;
  49
  50   MoveOnly(MoveOnly&& other) {
  51     value = other.value;
  52     other.value = kDeleted;
  53   }
  54
  55   static constexpr int kDeleted = -1138;
  56
  57   int value;
  58 };
  59
  60 struct Counter {
  61   static int created;
  62   static int destroyed;
  63   static int moved;
  64
  65   static void Reset() { created = destroyed = moved = 0; }
  66
  67   Counter() : value(0) { created += 1; }
  68
  69   Counter(int val) : value(val) { created += 1; }
  70
  71   Counter(const Counter& other) : value(other.value) { created += 1; }
  72
  73   Counter(Counter&& other) : value(other.value) {
  74     other.value = 0;
  75     moved += 1;
  76   }
  77
  78   ~Counter() { destroyed += 1; }
  79
  80   int value;
  81 };
  82
  83 int Counter::created = 0;
  84 int Counter::destroyed = 0;
  85 int Counter::moved = 0;
  86
  87 TEST(Vector, Construct_NoArg) {
  88   Vector<int, 3> vector;
  89   EXPECT_TRUE(vector.empty());
  90 }
  91
  92 TEST(Vector, Construct_MultipleCopies) {
  93   Vector<int, 3> vector(3, 123);
  94
  95   EXPECT_EQ(vector.size(), 3u);
  96   EXPECT_EQ(vector[0], 123);
  97   EXPECT_EQ(vector[1], 123);
  98   EXPECT_EQ(vector[2], 123);
  99 }
 100
 101 TEST(Vector, Construct_DefaultSize) {
 102   Vector<int, 3> vector(3);
 103
 104   EXPECT_EQ(vector.size(), 3u);
 105   EXPECT_EQ(vector[0], 0);
 106   EXPECT_EQ(vector[1], 0);
 107   EXPECT_EQ(vector[2], 0);
 108 }
 109
 110 TEST(Vector, Construct_Iterators) {
 111   std::array array{1, 2, 3, 4, 5};
 112
 113   Vector<int, 64> vector(array.begin(), array.end());
 114
 115   EXPECT_EQ(vector.size(), array.size());
 116   for (size_t i = 0; i < array.size(); ++i) {
 117     EXPECT_EQ(vector[i], array[i]);
 118   }
 119 }
 120
 121 TEST(Vector, Construct_Copy) {
 122   CopyOnly origin(5);
 123   Vector<CopyOnly, 10> origin_vector(3, origin);
 124
 125   Vector<CopyOnly, 100> vector(origin_vector);
 126
 127   EXPECT_EQ(3u, vector.size());
 128
 129   for (size_t i = 0; i < vector.size(); ++i) {
 130     EXPECT_EQ(vector[i].value, origin.value);
 131   }
 132 }
 133
 134 TEST(Vector, Construct_Move) {
 135   Vector<MoveOnly, 10> origin_vector;
 136
 137   for (int i = 0; i < 5; ++i) {
 138     origin_vector.emplace_back(421);
 139   }
 140
 141   Vector<MoveOnly, 100> vector(std::move(origin_vector));
 142
 143   EXPECT_EQ(5u, vector.size());
 144
 145   for (size_t i = 0; i < vector.size(); ++i) {
 146     EXPECT_EQ(vector[i].value, 421);
 147   }
 148
 149   for (size_t i = 0; i < origin_vector.size(); ++i) {
 150     EXPECT_EQ(origin_vector[i].value, MoveOnly::kDeleted);
 151   }
 152 }
 153
 154 TEST(Vector, Construct_InitializerList) {
 155   Vector<int, 3> vector{100, 200};
 156   EXPECT_EQ(vector.size(), 2u);
 157   EXPECT_EQ(vector[0], 100);
 158   EXPECT_EQ(vector[1], 200);
 159 }
 160
 161 TEST(Vector, Destruct_ZeroLength) {
 162   Counter::Reset();
 163
 164   { Vector<Counter, 0> destroyed; }
 165   EXPECT_EQ(Counter::created, 0);
 166   EXPECT_EQ(Counter::destroyed, 0);
 167 }
 168
 169 TEST(Vector, Destruct_Empty) {
 170   Counter::Reset();
 171
 172   { Vector<Counter, 128> destroyed; }
 173   EXPECT_EQ(Counter::created, 0);
 174   EXPECT_EQ(Counter::destroyed, 0);
 175 }
 176
 177 TEST(Vector, Destruct_MultpileEntries) {
 178   Counter value;
 179   Counter::Reset();
 180
 181   { Vector<Counter, 128> destroyed(100, value); }
 182
 183   EXPECT_EQ(Counter::created, 100);
 184   EXPECT_EQ(Counter::destroyed, 100);
 185 }
 186
 187 TEST(Vector, Assign_Copy_SmallerToLarger) {
 188   CopyOnly origin(5);
 189   Vector<CopyOnly, 3> origin_vector(3, origin);
 190
 191   Vector<CopyOnly, 2> vector;
 192   vector = origin_vector;
 193
 194   EXPECT_EQ(2u, vector.size());
 195
 196   for (size_t i = 0; i < vector.size(); ++i) {
 197     EXPECT_EQ(vector[i].value, origin.value);
 198   }
 199 }
 200
 201 TEST(Vector, Assign_DifferentMaxSize_Copy) {
 202   const Vector<int, 10> origin_vector = {1, 1, 2, 3};
 203
 204   Vector<int, 100> vector;
 205   vector = origin_vector;
 206
 207   ASSERT_EQ(4u, vector.size());
 208   EXPECT_EQ(1, vector[0]);
 209   EXPECT_EQ(1, vector[1]);
 210   EXPECT_EQ(2, vector[2]);
 211   EXPECT_EQ(3, vector[3]);
 212 }
 213
 214 TEST(Vector, Assign_SameMaxSize_Copy) {
 215   const Vector<int, 10> origin_vector = {1, 1, 2, 3};
 216
 217   Vector<int, 10> vector;
 218   vector = origin_vector;
 219
 220   ASSERT_EQ(4u, vector.size());
 221   EXPECT_EQ(1, vector[0]);
 222   EXPECT_EQ(1, vector[1]);
 223   EXPECT_EQ(2, vector[2]);
 224   EXPECT_EQ(3, vector[3]);
 225 }
 226
 227 TEST(Vector, Assign_Generic_Copy) {
 228   const Vector<int, 10> origin_vector = {1, 1, 2, 3};
 229
 230   Vector<int, 10> vector;
 231   Vector<int>& ref = vector;
 232   ref = static_cast<const Vector<int>&>(origin_vector);
 233
 234   ASSERT_EQ(4u, vector.size());
 235   EXPECT_EQ(1, vector[0]);
 236   EXPECT_EQ(1, vector[1]);
 237   EXPECT_EQ(2, vector[2]);
 238   EXPECT_EQ(3, vector[3]);
 239 }
 240
 241 TEST(Vector, Assign_Move) {
 242   Vector<MoveOnly, 10> origin_vector;
 243
 244   for (int i = 0; i < 5; ++i) {
 245     origin_vector.emplace_back(421);
 246   }
 247
 248   Vector<MoveOnly, 10> vector;
 249   vector = std::move(origin_vector);
 250
 251   EXPECT_EQ(5u, vector.size());
 252
 253   for (size_t i = 0; i < vector.size(); ++i) {
 254     EXPECT_EQ(vector[i].value, 421);
 255   }
 256
 257   for (size_t i = 0; i < origin_vector.size(); ++i) {
 258     EXPECT_EQ(origin_vector[i].value, MoveOnly::kDeleted);
 259   }
 260 }
 261
 262 TEST(Vector, Assign_InitializerList) {
 263   Vector<int, 4> vector;
 264   vector = {1, 3, 5, 7, 9};
 265
 266   EXPECT_EQ(4u, vector.size());
 267
 268   EXPECT_EQ(1, vector[0]);
 269   EXPECT_EQ(3, vector[1]);
 270   EXPECT_EQ(5, vector[2]);
 271   EXPECT_EQ(7, vector[3]);
 272 }
 273
 274 TEST(Vector, Access_ZeroLength) {
 275   Vector<Counter, 0> vector;
 276
 277   EXPECT_EQ(0u, vector.size());
 278   EXPECT_EQ(0u, vector.max_size());
 279   EXPECT_TRUE(vector.empty());
 280   EXPECT_TRUE(vector.full());
 281
 282   for (auto& item : vector) {
 283     (void)item;
 284     FAIL();
 285   }
 286 }
 287
 288 TEST(Vector, Access_Data_ArrayLocationIsIndependentOfMaxSize) {
 289   Vector<int, 10> vector;
 290   Vector<int>& base = static_cast<Vector<int>&>(vector);
 291
 292   EXPECT_EQ(vector.data(), base.data());
 293   EXPECT_EQ(vector.data(), (static_cast<Vector<int, 0>&>(base).data()));
 294   EXPECT_EQ(vector.data(), (static_cast<Vector<int, 1>&>(base).data()));
 295 }
 296
 297 TEST(Vector, Modify_Clear) {
 298   Counter::Reset();
 299
 300   Vector<Counter, 100> vector;
 301   vector.emplace_back();
 302   vector.emplace_back();
 303   vector.emplace_back();
 304
 305   vector.clear();
 306
 307   EXPECT_EQ(3, Counter::created);
 308   EXPECT_EQ(3, Counter::destroyed);
 309 }
 310
 311 TEST(Vector, Modify_PushBack_Copy) {
 312   Counter value(99);
 313   Counter::Reset();
 314
 315   {
 316     Vector<Counter, 10> vector;
 317     vector.push_back(value);
 318
 319     EXPECT_EQ(vector.size(), 1u);
 320     EXPECT_EQ(vector.front().value, 99);
 321   }
 322
 323   EXPECT_EQ(Counter::created, 1);
 324   EXPECT_EQ(Counter::destroyed, 1);
 325 }
 326
 327 TEST(Vector, Modify_PushBack_Move) {
 328   Counter::Reset();
 329
 330   {
 331     Counter value(99);
 332     Vector<Counter, 10> vector;
 333     vector.push_back(std::move(value));
 334
 335     EXPECT_EQ(vector.size(), 1u);
 336     EXPECT_EQ(vector.front().value, 99);
 337     EXPECT_EQ(value.value, 0);
 338   }
 339
 340   EXPECT_EQ(Counter::created, 1);
 341   EXPECT_EQ(Counter::destroyed, 2);
 342   EXPECT_EQ(Counter::moved, 1);
 343 }
 344
 345 TEST(Vector, Modify_EmplaceBack) {
 346   Counter::Reset();
 347
 348   {
 349     Vector<Counter, 10> vector;
 350     vector.emplace_back(314);
 351
 352     EXPECT_EQ(vector.size(), 1u);
 353     EXPECT_EQ(vector.front().value, 314);
 354   }
 355
 356   EXPECT_EQ(Counter::created, 1);
 357   EXPECT_EQ(Counter::destroyed, 1);
 358 }
 359
 360 TEST(Vector, Modify_Resize_Larger) {
 361   Vector<CopyOnly, 10> vector(1, CopyOnly(123));
 362   vector.resize(3, CopyOnly(123));
 363
 364   EXPECT_EQ(vector.size(), 3u);
 365   for (auto& i : vector) {
 366     EXPECT_EQ(i.value, 123);
 367   }
 368 }
 369
 370 TEST(Vector, Modify_Resize_LargerThanMax) {
 371   Vector<CopyOnly, 10> vector;
 372   vector.resize(1000, CopyOnly(123));
 373
 374   EXPECT_EQ(vector.size(), 10u);
 375   for (auto& i : vector) {
 376     EXPECT_EQ(i.value, 123);
 377   }
 378 }
 379
 380 TEST(Vector, Modify_Resize_Smaller) {
 381   Vector<CopyOnly, 10> vector(9, CopyOnly(123));
 382   vector.resize(3, CopyOnly(123));
 383
 384   EXPECT_EQ(vector.size(), 3u);
 385   for (auto& i : vector) {
 386     EXPECT_EQ(i.value, 123);
 387   }
 388 }
 389
 390 TEST(Vector, Modify_PopBack) {
 391   Vector<Counter, 10> vector({Counter(1), Counter(2), Counter(3)});
 392   Counter::Reset();
 393
 394   vector.pop_back();
 395
 396   EXPECT_EQ(vector.size(), 2u);
 397   EXPECT_EQ(vector[0].value, 1);
 398   EXPECT_EQ(vector[1].value, 2);
 399
 400   EXPECT_EQ(Counter::created, 0);
 401   EXPECT_EQ(Counter::destroyed, 1);
 402 }
 403
 404 TEST(Vector, Modify_Resize_Zero) {
 405   Vector<CopyOnly, 10> vector(10, CopyOnly(123));
 406   vector.resize(0, CopyOnly(123));
 407
 408   EXPECT_EQ(vector.size(), 0u);
 409 }
 410
 411 TEST(Vector, Generic) {
 412   Vector<int, 10> vector{1, 2, 3, 4, 5};
 413
 414   Vector<int>& generic_vector(vector);
 415
 416   EXPECT_EQ(generic_vector.size(), vector.size());
 417   EXPECT_EQ(generic_vector.max_size(), vector.max_size());
 418
 419   int i = 0;
 420   for (int value : vector) {
 421     EXPECT_EQ(value, generic_vector[i]);
 422     i += 1;
 423   }
 424
 425   i = 0;
 426   for (int value : generic_vector) {
 427     EXPECT_EQ(vector[i], value);
 428     i += 1;
 429   }
 430 }
 431
 432 }  // namespace
 433 }  // namespace pw