folly/test/small_vector_test.cpp

   1 /*
   2  * Copyright 2014 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 <gtest/gtest.h>
  20 #include <string>
  21 #include <memory>
  22 #include <iostream>
  23 #include <limits>
  24
  25 #include <boost/algorithm/string.hpp>
  26
  27 #include "folly/Conv.h"
  28
  29 using folly::small_vector;
  30 using namespace folly::small_vector_policy;
  31
  32 #if defined(__x86_64__)
  33
  34 static_assert(sizeof(small_vector<int>) == 16,
  35               "Object size is not what we expect for small_vector<int>");
  36 static_assert(sizeof(small_vector<int32_t,2>) == 16,
  37               "Object size is not what we expect for "
  38               "small_vector<int32_t,2>");
  39 static_assert(sizeof(small_vector<int,10>) ==
  40                 10 * sizeof(int) + sizeof(std::size_t),
  41               "Object size is not what we expect for small_vector<int,10>");
  42
  43 static_assert(sizeof(small_vector<int32_t,1,uint32_t>) ==
  44                 8 + 4,
  45               "small_vector<int32_t,1,uint32_t> is wrong size");
  46 static_assert(sizeof(small_vector<int32_t,1,uint16_t>) ==
  47                 8 + 2,
  48               "small_vector<int32_t,1,uint32_t> is wrong size");
  49 static_assert(sizeof(small_vector<int32_t,1,uint8_t>) ==
  50                 8 + 1,
  51               "small_vector<int32_t,1,uint32_t> is wrong size");
  52
  53 static_assert(sizeof(small_vector<int32_t,1,OneBitMutex>) == 16,
  54               "OneBitMutex took more space than expected");
  55
  56 static_assert(sizeof(small_vector<int16_t,4,uint16_t>) == 10,
  57               "Sizeof unexpectedly large");
  58 static_assert(sizeof(small_vector<int16_t,4,uint16_t,OneBitMutex>) == 10,
  59               "Sizeof unexpectedly large");
  60 static_assert(sizeof(small_vector<int16_t,4,NoHeap,uint16_t,
  61                                   OneBitMutex>) == 10,
  62               "Sizeof unexpectedly large");
  63
  64 #endif
  65
  66 static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(std::unique_ptr<int>),
  67               "std::unique_ptr<> is trivially copyable");
  68
  69 namespace {
  70
  71 struct NontrivialType {
  72   static int ctored;
  73   explicit NontrivialType() : a(0) {}
  74
  75   /* implicit */ NontrivialType(int a) : a(a) {
  76     ++ctored;
  77   }
  78
  79   NontrivialType(NontrivialType const& s) {
  80     ++ctored;
  81   }
  82
  83   NontrivialType& operator=(NontrivialType const& o) {
  84     a = o.a;
  85     return *this;
  86   }
  87
  88   int32_t a;
  89 };
  90 static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(NontrivialType),
  91               "NontrivialType is trivially copyable");
  92
  93 int NontrivialType::ctored = 0;
  94
  95 struct TestException {};
  96
  97 int throwCounter = 1;
  98 void MaybeThrow() {
  99   if (!--throwCounter) {
 100     throw TestException();
 101   }
 102 }
 103
 104 const int kMagic = 0xdeadbeef;
 105 struct Thrower {
 106   static int alive;
 107
 108   Thrower() : magic(kMagic) {
 109     EXPECT_EQ(magic, kMagic);
 110     MaybeThrow();
 111     ++alive;
 112   }
 113   Thrower(Thrower const& other) : magic(other.magic) {
 114     EXPECT_EQ(magic, kMagic);
 115     MaybeThrow();
 116     ++alive;
 117   }
 118   ~Thrower() noexcept {
 119     EXPECT_EQ(magic, kMagic);
 120     magic = 0;
 121     --alive;
 122   }
 123
 124   Thrower& operator=(Thrower const& other) {
 125     EXPECT_EQ(magic, kMagic);
 126     MaybeThrow();
 127     return *this;
 128   }
 129
 130   // This is just to try to make sure we don't get our member
 131   // functions called on uninitialized memory.
 132   int magic;
 133 };
 134
 135 int Thrower::alive = 0;
 136
 137 // Type that counts how many exist and doesn't support copy
 138 // construction.
 139 struct NoncopyableCounter {
 140   static int alive;
 141   NoncopyableCounter() {
 142     ++alive;
 143   }
 144   ~NoncopyableCounter() {
 145     --alive;
 146   }
 147   NoncopyableCounter(NoncopyableCounter&&) { ++alive; }
 148   NoncopyableCounter(NoncopyableCounter const&) = delete;
 149   NoncopyableCounter& operator=(NoncopyableCounter const&) const = delete;
 150   NoncopyableCounter& operator=(NoncopyableCounter&&) { return *this; }
 151 };
 152 int NoncopyableCounter::alive = 0;
 153
 154 static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(NoncopyableCounter),
 155               "NoncopyableCounter is trivially copyable");
 156
 157 // Check that throws don't break the basic guarantee for some cases.
 158 // Uses the method for testing exception safety described at
 159 // http://www.boost.org/community/exception_safety.html, to force all
 160 // throwing code paths to occur.
 161 struct TestBasicGuarantee {
 162   folly::small_vector<Thrower,3> vec;
 163   int const prepopulate;
 164
 165   explicit TestBasicGuarantee(int prepopulate)
 166     : prepopulate(prepopulate)
 167   {
 168     throwCounter = 1000;
 169     for (int i = 0; i < prepopulate; ++i) {
 170       vec.push_back(Thrower());
 171     }
 172   }
 173
 174   ~TestBasicGuarantee() {
 175     throwCounter = 1000;
 176   }
 177
 178   template<class Operation>
 179   void operator()(int insertCount, Operation const& op) {
 180     bool done = false;
 181
 182     std::unique_ptr<folly::small_vector<Thrower,3> > workingVec;
 183     for (int counter = 1; !done; ++counter) {
 184       throwCounter = 1000;
 185       workingVec.reset(new folly::small_vector<Thrower,3>(vec));
 186       throwCounter = counter;
 187       EXPECT_EQ(Thrower::alive, prepopulate * 2);
 188       try {
 189         op(*workingVec);
 190         done = true;
 191       } catch (...) {
 192         // Note that the size of the vector can change if we were
 193         // inserting somewhere other than the end (it's a basic only
 194         // guarantee).  All we're testing here is that we have the
 195         // right amount of uninitialized vs initialized memory.
 196         EXPECT_EQ(Thrower::alive, workingVec->size() + vec.size());
 197         continue;
 198       }
 199
 200       // If things succeeded.
 201       EXPECT_EQ(workingVec->size(), prepopulate + insertCount);
 202       EXPECT_EQ(Thrower::alive, prepopulate * 2 + insertCount);
 203     }
 204   }
 205 };
 206
 207 }
 208
 209 TEST(small_vector, BasicGuarantee) {
 210   for (int prepop = 1; prepop < 30; ++prepop) {
 211     (TestBasicGuarantee(prepop))( // parens or a mildly vexing parse :(
 212       1,
 213       [&] (folly::small_vector<Thrower,3>& v) {
 214         v.push_back(Thrower());
 215       }
 216     );
 217
 218     EXPECT_EQ(Thrower::alive, 0);
 219
 220     (TestBasicGuarantee(prepop))(
 221       1,
 222       [&] (folly::small_vector<Thrower,3>& v) {
 223         v.insert(v.begin(), Thrower());
 224       }
 225     );
 226
 227     EXPECT_EQ(Thrower::alive, 0);
 228
 229     (TestBasicGuarantee(prepop))(
 230       1,
 231       [&] (folly::small_vector<Thrower,3>& v) {
 232         v.insert(v.begin() + 1, Thrower());
 233       }
 234     );
 235
 236     EXPECT_EQ(Thrower::alive, 0);
 237   }
 238
 239   TestBasicGuarantee(4)(
 240     3,
 241     [&] (folly::small_vector<Thrower,3>& v) {
 242       std::vector<Thrower> b;
 243       b.push_back(Thrower());
 244       b.push_back(Thrower());
 245       b.push_back(Thrower());
 246
 247       /*
 248        * Apparently if you do the following initializer_list instead
 249        * of the above push_back's, and one of the Throwers throws,
 250        * g++4.6 doesn't destruct the previous ones.  Heh.
 251        */
 252       //b = { Thrower(), Thrower(), Thrower() };
 253       v.insert(v.begin() + 1, b.begin(), b.end());
 254     }
 255   );
 256
 257   TestBasicGuarantee(2)(
 258     6,
 259     [&] (folly::small_vector<Thrower,3>& v) {
 260       std::vector<Thrower> b;
 261       for (int i = 0; i < 6; ++i) {
 262         b.push_back(Thrower());
 263       }
 264
 265       v.insert(v.begin() + 1, b.begin(), b.end());
 266     }
 267   );
 268
 269   EXPECT_EQ(Thrower::alive, 0);
 270   try {
 271     throwCounter = 4;
 272     folly::small_vector<Thrower,1> p(14, Thrower());
 273   } catch (...) {
 274   }
 275   EXPECT_EQ(Thrower::alive, 0);
 276 }
 277
 278 // Run this with.
 279 // MALLOC_CONF=prof_leak:true
 280 // LD_PRELOAD=${JEMALLOC_PATH}/lib/libjemalloc.so.1
 281 // LD_PRELOAD="$LD_PRELOAD:"${UNWIND_PATH}/lib/libunwind.so.7
 282 TEST(small_vector, leak_test) {
 283   for (int j = 0; j < 1000; ++j) {
 284     folly::small_vector<int, 10> someVec(300);
 285     for (int i = 0; i < 10000; ++i) {
 286       someVec.push_back(12);
 287     }
 288   }
 289 }
 290
 291 TEST(small_vector, Insert) {
 292   folly::small_vector<int> someVec(3, 3);
 293   someVec.insert(someVec.begin(), 12, 12);
 294   EXPECT_EQ(someVec.size(), 15);
 295   for (int i = 0; i < someVec.size(); ++i) {
 296     if (i < 12) {
 297       EXPECT_EQ(someVec[i], 12);
 298     } else {
 299       EXPECT_EQ(someVec[i], 3);
 300     }
 301   }
 302
 303   auto oldSize = someVec.size();
 304   someVec.insert(someVec.begin() + 1, 12, 12);
 305   EXPECT_EQ(someVec.size(), oldSize + 12);
 306
 307   folly::small_vector<std::string> v1(6, "asd"), v2(7, "wat");
 308   v1.insert(v1.begin() + 1, v2.begin(), v2.end());
 309   EXPECT_TRUE(v1.size() == 6 + 7);
 310   EXPECT_EQ(v1.front(), "asd");
 311   EXPECT_EQ(v1[1], "wat");
 312 }
 313
 314 TEST(small_vector, Swap) {
 315   folly::small_vector<int,10> somethingVec, emptyVec;
 316   somethingVec.push_back(1);
 317   somethingVec.push_back(2);
 318   somethingVec.push_back(3);
 319   somethingVec.push_back(4);
 320
 321   // Swapping intern'd with intern'd.
 322   auto vec = somethingVec;
 323   EXPECT_TRUE(vec == somethingVec);
 324   EXPECT_FALSE(vec == emptyVec);
 325   EXPECT_FALSE(somethingVec == emptyVec);
 326
 327   // Swapping a heap vector with an intern vector.
 328   folly::small_vector<int,10> junkVec;
 329   junkVec.assign(12, 12);
 330   EXPECT_EQ(junkVec.size(), 12);
 331   for (auto i : junkVec) {
 332     EXPECT_EQ(i, 12);
 333   }
 334   swap(junkVec, vec);
 335   EXPECT_TRUE(junkVec == somethingVec);
 336   EXPECT_EQ(vec.size(), 12);
 337   for (auto i : vec) {
 338     EXPECT_EQ(i, 12);
 339   }
 340
 341   // Swapping two heap vectors.
 342   folly::small_vector<int,10> moreJunk(15, 15);
 343   EXPECT_EQ(moreJunk.size(), 15);
 344   for (auto i : moreJunk) {
 345     EXPECT_EQ(i, 15);
 346   }
 347   swap(vec, moreJunk);
 348   EXPECT_EQ(moreJunk.size(), 12);
 349   for (auto i : moreJunk) {
 350     EXPECT_EQ(i, 12);
 351   }
 352   EXPECT_EQ(vec.size(), 15);
 353   for (auto i : vec) {
 354     EXPECT_EQ(i, 15);
 355   }
 356
 357   // Making a vector heap, then smaller than another non-heap vector,
 358   // then swapping.
 359   folly::small_vector<int,5> shrinker, other(4, 10);
 360   shrinker = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
 361   shrinker.erase(shrinker.begin() + 2, shrinker.end());
 362   EXPECT_LT(shrinker.size(), other.size());
 363   swap(shrinker, other);
 364   EXPECT_EQ(shrinker.size(), 4);
 365   EXPECT_TRUE(boost::all(shrinker, boost::is_any_of(std::vector<int>{10})));
 366   EXPECT_TRUE((other == small_vector<int,5>{ 0, 1 }));
 367 }
 368
 369 TEST(small_vector, Emplace) {
 370   NontrivialType::ctored = 0;
 371
 372   folly::small_vector<NontrivialType> vec;
 373   vec.reserve(1024);
 374   vec.emplace_back(12);
 375   EXPECT_EQ(NontrivialType::ctored, 1);
 376   EXPECT_EQ(vec.front().a, 12);
 377   vec.emplace_back(13);
 378   EXPECT_EQ(vec.front().a, 12);
 379   EXPECT_EQ(vec.back().a, 13);
 380   EXPECT_EQ(NontrivialType::ctored, 2);
 381
 382   NontrivialType::ctored = 0;
 383   for (int i = 0; i < 120; ++i) {
 384     vec.emplace_back(i);
 385   }
 386   EXPECT_EQ(NontrivialType::ctored, 120);
 387   EXPECT_EQ(vec[0].a, 12);
 388   EXPECT_EQ(vec[1].a, 13);
 389   EXPECT_EQ(vec.back().a, 119);
 390
 391   // We implement emplace() with a temporary (see the implementation
 392   // for a comment about why), so this should make 2 ctor calls.
 393   NontrivialType::ctored = 0;
 394   vec.emplace(vec.begin(), 12);
 395   EXPECT_EQ(NontrivialType::ctored, 2);
 396 }
 397
 398 TEST(small_vector, Erase) {
 399   folly::small_vector<int,4> notherVec = { 1, 2, 3, 4, 5 };
 400   EXPECT_EQ(notherVec.front(), 1);
 401   EXPECT_EQ(notherVec.size(), 5);
 402   notherVec.erase(notherVec.begin());
 403   EXPECT_EQ(notherVec.front(), 2);
 404   EXPECT_EQ(notherVec.size(), 4);
 405   EXPECT_EQ(notherVec[2], 4);
 406   EXPECT_EQ(notherVec[3], 5);
 407   notherVec.erase(notherVec.begin() + 2);
 408   EXPECT_EQ(notherVec.size(), 3);
 409   EXPECT_EQ(notherVec[2], 5);
 410
 411   folly::small_vector<int,2> vec2 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
 412   vec2.erase(vec2.begin() + 1, vec2.end() - 1);
 413   folly::small_vector<int,2> expected = { 1, 10 };
 414   EXPECT_TRUE(vec2 == expected);
 415
 416   folly::small_vector<std::string,3> v(102, "ASD");
 417   v.resize(1024, "D");
 418   EXPECT_EQ(v.size(), 1024);
 419   EXPECT_EQ(v.back(), "D");
 420   EXPECT_EQ(v.front(), "ASD");
 421   v.resize(1);
 422   EXPECT_EQ(v.front(), "ASD");
 423   EXPECT_EQ(v.size(), 1);
 424   v.resize(0);
 425   EXPECT_TRUE(v.empty());
 426 }
 427
 428 TEST(small_vector, GrowShrinkGrow) {
 429   folly::small_vector<NontrivialType,7> vec = { 1, 2, 3, 4, 5 };
 430   std::generate_n(std::back_inserter(vec), 102, std::rand);
 431
 432   auto capacity = vec.capacity();
 433
 434   auto oldSize = vec.size();
 435   for (int i = 0; i < oldSize; ++i) {
 436     vec.erase(vec.begin() + (std::rand() % vec.size()));
 437     EXPECT_EQ(vec.capacity(), capacity);
 438   }
 439   EXPECT_TRUE(vec.empty());
 440
 441   EXPECT_EQ(vec.capacity(), capacity);
 442   std::generate_n(std::back_inserter(vec), 102, std::rand);
 443   EXPECT_EQ(vec.capacity(), capacity);
 444
 445   std::generate_n(std::back_inserter(vec), 4096, std::rand);
 446   EXPECT_GT(vec.capacity(), capacity);
 447
 448   vec.resize(10);
 449   vec.shrink_to_fit();
 450   EXPECT_LT(vec.capacity(), capacity);
 451   vec.resize(4);
 452   vec.shrink_to_fit();
 453   EXPECT_EQ(vec.capacity(), 7); // in situ size
 454 }
 455
 456 TEST(small_vector, Iteration) {
 457   folly::small_vector<std::string,3> vec = { "foo", "bar" };
 458   vec.push_back("blah");
 459   vec.push_back("blah2");
 460   vec.push_back("blah3");
 461   vec.erase(vec.begin() + 2);
 462
 463   std::vector<std::string> otherVec;
 464   for (auto& s : vec) {
 465     otherVec.push_back(s);
 466   }
 467   EXPECT_EQ(otherVec.size(), vec.size());
 468   if (otherVec.size() == vec.size()) {
 469     EXPECT_TRUE(std::equal(otherVec.begin(), otherVec.end(), vec.begin()));
 470   }
 471
 472   std::reverse(otherVec.begin(), otherVec.end());
 473   auto oit = otherVec.begin();
 474   auto rit = vec.crbegin();
 475   for (; rit != vec.crend(); ++oit, ++rit) {
 476     EXPECT_EQ(*oit, *rit);
 477   }
 478 }
 479
 480 TEST(small_vector, NonCopyableType) {
 481   folly::small_vector<NontrivialType,2> vec;
 482
 483   for (int i = 0; i < 10; ++i) {
 484     vec.emplace(vec.begin(), 13);
 485   }
 486   EXPECT_EQ(vec.size(), 10);
 487   auto vec2 = std::move(vec);
 488   EXPECT_EQ(vec.size(), 0);
 489   EXPECT_EQ(vec2.size(), 10);
 490   vec2.clear();
 491
 492   folly::small_vector<NoncopyableCounter,3> vec3;
 493   for (int i = 0; i < 10; ++i) {
 494     EXPECT_EQ(vec3.size(), i);
 495     EXPECT_EQ(NoncopyableCounter::alive, i);
 496     vec3.insert(vec3.begin(), NoncopyableCounter());
 497   }
 498   EXPECT_EQ(vec3.size(), 10);
 499   EXPECT_EQ(NoncopyableCounter::alive, 10);
 500
 501   vec3.insert(vec3.begin() + 3, NoncopyableCounter());
 502   EXPECT_EQ(NoncopyableCounter::alive, 11);
 503   auto vec4 = std::move(vec3);
 504   EXPECT_EQ(NoncopyableCounter::alive, 11);
 505   vec4.resize(30);
 506   EXPECT_EQ(NoncopyableCounter::alive, 30);
 507   vec4.erase(vec4.begin(), vec4.end());
 508   EXPECT_EQ(vec4.size(), 0);
 509   EXPECT_EQ(NoncopyableCounter::alive, 0);
 510 }
 511
 512 TEST(small_vector, MoveConstructor) {
 513   folly::small_vector<std::string,10> v1;
 514   v1.push_back("asd");
 515   v1.push_back("bsd");
 516   auto v2 = std::move(v1);
 517   EXPECT_EQ(v2.size(), 2);
 518   EXPECT_EQ(v2[0], "asd");
 519   EXPECT_EQ(v2[1], "bsd");
 520
 521   v1 = std::move(v2);
 522   EXPECT_EQ(v1.size(), 2);
 523   EXPECT_EQ(v1[0], "asd");
 524   EXPECT_EQ(v1[1], "bsd");
 525 }
 526
 527 TEST(small_vector, NoHeap) {
 528   typedef folly::small_vector<std::string,10,
 529     std::size_t,folly::small_vector_policy::NoHeap> Vector;
 530
 531   Vector v;
 532   EXPECT_EQ(v.max_size(), 10);
 533
 534   for (int i = 0; i < 10; ++i) {
 535     v.push_back(folly::to<std::string>(i));
 536     EXPECT_EQ(v.size(), i + 1);
 537   }
 538
 539   bool caught = false;
 540   try {
 541     v.insert(v.begin(), "ha");
 542   } catch (const std::length_error&) {
 543     caught = true;
 544   }
 545   EXPECT_TRUE(caught);
 546
 547   // Check max_size works right with various policy combinations.
 548   folly::small_vector<std::string,32,uint32_t,NoHeap,OneBitMutex> v2;
 549   EXPECT_EQ(v2.max_size(), 32);
 550   folly::small_vector<std::string,32,uint32_t,OneBitMutex> v3;
 551   EXPECT_EQ(v3.max_size(), (1ul << 30) - 1);
 552   folly::small_vector<std::string,32,uint32_t> v4;
 553   EXPECT_EQ(v4.max_size(), (1ul << 31) - 1);
 554
 555   /*
 556    * Test that even when we ask for a small number inlined it'll still
 557    * inline at least as much as it takes to store the value_type
 558    * pointer.
 559    */
 560   folly::small_vector<char,1,NoHeap> notsosmall;
 561   EXPECT_EQ(notsosmall.max_size(), sizeof(char*));
 562   caught = false;
 563   try {
 564     notsosmall.push_back(12);
 565     notsosmall.push_back(13);
 566     notsosmall.push_back(14);
 567   } catch (const std::length_error&) {
 568     caught = true;
 569   }
 570   EXPECT_FALSE(caught);
 571 }
 572
 573 TEST(small_vector, MaxSize) {
 574   folly::small_vector<int,2,uint8_t> vec;
 575   EXPECT_EQ(vec.max_size(), 127);
 576   folly::small_vector<int,2,uint16_t> vec2;
 577   EXPECT_EQ(vec2.max_size(), (1 << 15) - 1);
 578   folly::small_vector<int,2,uint16_t,OneBitMutex> vec3;
 579   EXPECT_EQ(vec3.max_size(), (1 << 14) - 1);
 580 }
 581
 582 TEST(small_vector, AllHeap) {
 583   // Use something bigger than the pointer so it can't get inlined.
 584   struct SomeObj {
 585     double a, b, c, d, e; int val;
 586     SomeObj(int val) : val(val) {}
 587     bool operator==(SomeObj const& o) const {
 588       return o.val == val;
 589     }
 590   };
 591
 592   folly::small_vector<SomeObj,0> vec = { 1 };
 593   EXPECT_EQ(vec.size(), 1);
 594   if (!vec.empty()) {
 595     EXPECT_TRUE(vec[0] == 1);
 596   }
 597   vec.insert(vec.begin(), { 0, 1, 2, 3 });
 598   EXPECT_EQ(vec.size(), 5);
 599   EXPECT_TRUE((vec == folly::small_vector<SomeObj,0>{ 0, 1, 2, 3, 1 }));
 600 }
 601
 602 TEST(small_vector, Basic) {
 603   typedef folly::small_vector<int,3,uint32_t
 604 #ifdef __x86_64__
 605     ,OneBitMutex
 606 #endif
 607   > Vector;
 608
 609   Vector a;
 610
 611 #ifdef __x86_64__
 612   a.lock();
 613   a.unlock();
 614 #endif
 615
 616   a.push_back(12);
 617   EXPECT_EQ(a.front(), 12);
 618   EXPECT_EQ(a.size(), 1);
 619   a.push_back(13);
 620   EXPECT_EQ(a.size(), 2);
 621   EXPECT_EQ(a.front(), 12);
 622   EXPECT_EQ(a.back(), 13);
 623
 624   a.emplace(a.end(), 32);
 625   EXPECT_EQ(a.back(), 32);
 626
 627   a.emplace(a.begin(), 12);
 628   EXPECT_EQ(a.front(), 12);
 629   EXPECT_EQ(a.back(), 32);
 630   a.erase(a.end() - 1);
 631   EXPECT_EQ(a.back(), 13);
 632
 633   a.push_back(12);
 634   EXPECT_EQ(a.back(), 12);
 635   a.pop_back();
 636   EXPECT_EQ(a.back(), 13);
 637
 638   const int s = 12;
 639   a.push_back(s); // lvalue reference
 640
 641   Vector b, c;
 642   b = a;
 643   EXPECT_TRUE(b == a);
 644   c = std::move(b);
 645   EXPECT_TRUE(c == a);
 646   EXPECT_TRUE(c != b && b != a);
 647
 648   EXPECT_GT(c.size(), 0);
 649   c.resize(1);
 650   EXPECT_EQ(c.size(), 1);
 651
 652   Vector intCtor(12);
 653 }
 654
 655 TEST(small_vector, Capacity) {
 656   folly::small_vector<unsigned long, 1> vec;
 657   EXPECT_EQ(vec.size(), 0);
 658   EXPECT_EQ(vec.capacity(), 1);
 659
 660   vec.push_back(0);
 661   EXPECT_EQ(vec.size(), 1);
 662   EXPECT_EQ(vec.capacity(), 1);
 663
 664   vec.push_back(1);
 665   EXPECT_EQ(vec.size(), 2);
 666   EXPECT_GT(vec.capacity(), 1);
 667
 668
 669   folly::small_vector<unsigned long, 2> vec2;
 670   EXPECT_EQ(vec2.size(), 0);
 671   EXPECT_EQ(vec2.capacity(), 2);
 672
 673   vec2.push_back(0);
 674   vec2.push_back(1);
 675   EXPECT_EQ(vec2.size(), 2);
 676   EXPECT_EQ(vec2.capacity(), 2);
 677
 678   vec2.push_back(2);
 679   EXPECT_EQ(vec2.size(), 3);
 680   EXPECT_GT(vec2.capacity(), 2);
 681
 682   // Test capacity heapifying logic
 683   folly::small_vector<unsigned char, 1> vec3;
 684   const size_t hc_size = 1000000;
 685   for (size_t i = 0; i < hc_size; ++i) {
 686     auto v = (unsigned char)i;
 687     vec3.push_back(v);
 688     EXPECT_EQ(vec3[i], v);
 689     EXPECT_EQ(vec3.size(), i + 1);
 690     EXPECT_GT(vec3.capacity(), i);
 691   }
 692   for (auto i = hc_size; i > 0; --i) {
 693     auto v = (unsigned char)(i - 1);
 694     EXPECT_EQ(vec3.back(), v);
 695     vec3.pop_back();
 696     EXPECT_EQ(vec3.size(), i - 1);
 697   }
 698 }
 699
 700 TEST(small_vector, SelfPushBack) {
 701   for (int i = 1; i < 33; ++i) {
 702     folly::small_vector<std::string> vec;
 703     for (int j = 0; j < i; ++j) {
 704       vec.push_back("abc");
 705     }
 706     EXPECT_EQ(vec.size(), i);
 707     vec.push_back(std::move(vec[0]));
 708     EXPECT_EQ(vec.size(), i + 1);
 709
 710     EXPECT_EQ(vec[i], "abc");
 711   }
 712 }
 713
 714 TEST(small_vector, SelfEmplaceBack) {
 715   for (int i = 1; i < 33; ++i) {
 716     folly::small_vector<std::string> vec;
 717     for (int j = 0; j < i; ++j) {
 718       vec.emplace_back("abc");
 719     }
 720     EXPECT_EQ(vec.size(), i);
 721     vec.emplace_back(std::move(vec[0]));
 722     EXPECT_EQ(vec.size(), i + 1);
 723
 724     EXPECT_EQ(vec[i], "abc");
 725   }
 726 }
 727
 728 TEST(small_vector, SelfInsert) {
 729   // end insert
 730   for (int i = 1; i < 33; ++i) {
 731     folly::small_vector<std::string> vec;
 732     for (int j = 0; j < i; ++j) {
 733       vec.push_back("abc");
 734     }
 735     EXPECT_EQ(vec.size(), i);
 736     vec.insert(vec.end(), std::move(vec[0]));
 737     EXPECT_EQ(vec.size(), i + 1);
 738
 739     EXPECT_EQ(vec[i], "abc");
 740     EXPECT_EQ(vec[vec.size() - 1], "abc");
 741   }
 742
 743   // middle insert
 744   for (int i = 2; i < 33; ++i) {
 745     folly::small_vector<std::string> vec;
 746     for (int j = 0; j < i; ++j) {
 747       vec.push_back("abc");
 748     }
 749     EXPECT_EQ(vec.size(), i);
 750     vec.insert(vec.end()-1, std::move(vec[0]));
 751     EXPECT_EQ(vec.size(), i + 1);
 752
 753     EXPECT_EQ(vec[i-1], "abc");
 754     EXPECT_EQ(vec[i], "abc");
 755   }
 756 }