folly/test/sorted_vector_test.cpp

   1 /*
   2  * Copyright 2017 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 <iterator>
  20 #include <list>
  21 #include <memory>
  22
  23 #include <folly/portability/GMock.h>
  24 #include <folly/portability/GTest.h>
  25
  26 using folly::sorted_vector_set;
  27 using folly::sorted_vector_map;
  28
  29 namespace {
  30
  31 template <class T>
  32 struct less_invert {
  33   bool operator()(const T& a, const T& b) const {
  34     return b < a;
  35   }
  36 };
  37
  38 template <class Container>
  39 void check_invariant(Container& c) {
  40   auto it = c.begin();
  41   auto end = c.end();
  42   if (it == end)
  43     return;
  44   auto prev = it;
  45   ++it;
  46   for (; it != end; ++it, ++prev) {
  47     EXPECT_TRUE(c.value_comp()(*prev, *it));
  48   }
  49 }
  50
  51 struct OneAtATimePolicy {
  52   template <class Container>
  53   void increase_capacity(Container& c) {
  54     if (c.size() == c.capacity()) {
  55       c.reserve(c.size() + 1);
  56     }
  57   }
  58 };
  59
  60 struct CountCopyCtor {
  61   explicit CountCopyCtor() : val_(0) {}
  62
  63   explicit CountCopyCtor(int val) : val_(val), count_(0) {}
  64
  65   CountCopyCtor(const CountCopyCtor& c)
  66     : val_(c.val_)
  67     , count_(c.count_ + 1)
  68   {}
  69
  70   bool operator<(const CountCopyCtor& o) const {
  71     return val_ < o.val_;
  72   }
  73
  74   int val_;
  75   int count_;
  76 };
  77
  78 }
  79
  80 TEST(SortedVectorTypes, SimpleSetTest) {
  81   sorted_vector_set<int> s;
  82   EXPECT_TRUE(s.empty());
  83   for (int i = 0; i < 1000; ++i) {
  84     s.insert(rand() % 100000);
  85   }
  86   EXPECT_FALSE(s.empty());
  87   check_invariant(s);
  88
  89   sorted_vector_set<int> s2;
  90   s2.insert(s.begin(), s.end());
  91   check_invariant(s2);
  92   EXPECT_TRUE(s == s2);
  93
  94   auto it = s2.lower_bound(32);
  95   if (*it == 32) {
  96     s2.erase(it);
  97     it = s2.lower_bound(32);
  98   }
  99   check_invariant(s2);
 100   auto oldSz = s2.size();
 101   s2.insert(it, 32);
 102   EXPECT_TRUE(s2.size() == oldSz + 1);
 103   check_invariant(s2);
 104
 105   const sorted_vector_set<int>& cs2 = s2;
 106   auto range = cs2.equal_range(32);
 107   auto lbound = cs2.lower_bound(32);
 108   auto ubound = cs2.upper_bound(32);
 109   EXPECT_TRUE(range.first == lbound);
 110   EXPECT_TRUE(range.second == ubound);
 111   EXPECT_TRUE(range.first != cs2.end());
 112   EXPECT_TRUE(range.second != cs2.end());
 113   EXPECT_TRUE(cs2.count(32) == 1);
 114   EXPECT_FALSE(cs2.find(32) == cs2.end());
 115
 116   // Bad insert hint.
 117   s2.insert(s2.begin() + 3, 33);
 118   EXPECT_TRUE(s2.find(33) != s2.begin());
 119   EXPECT_TRUE(s2.find(33) != s2.end());
 120   check_invariant(s2);
 121   s2.erase(33);
 122   check_invariant(s2);
 123
 124   it = s2.find(32);
 125   EXPECT_FALSE(it == s2.end());
 126   s2.erase(it);
 127   EXPECT_TRUE(s2.size() == oldSz);
 128   check_invariant(s2);
 129
 130   sorted_vector_set<int> cpy(s);
 131   check_invariant(cpy);
 132   EXPECT_TRUE(cpy == s);
 133   sorted_vector_set<int> cpy2(s);
 134   cpy2.insert(100001);
 135   EXPECT_TRUE(cpy2 != cpy);
 136   EXPECT_TRUE(cpy2 != s);
 137   check_invariant(cpy2);
 138   EXPECT_TRUE(cpy2.count(100001) == 1);
 139   s.swap(cpy2);
 140   check_invariant(cpy2);
 141   check_invariant(s);
 142   EXPECT_TRUE(s != cpy);
 143   EXPECT_TRUE(s != cpy2);
 144   EXPECT_TRUE(cpy2 == cpy);
 145 }
 146
 147 TEST(SortedVectorTypes, BadHints) {
 148   for (int toInsert = -1; toInsert <= 7; ++toInsert) {
 149     for (int hintPos = 0; hintPos <= 4; ++hintPos) {
 150       sorted_vector_set<int> s;
 151       for (int i = 0; i <= 3; ++i) {
 152         s.insert(i * 2);
 153       }
 154       s.insert(s.begin() + hintPos, toInsert);
 155       size_t expectedSize = (toInsert % 2) == 0 ? 4 : 5;
 156       EXPECT_EQ(s.size(), expectedSize);
 157       check_invariant(s);
 158     }
 159   }
 160 }
 161
 162 TEST(SortedVectorTypes, SimpleMapTest) {
 163   sorted_vector_map<int,float> m;
 164   for (int i = 0; i < 1000; ++i) {
 165     m[i] = i / 1000.0;
 166   }
 167   check_invariant(m);
 168
 169   m[32] = 100.0;
 170   check_invariant(m);
 171   EXPECT_TRUE(m.count(32) == 1);
 172   EXPECT_DOUBLE_EQ(100.0, m.at(32));
 173   EXPECT_FALSE(m.find(32) == m.end());
 174   m.erase(32);
 175   EXPECT_TRUE(m.find(32) == m.end());
 176   check_invariant(m);
 177   EXPECT_THROW(m.at(32), std::out_of_range);
 178
 179   sorted_vector_map<int,float> m2 = m;
 180   EXPECT_TRUE(m2 == m);
 181   EXPECT_FALSE(m2 != m);
 182   auto it = m2.lower_bound(1 << 20);
 183   EXPECT_TRUE(it == m2.end());
 184   m2.insert(it, std::make_pair(1 << 20, 10.0f));
 185   check_invariant(m2);
 186   EXPECT_TRUE(m2.count(1 << 20) == 1);
 187   EXPECT_TRUE(m < m2);
 188   EXPECT_TRUE(m <= m2);
 189
 190   const sorted_vector_map<int,float>& cm = m;
 191   auto range = cm.equal_range(42);
 192   auto lbound = cm.lower_bound(42);
 193   auto ubound = cm.upper_bound(42);
 194   EXPECT_TRUE(range.first == lbound);
 195   EXPECT_TRUE(range.second == ubound);
 196   EXPECT_FALSE(range.first == cm.end());
 197   EXPECT_FALSE(range.second == cm.end());
 198   m.erase(m.lower_bound(42));
 199   check_invariant(m);
 200
 201   sorted_vector_map<int,float> m3;
 202   m3.insert(m2.begin(), m2.end());
 203   check_invariant(m3);
 204   EXPECT_TRUE(m3 == m2);
 205   EXPECT_FALSE(m3 == m);
 206
 207   EXPECT_TRUE(m != m2);
 208   EXPECT_TRUE(m2 == m3);
 209   EXPECT_TRUE(m3 != m);
 210   m.swap(m3);
 211   check_invariant(m);
 212   check_invariant(m2);
 213   check_invariant(m3);
 214   EXPECT_TRUE(m3 != m2);
 215   EXPECT_TRUE(m3 != m);
 216   EXPECT_TRUE(m == m2);
 217
 218   // Bad insert hint.
 219   m.insert(m.begin() + 3, std::make_pair(1 << 15, 1.0f));
 220   check_invariant(m);
 221 }
 222
 223 TEST(SortedVectorTypes, Sizes) {
 224   EXPECT_EQ(sizeof(sorted_vector_set<int>),
 225             sizeof(std::vector<int>));
 226   EXPECT_EQ(sizeof(sorted_vector_map<int,int>),
 227             sizeof(std::vector<std::pair<int,int> >));
 228
 229   typedef sorted_vector_set<int,std::less<int>,
 230     std::allocator<int>,OneAtATimePolicy> SetT;
 231   typedef sorted_vector_map<int,int,std::less<int>,
 232     std::allocator<std::pair<int,int>>,OneAtATimePolicy> MapT;
 233
 234   EXPECT_EQ(sizeof(SetT), sizeof(std::vector<int>));
 235   EXPECT_EQ(sizeof(MapT), sizeof(std::vector<std::pair<int,int> >));
 236 }
 237
 238 TEST(SortedVectorTypes, InitializerLists) {
 239   sorted_vector_set<int> empty_initialized_set{};
 240   EXPECT_TRUE(empty_initialized_set.empty());
 241
 242   sorted_vector_set<int> singleton_initialized_set{1};
 243   EXPECT_EQ(1, singleton_initialized_set.size());
 244   EXPECT_EQ(1, *singleton_initialized_set.begin());
 245
 246   sorted_vector_set<int> forward_initialized_set{1, 2};
 247   sorted_vector_set<int> backward_initialized_set{2, 1};
 248   EXPECT_EQ(2, forward_initialized_set.size());
 249   EXPECT_EQ(1, *forward_initialized_set.begin());
 250   EXPECT_EQ(2, *forward_initialized_set.rbegin());
 251   EXPECT_TRUE(forward_initialized_set == backward_initialized_set);
 252
 253   sorted_vector_map<int,int> empty_initialized_map{};
 254   EXPECT_TRUE(empty_initialized_map.empty());
 255
 256   sorted_vector_map<int,int> singleton_initialized_map{{1,10}};
 257   EXPECT_EQ(1, singleton_initialized_map.size());
 258   EXPECT_EQ(10, singleton_initialized_map[1]);
 259
 260   sorted_vector_map<int,int> forward_initialized_map{{1,10}, {2,20}};
 261   sorted_vector_map<int,int> backward_initialized_map{{2,20}, {1,10}};
 262   EXPECT_EQ(2, forward_initialized_map.size());
 263   EXPECT_EQ(10, forward_initialized_map[1]);
 264   EXPECT_EQ(20, forward_initialized_map[2]);
 265   EXPECT_TRUE(forward_initialized_map == backward_initialized_map);
 266 }
 267
 268 TEST(SortedVectorTypes, CustomCompare) {
 269   sorted_vector_set<int,less_invert<int> > s;
 270   for (int i = 0; i < 200; ++i)
 271     s.insert(i);
 272   check_invariant(s);
 273
 274   sorted_vector_map<int,float,less_invert<int> > m;
 275   for (int i = 0; i < 200; ++i)
 276     m[i] = 12.0;
 277   check_invariant(m);
 278 }
 279
 280 TEST(SortedVectorTypes, GrowthPolicy) {
 281   typedef sorted_vector_set<CountCopyCtor,
 282                             std::less<CountCopyCtor>,
 283                             std::allocator<CountCopyCtor>,
 284                             OneAtATimePolicy>
 285     SetT;
 286
 287   SetT a;
 288   for (int i = 0; i < 20; ++i) {
 289     a.insert(CountCopyCtor(i));
 290   }
 291   check_invariant(a);
 292   SetT::iterator it = a.begin();
 293   EXPECT_FALSE(it == a.end());
 294   if (it != a.end()) {
 295     EXPECT_EQ(it->val_, 0);
 296     // 1 copy for the initial insertion, 19 more for reallocs on the
 297     // additional insertions.
 298     EXPECT_EQ(it->count_, 20);
 299   }
 300
 301   std::list<CountCopyCtor> v;
 302   for (int i = 0; i < 20; ++i) {
 303     v.emplace_back(20 + i);
 304   }
 305   a.insert(v.begin(), v.end());
 306   check_invariant(a);
 307
 308   it = a.begin();
 309   EXPECT_FALSE(it == a.end());
 310   if (it != a.end()) {
 311     EXPECT_EQ(it->val_, 0);
 312     // Should be only 1 more copy for inserting this above range.
 313     EXPECT_EQ(it->count_, 21);
 314   }
 315 }
 316
 317 TEST(SortedVectorTest, EmptyTest) {
 318   sorted_vector_set<int> emptySet;
 319   EXPECT_TRUE(emptySet.lower_bound(10) == emptySet.end());
 320   EXPECT_TRUE(emptySet.find(10) == emptySet.end());
 321
 322   sorted_vector_map<int,int> emptyMap;
 323   EXPECT_TRUE(emptyMap.lower_bound(10) == emptyMap.end());
 324   EXPECT_TRUE(emptyMap.find(10) == emptyMap.end());
 325   EXPECT_THROW(emptyMap.at(10), std::out_of_range);
 326 }
 327
 328 TEST(SortedVectorTest, MoveTest) {
 329   sorted_vector_set<std::unique_ptr<int>> s;
 330   s.insert(std::unique_ptr<int>(new int(5)));
 331   s.insert(s.end(), std::unique_ptr<int>(new int(10)));
 332   EXPECT_EQ(s.size(), 2);
 333
 334   for (const auto& p : s) {
 335     EXPECT_TRUE(*p == 5 || *p == 10);
 336   }
 337
 338   sorted_vector_map<int, std::unique_ptr<int>> m;
 339   m.insert(std::make_pair(5, std::unique_ptr<int>(new int(5))));
 340   m.insert(m.end(), std::make_pair(10, std::unique_ptr<int>(new int(10))));
 341
 342   EXPECT_EQ(*m[5], 5);
 343   EXPECT_EQ(*m[10], 10);
 344 }
 345
 346 TEST(SortedVectorTest, ShrinkTest) {
 347   sorted_vector_set<int> s;
 348   int i = 0;
 349   // Hopefully your resize policy doubles when capacity is full, or this will
 350   // hang forever :(
 351   while (s.capacity() == s.size()) {
 352     s.insert(i++);
 353   }
 354   s.shrink_to_fit();
 355   // The standard does not actually enforce that this be true, but assume that
 356   // vector::shrink_to_fit respects the caller.
 357   EXPECT_EQ(s.capacity(), s.size());
 358 }
 359
 360 TEST(SortedVectorTypes, EraseTest) {
 361   sorted_vector_set<int> s1;
 362   s1.insert(1);
 363   sorted_vector_set<int> s2(s1);
 364   EXPECT_EQ(0, s1.erase(0));
 365   EXPECT_EQ(s2, s1);
 366 }
 367
 368 std::vector<int> extractValues(sorted_vector_set<CountCopyCtor> const& in) {
 369   std::vector<int> ret;
 370   std::transform(
 371       in.begin(),
 372       in.end(),
 373       std::back_inserter(ret),
 374       [](const CountCopyCtor& c) { return c.val_; });
 375   return ret;
 376 }
 377
 378 template <typename T, typename S>
 379 std::vector<T> makeVectorOfWrappers(std::vector<S> ss) {
 380   std::vector<T> ts;
 381   ts.reserve(ss.size());
 382   for (auto const& s : ss) {
 383     ts.emplace_back(s);
 384   }
 385   return ts;
 386 }
 387
 388 TEST(SortedVectorTypes, TestSetBulkInsertionSortMerge) {
 389   auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
 390
 391   sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
 392   check_invariant(vset);
 393
 394   // Add an unsorted range that will have to be merged in.
 395   s = makeVectorOfWrappers<CountCopyCtor, int>({10, 7, 5, 1});
 396
 397   vset.insert(s.begin(), s.end());
 398   check_invariant(vset);
 399   EXPECT_EQ(vset.rbegin()->count_, 1);
 400
 401   EXPECT_THAT(
 402       extractValues(vset),
 403       testing::ElementsAreArray({1, 2, 4, 5, 6, 7, 8, 10}));
 404 }
 405
 406 TEST(SortedVectorTypes, TestSetBulkInsertionSortMergeDups) {
 407   auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
 408
 409   sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
 410   check_invariant(vset);
 411
 412   // Add an unsorted range that will have to be merged in.
 413   s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
 414
 415   vset.insert(s.begin(), s.end());
 416   check_invariant(vset);
 417   EXPECT_EQ(vset.rbegin()->count_, 1);
 418   EXPECT_THAT(
 419       extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10}));
 420 }
 421
 422 TEST(SortedVectorTypes, TestSetInsertionDupsOneByOne) {
 423   auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
 424
 425   sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
 426   check_invariant(vset);
 427
 428   // Add an unsorted range that will have to be merged in.
 429   s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
 430
 431   for (const auto& elem : s) {
 432     vset.insert(elem);
 433   }
 434   check_invariant(vset);
 435   EXPECT_EQ(vset.rbegin()->count_, 3);
 436   EXPECT_THAT(
 437       extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10}));
 438 }
 439
 440 TEST(SortedVectorTypes, TestSetBulkInsertionSortNoMerge) {
 441   auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
 442
 443   sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
 444   check_invariant(vset);
 445
 446   // Add an unsorted range that will not have to be merged in.
 447   s = makeVectorOfWrappers<CountCopyCtor, int>({20, 15, 16, 13});
 448
 449   vset.insert(s.begin(), s.end());
 450   check_invariant(vset);
 451   EXPECT_EQ(vset.rbegin()->count_, 1);
 452   EXPECT_THAT(
 453       extractValues(vset),
 454       testing::ElementsAreArray({2, 4, 6, 8, 13, 15, 16, 20}));
 455 }
 456
 457 TEST(SortedVectorTypes, TestSetBulkInsertionNoSortMerge) {
 458   auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
 459
 460   sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
 461   check_invariant(vset);
 462
 463   // Add a sorted range that will have to be merged in.
 464   s = makeVectorOfWrappers<CountCopyCtor, int>({1, 3, 5, 9});
 465
 466   vset.insert(s.begin(), s.end());
 467   check_invariant(vset);
 468   EXPECT_EQ(vset.rbegin()->count_, 1);
 469   EXPECT_THAT(
 470       extractValues(vset), testing::ElementsAreArray({1, 2, 3, 4, 5, 6, 8, 9}));
 471 }
 472
 473 TEST(SortedVectorTypes, TestSetBulkInsertionNoSortNoMerge) {
 474   auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
 475
 476   sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
 477   check_invariant(vset);
 478
 479   // Add a sorted range that will not have to be merged in.
 480   s = makeVectorOfWrappers<CountCopyCtor, int>({21, 22, 23, 24});
 481
 482   vset.insert(s.begin(), s.end());
 483   check_invariant(vset);
 484   EXPECT_EQ(vset.rbegin()->count_, 1);
 485   EXPECT_THAT(
 486       extractValues(vset),
 487       testing::ElementsAreArray({2, 4, 6, 8, 21, 22, 23, 24}));
 488 }
 489
 490 TEST(SortedVectorTypes, TestSetBulkInsertionEmptyRange) {
 491   std::vector<CountCopyCtor> s;
 492   EXPECT_TRUE(s.empty());
 493
 494   // insertion of empty range into empty container.
 495   sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
 496   check_invariant(vset);
 497
 498   s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
 499
 500   vset.insert(s.begin(), s.end());
 501
 502   // insertion of empty range into non-empty container.
 503   s.clear();
 504   vset.insert(s.begin(), s.end());
 505   check_invariant(vset);
 506
 507   EXPECT_THAT(extractValues(vset), testing::ElementsAreArray({2, 4, 6, 8}));
 508 }
 509
 510 // This is a test of compilation - the behavior has already been tested
 511 // extensively above.
 512 TEST(SortedVectorTypes, TestBulkInsertionUncopyableTypes) {
 513   std::vector<std::pair<int, std::unique_ptr<int>>> s;
 514   s.emplace_back(1, std::make_unique<int>(0));
 515
 516   sorted_vector_map<int, std::unique_ptr<int>> vmap(
 517       std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
 518
 519   s.clear();
 520   s.emplace_back(3, std::make_unique<int>(0));
 521   vmap.insert(
 522       std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
 523 }
 524
 525 // A moveable and copyable struct, which we use to make sure that no copy
 526 // operations are performed during bulk insertion if moving is an option.
 527 struct Movable {
 528   int x_;
 529   explicit Movable(int x) : x_(x) {}
 530   Movable(const Movable&) {
 531     ADD_FAILURE() << "Copy ctor should not be called";
 532   }
 533   Movable& operator=(const Movable&) {
 534     ADD_FAILURE() << "Copy assignment should not be called";
 535     return *this;
 536   }
 537
 538   Movable(Movable&&) = default;
 539   Movable& operator=(Movable&&) = default;
 540 };
 541
 542 TEST(SortedVectorTypes, TestBulkInsertionMovableTypes) {
 543   std::vector<std::pair<int, Movable>> s;
 544   s.emplace_back(3, Movable(2));
 545   s.emplace_back(1, Movable(0));
 546
 547   sorted_vector_map<int, Movable> vmap(
 548       std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
 549
 550   s.clear();
 551   s.emplace_back(4, Movable(3));
 552   s.emplace_back(2, Movable(1));
 553   vmap.insert(
 554       std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
 555 }
 556
 557 TEST(SortedVectorTypes, TestSetCreationFromVector) {
 558   std::vector<int> vec = {3, 1, -1, 5, 0};
 559   sorted_vector_set<int> vset(std::move(vec));
 560   check_invariant(vset);
 561   EXPECT_THAT(vset, testing::ElementsAreArray({-1, 0, 1, 3, 5}));
 562 }
 563
 564 TEST(SortedVectorTypes, TestMapCreationFromVector) {
 565   std::vector<std::pair<int, int>> vec = {
 566       {3, 1}, {1, 5}, {-1, 2}, {5, 3}, {0, 3}};
 567   sorted_vector_map<int, int> vmap(std::move(vec));
 568   check_invariant(vmap);
 569   auto contents = std::vector<std::pair<int, int>>(vmap.begin(), vmap.end());
 570   auto expected_contents = std::vector<std::pair<int, int>>({
 571       {-1, 2}, {0, 3}, {1, 5}, {3, 1}, {5, 3},
 572   });
 573   EXPECT_EQ(contents, expected_contents);
 574 }