folly/test/sorted_vector_test.cpp

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