folly/test/sorted_vector_test.cpp

   1 /*
   2  * Copyright 2016 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/sorted_vector_types.h>
  18
  19 #include <list>
  20 #include <memory>
  21
  22 #include <folly/portability/GTest.h>
  23
  24 using folly::sorted_vector_set;
  25 using folly::sorted_vector_map;
  26
  27 namespace {
  28
  29 template <class T>
  30 struct less_invert {
  31   bool operator()(const T& a, const T& b) const {
  32     return b < a;
  33   }
  34 };
  35
  36 template<class Container>
  37 void check_invariant(Container& c) {
  38   auto it = c.begin();
  39   auto end = c.end();
  40   if (it == end)
  41     return;
  42   auto prev = it;
  43   ++it;
  44   for (; it != end; ++it, ++prev) {
  45     EXPECT_TRUE(c.value_comp()(*prev, *it));
  46   }
  47 }
  48
  49 struct OneAtATimePolicy {
  50   template<class Container>
  51   void increase_capacity(Container& c) {
  52     if (c.size() == c.capacity()) {
  53       c.reserve(c.size() + 1);
  54     }
  55   }
  56 };
  57
  58 struct CountCopyCtor {
  59   explicit CountCopyCtor() : val_(0) {}
  60
  61   explicit CountCopyCtor(int val) : val_(val), count_(0) {}
  62
  63   CountCopyCtor(const CountCopyCtor& c)
  64     : val_(c.val_)
  65     , count_(c.count_ + 1)
  66   {}
  67
  68   bool operator<(const CountCopyCtor& o) const {
  69     return val_ < o.val_;
  70   }
  71
  72   int val_;
  73   int count_;
  74 };
  75
  76 }
  77
  78 TEST(SortedVectorTypes, SimpleSetTest) {
  79   sorted_vector_set<int> s;
  80   EXPECT_TRUE(s.empty());
  81   for (int i = 0; i < 1000; ++i) {
  82     s.insert(rand() % 100000);
  83   }
  84   EXPECT_FALSE(s.empty());
  85   check_invariant(s);
  86
  87   sorted_vector_set<int> s2;
  88   s2.insert(s.begin(), s.end());
  89   check_invariant(s2);
  90   EXPECT_TRUE(s == s2);
  91
  92   auto it = s2.lower_bound(32);
  93   if (*it == 32) {
  94     s2.erase(it);
  95     it = s2.lower_bound(32);
  96   }
  97   check_invariant(s2);
  98   auto oldSz = s2.size();
  99   s2.insert(it, 32);
 100   EXPECT_TRUE(s2.size() == oldSz + 1);
 101   check_invariant(s2);
 102
 103   const sorted_vector_set<int>& cs2 = s2;
 104   auto range = cs2.equal_range(32);
 105   auto lbound = cs2.lower_bound(32);
 106   auto ubound = cs2.upper_bound(32);
 107   EXPECT_TRUE(range.first == lbound);
 108   EXPECT_TRUE(range.second == ubound);
 109   EXPECT_TRUE(range.first != cs2.end());
 110   EXPECT_TRUE(range.second != cs2.end());
 111   EXPECT_TRUE(cs2.count(32) == 1);
 112   EXPECT_FALSE(cs2.find(32) == cs2.end());
 113
 114   // Bad insert hint.
 115   s2.insert(s2.begin() + 3, 33);
 116   EXPECT_TRUE(s2.find(33) != s2.begin());
 117   EXPECT_TRUE(s2.find(33) != s2.end());
 118   check_invariant(s2);
 119   s2.erase(33);
 120   check_invariant(s2);
 121
 122   it = s2.find(32);
 123   EXPECT_FALSE(it == s2.end());
 124   s2.erase(it);
 125   EXPECT_TRUE(s2.size() == oldSz);
 126   check_invariant(s2);
 127
 128   sorted_vector_set<int> cpy(s);
 129   check_invariant(cpy);
 130   EXPECT_TRUE(cpy == s);
 131   sorted_vector_set<int> cpy2(s);
 132   cpy2.insert(100001);
 133   EXPECT_TRUE(cpy2 != cpy);
 134   EXPECT_TRUE(cpy2 != s);
 135   check_invariant(cpy2);
 136   EXPECT_TRUE(cpy2.count(100001) == 1);
 137   s.swap(cpy2);
 138   check_invariant(cpy2);
 139   check_invariant(s);
 140   EXPECT_TRUE(s != cpy);
 141   EXPECT_TRUE(s != cpy2);
 142   EXPECT_TRUE(cpy2 == cpy);
 143 }
 144
 145 TEST(SortedVectorTypes, SimpleMapTest) {
 146   sorted_vector_map<int,float> m;
 147   for (int i = 0; i < 1000; ++i) {
 148     m[i] = i / 1000.0;
 149   }
 150   check_invariant(m);
 151
 152   m[32] = 100.0;
 153   check_invariant(m);
 154   EXPECT_TRUE(m.count(32) == 1);
 155   EXPECT_DOUBLE_EQ(100.0, m.at(32));
 156   EXPECT_FALSE(m.find(32) == m.end());
 157   m.erase(32);
 158   EXPECT_TRUE(m.find(32) == m.end());
 159   check_invariant(m);
 160   EXPECT_THROW(m.at(32), std::out_of_range);
 161
 162   sorted_vector_map<int,float> m2 = m;
 163   EXPECT_TRUE(m2 == m);
 164   EXPECT_FALSE(m2 != m);
 165   auto it = m2.lower_bound(1 << 20);
 166   EXPECT_TRUE(it == m2.end());
 167   m2.insert(it, std::make_pair(1 << 20, 10.0f));
 168   check_invariant(m2);
 169   EXPECT_TRUE(m2.count(1 << 20) == 1);
 170   EXPECT_TRUE(m < m2);
 171   EXPECT_TRUE(m <= m2);
 172
 173   const sorted_vector_map<int,float>& cm = m;
 174   auto range = cm.equal_range(42);
 175   auto lbound = cm.lower_bound(42);
 176   auto ubound = cm.upper_bound(42);
 177   EXPECT_TRUE(range.first == lbound);
 178   EXPECT_TRUE(range.second == ubound);
 179   EXPECT_FALSE(range.first == cm.end());
 180   EXPECT_FALSE(range.second == cm.end());
 181   m.erase(m.lower_bound(42));
 182   check_invariant(m);
 183
 184   sorted_vector_map<int,float> m3;
 185   m3.insert(m2.begin(), m2.end());
 186   check_invariant(m3);
 187   EXPECT_TRUE(m3 == m2);
 188   EXPECT_FALSE(m3 == m);
 189
 190   EXPECT_TRUE(m != m2);
 191   EXPECT_TRUE(m2 == m3);
 192   EXPECT_TRUE(m3 != m);
 193   m.swap(m3);
 194   check_invariant(m);
 195   check_invariant(m2);
 196   check_invariant(m3);
 197   EXPECT_TRUE(m3 != m2);
 198   EXPECT_TRUE(m3 != m);
 199   EXPECT_TRUE(m == m2);
 200
 201   // Bad insert hint.
 202   m.insert(m.begin() + 3, std::make_pair(1 << 15, 1.0f));
 203   check_invariant(m);
 204 }
 205
 206 TEST(SortedVectorTypes, Sizes) {
 207   EXPECT_EQ(sizeof(sorted_vector_set<int>),
 208             sizeof(std::vector<int>));
 209   EXPECT_EQ(sizeof(sorted_vector_map<int,int>),
 210             sizeof(std::vector<std::pair<int,int> >));
 211
 212   typedef sorted_vector_set<int,std::less<int>,
 213     std::allocator<int>,OneAtATimePolicy> SetT;
 214   typedef sorted_vector_map<int,int,std::less<int>,
 215     std::allocator<std::pair<int,int>>,OneAtATimePolicy> MapT;
 216
 217   EXPECT_EQ(sizeof(SetT), sizeof(std::vector<int>));
 218   EXPECT_EQ(sizeof(MapT), sizeof(std::vector<std::pair<int,int> >));
 219 }
 220
 221 TEST(SortedVectorTypes, InitializerLists) {
 222   sorted_vector_set<int> empty_initialized_set{};
 223   EXPECT_TRUE(empty_initialized_set.empty());
 224
 225   sorted_vector_set<int> singleton_initialized_set{1};
 226   EXPECT_EQ(1, singleton_initialized_set.size());
 227   EXPECT_EQ(1, *singleton_initialized_set.begin());
 228
 229   sorted_vector_set<int> forward_initialized_set{1, 2};
 230   sorted_vector_set<int> backward_initialized_set{2, 1};
 231   EXPECT_EQ(2, forward_initialized_set.size());
 232   EXPECT_EQ(1, *forward_initialized_set.begin());
 233   EXPECT_EQ(2, *forward_initialized_set.rbegin());
 234   EXPECT_TRUE(forward_initialized_set == backward_initialized_set);
 235
 236   sorted_vector_map<int,int> empty_initialized_map{};
 237   EXPECT_TRUE(empty_initialized_map.empty());
 238
 239   sorted_vector_map<int,int> singleton_initialized_map{{1,10}};
 240   EXPECT_EQ(1, singleton_initialized_map.size());
 241   EXPECT_EQ(10, singleton_initialized_map[1]);
 242
 243   sorted_vector_map<int,int> forward_initialized_map{{1,10}, {2,20}};
 244   sorted_vector_map<int,int> backward_initialized_map{{2,20}, {1,10}};
 245   EXPECT_EQ(2, forward_initialized_map.size());
 246   EXPECT_EQ(10, forward_initialized_map[1]);
 247   EXPECT_EQ(20, forward_initialized_map[2]);
 248   EXPECT_TRUE(forward_initialized_map == backward_initialized_map);
 249 }
 250
 251 TEST(SortedVectorTypes, CustomCompare) {
 252   sorted_vector_set<int,less_invert<int> > s;
 253   for (int i = 0; i < 200; ++i)
 254     s.insert(i);
 255   check_invariant(s);
 256
 257   sorted_vector_map<int,float,less_invert<int> > m;
 258   for (int i = 0; i < 200; ++i)
 259     m[i] = 12.0;
 260   check_invariant(m);
 261 }
 262
 263 TEST(SortedVectorTypes, GrowthPolicy) {
 264   typedef sorted_vector_set<CountCopyCtor,
 265                             std::less<CountCopyCtor>,
 266                             std::allocator<CountCopyCtor>,
 267                             OneAtATimePolicy>
 268     SetT;
 269
 270   SetT a;
 271   for (int i = 0; i < 20; ++i) {
 272     a.insert(CountCopyCtor(i));
 273   }
 274   check_invariant(a);
 275   SetT::iterator it = a.begin();
 276   EXPECT_FALSE(it == a.end());
 277   if (it != a.end()) {
 278     EXPECT_EQ(it->val_, 0);
 279     // 1 copy for the initial insertion, 19 more for reallocs on the
 280     // additional insertions.
 281     EXPECT_EQ(it->count_, 20);
 282   }
 283
 284   std::list<CountCopyCtor> v;
 285   for (int i = 0; i < 20; ++i) {
 286     v.emplace_back(20 + i);
 287   }
 288   a.insert(v.begin(), v.end());
 289   check_invariant(a);
 290
 291   it = a.begin();
 292   EXPECT_FALSE(it == a.end());
 293   if (it != a.end()) {
 294     EXPECT_EQ(it->val_, 0);
 295     // Should be only 1 more copy for inserting this above range.
 296     EXPECT_EQ(it->count_, 21);
 297   }
 298 }
 299
 300 TEST(SortedVectorTest, EmptyTest) {
 301   sorted_vector_set<int> emptySet;
 302   EXPECT_TRUE(emptySet.lower_bound(10) == emptySet.end());
 303   EXPECT_TRUE(emptySet.find(10) == emptySet.end());
 304
 305   sorted_vector_map<int,int> emptyMap;
 306   EXPECT_TRUE(emptyMap.lower_bound(10) == emptyMap.end());
 307   EXPECT_TRUE(emptyMap.find(10) == emptyMap.end());
 308   EXPECT_THROW(emptyMap.at(10), std::out_of_range);
 309 }
 310
 311 TEST(SortedVectorTest, MoveTest) {
 312   sorted_vector_set<std::unique_ptr<int>> s;
 313   s.insert(std::unique_ptr<int>(new int(5)));
 314   s.insert(s.end(), std::unique_ptr<int>(new int(10)));
 315   EXPECT_EQ(s.size(), 2);
 316
 317   for (const auto& p : s) {
 318     EXPECT_TRUE(*p == 5 || *p == 10);
 319   }
 320
 321   sorted_vector_map<int, std::unique_ptr<int>> m;
 322   m.insert(std::make_pair(5, std::unique_ptr<int>(new int(5))));
 323   m.insert(m.end(), std::make_pair(10, std::unique_ptr<int>(new int(10))));
 324
 325   EXPECT_EQ(*m[5], 5);
 326   EXPECT_EQ(*m[10], 10);
 327 }
 328
 329 TEST(SortedVectorTest, ShrinkTest) {
 330   sorted_vector_set<int> s;
 331   int i = 0;
 332   // Hopefully your resize policy doubles when capacity is full, or this will
 333   // hang forever :(
 334   while (s.capacity() == s.size()) {
 335     s.insert(i++);
 336   }
 337   s.shrink_to_fit();
 338   // The standard does not actually enforce that this be true, but assume that
 339   // vector::shrink_to_fit respects the caller.
 340   EXPECT_EQ(s.capacity(), s.size());
 341 }
 342
 343 TEST(SortedVectorTypes, EraseTest) {
 344   sorted_vector_set<int> s1;
 345   s1.insert(1);
 346   sorted_vector_set<int> s2(s1);
 347   EXPECT_EQ(0, s1.erase(0));
 348   EXPECT_EQ(s2, s1);
 349 }