small_vector_test.cpp File Reference

#include <folly/small_vector.h>
#include <folly/sorted_vector_types.h>
#include <iostream>
#include <iterator>
#include <limits>
#include <memory>
#include <sstream>
#include <string>
#include <vector>
#include <boost/algorithm/string.hpp>
#include <folly/Conv.h>
#include <folly/Traits.h>
#include <folly/portability/GTest.h>

Go to the source code of this file.

Classes
struct	CheckedInt

Functions
	TEST (small_vector, BasicGuarantee)
	TEST (small_vector, leak_test)
	TEST (small_vector, Insert)
	TEST (small_vector, Swap)
	TEST (small_vector, Emplace)
	TEST (small_vector, Erase)
	TEST (small_vector, GrowShrinkGrow)
	TEST (small_vector, Iteration)
	TEST (small_vector, NonCopyableType)
	TEST (small_vector, MoveConstructor)
	TEST (small_vector, NoHeap)
	TEST (small_vector, MaxSize)
	TEST (small_vector, AllHeap)
	TEST (small_vector, Basic)
	TEST (small_vector, Capacity)
	TEST (small_vector, SelfPushBack)
	TEST (small_vector, SelfEmplaceBack)
	TEST (small_vector, SelfInsert)
	TEST (small_vector, ForwardingEmplaceInsideVector)
	TEST (small_vector, LVEmplaceInsideVector)
	TEST (small_vector, CLVEmplaceInsideVector)
	TEST (small_vector, RVEmplaceInsideVector)
	TEST (small_vector, LVPushValueInsideVector)
	TEST (small_vector, RVPushValueInsideVector)
	TEST (small_vector, EmplaceIterCtor)
	TEST (small_vector, InputIterator)
	TEST (small_vector, NoCopyCtor)
	TEST (small_vector, ZeroInitializable)
	TEST (small_vector, InsertMoreThanGrowth)
	TEST (small_vector, EmplaceBackExponentialGrowth)
	TEST (small_vector, InsertExponentialGrowth)
	TEST (small_vector, InsertNExponentialGrowth)
	TEST (small_vector, EmplaceBackEfficiency)
	TEST (small_vector, RVPushBackEfficiency)
	TEST (small_vector, CLVPushBackEfficiency)
	TEST (small_vector, StorageForSortedVectorMap)
	TEST (small_vector, NoHeapStorageForSortedVectorMap)
	TEST (small_vector, StorageForSortedVectorSet)
	TEST (small_vector, NoHeapStorageForSortedVectorSet)
	TEST (small_vector, SelfMoveAssignmentForVectorOfPair)
	TEST (small_vector, SelfCopyAssignmentForVectorOfPair)

Function Documentation

TEST	(	small_vector	,
		BasicGuarantee
	)

Definition at line 265 of file small_vector_test.cpp.

