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