X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2Ftest%2Fsorted_vector_test.cpp;h=7efa4c8f0cfd351060f257cb7fcf7faddda74f34;hb=2bbf87af3ab2fa277c9a9a81d907d754ccf28c50;hp=80038a0a89aa461eb17a3cde0a2b84e1396ce2b2;hpb=cd3fcbcf5f7bbf06c5cae424b15fdc02e24407f5;p=folly.git

diff --git a/folly/test/sorted_vector_test.cpp b/folly/test/sorted_vector_test.cpp
index 80038a0a..7efa4c8f 100644
--- a/folly/test/sorted_vector_test.cpp
+++ b/folly/test/sorted_vector_test.cpp
@@ -1,5 +1,5 @@
 /*
- * 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.
@@ -14,28 +14,34 @@
  * 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;
   }
 };
 
-template<class Container>
+template <class Container>
 void check_invariant(Container& c) {
   auto it = c.begin();
   auto end = c.end();
-  if (it == end)
+  if (it == end) {
     return;
+  }
   auto prev = it;
   ++it;
   for (; it != end; ++it, ++prev) {
@@ -44,7 +50,7 @@ void check_invariant(Container& c) {
 }
 
 struct OneAtATimePolicy {
-  template<class Container>
+  template <class Container>
   void increase_capacity(Container& c) {
     if (c.size() == c.capacity()) {
       c.reserve(c.size() + 1);
@@ -70,7 +76,28 @@ struct CountCopyCtor {
   int count_;
 };
 
-}
+struct Opaque {
+  int value;
+  friend bool operator==(Opaque a, Opaque b) {
+    return a.value == b.value;
+  }
+  friend bool operator<(Opaque a, Opaque b) {
+    return a.value < b.value;
+  }
+  struct Compare : std::less<int>, std::less<Opaque> {
+    using is_transparent = void;
+    using std::less<int>::operator();
+    using std::less<Opaque>::operator();
+    bool operator()(int a, Opaque b) const {
+      return std::less<int>::operator()(a, b.value);
+    }
+    bool operator()(Opaque a, int b) const {
+      return std::less<int>::operator()(a.value, b);
+    }
+  };
+};
+
+} // namespace
 
 TEST(SortedVectorTypes, SimpleSetTest) {
   sorted_vector_set<int> s;
@@ -139,6 +166,88 @@ TEST(SortedVectorTypes, SimpleSetTest) {
   EXPECT_TRUE(cpy2 == cpy);
 }
 
+TEST(SortedVectorTypes, TransparentSetTest) {
+  sorted_vector_set<Opaque, Opaque::Compare> s;
+  EXPECT_TRUE(s.empty());
+  for (int i = 0; i < 1000; ++i) {
+    s.insert(Opaque{rand() % 100000});
+  }
+  EXPECT_FALSE(s.empty());
+  check_invariant(s);
+
+  sorted_vector_set<Opaque, Opaque::Compare> s2;
+  s2.insert(s.begin(), s.end());
+  check_invariant(s2);
+  EXPECT_TRUE(s == s2);
+
+  auto it = s2.lower_bound(32);
+  if (it->value == 32) {
+    s2.erase(it);
+    it = s2.lower_bound(32);
+  }
+  check_invariant(s2);
+  auto oldSz = s2.size();
+  s2.insert(it, Opaque{32});
+  EXPECT_TRUE(s2.size() == oldSz + 1);
+  check_invariant(s2);
+
+  const sorted_vector_set<Opaque, Opaque::Compare>& cs2 = s2;
+  auto range = cs2.equal_range(32);
+  auto lbound = cs2.lower_bound(32);
+  auto ubound = cs2.upper_bound(32);
+  EXPECT_TRUE(range.first == lbound);
+  EXPECT_TRUE(range.second == ubound);
+  EXPECT_TRUE(range.first != cs2.end());
+  EXPECT_TRUE(range.second != cs2.end());
+  EXPECT_TRUE(cs2.count(32) == 1);
+  EXPECT_FALSE(cs2.find(32) == cs2.end());
+
+  // Bad insert hint.
+  s2.insert(s2.begin() + 3, Opaque{33});
+  EXPECT_TRUE(s2.find(33) != s2.begin());
+  EXPECT_TRUE(s2.find(33) != s2.end());
+  check_invariant(s2);
+  s2.erase(Opaque{33});
+  check_invariant(s2);
+
+  it = s2.find(32);
+  EXPECT_FALSE(it == s2.end());
+  s2.erase(it);
+  EXPECT_TRUE(s2.size() == oldSz);
+  check_invariant(s2);
+
+  sorted_vector_set<Opaque, Opaque::Compare> cpy(s);
+  check_invariant(cpy);
+  EXPECT_TRUE(cpy == s);
+  sorted_vector_set<Opaque, Opaque::Compare> cpy2(s);
+  cpy2.insert(Opaque{100001});
+  EXPECT_TRUE(cpy2 != cpy);
+  EXPECT_TRUE(cpy2 != s);
+  check_invariant(cpy2);
+  EXPECT_TRUE(cpy2.count(100001) == 1);
+  s.swap(cpy2);
+  check_invariant(cpy2);
+  check_invariant(s);
+  EXPECT_TRUE(s != cpy);
+  EXPECT_TRUE(s != cpy2);
+  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) {
@@ -149,10 +258,12 @@ TEST(SortedVectorTypes, SimpleMapTest) {
   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);
@@ -198,6 +309,67 @@ TEST(SortedVectorTypes, SimpleMapTest) {
   check_invariant(m);
 }
 
+TEST(SortedVectorTypes, TransparentMapTest) {
+  sorted_vector_map<Opaque, float, Opaque::Compare> m;
+  for (int i = 0; i < 1000; ++i) {
+    m[Opaque{i}] = i / 1000.0;
+  }
+  check_invariant(m);
+
+  m[Opaque{32}] = 100.0;
+  check_invariant(m);
+  EXPECT_TRUE(m.count(32) == 1);
+  EXPECT_DOUBLE_EQ(100.0, m.at(Opaque{32}));
+  EXPECT_FALSE(m.find(32) == m.end());
+  m.erase(Opaque{32});
+  EXPECT_TRUE(m.find(32) == m.end());
+  check_invariant(m);
+  EXPECT_THROW(m.at(Opaque{32}), std::out_of_range);
+
+  sorted_vector_map<Opaque, float, Opaque::Compare> m2 = m;
+  EXPECT_TRUE(m2 == m);
+  EXPECT_FALSE(m2 != m);
+  auto it = m2.lower_bound(1 << 20);
+  EXPECT_TRUE(it == m2.end());
+  m2.insert(it, std::make_pair(Opaque{1 << 20}, 10.0f));
+  check_invariant(m2);
+  EXPECT_TRUE(m2.count(1 << 20) == 1);
+  EXPECT_TRUE(m < m2);
+  EXPECT_TRUE(m <= m2);
+
+  const sorted_vector_map<Opaque, float, Opaque::Compare>& cm = m;
+  auto range = cm.equal_range(42);
+  auto lbound = cm.lower_bound(42);
+  auto ubound = cm.upper_bound(42);
+  EXPECT_TRUE(range.first == lbound);
+  EXPECT_TRUE(range.second == ubound);
+  EXPECT_FALSE(range.first == cm.end());
+  EXPECT_FALSE(range.second == cm.end());
+  m.erase(m.lower_bound(42));
+  check_invariant(m);
+
+  sorted_vector_map<Opaque, float, Opaque::Compare> m3;
+  m3.insert(m2.begin(), m2.end());
+  check_invariant(m3);
+  EXPECT_TRUE(m3 == m2);
+  EXPECT_FALSE(m3 == m);
+
+  EXPECT_TRUE(m != m2);
+  EXPECT_TRUE(m2 == m3);
+  EXPECT_TRUE(m3 != m);
+  m.swap(m3);
+  check_invariant(m);
+  check_invariant(m2);
+  check_invariant(m3);
+  EXPECT_TRUE(m3 != m2);
+  EXPECT_TRUE(m3 != m);
+  EXPECT_TRUE(m == m2);
+
+  // Bad insert hint.
+  m.insert(m.begin() + 3, std::make_pair(Opaque{1 << 15}, 1.0f));
+  check_invariant(m);
+}
+
 TEST(SortedVectorTypes, Sizes) {
   EXPECT_EQ(sizeof(sorted_vector_set<int>),
             sizeof(std::vector<int>));
@@ -207,7 +379,7 @@ TEST(SortedVectorTypes, Sizes) {
   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> >));
@@ -245,13 +417,15 @@ TEST(SortedVectorTypes, InitializerLists) {
 
 TEST(SortedVectorTypes, CustomCompare) {
   sorted_vector_set<int,less_invert<int> > s;
-  for (int i = 0; i < 200; ++i)
+  for (int i = 0; i < 200; ++i) {
     s.insert(i);
+  }
   check_invariant(s);
 
   sorted_vector_map<int,float,less_invert<int> > m;
-  for (int i = 0; i < 200; ++i)
+  for (int i = 0; i < 200; ++i) {
     m[i] = 12.0;
+  }
   check_invariant(m);
 }
 
@@ -278,7 +452,7 @@ TEST(SortedVectorTypes, GrowthPolicy) {
 
   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);
@@ -300,4 +474,270 @@ TEST(SortedVectorTest, EmptyTest) {
   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::make_unique<int>(5));
+  s.insert(s.end(), std::make_unique<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::make_unique<int>(5)));
+  m.insert(m.end(), std::make_pair(10, std::make_unique<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, TestSetBulkInsertionMiddleValuesEqualDuplication) {
+  auto s = makeVectorOfWrappers<CountCopyCtor, int>({4, 6, 8});
+
+  sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
+  check_invariant(vset);
+
+  s = makeVectorOfWrappers<CountCopyCtor, int>({8, 10, 12});
+
+  vset.insert(s.begin(), s.end());
+  check_invariant(vset);
+  EXPECT_EQ(vset.rbegin()->count_, 1);
+
+  EXPECT_THAT(
+      extractValues(vset),
+      testing::ElementsAreArray({4, 6, 8, 10, 12}));
+}
+
+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);
 }