folly/test/sorted_vector_test.cpp

   1 /*
   2  * Copyright 2014 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_FALSE(m.find(32) == m.end());
 153   m.erase(32);
 154   EXPECT_TRUE(m.find(32) == m.end());
 155   check_invariant(m);
 156
 157   sorted_vector_map<int,float> m2 = m;
 158   EXPECT_TRUE(m2 == m);
 159   EXPECT_FALSE(m2 != m);
 160   auto it = m2.lower_bound(1 << 20);
 161   EXPECT_TRUE(it == m2.end());
 162   m2.insert(it, std::make_pair(1 << 20, 10.0f));
 163   check_invariant(m2);
 164   EXPECT_TRUE(m2.count(1 << 20) == 1);
 165   EXPECT_TRUE(m < m2);
 166   EXPECT_TRUE(m <= m2);
 167
 168   const sorted_vector_map<int,float>& cm = m;
 169   auto range = cm.equal_range(42);
 170   auto lbound = cm.lower_bound(42);
 171   auto ubound = cm.upper_bound(42);
 172   EXPECT_TRUE(range.first == lbound);
 173   EXPECT_TRUE(range.second == ubound);
 174   EXPECT_FALSE(range.first == cm.end());
 175   EXPECT_FALSE(range.second == cm.end());
 176   m.erase(m.lower_bound(42));
 177   check_invariant(m);
 178
 179   sorted_vector_map<int,float> m3;
 180   m3.insert(m2.begin(), m2.end());
 181   check_invariant(m3);
 182   EXPECT_TRUE(m3 == m2);
 183   EXPECT_FALSE(m3 == m);
 184
 185   EXPECT_TRUE(m != m2);
 186   EXPECT_TRUE(m2 == m3);
 187   EXPECT_TRUE(m3 != m);
 188   m.swap(m3);
 189   check_invariant(m);
 190   check_invariant(m2);
 191   check_invariant(m3);
 192   EXPECT_TRUE(m3 != m2);
 193   EXPECT_TRUE(m3 != m);
 194   EXPECT_TRUE(m == m2);
 195
 196   // Bad insert hint.
 197   m.insert(m.begin() + 3, std::make_pair(1 << 15, 1.0f));
 198   check_invariant(m);
 199 }
 200
 201 TEST(SortedVectorTypes, Sizes) {
 202   EXPECT_EQ(sizeof(sorted_vector_set<int>),
 203             sizeof(std::vector<int>));
 204   EXPECT_EQ(sizeof(sorted_vector_map<int,int>),
 205             sizeof(std::vector<std::pair<int,int> >));
 206
 207   typedef sorted_vector_set<int,std::less<int>,
 208     std::allocator<int>,OneAtATimePolicy> SetT;
 209   typedef sorted_vector_map<int,int,std::less<int>,
 210     std::allocator<int>,OneAtATimePolicy> MapT;
 211
 212   EXPECT_EQ(sizeof(SetT), sizeof(std::vector<int>));
 213   EXPECT_EQ(sizeof(MapT), sizeof(std::vector<std::pair<int,int> >));
 214 }
 215
 216 TEST(SortedVectorTypes, InitializerLists) {
 217   sorted_vector_set<int> empty_initialized_set{};
 218   EXPECT_TRUE(empty_initialized_set.empty());
 219
 220   sorted_vector_set<int> singleton_initialized_set{1};
 221   EXPECT_EQ(1, singleton_initialized_set.size());
 222   EXPECT_EQ(1, *singleton_initialized_set.begin());
 223
 224   sorted_vector_set<int> forward_initialized_set{1, 2};
 225   sorted_vector_set<int> backward_initialized_set{2, 1};
 226   EXPECT_EQ(2, forward_initialized_set.size());
 227   EXPECT_EQ(1, *forward_initialized_set.begin());
 228   EXPECT_EQ(2, *forward_initialized_set.rbegin());
 229   EXPECT_TRUE(forward_initialized_set == backward_initialized_set);
 230
 231   sorted_vector_map<int,int> empty_initialized_map{};
 232   EXPECT_TRUE(empty_initialized_map.empty());
 233
 234   sorted_vector_map<int,int> singleton_initialized_map{{1,10}};
 235   EXPECT_EQ(1, singleton_initialized_map.size());
 236   EXPECT_EQ(10, singleton_initialized_map[1]);
 237
 238   sorted_vector_map<int,int> forward_initialized_map{{1,10}, {2,20}};
 239   sorted_vector_map<int,int> backward_initialized_map{{2,20}, {1,10}};
 240   EXPECT_EQ(2, forward_initialized_map.size());
 241   EXPECT_EQ(10, forward_initialized_map[1]);
 242   EXPECT_EQ(20, forward_initialized_map[2]);
 243   EXPECT_TRUE(forward_initialized_map == backward_initialized_map);
 244 }
 245
 246 TEST(SortedVectorTypes, CustomCompare) {
 247   sorted_vector_set<int,less_invert<int> > s;
 248   for (int i = 0; i < 200; ++i)
 249     s.insert(i);
 250   check_invariant(s);
 251
 252   sorted_vector_map<int,float,less_invert<int> > m;
 253   for (int i = 0; i < 200; ++i)
 254     m[i] = 12.0;
 255   check_invariant(m);
 256 }
 257
 258 TEST(SortedVectorTypes, GrowthPolicy) {
 259   typedef sorted_vector_set<CountCopyCtor,
 260                             std::less<CountCopyCtor>,
 261                             std::allocator<CountCopyCtor>,
 262                             OneAtATimePolicy>
 263     SetT;
 264
 265   SetT a;
 266   for (int i = 0; i < 20; ++i) {
 267     a.insert(CountCopyCtor(i));
 268   }
 269   check_invariant(a);
 270   SetT::iterator it = a.begin();
 271   EXPECT_FALSE(it == a.end());
 272   if (it != a.end()) {
 273     EXPECT_EQ(it->val_, 0);
 274     // 1 copy for the initial insertion, 19 more for reallocs on the
 275     // additional insertions.
 276     EXPECT_EQ(it->count_, 20);
 277   }
 278
 279   std::list<CountCopyCtor> v;
 280   for (int i = 0; i < 20; ++i) {
 281     v.push_back(CountCopyCtor(20 + i));
 282   }
 283   a.insert(v.begin(), v.end());
 284   check_invariant(a);
 285
 286   it = a.begin();
 287   EXPECT_FALSE(it == a.end());
 288   if (it != a.end()) {
 289     EXPECT_EQ(it->val_, 0);
 290     // Should be only 1 more copy for inserting this above range.
 291     EXPECT_EQ(it->count_, 21);
 292   }
 293 }
 294
 295 TEST(SortedVectorTest, EmptyTest) {
 296   sorted_vector_set<int> emptySet;
 297   EXPECT_TRUE(emptySet.lower_bound(10) == emptySet.end());
 298   EXPECT_TRUE(emptySet.find(10) == emptySet.end());
 299
 300   sorted_vector_map<int,int> emptyMap;
 301   EXPECT_TRUE(emptyMap.lower_bound(10) == emptyMap.end());
 302   EXPECT_TRUE(emptyMap.find(10) == emptyMap.end());
 303 }
 304
 305 TEST(SortedVectorTest, MoveTest) {
 306   sorted_vector_set<std::unique_ptr<int>> s;
 307   s.insert(std::unique_ptr<int>(new int(5)));
 308   s.insert(s.end(), std::unique_ptr<int>(new int(10)));
 309   EXPECT_EQ(s.size(), 2);
 310
 311   for (const auto& p : s) {
 312     EXPECT_TRUE(*p == 5 || *p == 10);
 313   }
 314
 315   sorted_vector_map<int, std::unique_ptr<int>> m;
 316   m.insert(std::make_pair(5, std::unique_ptr<int>(new int(5))));
 317   m.insert(m.end(), std::make_pair(10, std::unique_ptr<int>(new int(10))));
 318
 319   EXPECT_EQ(*m[5], 5);
 320   EXPECT_EQ(*m[10], 10);
 321 }