test/core/gprpp/inlined_vector_test.cc

   1 /*
   2  *
   3  * Copyright 2017 gRPC authors.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  *     http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  *
  17  */
  18
  19 #include "src/core/lib/gprpp/inlined_vector.h"
  20 #include <grpc/support/log.h>
  21 #include <gtest/gtest.h>
  22 #include "src/core/lib/gprpp/memory.h"
  23 #include "test/core/util/test_config.h"
  24
  25 namespace grpc_core {
  26 namespace testing {
  27 namespace {
  28
  29 template <typename Vector>
  30 static void FillVector(Vector* v, int len, int start = 0) {
  31   for (int i = 0; i < len; i++) {
  32     v->push_back(i + start);
  33     EXPECT_EQ(i + 1UL, v->size());
  34   }
  35   EXPECT_EQ(static_cast<size_t>(len), v->size());
  36   EXPECT_LE(static_cast<size_t>(len), v->capacity());
  37 }
  38
  39 }  // namespace
  40
  41 TEST(InlinedVectorTest, CreateAndIterate) {
  42   const int kNumElements = 9;
  43   InlinedVector<int, 2> v;
  44   EXPECT_TRUE(v.empty());
  45   FillVector(&v, kNumElements);
  46   EXPECT_EQ(static_cast<size_t>(kNumElements), v.size());
  47   EXPECT_FALSE(v.empty());
  48   for (int i = 0; i < kNumElements; ++i) {
  49     EXPECT_EQ(i, v[i]);
  50     EXPECT_EQ(i, &v[i] - &v[0]);  // Ensure contiguous allocation.
  51   }
  52 }
  53
  54 TEST(InlinedVectorTest, ValuesAreInlined) {
  55   const int kNumElements = 5;
  56   InlinedVector<int, 10> v;
  57   FillVector(&v, kNumElements);
  58   EXPECT_EQ(static_cast<size_t>(kNumElements), v.size());
  59   for (int i = 0; i < kNumElements; ++i) {
  60     EXPECT_EQ(i, v[i]);
  61   }
  62 }
  63
  64 TEST(InlinedVectorTest, PushBackWithMove) {
  65   InlinedVector<UniquePtr<int>, 1> v;
  66   UniquePtr<int> i = MakeUnique<int>(3);
  67   v.push_back(std::move(i));
  68   EXPECT_EQ(nullptr, i.get());
  69   EXPECT_EQ(1UL, v.size());
  70   EXPECT_EQ(3, *v[0]);
  71 }
  72
  73 TEST(InlinedVectorTest, EmplaceBack) {
  74   InlinedVector<UniquePtr<int>, 1> v;
  75   v.emplace_back(New<int>(3));
  76   EXPECT_EQ(1UL, v.size());
  77   EXPECT_EQ(3, *v[0]);
  78 }
  79
  80 TEST(InlinedVectorTest, ClearAndRepopulate) {
  81   const int kNumElements = 10;
  82   InlinedVector<int, 5> v;
  83   EXPECT_EQ(0UL, v.size());
  84   FillVector(&v, kNumElements);
  85   for (int i = 0; i < kNumElements; ++i) {
  86     EXPECT_EQ(i, v[i]);
  87   }
  88   v.clear();
  89   EXPECT_EQ(0UL, v.size());
  90   FillVector(&v, kNumElements, kNumElements);
  91   for (int i = 0; i < kNumElements; ++i) {
  92     EXPECT_EQ(kNumElements + i, v[i]);
  93   }
  94 }
  95
  96 TEST(InlinedVectorTest, ConstIndexOperator) {
  97   constexpr int kNumElements = 10;
  98   InlinedVector<int, 5> v;
  99   EXPECT_EQ(0UL, v.size());
 100   FillVector(&v, kNumElements);
 101   // The following lambda function is exceptionally allowed to use an anonymous
 102   // capture due to the erroneous behavior of the MSVC compiler, that refuses to
 103   // capture the kNumElements constexpr, something allowed by the standard.
 104   auto const_func = [&](const InlinedVector<int, 5>& v) {
 105     for (int i = 0; i < kNumElements; ++i) {
 106       EXPECT_EQ(i, v[i]);
 107     }
 108   };
 109   const_func(v);
 110 }
 111
 112 // the following constants and typedefs are used for copy/move
 113 // construction/assignment
 114 const size_t kInlinedLength = 8;
 115 typedef InlinedVector<int, kInlinedLength> IntVec8;
 116 const size_t kInlinedFillSize = kInlinedLength - 1;
 117 const size_t kAllocatedFillSize = kInlinedLength + 1;
 118
 119 TEST(InlinedVectorTest, CopyConstructorInlined) {
 120   IntVec8 original;
 121   FillVector(&original, kInlinedFillSize);
 122   IntVec8 copy_constructed(original);
 123   for (size_t i = 0; i < original.size(); ++i) {
 124     EXPECT_EQ(original[i], copy_constructed[i]);
 125   }
 126 }
 127
 128 TEST(InlinedVectorTest, CopyConstructorAllocated) {
 129   IntVec8 original;
 130   FillVector(&original, kAllocatedFillSize);
 131   IntVec8 copy_constructed(original);
 132   for (size_t i = 0; i < original.size(); ++i) {
 133     EXPECT_EQ(original[i], copy_constructed[i]);
 134   }
 135 }
 136
 137 TEST(InlinedVectorTest, CopyAssignementInlinedInlined) {
 138   IntVec8 original;
 139   FillVector(&original, kInlinedFillSize);
 140   IntVec8 copy_assigned;
 141   FillVector(&copy_assigned, kInlinedFillSize, 99);
 142   copy_assigned = original;
 143   for (size_t i = 0; i < original.size(); ++i) {
 144     EXPECT_EQ(original[i], copy_assigned[i]);
 145   }
 146 }
 147
 148 TEST(InlinedVectorTest, CopyAssignementInlinedAllocated) {
 149   IntVec8 original;
 150   FillVector(&original, kInlinedFillSize);
 151   IntVec8 copy_assigned;
 152   FillVector(&copy_assigned, kAllocatedFillSize, 99);
 153   copy_assigned = original;
 154   for (size_t i = 0; i < original.size(); ++i) {
 155     EXPECT_EQ(original[i], copy_assigned[i]);
 156   }
 157 }
 158
 159 TEST(InlinedVectorTest, CopyAssignementAllocatedInlined) {
 160   IntVec8 original;
 161   FillVector(&original, kAllocatedFillSize);
 162   IntVec8 copy_assigned;
 163   FillVector(&copy_assigned, kInlinedFillSize, 99);
 164   copy_assigned = original;
 165   for (size_t i = 0; i < original.size(); ++i) {
 166     EXPECT_EQ(original[i], copy_assigned[i]);
 167   }
 168 }
 169
 170 TEST(InlinedVectorTest, CopyAssignementAllocatedAllocated) {
 171   IntVec8 original;
 172   FillVector(&original, kAllocatedFillSize);
 173   IntVec8 copy_assigned;
 174   FillVector(&copy_assigned, kAllocatedFillSize, 99);
 175   copy_assigned = original;
 176   for (size_t i = 0; i < original.size(); ++i) {
 177     EXPECT_EQ(original[i], copy_assigned[i]);
 178   }
 179 }
 180
 181 TEST(InlinedVectorTest, MoveConstructorInlined) {
 182   IntVec8 original;
 183   FillVector(&original, kInlinedFillSize);
 184   IntVec8 tmp(original);
 185   auto* old_data = tmp.data();
 186   IntVec8 move_constructed(std::move(tmp));
 187   for (size_t i = 0; i < original.size(); ++i) {
 188     EXPECT_EQ(original[i], move_constructed[i]);
 189   }
 190   // original data was inlined so it should have been copied, not moved.
 191   EXPECT_NE(move_constructed.data(), old_data);
 192 }
 193
 194 TEST(InlinedVectorTest, MoveConstructorAllocated) {
 195   IntVec8 original;
 196   FillVector(&original, kAllocatedFillSize);
 197   IntVec8 tmp(original);
 198   auto* old_data = tmp.data();
 199   IntVec8 move_constructed(std::move(tmp));
 200   for (size_t i = 0; i < original.size(); ++i) {
 201     EXPECT_EQ(original[i], move_constructed[i]);
 202   }
 203   // original data was allocated, so it should been moved, not copied
 204   EXPECT_EQ(move_constructed.data(), old_data);
 205 }
 206
 207 TEST(InlinedVectorTest, MoveAssignmentInlinedInlined) {
 208   IntVec8 original;
 209   FillVector(&original, kInlinedFillSize);
 210   IntVec8 move_assigned;
 211   FillVector(&move_assigned, kInlinedFillSize, 99);  // Add dummy elements
 212   IntVec8 tmp(original);
 213   auto* old_data = tmp.data();
 214   move_assigned = std::move(tmp);
 215   for (size_t i = 0; i < original.size(); ++i) {
 216     EXPECT_EQ(original[i], move_assigned[i]);
 217   }
 218   // original data was inlined so it should have been copied, not moved.
 219   EXPECT_NE(move_assigned.data(), old_data);
 220 }
 221
 222 TEST(InlinedVectorTest, MoveAssignmentInlinedAllocated) {
 223   IntVec8 original;
 224   FillVector(&original, kInlinedFillSize);
 225   IntVec8 move_assigned;
 226   FillVector(&move_assigned, kAllocatedFillSize, 99);  // Add dummy elements
 227   IntVec8 tmp(original);
 228   auto* old_data = tmp.data();
 229   move_assigned = std::move(tmp);
 230   for (size_t i = 0; i < original.size(); ++i) {
 231     EXPECT_EQ(original[i], move_assigned[i]);
 232   }
 233   // original data was inlined so it should have been copied, not moved.
 234   EXPECT_NE(move_assigned.data(), old_data);
 235 }
 236
 237 TEST(InlinedVectorTest, MoveAssignmentAllocatedInlined) {
 238   IntVec8 original;
 239   FillVector(&original, kAllocatedFillSize);
 240   IntVec8 move_assigned;
 241   FillVector(&move_assigned, kInlinedFillSize, 99);  // Add dummy elements
 242   IntVec8 tmp(original);
 243   auto* old_data = tmp.data();
 244   move_assigned = std::move(tmp);
 245   for (size_t i = 0; i < original.size(); ++i) {
 246     EXPECT_EQ(original[i], move_assigned[i]);
 247   }
 248   // original data was allocated so it should have been moved, not copied.
 249   EXPECT_EQ(move_assigned.data(), old_data);
 250 }
 251
 252 TEST(InlinedVectorTest, MoveAssignmentAllocatedAllocated) {
 253   IntVec8 original;
 254   FillVector(&original, kAllocatedFillSize);
 255   IntVec8 move_assigned;
 256   FillVector(&move_assigned, kAllocatedFillSize, 99);  // Add dummy elements
 257   IntVec8 tmp(original);
 258   auto* old_data = tmp.data();
 259   move_assigned = std::move(tmp);
 260   for (size_t i = 0; i < original.size(); ++i) {
 261     EXPECT_EQ(original[i], move_assigned[i]);
 262   }
 263   // original data was allocated so it should have been moved, not copied.
 264   EXPECT_EQ(move_assigned.data(), old_data);
 265 }
 266
 267 // A copyable and movable value class, used to test that elements' copy
 268 // and move methods are called correctly.
 269 class Value {
 270  public:
 271   explicit Value(int v) : value_(MakeUnique<int>(v)) {}
 272
 273   // copyable
 274   Value(const Value& v) {
 275     value_ = MakeUnique<int>(*v.value_);
 276     copied_ = true;
 277   }
 278   Value& operator=(const Value& v) {
 279     value_ = MakeUnique<int>(*v.value_);
 280     copied_ = true;
 281     return *this;
 282   }
 283
 284   // movable
 285   Value(Value&& v) {
 286     value_ = std::move(v.value_);
 287     moved_ = true;
 288   }
 289   Value& operator=(Value&& v) {
 290     value_ = std::move(v.value_);
 291     moved_ = true;
 292     return *this;
 293   }
 294
 295   const UniquePtr<int>& value() const { return value_; }
 296   bool copied() const { return copied_; }
 297   bool moved() const { return moved_; }
 298
 299  private:
 300   UniquePtr<int> value_;
 301   bool copied_ = false;
 302   bool moved_ = false;
 303 };
 304
 305 TEST(InlinedVectorTest, CopyConstructorCopiesElementsInlined) {
 306   InlinedVector<Value, 1> v1;
 307   v1.emplace_back(3);
 308   InlinedVector<Value, 1> v2(v1);
 309   EXPECT_EQ(v2.size(), 1UL);
 310   EXPECT_EQ(*v2[0].value(), 3);
 311   // Addresses should differ.
 312   EXPECT_NE(v1[0].value().get(), v2[0].value().get());
 313   EXPECT_TRUE(v2[0].copied());
 314 }
 315
 316 TEST(InlinedVectorTest, CopyConstructorCopiesElementsAllocated) {
 317   InlinedVector<Value, 1> v1;
 318   v1.reserve(2);
 319   v1.emplace_back(3);
 320   v1.emplace_back(5);
 321   InlinedVector<Value, 1> v2(v1);
 322   EXPECT_EQ(v2.size(), 2UL);
 323   EXPECT_EQ(*v2[0].value(), 3);
 324   EXPECT_EQ(*v2[1].value(), 5);
 325   // Addresses should differ.
 326   EXPECT_NE(v1[0].value().get(), v2[0].value().get());
 327   EXPECT_NE(v1[1].value().get(), v2[1].value().get());
 328   EXPECT_TRUE(v2[0].copied());
 329   EXPECT_TRUE(v2[1].copied());
 330 }
 331
 332 TEST(InlinedVectorTest, CopyAssignmentCopiesElementsInlined) {
 333   InlinedVector<Value, 1> v1;
 334   v1.emplace_back(3);
 335   InlinedVector<Value, 1> v2;
 336   EXPECT_EQ(v2.size(), 0UL);
 337   v2 = v1;
 338   EXPECT_EQ(v2.size(), 1UL);
 339   EXPECT_EQ(*v2[0].value(), 3);
 340   // Addresses should differ.
 341   EXPECT_NE(v1[0].value().get(), v2[0].value().get());
 342   EXPECT_TRUE(v2[0].copied());
 343 }
 344
 345 TEST(InlinedVectorTest, CopyAssignmentCopiesElementsAllocated) {
 346   InlinedVector<Value, 1> v1;
 347   v1.reserve(2);
 348   v1.emplace_back(3);
 349   v1.emplace_back(5);
 350   InlinedVector<Value, 1> v2;
 351   EXPECT_EQ(v2.size(), 0UL);
 352   v2 = v1;
 353   EXPECT_EQ(v2.size(), 2UL);
 354   EXPECT_EQ(*v2[0].value(), 3);
 355   EXPECT_EQ(*v2[1].value(), 5);
 356   // Addresses should differ.
 357   EXPECT_NE(v1[0].value().get(), v2[0].value().get());
 358   EXPECT_NE(v1[1].value().get(), v2[1].value().get());
 359   EXPECT_TRUE(v2[0].copied());
 360   EXPECT_TRUE(v2[1].copied());
 361 }
 362
 363 TEST(InlinedVectorTest, MoveConstructorMovesElementsInlined) {
 364   InlinedVector<Value, 1> v1;
 365   v1.emplace_back(3);
 366   int* addr = v1[0].value().get();
 367   InlinedVector<Value, 1> v2(std::move(v1));
 368   EXPECT_EQ(v2.size(), 1UL);
 369   EXPECT_EQ(*v2[0].value(), 3);
 370   EXPECT_EQ(addr, v2[0].value().get());
 371   EXPECT_TRUE(v2[0].moved());
 372 }
 373
 374 TEST(InlinedVectorTest, MoveConstructorMovesElementsAllocated) {
 375   InlinedVector<Value, 1> v1;
 376   v1.reserve(2);
 377   v1.emplace_back(3);
 378   v1.emplace_back(5);
 379   int* addr1 = v1[0].value().get();
 380   int* addr2 = v1[1].value().get();
 381   Value* data1 = v1.data();
 382   InlinedVector<Value, 1> v2(std::move(v1));
 383   EXPECT_EQ(v2.size(), 2UL);
 384   EXPECT_EQ(*v2[0].value(), 3);
 385   EXPECT_EQ(*v2[1].value(), 5);
 386   EXPECT_EQ(addr1, v2[0].value().get());
 387   EXPECT_EQ(addr2, v2[1].value().get());
 388   // In this case, elements won't be moved, because we have just stolen
 389   // the underlying storage.
 390   EXPECT_EQ(data1, v2.data());
 391 }
 392
 393 TEST(InlinedVectorTest, MoveAssignmentMovesElementsInlined) {
 394   InlinedVector<Value, 1> v1;
 395   v1.emplace_back(3);
 396   int* addr = v1[0].value().get();
 397   InlinedVector<Value, 1> v2;
 398   EXPECT_EQ(v2.size(), 0UL);
 399   v2 = std::move(v1);
 400   EXPECT_EQ(v2.size(), 1UL);
 401   EXPECT_EQ(*v2[0].value(), 3);
 402   EXPECT_EQ(addr, v2[0].value().get());
 403   EXPECT_TRUE(v2[0].moved());
 404 }
 405
 406 TEST(InlinedVectorTest, MoveAssignmentMovesElementsAllocated) {
 407   InlinedVector<Value, 1> v1;
 408   v1.reserve(2);
 409   v1.emplace_back(3);
 410   v1.emplace_back(5);
 411   int* addr1 = v1[0].value().get();
 412   int* addr2 = v1[1].value().get();
 413   Value* data1 = v1.data();
 414   InlinedVector<Value, 1> v2;
 415   EXPECT_EQ(v2.size(), 0UL);
 416   v2 = std::move(v1);
 417   EXPECT_EQ(v2.size(), 2UL);
 418   EXPECT_EQ(*v2[0].value(), 3);
 419   EXPECT_EQ(*v2[1].value(), 5);
 420   EXPECT_EQ(addr1, v2[0].value().get());
 421   EXPECT_EQ(addr2, v2[1].value().get());
 422   // In this case, elements won't be moved, because we have just stolen
 423   // the underlying storage.
 424   EXPECT_EQ(data1, v2.data());
 425 }
 426
 427 TEST(InlinedVectorTest, PopBackInlined) {
 428   InlinedVector<UniquePtr<int>, 2> v;
 429   // Add two elements, pop one out
 430   v.push_back(MakeUnique<int>(3));
 431   EXPECT_EQ(1UL, v.size());
 432   EXPECT_EQ(3, *v[0]);
 433   v.push_back(MakeUnique<int>(5));
 434   EXPECT_EQ(2UL, v.size());
 435   EXPECT_EQ(5, *v[1]);
 436   v.pop_back();
 437   EXPECT_EQ(1UL, v.size());
 438 }
 439
 440 TEST(InlinedVectorTest, PopBackAllocated) {
 441   const int kInlinedSize = 2;
 442   InlinedVector<UniquePtr<int>, kInlinedSize> v;
 443   // Add elements to ensure allocated backing.
 444   for (size_t i = 0; i < kInlinedSize + 1; ++i) {
 445     v.push_back(MakeUnique<int>(3));
 446     EXPECT_EQ(i + 1, v.size());
 447   }
 448   size_t sz = v.size();
 449   v.pop_back();
 450   EXPECT_EQ(sz - 1, v.size());
 451 }
 452
 453 }  // namespace testing
 454 }  // namespace grpc_core
 455
 456 int main(int argc, char** argv) {
 457   grpc::testing::TestEnvironment env(argc, argv);
 458   ::testing::InitGoogleTest(&argc, argv);
 459   return RUN_ALL_TESTS();
 460 }