folly/test/small_vector_test.cpp

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