References b, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::begin(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::emplace_back(), EXPECT_EQ, i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::insert(), and v.

                                   {
  for (int prepop = 1; prepop < 30; ++prepop) {
    (TestBasicGuarantee(prepop))( // parens or a mildly vexing parse :(
        1,
        [&](folly::small_vector<Thrower, 3>& v) { v.emplace_back(); });

    EXPECT_EQ(Thrower::alive, 0);

    (TestBasicGuarantee(prepop))(1, [&](folly::small_vector<Thrower, 3>& v) {
      v.insert(v.begin(), Thrower());
    });

    EXPECT_EQ(Thrower::alive, 0);

    (TestBasicGuarantee(prepop))(1, [&](folly::small_vector<Thrower, 3>& v) {
      v.insert(v.begin() + 1, Thrower());
    });

    EXPECT_EQ(Thrower::alive, 0);
  }

  TestBasicGuarantee(4)(3, [&](folly::small_vector<Thrower, 3>& v) {
    std::vector<Thrower> b;
    b.emplace_back();
    b.emplace_back();
    b.emplace_back();

    /*
     * Apparently if you do the following initializer_list instead
     * of the above push_back's, and one of the Throwers throws,
     * g++4.6 doesn't destruct the previous ones.  Heh.
     */
    // b = { Thrower(), Thrower(), Thrower() };
    v.insert(v.begin() + 1, b.begin(), b.end());
  });

  TestBasicGuarantee(2)(6, [&](folly::small_vector<Thrower, 3>& v) {
    std::vector<Thrower> b;
    for (int i = 0; i < 6; ++i) {
      b.emplace_back();
    }

    v.insert(v.begin() + 1, b.begin(), b.end());
  });

  EXPECT_EQ(Thrower::alive, 0);
  try {
    throwCounter = 4;
    folly::small_vector<Thrower, 1> p(14, Thrower());
  } catch (...) {
  }
  EXPECT_EQ(Thrower::alive, 0);
}

TEST	(	small_vector	,
		leak_test
	)

Definition at line 323 of file small_vector_test.cpp.

References i, and folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back().

                              {
  for (int j = 0; j < 1000; ++j) {
    folly::small_vector<int, 10> someVec(300);
    for (int i = 0; i < 10000; ++i) {
      someVec.push_back(12);
    }
  }
}

TEST	(	small_vector	,
		Insert
	)

Definition at line 332 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::begin(), EXPECT_EQ, EXPECT_TRUE, i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::insert(), and folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size().

                           {
  folly::small_vector<int> someVec(3, 3);
  someVec.insert(someVec.begin(), 12, 12);
  EXPECT_EQ(someVec.size(), 15);
  for (size_t i = 0; i < someVec.size(); ++i) {
    if (i < 12) {
      EXPECT_EQ(someVec[i], 12);
    } else {
      EXPECT_EQ(someVec[i], 3);
    }
  }

  auto oldSize = someVec.size();
  someVec.insert(someVec.begin() + 1, 12, 12);
  EXPECT_EQ(someVec.size(), oldSize + 12);

  folly::small_vector<std::string> v1(6, "asd"), v2(7, "wat");
  v1.insert(v1.begin() + 1, v2.begin(), v2.end());
  EXPECT_TRUE(v1.size() == 6 + 7);
  EXPECT_EQ(v1.front(), "asd");
  EXPECT_EQ(v1[1], "wat");
}

TEST	(	small_vector	,
		Swap
	)

Definition at line 355 of file small_vector_test.cpp.

References folly::gen::all(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::assign(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::begin(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::end(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::erase(), EXPECT_EQ, EXPECT_FALSE, EXPECT_LT, EXPECT_TRUE, i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size(), and folly::swap().

                         {
  folly::small_vector<int, 10> somethingVec, emptyVec;
  somethingVec.push_back(1);
  somethingVec.push_back(2);
  somethingVec.push_back(3);
  somethingVec.push_back(4);

  // Swapping intern'd with intern'd.
  auto vec = somethingVec;
  EXPECT_TRUE(vec == somethingVec);
  EXPECT_FALSE(vec == emptyVec);
  EXPECT_FALSE(somethingVec == emptyVec);

  // Swapping a heap vector with an intern vector.
  folly::small_vector<int, 10> junkVec;
  junkVec.assign(12, 12);
  EXPECT_EQ(junkVec.size(), 12);
  for (auto i : junkVec) {
    EXPECT_EQ(i, 12);
  }
  swap(junkVec, vec);
  EXPECT_TRUE(junkVec == somethingVec);
  EXPECT_EQ(vec.size(), 12);
  for (auto i : vec) {
    EXPECT_EQ(i, 12);
  }

  // Swapping two heap vectors.
  folly::small_vector<int, 10> moreJunk(15, 15);
  EXPECT_EQ(moreJunk.size(), 15);
  for (auto i : moreJunk) {
    EXPECT_EQ(i, 15);
  }
  swap(vec, moreJunk);
  EXPECT_EQ(moreJunk.size(), 12);
  for (auto i : moreJunk) {
    EXPECT_EQ(i, 12);
  }
  EXPECT_EQ(vec.size(), 15);
  for (auto i : vec) {
    EXPECT_EQ(i, 15);
  }

  // Making a vector heap, then smaller than another non-heap vector,
  // then swapping.
  folly::small_vector<int, 5> shrinker, other(4, 10);
  shrinker = {0, 1, 2, 3, 4, 5, 6, 7, 8};
  shrinker.erase(shrinker.begin() + 2, shrinker.end());
  EXPECT_LT(shrinker.size(), other.size());
  swap(shrinker, other);
  EXPECT_EQ(shrinker.size(), 4);
  EXPECT_TRUE(boost::all(shrinker, boost::is_any_of(std::vector<int>{10})));
  EXPECT_TRUE((other == small_vector<int, 5>{0, 1}));
}

TEST	(	small_vector	,
		Emplace
	)

Definition at line 410 of file small_vector_test.cpp.

References a, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::back(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::begin(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::emplace(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::emplace_back(), EXPECT_EQ, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::front(), i, and folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::reserve().

                            {
  NontrivialType::ctored = 0;

  folly::small_vector<NontrivialType> vec;
  vec.reserve(1024);
  vec.emplace_back(12);
  EXPECT_EQ(NontrivialType::ctored, 1);
  EXPECT_EQ(vec.front().a, 12);
  vec.emplace_back(13);
  EXPECT_EQ(vec.front().a, 12);
  EXPECT_EQ(vec.back().a, 13);
  EXPECT_EQ(NontrivialType::ctored, 2);

  NontrivialType::ctored = 0;
  for (int i = 0; i < 120; ++i) {
    vec.emplace_back(i);
  }
  EXPECT_EQ(NontrivialType::ctored, 120);
  EXPECT_EQ(vec[0].a, 12);
  EXPECT_EQ(vec[1].a, 13);
  EXPECT_EQ(vec.back().a, 119);

  // We implement emplace() with a temporary (see the implementation
  // for a comment about why), so this should make 2 ctor calls.
  NontrivialType::ctored = 0;
  vec.emplace(vec.begin(), 12);
  EXPECT_EQ(NontrivialType::ctored, 2);
}

TEST	(	small_vector	,
		Erase
	)

Definition at line 439 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::back(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::begin(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::empty(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::end(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::erase(), EXPECT_EQ, EXPECT_TRUE, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::front(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::resize(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size(), and v.

                          {
  folly::small_vector<int, 4> notherVec = {1, 2, 3, 4, 5};
  EXPECT_EQ(notherVec.front(), 1);
  EXPECT_EQ(notherVec.size(), 5);
  notherVec.erase(notherVec.begin());
  EXPECT_EQ(notherVec.front(), 2);
  EXPECT_EQ(notherVec.size(), 4);
  EXPECT_EQ(notherVec[2], 4);
  EXPECT_EQ(notherVec[3], 5);
  notherVec.erase(notherVec.begin() + 2);
  EXPECT_EQ(notherVec.size(), 3);
  EXPECT_EQ(notherVec[2], 5);

  folly::small_vector<int, 2> vec2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  vec2.erase(vec2.begin() + 1, vec2.end() - 1);
  folly::small_vector<int, 2> expected = {1, 10};
  EXPECT_TRUE(vec2 == expected);

  folly::small_vector<std::string, 3> v(102, "ASD");
  v.resize(1024, "D");
  EXPECT_EQ(v.size(), 1024);
  EXPECT_EQ(v.back(), "D");
  EXPECT_EQ(v.front(), "ASD");
  v.resize(1);
  EXPECT_EQ(v.front(), "ASD");
  EXPECT_EQ(v.size(), 1);
  v.resize(0);
  EXPECT_TRUE(v.empty());
}

TEST	(	small_vector	,
		GrowShrinkGrow
	)

Definition at line 469 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::begin(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::capacity(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::empty(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::erase(), EXPECT_EQ, EXPECT_GT, EXPECT_LT, EXPECT_TRUE, i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::resize(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::shrink_to_fit(), and folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size().

                                   {
  folly::small_vector<NontrivialType, 7> vec = {1, 2, 3, 4, 5};
  std::generate_n(std::back_inserter(vec), 102, std::rand);

  auto capacity = vec.capacity();

  auto oldSize = vec.size();
  for (size_t i = 0; i < oldSize; ++i) {
    vec.erase(vec.begin() + (std::rand() % vec.size()));
    EXPECT_EQ(vec.capacity(), capacity);
  }
  EXPECT_TRUE(vec.empty());

  EXPECT_EQ(vec.capacity(), capacity);
  std::generate_n(std::back_inserter(vec), 102, std::rand);
  EXPECT_EQ(vec.capacity(), capacity);

  std::generate_n(std::back_inserter(vec), 4096, std::rand);
  EXPECT_GT(vec.capacity(), capacity);

  vec.resize(10);
  vec.shrink_to_fit();
  EXPECT_LT(vec.capacity(), capacity);
  vec.resize(4);
  vec.shrink_to_fit();
  EXPECT_EQ(vec.capacity(), 7); // in situ size
}

TEST	(	small_vector	,
		Iteration
	)

Definition at line 497 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::begin(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::erase(), EXPECT_EQ, EXPECT_TRUE, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back(), and s.

                              {
  folly::small_vector<std::string, 3> vec = {"foo", "bar"};
  vec.push_back("blah");
  vec.push_back("blah2");
  vec.push_back("blah3");
  vec.erase(vec.begin() + 2);

  std::vector<std::string> otherVec;
  for (auto& s : vec) {
    otherVec.push_back(s);
  }
  EXPECT_EQ(otherVec.size(), vec.size());
  if (otherVec.size() == vec.size()) {
    EXPECT_TRUE(std::equal(otherVec.begin(), otherVec.end(), vec.begin()));
  }

  std::reverse(otherVec.begin(), otherVec.end());
  auto oit = otherVec.begin();
  auto rit = vec.crbegin();
  for (; rit != vec.crend(); ++oit, ++rit) {
    EXPECT_EQ(*oit, *rit);
  }
}

TEST	(	small_vector	,
		NonCopyableType
	)

Definition at line 521 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::begin(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::emplace(), EXPECT_EQ, i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::insert(), folly::gen::move, and folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size().

                                    {
  folly::small_vector<NontrivialType, 2> vec;

  for (int i = 0; i < 10; ++i) {
    vec.emplace(vec.begin(), 13);
  }
  EXPECT_EQ(vec.size(), 10);
  auto vec2 = std::move(vec);
  EXPECT_EQ(vec.size(), 0);
  EXPECT_EQ(vec2.size(), 10);
  vec2.clear();

  folly::small_vector<NoncopyableCounter, 3> vec3;
  for (int i = 0; i < 10; ++i) {
    EXPECT_EQ(vec3.size(), i);
    EXPECT_EQ(NoncopyableCounter::alive, i);
    vec3.insert(vec3.begin(), NoncopyableCounter());
  }
  EXPECT_EQ(vec3.size(), 10);
  EXPECT_EQ(NoncopyableCounter::alive, 10);

  vec3.insert(vec3.begin() + 3, NoncopyableCounter());
  EXPECT_EQ(NoncopyableCounter::alive, 11);
  auto vec4 = std::move(vec3);
  EXPECT_EQ(NoncopyableCounter::alive, 11);
  vec4.resize(30);
  EXPECT_EQ(NoncopyableCounter::alive, 30);
  vec4.erase(vec4.begin(), vec4.end());
  EXPECT_EQ(vec4.size(), 0);
  EXPECT_EQ(NoncopyableCounter::alive, 0);
}

TEST	(	small_vector	,
		MoveConstructor
	)

Definition at line 553 of file small_vector_test.cpp.

References EXPECT_EQ, folly::gen::move, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back(), and folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size().

                                    {
  folly::small_vector<std::string, 10> v1;
  v1.push_back("asd");
  v1.push_back("bsd");
  auto v2 = std::move(v1);
  EXPECT_EQ(v2.size(), 2);
  EXPECT_EQ(v2[0], "asd");
  EXPECT_EQ(v2[1], "bsd");

  v1 = std::move(v2);
  EXPECT_EQ(v1.size(), 2);
  EXPECT_EQ(v1[0], "asd");
  EXPECT_EQ(v1[1], "bsd");
}

TEST	(	small_vector	,
		NoHeap
	)

Definition at line 568 of file small_vector_test.cpp.

References EXPECT_EQ, EXPECT_FALSE, EXPECT_TRUE, i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::max_size(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back(), string, and v.

                           {
  typedef folly::small_vector<
      std::string,
      10,
      std::size_t,
      folly::small_vector_policy::NoHeap>
      Vector;

  Vector v;
  static_assert(v.max_size() == 10, "max_size is incorrect");

  for (int i = 0; i < 10; ++i) {
    v.push_back(folly::to<std::string>(i));
    EXPECT_EQ(v.size(), i + 1);
  }

  bool caught = false;
  try {
    v.insert(v.begin(), "ha");
  } catch (const std::length_error&) {
    caught = true;
  }
  EXPECT_TRUE(caught);

  // Check max_size works right with various policy combinations.
  folly::small_vector<std::string, 32, uint32_t> v4;
  EXPECT_EQ(v4.max_size(), (1ul << 31) - 1);

  /*
   * Test that even when we ask for a small number inlined it'll still
   * inline at least as much as it takes to store the value_type
   * pointer.
   */
  folly::small_vector<char, 1, NoHeap> notsosmall;
  static_assert(
      notsosmall.max_size() == sizeof(char*), "max_size is incorrect");
  caught = false;
  try {
    notsosmall.push_back(12);
    notsosmall.push_back(13);
    notsosmall.push_back(14);
  } catch (const std::length_error&) {
    caught = true;
  }
  EXPECT_FALSE(caught);
}

TEST	(	small_vector	,
		MaxSize
	)

Definition at line 615 of file small_vector_test.cpp.

References EXPECT_EQ, and folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::max_size().

                            {
  folly::small_vector<int, 2, uint8_t> vec;
  EXPECT_EQ(vec.max_size(), 127);
  folly::small_vector<int, 2, uint16_t> vec2;
  EXPECT_EQ(vec2.max_size(), (1 << 15) - 1);
}

TEST	(	small_vector	,
		AllHeap
	)

Definition at line 622 of file small_vector_test.cpp.

References a, b, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::begin(), c, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::empty(), EXPECT_EQ, EXPECT_TRUE, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::insert(), folly::operator==(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size(), and val.

                            {
  // Use something bigger than the pointer so it can't get inlined.
  struct SomeObj {
    double a, b, c, d, e;
    int val;
    SomeObj(int val_) : val(val_) {}
    bool operator==(SomeObj const& o) const {
      return o.val == val;
    }
  };

  folly::small_vector<SomeObj, 0> vec = {1};
  EXPECT_EQ(vec.size(), 1);
  if (!vec.empty()) {
    EXPECT_TRUE(vec[0] == 1);
  }
  vec.insert(vec.begin(), {0, 1, 2, 3});
  EXPECT_EQ(vec.size(), 5);
  EXPECT_TRUE((vec == folly::small_vector<SomeObj, 0>{0, 1, 2, 3, 1}));
}

TEST	(	small_vector	,
		Basic
	)

Definition at line 643 of file small_vector_test.cpp.

References a, b, c, EXPECT_EQ, EXPECT_GT, EXPECT_TRUE, folly::gen::move, and s.

                          {
  typedef folly::small_vector<int, 3, uint32_t> Vector;

  Vector a;

  a.push_back(12);
  EXPECT_EQ(a.front(), 12);
  EXPECT_EQ(a.size(), 1);
  a.push_back(13);
  EXPECT_EQ(a.size(), 2);
  EXPECT_EQ(a.front(), 12);
  EXPECT_EQ(a.back(), 13);

  a.emplace(a.end(), 32);
  EXPECT_EQ(a.back(), 32);

  a.emplace(a.begin(), 12);
  EXPECT_EQ(a.front(), 12);
  EXPECT_EQ(a.back(), 32);
  a.erase(a.end() - 1);
  EXPECT_EQ(a.back(), 13);

  a.push_back(12);
  EXPECT_EQ(a.back(), 12);
  a.pop_back();
  EXPECT_EQ(a.back(), 13);

  const int s = 12;
  a.push_back(s); // lvalue reference

  Vector b, c;
  b = a;
  EXPECT_TRUE(b == a);
  c = std::move(b);
  EXPECT_TRUE(c == a);
  EXPECT_TRUE(c != b && b != a);

  EXPECT_GT(c.size(), 0);
  c.resize(1);
  EXPECT_EQ(c.size(), 1);

  Vector intCtor(12);
}

TEST	(	small_vector	,
		Capacity
	)

Definition at line 687 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::capacity(), EXPECT_EQ, EXPECT_GT, i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size(), and v.

                             {
  folly::small_vector<uint64_t, 1> vec;
  EXPECT_EQ(vec.size(), 0);
  EXPECT_EQ(vec.capacity(), 1);

  vec.push_back(0);
  EXPECT_EQ(vec.size(), 1);
  EXPECT_EQ(vec.capacity(), 1);

  vec.push_back(1);
  EXPECT_EQ(vec.size(), 2);
  EXPECT_GT(vec.capacity(), 1);

  folly::small_vector<uint64_t, 2> vec2;
  EXPECT_EQ(vec2.size(), 0);
  EXPECT_EQ(vec2.capacity(), 2);

  vec2.push_back(0);
  vec2.push_back(1);
  EXPECT_EQ(vec2.size(), 2);
  EXPECT_EQ(vec2.capacity(), 2);

  vec2.push_back(2);
  EXPECT_EQ(vec2.size(), 3);
  EXPECT_GT(vec2.capacity(), 2);

  // Test capacity heapifying logic
  folly::small_vector<unsigned char, 1> vec3;
  const size_t hc_size = 100000;
  for (size_t i = 0; i < hc_size; ++i) {
    auto v = (unsigned char)i;
    vec3.push_back(v);
    EXPECT_EQ(vec3[i], v);
    EXPECT_EQ(vec3.size(), i + 1);
    EXPECT_GT(vec3.capacity(), i);
  }
  for (auto i = hc_size; i > 0; --i) {
    auto v = (unsigned char)(i - 1);
    EXPECT_EQ(vec3.back(), v);
    vec3.pop_back();
    EXPECT_EQ(vec3.size(), i - 1);
  }
}

TEST	(	small_vector	,
		SelfPushBack
	)

Definition at line 731 of file small_vector_test.cpp.

References EXPECT_EQ, i, folly::gen::move, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back(), and folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size().

                                 {
  for (int i = 1; i < 33; ++i) {
    folly::small_vector<std::string> vec;
    for (int j = 0; j < i; ++j) {
      vec.push_back("abc");
    }
    EXPECT_EQ(vec.size(), i);
    vec.push_back(std::move(vec[0]));
    EXPECT_EQ(vec.size(), i + 1);

    EXPECT_EQ(vec[i], "abc");
  }
}

TEST	(	small_vector	,
		SelfEmplaceBack
	)

Definition at line 745 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::emplace_back(), EXPECT_EQ, i, folly::gen::move, and folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size().

                                    {
  for (int i = 1; i < 33; ++i) {
    folly::small_vector<std::string> vec;
    for (int j = 0; j < i; ++j) {
      vec.emplace_back("abc");
    }
    EXPECT_EQ(vec.size(), i);
    vec.emplace_back(std::move(vec[0]));
    EXPECT_EQ(vec.size(), i + 1);

    EXPECT_EQ(vec[i], "abc");
  }
}

TEST	(	small_vector	,
		SelfInsert
	)

Definition at line 759 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::end(), EXPECT_EQ, i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::insert(), folly::gen::move, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back(), and folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size().

                               {
  // end insert
  for (int i = 1; i < 33; ++i) {
    folly::small_vector<std::string> vec;
    for (int j = 0; j < i; ++j) {
      vec.push_back("abc");
    }
    EXPECT_EQ(vec.size(), i);
    vec.insert(vec.end(), std::move(vec[0]));
    EXPECT_EQ(vec.size(), i + 1);

    EXPECT_EQ(vec[i], "abc");
    EXPECT_EQ(vec[vec.size() - 1], "abc");
  }

  // middle insert
  for (int i = 2; i < 33; ++i) {
    folly::small_vector<std::string> vec;
    for (int j = 0; j < i; ++j) {
      vec.push_back("abc");
    }
    EXPECT_EQ(vec.size(), i);
    vec.insert(vec.end() - 1, std::move(vec[0]));
    EXPECT_EQ(vec.size(), i + 1);

    EXPECT_EQ(vec[i - 1], "abc");
    EXPECT_EQ(vec[i], "abc");
  }
}

TEST	(	small_vector	,
		ForwardingEmplaceInsideVector
	)

Definition at line 811 of file small_vector_test.cpp.

References ASSERT_EQ, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::back(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::emplace_back(), i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back(), v, and CheckedInt::value.

                                                  {
  folly::small_vector<CheckedInt> v;
  v.push_back(CheckedInt(1));
  for (int i = 1; i < 20; ++i) {
    v.emplace_back(v[0], 42);
    ASSERT_EQ(1, v.back().value);
  }
}

TEST	(	small_vector	,
		LVEmplaceInsideVector
	)

Definition at line 820 of file small_vector_test.cpp.

References ASSERT_EQ, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::back(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::emplace_back(), i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back(), v, and CheckedInt::value.

                                          {
  folly::small_vector<CheckedInt> v;
  v.push_back(CheckedInt(1));
  for (int i = 1; i < 20; ++i) {
    v.emplace_back(v[0]);
    ASSERT_EQ(1, v.back().value);
  }
}

TEST	(	small_vector	,
		CLVEmplaceInsideVector
	)

Definition at line 829 of file small_vector_test.cpp.

References ASSERT_EQ, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::back(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::emplace_back(), i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back(), v, and CheckedInt::value.

                                           {
  folly::small_vector<CheckedInt> v;
  const folly::small_vector<CheckedInt>& cv = v;
  v.push_back(CheckedInt(1));
  for (int i = 1; i < 20; ++i) {
    v.emplace_back(cv[0]);
    ASSERT_EQ(1, v.back().value);
  }
}

TEST	(	small_vector	,
		RVEmplaceInsideVector
	)

Definition at line 839 of file small_vector_test.cpp.

References ASSERT_EQ, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::back(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::emplace_back(), i, folly::gen::move, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back(), v, and CheckedInt::value.

                                          {
  folly::small_vector<CheckedInt> v;
  v.push_back(CheckedInt(0));
  for (int i = 1; i < 20; ++i) {
    v[0] = CheckedInt(1);
    v.emplace_back(std::move(v[0]));
    ASSERT_EQ(1, v.back().value);
  }
}

TEST	(	small_vector	,
		LVPushValueInsideVector
	)

Definition at line 849 of file small_vector_test.cpp.

References ASSERT_EQ, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::back(), i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back(), v, and CheckedInt::value.

                                            {
  folly::small_vector<CheckedInt> v;
  v.push_back(CheckedInt(1));
  for (int i = 1; i < 20; ++i) {
    v.push_back(v[0]);
    ASSERT_EQ(1, v.back().value);
  }
}

TEST	(	small_vector	,
		RVPushValueInsideVector
	)

Definition at line 858 of file small_vector_test.cpp.

References ASSERT_EQ, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::back(), i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back(), v, and CheckedInt::value.

                                            {
  folly::small_vector<CheckedInt> v;
  v.push_back(CheckedInt(0));
  for (int i = 1; i < 20; ++i) {
    v[0] = CheckedInt(1);
    v.push_back(v[0]);
    ASSERT_EQ(1, v.back().value);
  }
}

TEST	(	small_vector	,
		EmplaceIterCtor
	)

Definition at line 868 of file small_vector_test.cpp.

                                    {
  std::vector<int*> v{new int(1), new int(2)};
  std::vector<std::unique_ptr<int>> uv(v.begin(), v.end());

  std::vector<int*> w{new int(1), new int(2)};
  small_vector<std::unique_ptr<int>> uw(w.begin(), w.end());
}

TEST	(	small_vector	,
		InputIterator
	)

Definition at line 876 of file small_vector_test.cpp.

References ASSERT_EQ, i, string, and values().

                                  {
  std::vector<int> expected{125, 320, 512, 750, 333};
  std::string values = "125 320 512 750 333";
  std::istringstream is1(values);
  std::istringstream is2(values);

  std::vector<int> stdV{std::istream_iterator<int>(is1),
                        std::istream_iterator<int>()};
  ASSERT_EQ(stdV.size(), expected.size());
  for (size_t i = 0; i < expected.size(); i++) {
    ASSERT_EQ(stdV[i], expected[i]);
  }

  small_vector<int> smallV{std::istream_iterator<int>(is2),
                           std::istream_iterator<int>()};
  ASSERT_EQ(smallV.size(), expected.size());
  for (size_t i = 0; i < expected.size(); i++) {
    ASSERT_EQ(smallV[i], expected[i]);
  }
}

TEST	(	small_vector	,
		NoCopyCtor
	)

Definition at line 897 of file small_vector_test.cpp.

References ASSERT_EQ, EXPECT_EQ, folly::gen::field(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size(), and test().

                               {
  struct Test {
    Test() = default;
    Test(const Test&) = delete;
    Test(Test&&) = default;

    int field = 42;
  };

  small_vector<Test> test(10);
  ASSERT_EQ(test.size(), 10);
  for (const auto& element : test) {
    EXPECT_EQ(element.field, 42);
  }
}

TEST	(	small_vector	,
		ZeroInitializable
	)

Definition at line 913 of file small_vector_test.cpp.

References ASSERT_EQ, EXPECT_EQ, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size(), and test().

                                      {
  small_vector<int> test(10);
  ASSERT_EQ(test.size(), 10);
  for (const auto& element : test) {
    EXPECT_EQ(element, 0);
  }
}

TEST	(	small_vector	,
		InsertMoreThanGrowth
	)

Definition at line 921 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::end(), EXPECT_EQ, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::insert(), and test().

                                         {
  small_vector<int, 10> test;
  test.insert(test.end(), 30, 0);
  for (auto element : test) {
    EXPECT_EQ(element, 0);
  }
}

TEST	(	small_vector	,
		EmplaceBackExponentialGrowth
	)

Definition at line 929 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::capacity(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::emplace_back(), EXPECT_LE, i, and test().

                                                 {
  small_vector<std::pair<int, int>> test;
  std::vector<size_t> capacities;
  capacities.push_back(test.capacity());
  for (int i = 0; i < 10000; ++i) {
    test.emplace_back(0, 0);
    if (test.capacity() != capacities.back()) {
      capacities.push_back(test.capacity());
    }
  }
  EXPECT_LE(capacities.size(), 25);
}

TEST	(	small_vector	,
		InsertExponentialGrowth
	)

Definition at line 942 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::begin(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::capacity(), EXPECT_LE, i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::insert(), and test().

                                            {
  small_vector<std::pair<int, int>> test;
  std::vector<size_t> capacities;
  capacities.push_back(test.capacity());
  for (int i = 0; i < 10000; ++i) {
    test.insert(test.begin(), std::make_pair(0, 0));
    if (test.capacity() != capacities.back()) {
      capacities.push_back(test.capacity());
    }
  }
  EXPECT_LE(capacities.size(), 25);
}

TEST	(	small_vector	,
		InsertNExponentialGrowth
	)

Definition at line 955 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::begin(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::capacity(), EXPECT_EQ, EXPECT_LE, i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::insert(), folly::pushmi::__adl::noexcept(), folly::detail::rhs, and test().

                                             {
  small_vector<int> test;
  std::vector<size_t> capacities;
  capacities.push_back(test.capacity());
  for (int i = 0; i < 10000; ++i) {
    test.insert(test.begin(), 100, 0);
    if (test.capacity() != capacities.back()) {
      capacities.push_back(test.capacity());
    }
  }
  EXPECT_LE(capacities.size(), 25);
}

TEST	(	small_vector	,
		EmplaceBackEfficiency
	)

Definition at line 998 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::capacity(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::emplace_back(), EXPECT_EQ, EXPECT_LT, i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size(), and test().

                                          {
  small_vector<Counter, 2> test;
  Counts counts;
  for (size_t i = 1; i <= test.capacity(); ++i) {
    test.emplace_back(counts);
    EXPECT_EQ(0, counts.copyCount);
    EXPECT_EQ(0, counts.moveCount);
  }
  EXPECT_EQ(test.size(), test.capacity());
  test.emplace_back(counts);
  // Every element except the last has to be moved to the new position
  EXPECT_EQ(0, counts.copyCount);
  EXPECT_EQ(test.size() - 1, counts.moveCount);
  EXPECT_LT(test.size(), test.capacity());
}

TEST	(	small_vector	,
		RVPushBackEfficiency
	)

Definition at line 1014 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::capacity(), EXPECT_EQ, EXPECT_LT, i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size(), and test().

                                         {
  small_vector<Counter, 2> test;
  Counts counts;
  for (size_t i = 1; i <= test.capacity(); ++i) {
    test.push_back(Counter(counts));
    // 1 copy for each push_back()
    EXPECT_EQ(0, counts.copyCount);
    EXPECT_EQ(i, counts.moveCount);
  }
  EXPECT_EQ(test.size(), test.capacity());
  test.push_back(Counter(counts));
  // 1 move for each push_back()
  // Every element except the last has to be moved to the new position
  EXPECT_EQ(0, counts.copyCount);
  EXPECT_EQ(test.size() + test.size() - 1, counts.moveCount);
  EXPECT_LT(test.size(), test.capacity());
}

TEST	(	small_vector	,
		CLVPushBackEfficiency
	)

Definition at line 1032 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::capacity(), counter, EXPECT_EQ, EXPECT_LT, i, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::push_back(), folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size(), and test().

                                          {
  small_vector<Counter, 2> test;
  Counts counts;
  Counter const counter(counts);
  for (size_t i = 1; i <= test.capacity(); ++i) {
    test.push_back(counter);
    // 1 copy for each push_back()
    EXPECT_EQ(i, counts.copyCount);
    EXPECT_EQ(0, counts.moveCount);
  }
  EXPECT_EQ(test.size(), test.capacity());
  test.push_back(counter);
  // 1 copy for each push_back()
  EXPECT_EQ(test.size(), counts.copyCount);
  // Every element except the last has to be moved to the new position
  EXPECT_EQ(test.size() - 1, counts.moveCount);
  EXPECT_LT(test.size(), test.capacity());
}

TEST	(	small_vector	,
		StorageForSortedVectorMap
	)

Definition at line 1051 of file small_vector_test.cpp.

References EXPECT_EQ, and test().

                                              {
  small_sorted_vector_map<int32_t, int32_t, 2> test;
  test.insert(std::make_pair(10, 10));
  EXPECT_EQ(test.size(), 1);
  test.insert(std::make_pair(10, 10));
  EXPECT_EQ(test.size(), 1);
  test.insert(std::make_pair(20, 10));
  EXPECT_EQ(test.size(), 2);
  test.insert(std::make_pair(30, 10));
  EXPECT_EQ(test.size(), 3);
}

TEST	(	small_vector	,
		NoHeapStorageForSortedVectorMap
	)

Definition at line 1063 of file small_vector_test.cpp.

References EXPECT_EQ, EXPECT_THROW, and test().

                                                    {
  noheap_sorted_vector_map<int32_t, int32_t, 2> test;
  test.insert(std::make_pair(10, 10));
  EXPECT_EQ(test.size(), 1);
  test.insert(std::make_pair(10, 10));
  EXPECT_EQ(test.size(), 1);
  test.insert(std::make_pair(20, 10));
  EXPECT_EQ(test.size(), 2);
  EXPECT_THROW(test.insert(std::make_pair(30, 10)), std::length_error);
  EXPECT_EQ(test.size(), 2);
}

TEST	(	small_vector	,
		StorageForSortedVectorSet
	)

Definition at line 1075 of file small_vector_test.cpp.

References EXPECT_EQ, and test().

                                              {
  small_sorted_vector_set<int32_t, 2> test;
  test.insert(10);
  EXPECT_EQ(test.size(), 1);
  test.insert(10);
  EXPECT_EQ(test.size(), 1);
  test.insert(20);
  EXPECT_EQ(test.size(), 2);
  test.insert(30);
  EXPECT_EQ(test.size(), 3);
}

TEST	(	small_vector	,
		NoHeapStorageForSortedVectorSet
	)

Definition at line 1087 of file small_vector_test.cpp.

References EXPECT_EQ, EXPECT_THROW, and test().

                                                    {
  noheap_sorted_vector_set<int32_t, 2> test;
  test.insert(10);
  EXPECT_EQ(test.size(), 1);
  test.insert(10);
  EXPECT_EQ(test.size(), 1);
  test.insert(20);
  EXPECT_EQ(test.size(), 2);
  EXPECT_THROW(test.insert(30), std::length_error);
  EXPECT_EQ(test.size(), 2);
}

TEST	(	small_vector	,
		SelfMoveAssignmentForVectorOfPair
	)

Definition at line 1099 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::emplace_back(), EXPECT_EQ, folly::gen::first, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size(), and test().

                                                      {
  folly::small_vector<std::pair<int, int>, 2> test;
  test.emplace_back(13, 2);
  EXPECT_EQ(test.size(), 1);
  EXPECT_EQ(test[0].first, 13);
  test = static_cast<decltype(test)&&>(test); // suppress self-move warning
  EXPECT_EQ(test.size(), 1);
  EXPECT_EQ(test[0].first, 13);
}

TEST	(	small_vector	,
		SelfCopyAssignmentForVectorOfPair
	)

Definition at line 1109 of file small_vector_test.cpp.

References folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::emplace_back(), EXPECT_EQ, folly::gen::first, folly::small_vector< Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC >::size(), and test().

                                                      {
  folly::small_vector<std::pair<int, int>, 2> test;
  test.emplace_back(13, 2);
  EXPECT_EQ(test.size(), 1);
  EXPECT_EQ(test[0].first, 13);
  test = static_cast<decltype(test)&>(test); // suppress self-assign warning
  EXPECT_EQ(test.size(), 1);
  EXPECT_EQ(test[0].first, 13);
}