folly/test/sorted_vector_test.cpp

   1 /*
   2  * Copyright 2013 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, CustomCompare) {
 217   sorted_vector_set<int,less_invert<int> > s;
 218   for (int i = 0; i < 200; ++i)
 219     s.insert(i);
 220   check_invariant(s);
 221
 222   sorted_vector_map<int,float,less_invert<int> > m;
 223   for (int i = 0; i < 200; ++i)
 224     m[i] = 12.0;
 225   check_invariant(m);
 226 }
 227
 228 TEST(SortedVectorTypes, GrowthPolicy) {
 229   typedef sorted_vector_set<CountCopyCtor,
 230                             std::less<CountCopyCtor>,
 231                             std::allocator<CountCopyCtor>,
 232                             OneAtATimePolicy>
 233     SetT;
 234
 235   SetT a;
 236   for (int i = 0; i < 20; ++i) {
 237     a.insert(CountCopyCtor(i));
 238   }
 239   check_invariant(a);
 240   SetT::iterator it = a.begin();
 241   EXPECT_FALSE(it == a.end());
 242   if (it != a.end()) {
 243     EXPECT_EQ(it->val_, 0);
 244     // 1 copy for the initial insertion, 19 more for reallocs on the
 245     // additional insertions.
 246     EXPECT_EQ(it->count_, 20);
 247   }
 248
 249   std::list<CountCopyCtor> v;
 250   for (int i = 0; i < 20; ++i) {
 251     v.push_back(CountCopyCtor(20 + i));
 252   }
 253   a.insert(v.begin(), v.end());
 254   check_invariant(a);
 255
 256   it = a.begin();
 257   EXPECT_FALSE(it == a.end());
 258   if (it != a.end()) {
 259     EXPECT_EQ(it->val_, 0);
 260     // Should be only 1 more copy for inserting this above range.
 261     EXPECT_EQ(it->count_, 21);
 262   }
 263 }
 264
 265 TEST(SortedVectorTest, EmptyTest) {
 266   sorted_vector_set<int> emptySet;
 267   EXPECT_TRUE(emptySet.lower_bound(10) == emptySet.end());
 268   EXPECT_TRUE(emptySet.find(10) == emptySet.end());
 269
 270   sorted_vector_map<int,int> emptyMap;
 271   EXPECT_TRUE(emptyMap.lower_bound(10) == emptyMap.end());
 272   EXPECT_TRUE(emptyMap.find(10) == emptyMap.end());
 273 }