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