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