folly/test/small_vector_test.cpp

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   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 <folly/small_vector.h>
  18
  19 #include <iostream>
  20 #include <iterator>
  21 #include <limits>
  22 #include <memory>
  23 #include <sstream>
  24 #include <string>
  25 #include <vector>
  26
  27 #include <boost/algorithm/string.hpp>
  28
  29 #include <folly/Conv.h>
  30 #include <folly/portability/GTest.h>
  31 #include <folly/portability/TypeTraits.h>
  32
  33 using folly::small_vector;
  34 using namespace folly::small_vector_policy;
  35
  36 #if FOLLY_X64 || FOLLY_PPC64
  37
  38 static_assert(sizeof(small_vector<int>) == 16,
  39               "Object size is not what we expect for small_vector<int>");
  40 static_assert(sizeof(small_vector<int32_t,2>) == 16,
  41               "Object size is not what we expect for "
  42               "small_vector<int32_t,2>");
  43 static_assert(sizeof(small_vector<int,10>) ==
  44                 10 * sizeof(int) + sizeof(std::size_t),
  45               "Object size is not what we expect for small_vector<int,10>");
  46
  47 static_assert(sizeof(small_vector<int32_t,1,uint32_t>) ==
  48                 8 + 4,
  49               "small_vector<int32_t,1,uint32_t> is wrong size");
  50 static_assert(sizeof(small_vector<int32_t,1,uint16_t>) ==
  51                 8 + 2,
  52               "small_vector<int32_t,1,uint32_t> is wrong size");
  53 static_assert(sizeof(small_vector<int32_t,1,uint8_t>) ==
  54                 8 + 1,
  55               "small_vector<int32_t,1,uint32_t> is wrong size");
  56
  57 static_assert(sizeof(small_vector<int16_t,4,uint16_t>) == 10,
  58               "Sizeof unexpectedly large");
  59
  60 #endif
  61
  62 static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(std::unique_ptr<int>),
  63               "std::unique_ptr<> is trivially copyable");
  64
  65 namespace {
  66
  67 struct NontrivialType {
  68   static int ctored;
  69   explicit NontrivialType() : a(0) {}
  70
  71   /* implicit */ NontrivialType(int a) : a(a) {
  72     ++ctored;
  73   }
  74
  75   NontrivialType(NontrivialType const& /* s */) { ++ctored; }
  76
  77   NontrivialType& operator=(NontrivialType const& o) {
  78     a = o.a;
  79     return *this;
  80   }
  81
  82   int32_t a;
  83 };
  84 static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(NontrivialType),
  85               "NontrivialType is trivially copyable");
  86
  87 int NontrivialType::ctored = 0;
  88
  89 struct TestException {};
  90
  91 int throwCounter = 1;
  92 void MaybeThrow() {
  93   if (!--throwCounter) {
  94     throw TestException();
  95   }
  96 }
  97
  98 const int kMagic = 0xdeadbeef;
  99 struct Thrower {
 100   static int alive;
 101
 102   Thrower() : magic(kMagic) {
 103     EXPECT_EQ(magic, kMagic);
 104     MaybeThrow();
 105     ++alive;
 106   }
 107   Thrower(Thrower const& other) : magic(other.magic) {
 108     EXPECT_EQ(magic, kMagic);
 109     MaybeThrow();
 110     ++alive;
 111   }
 112   ~Thrower() noexcept {
 113     EXPECT_EQ(magic, kMagic);
 114     magic = 0;
 115     --alive;
 116   }
 117
 118   Thrower& operator=(Thrower const& /* other */) {
 119     EXPECT_EQ(magic, kMagic);
 120     MaybeThrow();
 121     return *this;
 122   }
 123
 124   // This is just to try to make sure we don't get our member
 125   // functions called on uninitialized memory.
 126   int magic;
 127 };
 128
 129 int Thrower::alive = 0;
 130
 131 // Type that counts how many exist and doesn't support copy
 132 // construction.
 133 struct NoncopyableCounter {
 134   static int alive;
 135   NoncopyableCounter() {
 136     ++alive;
 137   }
 138   ~NoncopyableCounter() {
 139     --alive;
 140   }
 141   NoncopyableCounter(NoncopyableCounter&&) noexcept { ++alive; }
 142   NoncopyableCounter(NoncopyableCounter const&) = delete;
 143   NoncopyableCounter& operator=(NoncopyableCounter const&) const = delete;
 144   NoncopyableCounter& operator=(NoncopyableCounter&&) { return *this; }
 145 };
 146 int NoncopyableCounter::alive = 0;
 147
 148 static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(NoncopyableCounter),
 149               "NoncopyableCounter is trivially copyable");
 150
 151 // Check that throws don't break the basic guarantee for some cases.
 152 // Uses the method for testing exception safety described at
 153 // http://www.boost.org/community/exception_safety.html, to force all
 154 // throwing code paths to occur.
 155 struct TestBasicGuarantee {
 156   folly::small_vector<Thrower,3> vec;
 157   int const prepopulate;
 158
 159   explicit TestBasicGuarantee(int prepopulate)
 160     : prepopulate(prepopulate)
 161   {
 162     throwCounter = 1000;
 163     for (int i = 0; i < prepopulate; ++i) {
 164       vec.emplace_back();
 165     }
 166   }
 167
 168   ~TestBasicGuarantee() {
 169     throwCounter = 1000;
 170   }
 171
 172   template<class Operation>
 173   void operator()(int insertCount, Operation const& op) {
 174     bool done = false;
 175
 176     std::unique_ptr<folly::small_vector<Thrower,3> > workingVec;
 177     for (int counter = 1; !done; ++counter) {
 178       throwCounter = 1000;
 179       workingVec.reset(new folly::small_vector<Thrower,3>(vec));
 180       throwCounter = counter;
 181       EXPECT_EQ(Thrower::alive, prepopulate * 2);
 182       try {
 183         op(*workingVec);
 184         done = true;
 185       } catch (...) {
 186         // Note that the size of the vector can change if we were
 187         // inserting somewhere other than the end (it's a basic only
 188         // guarantee).  All we're testing here is that we have the
 189         // right amount of uninitialized vs initialized memory.
 190         EXPECT_EQ(Thrower::alive, workingVec->size() + vec.size());
 191         continue;
 192       }
 193
 194       // If things succeeded.
 195       EXPECT_EQ(workingVec->size(), prepopulate + insertCount);
 196       EXPECT_EQ(Thrower::alive, prepopulate * 2 + insertCount);
 197     }
 198   }
 199 };
 200
 201 }
 202
 203 TEST(small_vector, BasicGuarantee) {
 204   for (int prepop = 1; prepop < 30; ++prepop) {
 205     (TestBasicGuarantee(prepop))( // parens or a mildly vexing parse :(
 206       1,
 207       [&] (folly::small_vector<Thrower,3>& v) {
 208         v.emplace_back();
 209       }
 210     );
 211
 212     EXPECT_EQ(Thrower::alive, 0);
 213
 214     (TestBasicGuarantee(prepop))(
 215       1,
 216       [&] (folly::small_vector<Thrower,3>& v) {
 217         v.insert(v.begin(), Thrower());
 218       }
 219     );
 220
 221     EXPECT_EQ(Thrower::alive, 0);
 222
 223     (TestBasicGuarantee(prepop))(
 224       1,
 225       [&] (folly::small_vector<Thrower,3>& v) {
 226         v.insert(v.begin() + 1, Thrower());
 227       }
 228     );
 229
 230     EXPECT_EQ(Thrower::alive, 0);
 231   }
 232
 233   TestBasicGuarantee(4)(
 234     3,
 235     [&] (folly::small_vector<Thrower,3>& v) {
 236       std::vector<Thrower> b;
 237       b.emplace_back();
 238       b.emplace_back();
 239       b.emplace_back();
 240
 241       /*
 242        * Apparently if you do the following initializer_list instead
 243        * of the above push_back's, and one of the Throwers throws,
 244        * g++4.6 doesn't destruct the previous ones.  Heh.
 245        */
 246       //b = { Thrower(), Thrower(), Thrower() };
 247       v.insert(v.begin() + 1, b.begin(), b.end());
 248     }
 249   );
 250
 251   TestBasicGuarantee(2)(
 252     6,
 253     [&] (folly::small_vector<Thrower,3>& v) {
 254       std::vector<Thrower> b;
 255       for (int i = 0; i < 6; ++i) {
 256         b.emplace_back();
 257       }
 258
 259       v.insert(v.begin() + 1, b.begin(), b.end());
 260     }
 261   );
 262
 263   EXPECT_EQ(Thrower::alive, 0);
 264   try {
 265     throwCounter = 4;
 266     folly::small_vector<Thrower,1> p(14, Thrower());
 267   } catch (...) {
 268   }
 269   EXPECT_EQ(Thrower::alive, 0);
 270 }
 271
 272 // Run this with.
 273 // MALLOC_CONF=prof_leak:true
 274 // LD_PRELOAD=${JEMALLOC_PATH}/lib/libjemalloc.so.2
 275 // LD_PRELOAD="$LD_PRELOAD:"${UNWIND_PATH}/lib/libunwind.so.7
 276 TEST(small_vector, leak_test) {
 277   for (int j = 0; j < 1000; ++j) {
 278     folly::small_vector<int, 10> someVec(300);
 279     for (int i = 0; i < 10000; ++i) {
 280       someVec.push_back(12);
 281     }
 282   }
 283 }
 284
 285 TEST(small_vector, Insert) {
 286   folly::small_vector<int> someVec(3, 3);
 287   someVec.insert(someVec.begin(), 12, 12);
 288   EXPECT_EQ(someVec.size(), 15);
 289   for (size_t i = 0; i < someVec.size(); ++i) {
 290     if (i < 12) {
 291       EXPECT_EQ(someVec[i], 12);
 292     } else {
 293       EXPECT_EQ(someVec[i], 3);
 294     }
 295   }
 296
 297   auto oldSize = someVec.size();
 298   someVec.insert(someVec.begin() + 1, 12, 12);
 299   EXPECT_EQ(someVec.size(), oldSize + 12);
 300
 301   folly::small_vector<std::string> v1(6, "asd"), v2(7, "wat");
 302   v1.insert(v1.begin() + 1, v2.begin(), v2.end());
 303   EXPECT_TRUE(v1.size() == 6 + 7);
 304   EXPECT_EQ(v1.front(), "asd");
 305   EXPECT_EQ(v1[1], "wat");
 306 }
 307
 308 TEST(small_vector, Swap) {
 309   folly::small_vector<int,10> somethingVec, emptyVec;
 310   somethingVec.push_back(1);
 311   somethingVec.push_back(2);
 312   somethingVec.push_back(3);
 313   somethingVec.push_back(4);
 314
 315   // Swapping intern'd with intern'd.
 316   auto vec = somethingVec;
 317   EXPECT_TRUE(vec == somethingVec);
 318   EXPECT_FALSE(vec == emptyVec);
 319   EXPECT_FALSE(somethingVec == emptyVec);
 320
 321   // Swapping a heap vector with an intern vector.
 322   folly::small_vector<int,10> junkVec;
 323   junkVec.assign(12, 12);
 324   EXPECT_EQ(junkVec.size(), 12);
 325   for (auto i : junkVec) {
 326     EXPECT_EQ(i, 12);
 327   }
 328   swap(junkVec, vec);
 329   EXPECT_TRUE(junkVec == somethingVec);
 330   EXPECT_EQ(vec.size(), 12);
 331   for (auto i : vec) {
 332     EXPECT_EQ(i, 12);
 333   }
 334
 335   // Swapping two heap vectors.
 336   folly::small_vector<int,10> moreJunk(15, 15);
 337   EXPECT_EQ(moreJunk.size(), 15);
 338   for (auto i : moreJunk) {
 339     EXPECT_EQ(i, 15);
 340   }
 341   swap(vec, moreJunk);
 342   EXPECT_EQ(moreJunk.size(), 12);
 343   for (auto i : moreJunk) {
 344     EXPECT_EQ(i, 12);
 345   }
 346   EXPECT_EQ(vec.size(), 15);
 347   for (auto i : vec) {
 348     EXPECT_EQ(i, 15);
 349   }
 350
 351   // Making a vector heap, then smaller than another non-heap vector,
 352   // then swapping.
 353   folly::small_vector<int,5> shrinker, other(4, 10);
 354   shrinker = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
 355   shrinker.erase(shrinker.begin() + 2, shrinker.end());
 356   EXPECT_LT(shrinker.size(), other.size());
 357   swap(shrinker, other);
 358   EXPECT_EQ(shrinker.size(), 4);
 359   EXPECT_TRUE(boost::all(shrinker, boost::is_any_of(std::vector<int>{10})));
 360   EXPECT_TRUE((other == small_vector<int,5>{ 0, 1 }));
 361 }
 362
 363 TEST(small_vector, Emplace) {
 364   NontrivialType::ctored = 0;
 365
 366   folly::small_vector<NontrivialType> vec;
 367   vec.reserve(1024);
 368   vec.emplace_back(12);
 369   EXPECT_EQ(NontrivialType::ctored, 1);
 370   EXPECT_EQ(vec.front().a, 12);
 371   vec.emplace_back(13);
 372   EXPECT_EQ(vec.front().a, 12);
 373   EXPECT_EQ(vec.back().a, 13);
 374   EXPECT_EQ(NontrivialType::ctored, 2);
 375
 376   NontrivialType::ctored = 0;
 377   for (int i = 0; i < 120; ++i) {
 378     vec.emplace_back(i);
 379   }
 380   EXPECT_EQ(NontrivialType::ctored, 120);
 381   EXPECT_EQ(vec[0].a, 12);
 382   EXPECT_EQ(vec[1].a, 13);
 383   EXPECT_EQ(vec.back().a, 119);
 384
 385   // We implement emplace() with a temporary (see the implementation
 386   // for a comment about why), so this should make 2 ctor calls.
 387   NontrivialType::ctored = 0;
 388   vec.emplace(vec.begin(), 12);
 389   EXPECT_EQ(NontrivialType::ctored, 2);
 390 }
 391
 392 TEST(small_vector, Erase) {
 393   folly::small_vector<int,4> notherVec = { 1, 2, 3, 4, 5 };
 394   EXPECT_EQ(notherVec.front(), 1);
 395   EXPECT_EQ(notherVec.size(), 5);
 396   notherVec.erase(notherVec.begin());
 397   EXPECT_EQ(notherVec.front(), 2);
 398   EXPECT_EQ(notherVec.size(), 4);
 399   EXPECT_EQ(notherVec[2], 4);
 400   EXPECT_EQ(notherVec[3], 5);
 401   notherVec.erase(notherVec.begin() + 2);
 402   EXPECT_EQ(notherVec.size(), 3);
 403   EXPECT_EQ(notherVec[2], 5);
 404
 405   folly::small_vector<int,2> vec2 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
 406   vec2.erase(vec2.begin() + 1, vec2.end() - 1);
 407   folly::small_vector<int,2> expected = { 1, 10 };
 408   EXPECT_TRUE(vec2 == expected);
 409
 410   folly::small_vector<std::string,3> v(102, "ASD");
 411   v.resize(1024, "D");
 412   EXPECT_EQ(v.size(), 1024);
 413   EXPECT_EQ(v.back(), "D");
 414   EXPECT_EQ(v.front(), "ASD");
 415   v.resize(1);
 416   EXPECT_EQ(v.front(), "ASD");
 417   EXPECT_EQ(v.size(), 1);
 418   v.resize(0);
 419   EXPECT_TRUE(v.empty());
 420 }
 421
 422 TEST(small_vector, GrowShrinkGrow) {
 423   folly::small_vector<NontrivialType,7> vec = { 1, 2, 3, 4, 5 };
 424   std::generate_n(std::back_inserter(vec), 102, std::rand);
 425
 426   auto capacity = vec.capacity();
 427
 428   auto oldSize = vec.size();
 429   for (size_t i = 0; i < oldSize; ++i) {
 430     vec.erase(vec.begin() + (std::rand() % vec.size()));
 431     EXPECT_EQ(vec.capacity(), capacity);
 432   }
 433   EXPECT_TRUE(vec.empty());
 434
 435   EXPECT_EQ(vec.capacity(), capacity);
 436   std::generate_n(std::back_inserter(vec), 102, std::rand);
 437   EXPECT_EQ(vec.capacity(), capacity);
 438
 439   std::generate_n(std::back_inserter(vec), 4096, std::rand);
 440   EXPECT_GT(vec.capacity(), capacity);
 441
 442   vec.resize(10);
 443   vec.shrink_to_fit();
 444   EXPECT_LT(vec.capacity(), capacity);
 445   vec.resize(4);
 446   vec.shrink_to_fit();
 447   EXPECT_EQ(vec.capacity(), 7); // in situ size
 448 }
 449
 450 TEST(small_vector, Iteration) {
 451   folly::small_vector<std::string,3> vec = { "foo", "bar" };
 452   vec.push_back("blah");
 453   vec.push_back("blah2");
 454   vec.push_back("blah3");
 455   vec.erase(vec.begin() + 2);
 456
 457   std::vector<std::string> otherVec;
 458   for (auto& s : vec) {
 459     otherVec.push_back(s);
 460   }
 461   EXPECT_EQ(otherVec.size(), vec.size());
 462   if (otherVec.size() == vec.size()) {
 463     EXPECT_TRUE(std::equal(otherVec.begin(), otherVec.end(), vec.begin()));
 464   }
 465
 466   std::reverse(otherVec.begin(), otherVec.end());
 467   auto oit = otherVec.begin();
 468   auto rit = vec.crbegin();
 469   for (; rit != vec.crend(); ++oit, ++rit) {
 470     EXPECT_EQ(*oit, *rit);
 471   }
 472 }
 473
 474 TEST(small_vector, NonCopyableType) {
 475   folly::small_vector<NontrivialType,2> vec;
 476
 477   for (int i = 0; i < 10; ++i) {
 478     vec.emplace(vec.begin(), 13);
 479   }
 480   EXPECT_EQ(vec.size(), 10);
 481   auto vec2 = std::move(vec);
 482   EXPECT_EQ(vec.size(), 0);
 483   EXPECT_EQ(vec2.size(), 10);
 484   vec2.clear();
 485
 486   folly::small_vector<NoncopyableCounter,3> vec3;
 487   for (int i = 0; i < 10; ++i) {
 488     EXPECT_EQ(vec3.size(), i);
 489     EXPECT_EQ(NoncopyableCounter::alive, i);
 490     vec3.insert(vec3.begin(), NoncopyableCounter());
 491   }
 492   EXPECT_EQ(vec3.size(), 10);
 493   EXPECT_EQ(NoncopyableCounter::alive, 10);
 494
 495   vec3.insert(vec3.begin() + 3, NoncopyableCounter());
 496   EXPECT_EQ(NoncopyableCounter::alive, 11);
 497   auto vec4 = std::move(vec3);
 498   EXPECT_EQ(NoncopyableCounter::alive, 11);
 499   vec4.resize(30);
 500   EXPECT_EQ(NoncopyableCounter::alive, 30);
 501   vec4.erase(vec4.begin(), vec4.end());
 502   EXPECT_EQ(vec4.size(), 0);
 503   EXPECT_EQ(NoncopyableCounter::alive, 0);
 504 }
 505
 506 TEST(small_vector, MoveConstructor) {
 507   folly::small_vector<std::string,10> v1;
 508   v1.push_back("asd");
 509   v1.push_back("bsd");
 510   auto v2 = std::move(v1);
 511   EXPECT_EQ(v2.size(), 2);
 512   EXPECT_EQ(v2[0], "asd");
 513   EXPECT_EQ(v2[1], "bsd");
 514
 515   v1 = std::move(v2);
 516   EXPECT_EQ(v1.size(), 2);
 517   EXPECT_EQ(v1[0], "asd");
 518   EXPECT_EQ(v1[1], "bsd");
 519 }
 520
 521 TEST(small_vector, NoHeap) {
 522   typedef folly::small_vector<std::string,10,
 523     std::size_t,folly::small_vector_policy::NoHeap> Vector;
 524
 525   Vector v;
 526   static_assert(v.max_size() == 10, "max_size is incorrect");
 527
 528   for (int i = 0; i < 10; ++i) {
 529     v.push_back(folly::to<std::string>(i));
 530     EXPECT_EQ(v.size(), i + 1);
 531   }
 532
 533   bool caught = false;
 534   try {
 535     v.insert(v.begin(), "ha");
 536   } catch (const std::length_error&) {
 537     caught = true;
 538   }
 539   EXPECT_TRUE(caught);
 540
 541   // Check max_size works right with various policy combinations.
 542   folly::small_vector<std::string,32,uint32_t> v4;
 543   EXPECT_EQ(v4.max_size(), (1ul << 31) - 1);
 544
 545   /*
 546    * Test that even when we ask for a small number inlined it'll still
 547    * inline at least as much as it takes to store the value_type
 548    * pointer.
 549    */
 550   folly::small_vector<char,1,NoHeap> notsosmall;
 551   static_assert(notsosmall.max_size() == sizeof(char*),
 552                 "max_size is incorrect");
 553   caught = false;
 554   try {
 555     notsosmall.push_back(12);
 556     notsosmall.push_back(13);
 557     notsosmall.push_back(14);
 558   } catch (const std::length_error&) {
 559     caught = true;
 560   }
 561   EXPECT_FALSE(caught);
 562 }
 563
 564 TEST(small_vector, MaxSize) {
 565   folly::small_vector<int,2,uint8_t> vec;
 566   EXPECT_EQ(vec.max_size(), 127);
 567   folly::small_vector<int,2,uint16_t> vec2;
 568   EXPECT_EQ(vec2.max_size(), (1 << 15) - 1);
 569 }
 570
 571 TEST(small_vector, AllHeap) {
 572   // Use something bigger than the pointer so it can't get inlined.
 573   struct SomeObj {
 574     double a, b, c, d, e; int val;
 575     SomeObj(int val) : val(val) {}
 576     bool operator==(SomeObj const& o) const {
 577       return o.val == val;
 578     }
 579   };
 580
 581   folly::small_vector<SomeObj,0> vec = { 1 };
 582   EXPECT_EQ(vec.size(), 1);
 583   if (!vec.empty()) {
 584     EXPECT_TRUE(vec[0] == 1);
 585   }
 586   vec.insert(vec.begin(), { 0, 1, 2, 3 });
 587   EXPECT_EQ(vec.size(), 5);
 588   EXPECT_TRUE((vec == folly::small_vector<SomeObj,0>{ 0, 1, 2, 3, 1 }));
 589 }
 590
 591 TEST(small_vector, Basic) {
 592   typedef folly::small_vector<int,3,uint32_t
 593   > Vector;
 594
 595   Vector a;
 596
 597   a.push_back(12);
 598   EXPECT_EQ(a.front(), 12);
 599   EXPECT_EQ(a.size(), 1);
 600   a.push_back(13);
 601   EXPECT_EQ(a.size(), 2);
 602   EXPECT_EQ(a.front(), 12);
 603   EXPECT_EQ(a.back(), 13);
 604
 605   a.emplace(a.end(), 32);
 606   EXPECT_EQ(a.back(), 32);
 607
 608   a.emplace(a.begin(), 12);
 609   EXPECT_EQ(a.front(), 12);
 610   EXPECT_EQ(a.back(), 32);
 611   a.erase(a.end() - 1);
 612   EXPECT_EQ(a.back(), 13);
 613
 614   a.push_back(12);
 615   EXPECT_EQ(a.back(), 12);
 616   a.pop_back();
 617   EXPECT_EQ(a.back(), 13);
 618
 619   const int s = 12;
 620   a.push_back(s); // lvalue reference
 621
 622   Vector b, c;
 623   b = a;
 624   EXPECT_TRUE(b == a);
 625   c = std::move(b);
 626   EXPECT_TRUE(c == a);
 627   EXPECT_TRUE(c != b && b != a);
 628
 629   EXPECT_GT(c.size(), 0);
 630   c.resize(1);
 631   EXPECT_EQ(c.size(), 1);
 632
 633   Vector intCtor(12);
 634 }
 635
 636 TEST(small_vector, Capacity) {
 637   folly::small_vector<uint64_t, 1> vec;
 638   EXPECT_EQ(vec.size(), 0);
 639   EXPECT_EQ(vec.capacity(), 1);
 640
 641   vec.push_back(0);
 642   EXPECT_EQ(vec.size(), 1);
 643   EXPECT_EQ(vec.capacity(), 1);
 644
 645   vec.push_back(1);
 646   EXPECT_EQ(vec.size(), 2);
 647   EXPECT_GT(vec.capacity(), 1);
 648
 649   folly::small_vector<uint64_t, 2> vec2;
 650   EXPECT_EQ(vec2.size(), 0);
 651   EXPECT_EQ(vec2.capacity(), 2);
 652
 653   vec2.push_back(0);
 654   vec2.push_back(1);
 655   EXPECT_EQ(vec2.size(), 2);
 656   EXPECT_EQ(vec2.capacity(), 2);
 657
 658   vec2.push_back(2);
 659   EXPECT_EQ(vec2.size(), 3);
 660   EXPECT_GT(vec2.capacity(), 2);
 661
 662   // Test capacity heapifying logic
 663   folly::small_vector<unsigned char, 1> vec3;
 664   const size_t hc_size = 100000;
 665   for (size_t i = 0; i < hc_size; ++i) {
 666     auto v = (unsigned char)i;
 667     vec3.push_back(v);
 668     EXPECT_EQ(vec3[i], v);
 669     EXPECT_EQ(vec3.size(), i + 1);
 670     EXPECT_GT(vec3.capacity(), i);
 671   }
 672   for (auto i = hc_size; i > 0; --i) {
 673     auto v = (unsigned char)(i - 1);
 674     EXPECT_EQ(vec3.back(), v);
 675     vec3.pop_back();
 676     EXPECT_EQ(vec3.size(), i - 1);
 677   }
 678 }
 679
 680 TEST(small_vector, SelfPushBack) {
 681   for (int i = 1; i < 33; ++i) {
 682     folly::small_vector<std::string> vec;
 683     for (int j = 0; j < i; ++j) {
 684       vec.push_back("abc");
 685     }
 686     EXPECT_EQ(vec.size(), i);
 687     vec.push_back(std::move(vec[0]));
 688     EXPECT_EQ(vec.size(), i + 1);
 689
 690     EXPECT_EQ(vec[i], "abc");
 691   }
 692 }
 693
 694 TEST(small_vector, SelfEmplaceBack) {
 695   for (int i = 1; i < 33; ++i) {
 696     folly::small_vector<std::string> vec;
 697     for (int j = 0; j < i; ++j) {
 698       vec.emplace_back("abc");
 699     }
 700     EXPECT_EQ(vec.size(), i);
 701     vec.emplace_back(std::move(vec[0]));
 702     EXPECT_EQ(vec.size(), i + 1);
 703
 704     EXPECT_EQ(vec[i], "abc");
 705   }
 706 }
 707
 708 TEST(small_vector, SelfInsert) {
 709   // end insert
 710   for (int i = 1; i < 33; ++i) {
 711     folly::small_vector<std::string> vec;
 712     for (int j = 0; j < i; ++j) {
 713       vec.push_back("abc");
 714     }
 715     EXPECT_EQ(vec.size(), i);
 716     vec.insert(vec.end(), std::move(vec[0]));
 717     EXPECT_EQ(vec.size(), i + 1);
 718
 719     EXPECT_EQ(vec[i], "abc");
 720     EXPECT_EQ(vec[vec.size() - 1], "abc");
 721   }
 722
 723   // middle insert
 724   for (int i = 2; i < 33; ++i) {
 725     folly::small_vector<std::string> vec;
 726     for (int j = 0; j < i; ++j) {
 727       vec.push_back("abc");
 728     }
 729     EXPECT_EQ(vec.size(), i);
 730     vec.insert(vec.end()-1, std::move(vec[0]));
 731     EXPECT_EQ(vec.size(), i + 1);
 732
 733     EXPECT_EQ(vec[i-1], "abc");
 734     EXPECT_EQ(vec[i], "abc");
 735   }
 736 }
 737
 738 struct CheckedInt {
 739   static const int DEFAULT_VALUE = (int)0xdeadbeef;
 740   CheckedInt(): value(DEFAULT_VALUE) {}
 741   explicit CheckedInt(int value): value(value) {}
 742   CheckedInt(const CheckedInt& rhs, int) : value(rhs.value) {}
 743   CheckedInt(const CheckedInt& rhs): value(rhs.value) {}
 744   CheckedInt(CheckedInt&& rhs) noexcept: value(rhs.value) {
 745     rhs.value = DEFAULT_VALUE;
 746   }
 747   CheckedInt& operator= (const CheckedInt& rhs) {
 748     value = rhs.value;
 749     return *this;
 750   }
 751   CheckedInt& operator= (CheckedInt&& rhs) noexcept {
 752     value = rhs.value;
 753     rhs.value = DEFAULT_VALUE;
 754     return *this;
 755   }
 756   ~CheckedInt() {}
 757   int value;
 758 };
 759
 760 TEST(small_vector, ForwardingEmplaceInsideVector) {
 761   folly::small_vector<CheckedInt> v;
 762   v.push_back(CheckedInt(1));
 763   for (int i = 1; i < 20; ++i) {
 764     v.emplace_back(v[0], 42);
 765     ASSERT_EQ(1, v.back().value);
 766   }
 767 }
 768
 769 TEST(small_vector, LVEmplaceInsideVector) {
 770   folly::small_vector<CheckedInt> v;
 771   v.push_back(CheckedInt(1));
 772   for (int i = 1; i < 20; ++i) {
 773     v.emplace_back(v[0]);
 774     ASSERT_EQ(1, v.back().value);
 775   }
 776 }
 777
 778 TEST(small_vector, CLVEmplaceInsideVector) {
 779   folly::small_vector<CheckedInt> v;
 780   const folly::small_vector<CheckedInt>& cv = v;
 781   v.push_back(CheckedInt(1));
 782   for (int i = 1; i < 20; ++i) {
 783     v.emplace_back(cv[0]);
 784     ASSERT_EQ(1, v.back().value);
 785   }
 786 }
 787
 788 TEST(small_vector, RVEmplaceInsideVector) {
 789   folly::small_vector<CheckedInt> v;
 790   v.push_back(CheckedInt(0));
 791   for (int i = 1; i < 20; ++i) {
 792     v[0] = CheckedInt(1);
 793     v.emplace_back(std::move(v[0]));
 794     ASSERT_EQ(1, v.back().value);
 795   }
 796 }
 797
 798 TEST(small_vector, LVPushValueInsideVector) {
 799   folly::small_vector<CheckedInt> v;
 800   v.push_back(CheckedInt(1));
 801   for (int i = 1; i < 20; ++i) {
 802     v.push_back(v[0]);
 803     ASSERT_EQ(1, v.back().value);
 804   }
 805 }
 806
 807 TEST(small_vector, RVPushValueInsideVector) {
 808   folly::small_vector<CheckedInt> v;
 809   v.push_back(CheckedInt(0));
 810   for (int i = 1; i < 20; ++i) {
 811     v[0] = CheckedInt(1);
 812     v.push_back(v[0]);
 813     ASSERT_EQ(1, v.back().value);
 814   }
 815 }
 816
 817 TEST(small_vector, EmplaceIterCtor) {
 818   std::vector<int*> v{new int(1), new int(2)};
 819   std::vector<std::unique_ptr<int>> uv(v.begin(), v.end());
 820
 821   std::vector<int*> w{new int(1), new int(2)};
 822   small_vector<std::unique_ptr<int>> uw(w.begin(), w.end());
 823 }
 824
 825 TEST(small_vector, InputIterator) {
 826   std::vector<int> expected{125, 320, 512, 750, 333};
 827   std::string values = "125 320 512 750 333";
 828   std::istringstream is1(values);
 829   std::istringstream is2(values);
 830
 831   std::vector<int> stdV{std::istream_iterator<int>(is1),
 832                         std::istream_iterator<int>()};
 833   ASSERT_EQ(stdV.size(), expected.size());
 834   for (size_t i = 0; i < expected.size(); i++) {
 835     ASSERT_EQ(stdV[i], expected[i]);
 836   }
 837
 838   small_vector<int> smallV{std::istream_iterator<int>(is2),
 839                            std::istream_iterator<int>()};
 840   ASSERT_EQ(smallV.size(), expected.size());
 841   for (size_t i = 0; i < expected.size(); i++) {
 842     ASSERT_EQ(smallV[i], expected[i]);
 843   }
 844 }
 845
 846 TEST(small_vector, NoCopyCtor) {
 847   struct Test {
 848     Test() = default;
 849     Test(const Test&) = delete;
 850     Test(Test&&) = default;
 851
 852     int field = 42;
 853   };
 854
 855   small_vector<Test> test(10);
 856   ASSERT_EQ(test.size(), 10);
 857   for (const auto& element : test) {
 858     EXPECT_EQ(element.field, 42);
 859   }
 860 }
 861
 862 TEST(small_vector, ZeroInitializable) {
 863   small_vector<int> test(10);
 864   ASSERT_EQ(test.size(), 10);
 865   for (const auto& element : test) {
 866     EXPECT_EQ(element, 0);
 867   }
 868 }
 869
 870 TEST(small_vector, InsertMoreThanGrowth) {
 871   small_vector<int, 10> test;
 872   test.insert(test.end(), 30, 0);
 873   for (auto element : test) {
 874     EXPECT_EQ(element, 0);
 875   }
 876 }
 877
 878 TEST(small_vector, EmplaceBackExponentialGrowth) {
 879   small_vector<std::pair<int, int>> test;
 880   std::vector<size_t> capacities;
 881   capacities.push_back(test.capacity());
 882   for (int i = 0; i < 10000; ++i) {
 883     test.emplace_back(0, 0);
 884     if (test.capacity() != capacities.back()) {
 885       capacities.push_back(test.capacity());
 886     }
 887   }
 888   EXPECT_LE(capacities.size(), 25);
 889 }
 890
 891 TEST(small_vector, InsertExponentialGrowth) {
 892   small_vector<std::pair<int, int>> test;
 893   std::vector<size_t> capacities;
 894   capacities.push_back(test.capacity());
 895   for (int i = 0; i < 10000; ++i) {
 896     test.insert(test.begin(), std::make_pair(0, 0));
 897     if (test.capacity() != capacities.back()) {
 898       capacities.push_back(test.capacity());
 899     }
 900   }
 901   EXPECT_LE(capacities.size(), 25);
 902 }
 903
 904 TEST(small_vector, InsertNExponentialGrowth) {
 905   small_vector<int> test;
 906   std::vector<size_t> capacities;
 907   capacities.push_back(test.capacity());
 908   for (int i = 0; i < 10000; ++i) {
 909     test.insert(test.begin(), 100, 0);
 910     if (test.capacity() != capacities.back()) {
 911       capacities.push_back(test.capacity());
 912     }
 913   }
 914   EXPECT_LE(capacities.size(), 25);
 915 }
 916
 917 namespace {
 918 struct Counts {
 919   size_t copyCount{0};
 920   size_t moveCount{0};
 921 };
 922
 923 class Counter {
 924   Counts* counts;
 925
 926  public:
 927   explicit Counter(Counts& counts) : counts(&counts) {}
 928   Counter(Counter const& other) noexcept : counts(other.counts) {
 929     ++counts->copyCount;
 930   }
 931   Counter(Counter&& other) noexcept : counts(other.counts) {
 932     ++counts->moveCount;
 933   }
 934   Counter& operator=(Counter const& rhs) noexcept {
 935     EXPECT_EQ(counts, rhs.counts);
 936     ++counts->copyCount;
 937     return *this;
 938   }
 939   Counter& operator=(Counter&& rhs) noexcept {
 940     EXPECT_EQ(counts, rhs.counts);
 941     ++counts->moveCount;
 942     return *this;
 943   }
 944 };
 945 }
 946
 947 TEST(small_vector, EmplaceBackEfficiency) {
 948   small_vector<Counter, 2> test;
 949   Counts counts;
 950   for (size_t i = 1; i <= test.capacity(); ++i) {
 951     test.emplace_back(counts);
 952     EXPECT_EQ(0, counts.copyCount);
 953     EXPECT_EQ(0, counts.moveCount);
 954   }
 955   EXPECT_EQ(test.size(), test.capacity());
 956   test.emplace_back(counts);
 957   // Every element except the last has to be moved to the new position
 958   EXPECT_EQ(0, counts.copyCount);
 959   EXPECT_EQ(test.size() - 1, counts.moveCount);
 960   EXPECT_LT(test.size(), test.capacity());
 961 }
 962
 963 TEST(small_vector, RVPushBackEfficiency) {
 964   small_vector<Counter, 2> test;
 965   Counts counts;
 966   for (size_t i = 1; i <= test.capacity(); ++i) {
 967     test.push_back(Counter(counts));
 968     // 1 copy for each push_back()
 969     EXPECT_EQ(0, counts.copyCount);
 970     EXPECT_EQ(i, counts.moveCount);
 971   }
 972   EXPECT_EQ(test.size(), test.capacity());
 973   test.push_back(Counter(counts));
 974   // 1 move for each push_back()
 975   // Every element except the last has to be moved to the new position
 976   EXPECT_EQ(0, counts.copyCount);
 977   EXPECT_EQ(test.size() + test.size() - 1, counts.moveCount);
 978   EXPECT_LT(test.size(), test.capacity());
 979 }
 980
 981 TEST(small_vector, CLVPushBackEfficiency) {
 982   small_vector<Counter, 2> test;
 983   Counts counts;
 984   Counter const counter(counts);
 985   for (size_t i = 1; i <= test.capacity(); ++i) {
 986     test.push_back(counter);
 987     // 1 copy for each push_back()
 988     EXPECT_EQ(i, counts.copyCount);
 989     EXPECT_EQ(0, counts.moveCount);
 990   }
 991   EXPECT_EQ(test.size(), test.capacity());
 992   test.push_back(counter);
 993   // 1 copy for each push_back()
 994   EXPECT_EQ(test.size(), counts.copyCount);
 995   // Every element except the last has to be moved to the new position
 996   EXPECT_EQ(test.size() - 1, counts.moveCount);
 997   EXPECT_LT(test.size(), test.capacity());
 998 }