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