/*
- * 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/sorted_vector_types.h"
-#include <gtest/gtest.h>
+#include <folly/sorted_vector_types.h>
+
+#include <iterator>
#include <list>
+#include <memory>
+
+#include <folly/portability/GMock.h>
+#include <folly/portability/GTest.h>
using folly::sorted_vector_set;
using folly::sorted_vector_map;
namespace {
-template<class T>
-struct less_invert : std::binary_function<T,T,bool> {
+template <class T>
+struct less_invert {
bool operator()(const T& a, const T& b) const {
return b < a;
}
EXPECT_TRUE(cpy2 == cpy);
}
+TEST(SortedVectorTypes, BadHints) {
+ for (int toInsert = -1; toInsert <= 7; ++toInsert) {
+ for (int hintPos = 0; hintPos <= 4; ++hintPos) {
+ sorted_vector_set<int> s;
+ for (int i = 0; i <= 3; ++i) {
+ s.insert(i * 2);
+ }
+ s.insert(s.begin() + hintPos, toInsert);
+ size_t expectedSize = (toInsert % 2) == 0 ? 4 : 5;
+ EXPECT_EQ(s.size(), expectedSize);
+ check_invariant(s);
+ }
+ }
+}
+
TEST(SortedVectorTypes, SimpleMapTest) {
sorted_vector_map<int,float> m;
for (int i = 0; i < 1000; ++i) {
m[32] = 100.0;
check_invariant(m);
EXPECT_TRUE(m.count(32) == 1);
+ EXPECT_DOUBLE_EQ(100.0, m.at(32));
EXPECT_FALSE(m.find(32) == m.end());
m.erase(32);
EXPECT_TRUE(m.find(32) == m.end());
check_invariant(m);
+ EXPECT_THROW(m.at(32), std::out_of_range);
sorted_vector_map<int,float> m2 = m;
EXPECT_TRUE(m2 == m);
typedef sorted_vector_set<int,std::less<int>,
std::allocator<int>,OneAtATimePolicy> SetT;
typedef sorted_vector_map<int,int,std::less<int>,
- std::allocator<int>,OneAtATimePolicy> MapT;
+ std::allocator<std::pair<int,int>>,OneAtATimePolicy> MapT;
EXPECT_EQ(sizeof(SetT), sizeof(std::vector<int>));
EXPECT_EQ(sizeof(MapT), sizeof(std::vector<std::pair<int,int> >));
std::list<CountCopyCtor> v;
for (int i = 0; i < 20; ++i) {
- v.push_back(CountCopyCtor(20 + i));
+ v.emplace_back(20 + i);
}
a.insert(v.begin(), v.end());
check_invariant(a);
sorted_vector_map<int,int> emptyMap;
EXPECT_TRUE(emptyMap.lower_bound(10) == emptyMap.end());
EXPECT_TRUE(emptyMap.find(10) == emptyMap.end());
+ EXPECT_THROW(emptyMap.at(10), std::out_of_range);
+}
+
+TEST(SortedVectorTest, MoveTest) {
+ sorted_vector_set<std::unique_ptr<int>> s;
+ s.insert(std::unique_ptr<int>(new int(5)));
+ s.insert(s.end(), std::unique_ptr<int>(new int(10)));
+ EXPECT_EQ(s.size(), 2);
+
+ for (const auto& p : s) {
+ EXPECT_TRUE(*p == 5 || *p == 10);
+ }
+
+ sorted_vector_map<int, std::unique_ptr<int>> m;
+ m.insert(std::make_pair(5, std::unique_ptr<int>(new int(5))));
+ m.insert(m.end(), std::make_pair(10, std::unique_ptr<int>(new int(10))));
+
+ EXPECT_EQ(*m[5], 5);
+ EXPECT_EQ(*m[10], 10);
+}
+
+TEST(SortedVectorTest, ShrinkTest) {
+ sorted_vector_set<int> s;
+ int i = 0;
+ // Hopefully your resize policy doubles when capacity is full, or this will
+ // hang forever :(
+ while (s.capacity() == s.size()) {
+ s.insert(i++);
+ }
+ s.shrink_to_fit();
+ // The standard does not actually enforce that this be true, but assume that
+ // vector::shrink_to_fit respects the caller.
+ EXPECT_EQ(s.capacity(), s.size());
+}
+
+TEST(SortedVectorTypes, EraseTest) {
+ sorted_vector_set<int> s1;
+ s1.insert(1);
+ sorted_vector_set<int> s2(s1);
+ EXPECT_EQ(0, s1.erase(0));
+ EXPECT_EQ(s2, s1);
+}
+
+std::vector<int> extractValues(sorted_vector_set<CountCopyCtor> const& in) {
+ std::vector<int> ret;
+ std::transform(
+ in.begin(),
+ in.end(),
+ std::back_inserter(ret),
+ [](const CountCopyCtor& c) { return c.val_; });
+ return ret;
+}
+
+template <typename T, typename S>
+std::vector<T> makeVectorOfWrappers(std::vector<S> ss) {
+ std::vector<T> ts;
+ ts.reserve(ss.size());
+ for (auto const& s : ss) {
+ ts.emplace_back(s);
+ }
+ return ts;
+}
+
+TEST(SortedVectorTypes, TestSetBulkInsertionSortMerge) {
+ auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
+
+ sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
+ check_invariant(vset);
+
+ // Add an unsorted range that will have to be merged in.
+ s = makeVectorOfWrappers<CountCopyCtor, int>({10, 7, 5, 1});
+
+ vset.insert(s.begin(), s.end());
+ check_invariant(vset);
+ EXPECT_EQ(vset.rbegin()->count_, 1);
+
+ EXPECT_THAT(
+ extractValues(vset),
+ testing::ElementsAreArray({1, 2, 4, 5, 6, 7, 8, 10}));
+}
+
+TEST(SortedVectorTypes, TestSetBulkInsertionSortMergeDups) {
+ auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
+
+ sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
+ check_invariant(vset);
+
+ // Add an unsorted range that will have to be merged in.
+ s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
+
+ vset.insert(s.begin(), s.end());
+ check_invariant(vset);
+ EXPECT_EQ(vset.rbegin()->count_, 1);
+ EXPECT_THAT(
+ extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10}));
+}
+
+TEST(SortedVectorTypes, TestSetInsertionDupsOneByOne) {
+ auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
+
+ sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
+ check_invariant(vset);
+
+ // Add an unsorted range that will have to be merged in.
+ s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
+
+ for (const auto& elem : s) {
+ vset.insert(elem);
+ }
+ check_invariant(vset);
+ EXPECT_EQ(vset.rbegin()->count_, 3);
+ EXPECT_THAT(
+ extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10}));
+}
+
+TEST(SortedVectorTypes, TestSetBulkInsertionSortNoMerge) {
+ auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
+
+ sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
+ check_invariant(vset);
+
+ // Add an unsorted range that will not have to be merged in.
+ s = makeVectorOfWrappers<CountCopyCtor, int>({20, 15, 16, 13});
+
+ vset.insert(s.begin(), s.end());
+ check_invariant(vset);
+ EXPECT_EQ(vset.rbegin()->count_, 1);
+ EXPECT_THAT(
+ extractValues(vset),
+ testing::ElementsAreArray({2, 4, 6, 8, 13, 15, 16, 20}));
+}
+
+TEST(SortedVectorTypes, TestSetBulkInsertionNoSortMerge) {
+ auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
+
+ sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
+ check_invariant(vset);
+
+ // Add a sorted range that will have to be merged in.
+ s = makeVectorOfWrappers<CountCopyCtor, int>({1, 3, 5, 9});
+
+ vset.insert(s.begin(), s.end());
+ check_invariant(vset);
+ EXPECT_EQ(vset.rbegin()->count_, 1);
+ EXPECT_THAT(
+ extractValues(vset), testing::ElementsAreArray({1, 2, 3, 4, 5, 6, 8, 9}));
+}
+
+TEST(SortedVectorTypes, TestSetBulkInsertionNoSortNoMerge) {
+ auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
+
+ sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
+ check_invariant(vset);
+
+ // Add a sorted range that will not have to be merged in.
+ s = makeVectorOfWrappers<CountCopyCtor, int>({21, 22, 23, 24});
+
+ vset.insert(s.begin(), s.end());
+ check_invariant(vset);
+ EXPECT_EQ(vset.rbegin()->count_, 1);
+ EXPECT_THAT(
+ extractValues(vset),
+ testing::ElementsAreArray({2, 4, 6, 8, 21, 22, 23, 24}));
+}
+
+TEST(SortedVectorTypes, TestSetBulkInsertionEmptyRange) {
+ std::vector<CountCopyCtor> s;
+ EXPECT_TRUE(s.empty());
+
+ // insertion of empty range into empty container.
+ sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
+ check_invariant(vset);
+
+ s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
+
+ vset.insert(s.begin(), s.end());
+
+ // insertion of empty range into non-empty container.
+ s.clear();
+ vset.insert(s.begin(), s.end());
+ check_invariant(vset);
+
+ EXPECT_THAT(extractValues(vset), testing::ElementsAreArray({2, 4, 6, 8}));
+}
+
+// This is a test of compilation - the behavior has already been tested
+// extensively above.
+TEST(SortedVectorTypes, TestBulkInsertionUncopyableTypes) {
+ std::vector<std::pair<int, std::unique_ptr<int>>> s;
+ s.emplace_back(1, std::make_unique<int>(0));
+
+ sorted_vector_map<int, std::unique_ptr<int>> vmap(
+ std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
+
+ s.clear();
+ s.emplace_back(3, std::make_unique<int>(0));
+ vmap.insert(
+ std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
+}
+
+// A moveable and copyable struct, which we use to make sure that no copy
+// operations are performed during bulk insertion if moving is an option.
+struct Movable {
+ int x_;
+ explicit Movable(int x) : x_(x) {}
+ Movable(const Movable&) {
+ ADD_FAILURE() << "Copy ctor should not be called";
+ }
+ Movable& operator=(const Movable&) {
+ ADD_FAILURE() << "Copy assignment should not be called";
+ return *this;
+ }
+
+ Movable(Movable&&) = default;
+ Movable& operator=(Movable&&) = default;
+};
+
+TEST(SortedVectorTypes, TestBulkInsertionMovableTypes) {
+ std::vector<std::pair<int, Movable>> s;
+ s.emplace_back(3, Movable(2));
+ s.emplace_back(1, Movable(0));
+
+ sorted_vector_map<int, Movable> vmap(
+ std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
+
+ s.clear();
+ s.emplace_back(4, Movable(3));
+ s.emplace_back(2, Movable(1));
+ vmap.insert(
+ std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
+}
+
+TEST(SortedVectorTypes, TestSetCreationFromVector) {
+ std::vector<int> vec = {3, 1, -1, 5, 0};
+ sorted_vector_set<int> vset(std::move(vec));
+ check_invariant(vset);
+ EXPECT_THAT(vset, testing::ElementsAreArray({-1, 0, 1, 3, 5}));
+}
+
+TEST(SortedVectorTypes, TestMapCreationFromVector) {
+ std::vector<std::pair<int, int>> vec = {
+ {3, 1}, {1, 5}, {-1, 2}, {5, 3}, {0, 3}};
+ sorted_vector_map<int, int> vmap(std::move(vec));
+ check_invariant(vmap);
+ auto contents = std::vector<std::pair<int, int>>(vmap.begin(), vmap.end());
+ auto expected_contents = std::vector<std::pair<int, int>>({
+ {-1, 2}, {0, 3}, {1, 5}, {3, 1}, {5, 3},
+ });
+ EXPECT_EQ(contents, expected_contents);
}
projects / folly.git / blobdiff