/*
- * Copyright 2014 Facebook, Inc.
+ * Copyright 2017 Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* limitations under the License.
*/
-#include "folly/small_vector.h"
+#include <folly/small_vector.h>
+#include <folly/sorted_vector_types.h>
-#include <gtest/gtest.h>
-#include <string>
-#include <memory>
#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/Conv.h>
+#include <folly/portability/GTest.h>
+#include <folly/portability/TypeTraits.h>
using folly::small_vector;
using namespace folly::small_vector_policy;
-#if defined(__x86_64__)
+#if FOLLY_X64 || FOLLY_PPC64
static_assert(sizeof(small_vector<int>) == 16,
"Object size is not what we expect for small_vector<int>");
8 + 1,
"small_vector<int32_t,1,uint32_t> is wrong size");
-static_assert(sizeof(small_vector<int32_t,1,OneBitMutex>) == 16,
- "OneBitMutex took more space than expected");
-
static_assert(sizeof(small_vector<int16_t,4,uint16_t>) == 10,
"Sizeof unexpectedly large");
-static_assert(sizeof(small_vector<int16_t,4,uint16_t,OneBitMutex>) == 10,
- "Sizeof unexpectedly large");
-static_assert(sizeof(small_vector<int16_t,4,NoHeap,uint16_t,
- OneBitMutex>) == 10,
- "Sizeof unexpectedly large");
#endif
namespace {
+template <typename Key, typename Value, size_t N>
+using small_sorted_vector_map = folly::sorted_vector_map<
+ Key,
+ Value,
+ std::less<Key>,
+ std::allocator<std::pair<Key, Value>>,
+ void,
+ folly::small_vector<std::pair<Key, Value>, N>>;
+
+template <typename Key, typename Value, size_t N>
+using noheap_sorted_vector_map = folly::sorted_vector_map<
+ Key,
+ Value,
+ std::less<Key>,
+ std::allocator<std::pair<Key, Value>>,
+ void,
+ folly::small_vector<
+ std::pair<Key, Value>,
+ N,
+ folly::small_vector_policy::NoHeap>>;
+
+template <typename T, size_t N>
+using small_sorted_vector_set = folly::sorted_vector_set<
+ T,
+ std::less<T>,
+ std::allocator<T>,
+ void,
+ folly::small_vector<T, N>>;
+
+template <typename T, size_t N>
+using noheap_sorted_vector_set = folly::sorted_vector_set<
+ T,
+ std::less<T>,
+ std::allocator<T>,
+ void,
+ folly::small_vector<T, N, folly::small_vector_policy::NoHeap>>;
+
struct NontrivialType {
static int ctored;
explicit NontrivialType() : a(0) {}
++ctored;
}
- NontrivialType(NontrivialType const& s) {
- ++ctored;
- }
+ NontrivialType(NontrivialType const& /* s */) { ++ctored; }
NontrivialType& operator=(NontrivialType const& o) {
a = o.a;
--alive;
}
- Thrower& operator=(Thrower const& other) {
+ Thrower& operator=(Thrower const& /* other */) {
EXPECT_EQ(magic, kMagic);
MaybeThrow();
return *this;
~NoncopyableCounter() {
--alive;
}
- NoncopyableCounter(NoncopyableCounter&&) { ++alive; }
+ NoncopyableCounter(NoncopyableCounter&&) noexcept { ++alive; }
NoncopyableCounter(NoncopyableCounter const&) = delete;
NoncopyableCounter& operator=(NoncopyableCounter const&) const = delete;
NoncopyableCounter& operator=(NoncopyableCounter&&) { return *this; }
{
throwCounter = 1000;
for (int i = 0; i < prepopulate; ++i) {
- vec.push_back(Thrower());
+ vec.emplace_back();
}
}
throwCounter = 1000;
}
- template<class Operation>
+ template <class Operation>
void operator()(int insertCount, Operation const& op) {
bool done = false;
std::unique_ptr<folly::small_vector<Thrower,3> > workingVec;
for (int counter = 1; !done; ++counter) {
throwCounter = 1000;
- workingVec.reset(new folly::small_vector<Thrower,3>(vec));
+ workingVec = std::make_unique<folly::small_vector<Thrower, 3>>(vec);
throwCounter = counter;
EXPECT_EQ(Thrower::alive, prepopulate * 2);
try {
}
};
-}
+} // namespace
TEST(small_vector, BasicGuarantee) {
for (int prepop = 1; prepop < 30; ++prepop) {
(TestBasicGuarantee(prepop))( // parens or a mildly vexing parse :(
1,
[&] (folly::small_vector<Thrower,3>& v) {
- v.push_back(Thrower());
+ v.emplace_back();
}
);
3,
[&] (folly::small_vector<Thrower,3>& v) {
std::vector<Thrower> b;
- b.push_back(Thrower());
- b.push_back(Thrower());
- b.push_back(Thrower());
+ b.emplace_back();
+ b.emplace_back();
+ b.emplace_back();
/*
* Apparently if you do the following initializer_list instead
[&] (folly::small_vector<Thrower,3>& v) {
std::vector<Thrower> b;
for (int i = 0; i < 6; ++i) {
- b.push_back(Thrower());
+ b.emplace_back();
}
v.insert(v.begin() + 1, b.begin(), b.end());
// Run this with.
// MALLOC_CONF=prof_leak:true
-// LD_PRELOAD=${JEMALLOC_PATH}/lib/libjemalloc.so.1
+// LD_PRELOAD=${JEMALLOC_PATH}/lib/libjemalloc.so.2
// LD_PRELOAD="$LD_PRELOAD:"${UNWIND_PATH}/lib/libunwind.so.7
TEST(small_vector, leak_test) {
for (int j = 0; j < 1000; ++j) {
folly::small_vector<int> someVec(3, 3);
someVec.insert(someVec.begin(), 12, 12);
EXPECT_EQ(someVec.size(), 15);
- for (int i = 0; i < someVec.size(); ++i) {
+ for (size_t i = 0; i < someVec.size(); ++i) {
if (i < 12) {
EXPECT_EQ(someVec[i], 12);
} else {
auto capacity = vec.capacity();
auto oldSize = vec.size();
- for (int i = 0; i < oldSize; ++i) {
+ for (size_t i = 0; i < oldSize; ++i) {
vec.erase(vec.begin() + (std::rand() % vec.size()));
EXPECT_EQ(vec.capacity(), capacity);
}
EXPECT_TRUE(caught);
// Check max_size works right with various policy combinations.
- folly::small_vector<std::string,32,uint32_t,NoHeap,OneBitMutex> v2;
- static_assert(v2.max_size() == 32, "max_size is incorrect");
- folly::small_vector<std::string,32,uint32_t,OneBitMutex> v3;
- EXPECT_EQ(v3.max_size(), (1ul << 30) - 1);
folly::small_vector<std::string,32,uint32_t> v4;
EXPECT_EQ(v4.max_size(), (1ul << 31) - 1);
EXPECT_EQ(vec.max_size(), 127);
folly::small_vector<int,2,uint16_t> vec2;
EXPECT_EQ(vec2.max_size(), (1 << 15) - 1);
- folly::small_vector<int,2,uint16_t,OneBitMutex> vec3;
- EXPECT_EQ(vec3.max_size(), (1 << 14) - 1);
}
TEST(small_vector, AllHeap) {
TEST(small_vector, Basic) {
typedef folly::small_vector<int,3,uint32_t
-#ifdef __x86_64__
- ,OneBitMutex
-#endif
> Vector;
Vector a;
-#ifdef __x86_64__
- a.lock();
- a.unlock();
-#endif
-
a.push_back(12);
EXPECT_EQ(a.front(), 12);
EXPECT_EQ(a.size(), 1);
}
TEST(small_vector, Capacity) {
- folly::small_vector<unsigned long, 1> vec;
+ folly::small_vector<uint64_t, 1> vec;
EXPECT_EQ(vec.size(), 0);
EXPECT_EQ(vec.capacity(), 1);
EXPECT_EQ(vec.size(), 2);
EXPECT_GT(vec.capacity(), 1);
-
- folly::small_vector<unsigned long, 2> vec2;
+ folly::small_vector<uint64_t, 2> vec2;
EXPECT_EQ(vec2.size(), 0);
EXPECT_EQ(vec2.capacity(), 2);
// Test capacity heapifying logic
folly::small_vector<unsigned char, 1> vec3;
- const size_t hc_size = 1000000;
+ 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(vec[i], "abc");
}
}
+
+struct CheckedInt {
+ static const int DEFAULT_VALUE = (int)0xdeadbeef;
+ CheckedInt(): value(DEFAULT_VALUE) {}
+ explicit CheckedInt(int value): value(value) {}
+ CheckedInt(const CheckedInt& rhs, int) : value(rhs.value) {}
+ CheckedInt(const CheckedInt& rhs): value(rhs.value) {}
+ CheckedInt(CheckedInt&& rhs) noexcept: value(rhs.value) {
+ rhs.value = DEFAULT_VALUE;
+ }
+ CheckedInt& operator= (const CheckedInt& rhs) {
+ value = rhs.value;
+ return *this;
+ }
+ CheckedInt& operator= (CheckedInt&& rhs) noexcept {
+ value = rhs.value;
+ rhs.value = DEFAULT_VALUE;
+ return *this;
+ }
+ ~CheckedInt() {}
+ int value;
+};
+
+TEST(small_vector, ForwardingEmplaceInsideVector) {
+ 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) {
+ 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) {
+ 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) {
+ 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) {
+ 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) {
+ 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) {
+ 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) {
+ 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) {
+ 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) {
+ small_vector<int> test(10);
+ ASSERT_EQ(test.size(), 10);
+ for (const auto& element : test) {
+ EXPECT_EQ(element, 0);
+ }
+}
+
+TEST(small_vector, InsertMoreThanGrowth) {
+ small_vector<int, 10> test;
+ test.insert(test.end(), 30, 0);
+ for (auto element : test) {
+ EXPECT_EQ(element, 0);
+ }
+}
+
+TEST(small_vector, EmplaceBackExponentialGrowth) {
+ 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) {
+ 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) {
+ 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);
+}
+
+namespace {
+struct Counts {
+ size_t copyCount{0};
+ size_t moveCount{0};
+};
+
+class Counter {
+ Counts* counts;
+
+ public:
+ explicit Counter(Counts& counts) : counts(&counts) {}
+ Counter(Counter const& other) noexcept : counts(other.counts) {
+ ++counts->copyCount;
+ }
+ Counter(Counter&& other) noexcept : counts(other.counts) {
+ ++counts->moveCount;
+ }
+ Counter& operator=(Counter const& rhs) noexcept {
+ EXPECT_EQ(counts, rhs.counts);
+ ++counts->copyCount;
+ return *this;
+ }
+ Counter& operator=(Counter&& rhs) noexcept {
+ EXPECT_EQ(counts, rhs.counts);
+ ++counts->moveCount;
+ return *this;
+ }
+};
+} // namespace
+
+TEST(small_vector, EmplaceBackEfficiency) {
+ 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) {
+ 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) {
+ 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) {
+ 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) {
+ 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) {
+ 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) {
+ 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);
+}
projects / folly.git / blobdiff