folly/test/small_vector_test.cpp

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