folly/test/small_vector_test.cpp

   1 /*
   2  * Copyright 2012 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(!boost::has_trivial_copy<NontrivialType>::value,
  88               "NontrivialType isn't 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 // 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.push_back(Thrower());
 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.push_back(Thrower());
 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.push_back(Thrower());
 238       b.push_back(Thrower());
 239       b.push_back(Thrower());
 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.push_back(Thrower());
 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.1
 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 (int 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 (int 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<std::unique_ptr<std::string>,2> vec;
 476   for (int i = 0; i < 10; ++i) {
 477     vec.emplace(vec.begin(), new std::string("asd"));
 478   }
 479   EXPECT_EQ(vec.size(), 10);
 480   auto vec2 = std::move(vec);
 481   EXPECT_EQ(vec.size(), 0);
 482   EXPECT_EQ(vec2.size(), 10);
 483   vec2.clear();
 484
 485   folly::small_vector<NoncopyableCounter,3> vec3;
 486   for (int i = 0; i < 10; ++i) {
 487     EXPECT_EQ(vec3.size(), i);
 488     EXPECT_EQ(NoncopyableCounter::alive, i);
 489     vec3.insert(vec3.begin(), NoncopyableCounter());
 490   }
 491   EXPECT_EQ(vec3.size(), 10);
 492   EXPECT_EQ(NoncopyableCounter::alive, 10);
 493
 494   vec3.insert(vec3.begin() + 3, NoncopyableCounter());
 495   EXPECT_EQ(NoncopyableCounter::alive, 11);
 496   auto vec4 = std::move(vec3);
 497   EXPECT_EQ(NoncopyableCounter::alive, 11);
 498   vec4.resize(30);
 499   EXPECT_EQ(NoncopyableCounter::alive, 30);
 500   vec4.erase(vec4.begin(), vec4.end());
 501   EXPECT_EQ(vec4.size(), 0);
 502   EXPECT_EQ(NoncopyableCounter::alive, 0);
 503 }
 504
 505 TEST(small_vector, MoveConstructor) {
 506   folly::small_vector<std::string,10> v1;
 507   v1.push_back("asd");
 508   v1.push_back("bsd");
 509   auto v2 = std::move(v1);
 510   EXPECT_EQ(v2.size(), 2);
 511   EXPECT_EQ(v2[0], "asd");
 512   EXPECT_EQ(v2[1], "bsd");
 513
 514   v1 = std::move(v2);
 515   EXPECT_EQ(v1.size(), 2);
 516   EXPECT_EQ(v1[0], "asd");
 517   EXPECT_EQ(v1[1], "bsd");
 518 }
 519
 520 TEST(small_vector, NoHeap) {
 521   typedef folly::small_vector<std::string,10,
 522     std::size_t,folly::small_vector_policy::NoHeap> Vector;
 523
 524   Vector v;
 525   EXPECT_EQ(v.max_size(), 10);
 526
 527   for (int i = 0; i < 10; ++i) {
 528     v.push_back(folly::to<std::string>(i));
 529     EXPECT_EQ(v.size(), i + 1);
 530   }
 531
 532   bool caught = false;
 533   try {
 534     v.insert(v.begin(), "ha");
 535   } catch (const std::length_error&) {
 536     caught = true;
 537   }
 538   EXPECT_TRUE(caught);
 539
 540   // Check max_size works right with various policy combinations.
 541   folly::small_vector<std::string,32,uint32_t,NoHeap,OneBitMutex> v2;
 542   EXPECT_EQ(v2.max_size(), 32);
 543   folly::small_vector<std::string,32,uint32_t,OneBitMutex> v3;
 544   EXPECT_EQ(v3.max_size(), (1ul << 30) - 1);
 545   folly::small_vector<std::string,32,uint32_t> v4;
 546   EXPECT_EQ(v4.max_size(), (1ul << 31) - 1);
 547
 548   /*
 549    * Test that even when we ask for a small number inlined it'll still
 550    * inline at least as much as it takes to store the value_type
 551    * pointer.
 552    */
 553   folly::small_vector<char,1,NoHeap> notsosmall;
 554   EXPECT_EQ(notsosmall.max_size(), sizeof(char*));
 555   caught = false;
 556   try {
 557     notsosmall.push_back(12);
 558     notsosmall.push_back(13);
 559     notsosmall.push_back(14);
 560   } catch (const std::length_error&) {
 561     caught = true;
 562   }
 563   EXPECT_FALSE(caught);
 564 }
 565
 566 TEST(small_vector, MaxSize) {
 567   folly::small_vector<int,2,uint8_t> vec;
 568   EXPECT_EQ(vec.max_size(), 127);
 569   folly::small_vector<int,2,uint16_t> vec2;
 570   EXPECT_EQ(vec2.max_size(), (1 << 15) - 1);
 571   folly::small_vector<int,2,uint16_t,OneBitMutex> vec3;
 572   EXPECT_EQ(vec3.max_size(), (1 << 14) - 1);
 573 }
 574
 575 TEST(small_vector, AllHeap) {
 576   // Use something bigger than the pointer so it can't get inlined.
 577   struct SomeObj {
 578     double a, b, c, d, e; int val;
 579     SomeObj(int val) : val(val) {}
 580     bool operator==(SomeObj const& o) const {
 581       return o.val == val;
 582     }
 583   };
 584
 585   folly::small_vector<SomeObj,0> vec = { 1 };
 586   EXPECT_EQ(vec.size(), 1);
 587   if (!vec.empty()) {
 588     EXPECT_TRUE(vec[0] == 1);
 589   }
 590   vec.insert(vec.begin(), { 0, 1, 2, 3 });
 591   EXPECT_EQ(vec.size(), 5);
 592   EXPECT_TRUE((vec == folly::small_vector<SomeObj,0>{ 0, 1, 2, 3, 1 }));
 593 }
 594
 595 TEST(small_vector, Basic) {
 596   typedef folly::small_vector<int,3,uint32_t
 597 #ifdef __x86_64__
 598     ,OneBitMutex
 599 #endif
 600   > Vector;
 601
 602   Vector a;
 603
 604 #ifdef __x86_64__
 605   a.lock();
 606   a.unlock();
 607 #endif
 608
 609   a.push_back(12);
 610   EXPECT_EQ(a.front(), 12);
 611   EXPECT_EQ(a.size(), 1);
 612   a.push_back(13);
 613   EXPECT_EQ(a.size(), 2);
 614   EXPECT_EQ(a.front(), 12);
 615   EXPECT_EQ(a.back(), 13);
 616
 617   a.emplace(a.end(), 32);
 618   EXPECT_EQ(a.back(), 32);
 619
 620   a.emplace(a.begin(), 12);
 621   EXPECT_EQ(a.front(), 12);
 622   EXPECT_EQ(a.back(), 32);
 623   a.erase(a.end() - 1);
 624   EXPECT_EQ(a.back(), 13);
 625
 626   a.push_back(12);
 627   EXPECT_EQ(a.back(), 12);
 628   a.pop_back();
 629   EXPECT_EQ(a.back(), 13);
 630
 631   const int s = 12;
 632   a.push_back(s); // lvalue reference
 633
 634   Vector b, c;
 635   b = a;
 636   EXPECT_TRUE(b == a);
 637   c = std::move(b);
 638   EXPECT_TRUE(c == a);
 639   EXPECT_TRUE(c != b && b != a);
 640
 641   EXPECT_GT(c.size(), 0);
 642   c.resize(1);
 643   EXPECT_EQ(c.size(), 1);
 644
 645   Vector intCtor(12);
 646 }
 647
 648 TEST(small_vector, Capacity) {
 649   folly::small_vector<unsigned long, 1> vec;
 650   EXPECT_EQ(vec.size(), 0);
 651   EXPECT_EQ(vec.capacity(), 1);
 652
 653   vec.push_back(0);
 654   EXPECT_EQ(vec.size(), 1);
 655   EXPECT_EQ(vec.capacity(), 1);
 656
 657   vec.push_back(1);
 658   EXPECT_EQ(vec.size(), 2);
 659   EXPECT_GT(vec.capacity(), 1);
 660
 661
 662   folly::small_vector<unsigned long, 2> vec2;
 663   EXPECT_EQ(vec2.size(), 0);
 664   EXPECT_EQ(vec2.capacity(), 2);
 665
 666   vec2.push_back(0);
 667   vec2.push_back(1);
 668   EXPECT_EQ(vec2.size(), 2);
 669   EXPECT_EQ(vec2.capacity(), 2);
 670
 671   vec2.push_back(2);
 672   EXPECT_EQ(vec2.size(), 3);
 673   EXPECT_GT(vec2.capacity(), 2);
 674
 675   // Both have grown by the minimum amount
 676   EXPECT_EQ(vec.capacity(), vec2.capacity());
 677
 678   // Test capacity heapifying logic
 679   folly::small_vector<unsigned char, 1> vec3;
 680   const size_t hc_size = 1000000;
 681   for (size_t i = 0; i < hc_size; ++i) {
 682     auto v = (unsigned char)i;
 683     vec3.push_back(v);
 684     EXPECT_EQ(vec3[i], v);
 685     EXPECT_EQ(vec3.size(), i + 1);
 686     EXPECT_GT(vec3.capacity(), i);
 687   }
 688   for (auto i = hc_size; i > 0; --i) {
 689     auto v = (unsigned char)(i - 1);
 690     EXPECT_EQ(vec3.back(), v);
 691     vec3.pop_back();
 692     EXPECT_EQ(vec3.size(), i - 1);
 693   }
 694 }
 695
 696 TEST(small_vector, SelfPushBack) {
 697   for (int i = 1; i < 33; ++i) {
 698     folly::small_vector<std::string> vec;
 699     for (int j = 0; j < i; ++j) {
 700       vec.push_back("abc");
 701     }
 702     EXPECT_EQ(vec.size(), i);
 703     vec.push_back(std::move(vec[0]));
 704     EXPECT_EQ(vec.size(), i + 1);
 705
 706     EXPECT_EQ(vec[i], "abc");
 707   }
 708 }
 709
 710 TEST(small_vector, SelfEmplaceBack) {
 711   for (int i = 1; i < 33; ++i) {
 712     folly::small_vector<std::string> vec;
 713     for (int j = 0; j < i; ++j) {
 714       vec.emplace_back("abc");
 715     }
 716     EXPECT_EQ(vec.size(), i);
 717     vec.emplace_back(std::move(vec[0]));
 718     EXPECT_EQ(vec.size(), i + 1);
 719
 720     EXPECT_EQ(vec[i], "abc");
 721   }
 722 }
 723
 724 TEST(small_vector, SelfInsert) {
 725   // end insert
 726   for (int i = 1; i < 33; ++i) {
 727     folly::small_vector<std::string> vec;
 728     for (int j = 0; j < i; ++j) {
 729       vec.push_back("abc");
 730     }
 731     EXPECT_EQ(vec.size(), i);
 732     vec.insert(vec.end(), std::move(vec[0]));
 733     EXPECT_EQ(vec.size(), i + 1);
 734
 735     EXPECT_EQ(vec[i], "abc");
 736     EXPECT_EQ(vec[vec.size() - 1], "abc");
 737   }
 738
 739   // middle insert
 740   for (int i = 2; i < 33; ++i) {
 741     folly::small_vector<std::string> vec;
 742     for (int j = 0; j < i; ++j) {
 743       vec.push_back("abc");
 744     }
 745     EXPECT_EQ(vec.size(), i);
 746     vec.insert(vec.end()-1, std::move(vec[0]));
 747     EXPECT_EQ(vec.size(), i + 1);
 748
 749     EXPECT_EQ(vec[i-1], "abc");
 750     EXPECT_EQ(vec[i], "abc");
 751   }
 752 }