folly/test/FBVectorTest.cpp

   1 /*
   2  * Copyright 2011-present 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 //
  18 // Author: andrei.alexandrescu@fb.com
  19
  20 #include <folly/FBVector.h>
  21
  22 #include <list>
  23 #include <map>
  24 #include <memory>
  25
  26 #include <boost/random.hpp>
  27
  28 #include <folly/FBString.h>
  29 #include <folly/Random.h>
  30 #include <folly/Traits.h>
  31 #include <folly/container/Foreach.h>
  32 #include <folly/portability/GTest.h>
  33
  34 using namespace std;
  35 using namespace folly;
  36
  37 namespace {
  38
  39 auto static const seed = randomNumberSeed();
  40 typedef boost::mt19937 RandomT;
  41 static RandomT rng(seed);
  42
  43 template <class Integral1, class Integral2>
  44 Integral2 random(Integral1 low, Integral2 up) {
  45   boost::uniform_int<> range(low, up);
  46   return range(rng);
  47 }
  48
  49 template <class String>
  50 void randomString(String* toFill, unsigned int maxSize = 1000) {
  51   assert(toFill);
  52   toFill->resize(random(0, maxSize));
  53   FOR_EACH (i, *toFill) {
  54     *i = random('a', 'z');
  55   }
  56 }
  57
  58 template <class String, class Integral>
  59 void Num2String(String& str, Integral /* n */) {
  60   str.resize(10, '\0');
  61   sprintf(&str[0], "%ul", 10);
  62   str.resize(strlen(str.c_str()));
  63 }
  64
  65 template <class T> T randomObject();
  66
  67 template <> int randomObject<int>() {
  68   return random(0, 1024);
  69 }
  70 } // namespace
  71
  72 ////////////////////////////////////////////////////////////////////////////////
  73 // Tests begin here
  74 ////////////////////////////////////////////////////////////////////////////////
  75
  76 TEST(fbvector, clause_23_3_6_1_3_ambiguity) {
  77   fbvector<int> v(10, 20);
  78   EXPECT_EQ(v.size(), 10);
  79   FOR_EACH (i, v) {
  80     EXPECT_EQ(*i, 20);
  81   }
  82 }
  83
  84 TEST(fbvector, clause_23_3_6_1_11_ambiguity) {
  85   fbvector<int> v;
  86   v.assign(10, 20);
  87   EXPECT_EQ(v.size(), 10);
  88   FOR_EACH (i, v) {
  89     EXPECT_EQ(*i, 20);
  90   }
  91 }
  92
  93 TEST(fbvector, clause_23_3_6_2_6) {
  94   fbvector<int> v;
  95   auto const n = random(0U, 10000U);
  96   v.reserve(n);
  97   auto const n1 = random(0U, 10000U);
  98   auto const obj = randomObject<int>();
  99   v.assign(n1, obj);
 100   v.shrink_to_fit();
 101   // Nothing to verify except that the call made it through
 102 }
 103
 104 TEST(fbvector, clause_23_3_6_4_ambiguity) {
 105   fbvector<int> v;
 106   fbvector<int>::const_iterator it = v.end();
 107   v.insert(it, 10, 20);
 108   EXPECT_EQ(v.size(), 10);
 109   for (auto i : v) {
 110     EXPECT_EQ(i, 20);
 111   }
 112 }
 113
 114 TEST(fbvector, composition) {
 115   fbvector< fbvector<double> > matrix(100, fbvector<double>(100));
 116 }
 117
 118 TEST(fbvector, works_with_std_string) {
 119   fbvector<std::string> v(10, "hello");
 120   EXPECT_EQ(v.size(), 10);
 121   v.push_back("world");
 122 }
 123
 124 namespace {
 125 class UserDefinedType { int whatevs_; };
 126 } // namespace
 127
 128 FOLLY_ASSUME_FBVECTOR_COMPATIBLE(UserDefinedType);
 129
 130 TEST(fbvector, works_with_user_defined_type) {
 131   fbvector<UserDefinedType> v(10);
 132   EXPECT_EQ(v.size(), 10);
 133   v.push_back(UserDefinedType());
 134 }
 135
 136 TEST(fbvector, move_construction) {
 137   fbvector<int> v1(100, 100);
 138   fbvector<int> v2;
 139   EXPECT_EQ(v1.size(), 100);
 140   EXPECT_EQ(v1.front(), 100);
 141   EXPECT_EQ(v2.size(), 0);
 142   v2 = std::move(v1);
 143   EXPECT_EQ(v1.size(), 0);
 144   EXPECT_EQ(v2.size(), 100);
 145   EXPECT_EQ(v2.front(), 100);
 146
 147   v1.assign(100, 100);
 148   auto other = std::move(v1);
 149   EXPECT_EQ(v1.size(), 0);
 150   EXPECT_EQ(other.size(), 100);
 151   EXPECT_EQ(other.front(), 100);
 152 }
 153
 154 TEST(fbvector, emplace) {
 155   fbvector<std::string> s(12, "asd");
 156   EXPECT_EQ(s.size(), 12);
 157   EXPECT_EQ(s.front(), "asd");
 158   s.emplace_back("funk");
 159   EXPECT_EQ(s.back(), "funk");
 160 }
 161
 162 TEST(fbvector, initializer_lists) {
 163   fbvector<int> vec = { 1, 2, 3 };
 164   EXPECT_EQ(vec.size(), 3);
 165   EXPECT_EQ(vec[0], 1);
 166   EXPECT_EQ(vec[1], 2);
 167   EXPECT_EQ(vec[2], 3);
 168
 169   vec = { 0, 0, 12, 16 };
 170   EXPECT_EQ(vec.size(), 4);
 171   EXPECT_EQ(vec[0], 0);
 172   EXPECT_EQ(vec[1], 0);
 173   EXPECT_EQ(vec[2], 12);
 174   EXPECT_EQ(vec[3], 16);
 175
 176   vec.insert(vec.begin() + 1, { 23, 23 });
 177   EXPECT_EQ(vec.size(), 6);
 178   EXPECT_EQ(vec[0], 0);
 179   EXPECT_EQ(vec[1], 23);
 180   EXPECT_EQ(vec[2], 23);
 181   EXPECT_EQ(vec[3], 0);
 182   EXPECT_EQ(vec[4], 12);
 183   EXPECT_EQ(vec[5], 16);
 184 }
 185
 186 TEST(fbvector, unique_ptr) {
 187   fbvector<std::unique_ptr<int> > v(12);
 188   std::unique_ptr<int> p(new int(12));
 189   v.push_back(std::move(p));
 190   EXPECT_EQ(*v.back(), 12);
 191
 192   v[0] = std::move(p);
 193   EXPECT_FALSE(v[0].get());
 194   v[0] = std::make_unique<int>(32);
 195   std::unique_ptr<int> somePtr;
 196   v.insert(v.begin(), std::move(somePtr));
 197   EXPECT_EQ(*v[1], 32);
 198 }
 199
 200 TEST(FBVector, task858056) {
 201   fbvector<fbstring> cycle;
 202   cycle.push_back("foo");
 203   cycle.push_back("bar");
 204   cycle.push_back("baz");
 205   fbstring message("Cycle detected: ");
 206   FOR_EACH_R (node_name, cycle) {
 207     message += "[";
 208     message += *node_name;
 209     message += "] ";
 210   }
 211   EXPECT_EQ("Cycle detected: [baz] [bar] [foo] ", message);
 212 }
 213
 214 TEST(FBVector, move_iterator) {
 215   fbvector<int> base = { 0, 1, 2 };
 216
 217   auto cp1 = base;
 218   fbvector<int> fbvi1(std::make_move_iterator(cp1.begin()),
 219                       std::make_move_iterator(cp1.end()));
 220   EXPECT_EQ(fbvi1, base);
 221
 222   auto cp2 = base;
 223   fbvector<int> fbvi2;
 224   fbvi2.assign(std::make_move_iterator(cp2.begin()),
 225                std::make_move_iterator(cp2.end()));
 226   EXPECT_EQ(fbvi2, base);
 227
 228   auto cp3 = base;
 229   fbvector<int> fbvi3;
 230   fbvi3.insert(fbvi3.end(),
 231                std::make_move_iterator(cp3.begin()),
 232                std::make_move_iterator(cp3.end()));
 233   EXPECT_EQ(fbvi3, base);
 234 }
 235
 236 TEST(FBVector, reserve_consistency) {
 237   struct S { int64_t a, b, c, d; };
 238
 239   fbvector<S> fb1;
 240   for (size_t i = 0; i < 1000; ++i) {
 241     fb1.reserve(1);
 242     EXPECT_EQ(fb1.size(), 0);
 243     fb1.shrink_to_fit();
 244   }
 245 }
 246
 247 TEST(FBVector, vector_of_maps) {
 248   fbvector<std::map<std::string, std::string>> v;
 249
 250   v.push_back(std::map<std::string, std::string>());
 251   v.push_back(std::map<std::string, std::string>());
 252
 253   EXPECT_EQ(2, v.size());
 254
 255   v[1]["hello"] = "world";
 256   EXPECT_EQ(0, v[0].size());
 257   EXPECT_EQ(1, v[1].size());
 258
 259   v[0]["foo"] = "bar";
 260   EXPECT_EQ(1, v[0].size());
 261   EXPECT_EQ(1, v[1].size());
 262 }
 263
 264 TEST(FBVector, shrink_to_fit_after_clear) {
 265   fbvector<int> fb1;
 266   fb1.push_back(42);
 267   fb1.push_back(1337);
 268   fb1.clear();
 269   fb1.shrink_to_fit();
 270   EXPECT_EQ(fb1.size(), 0);
 271   EXPECT_EQ(fb1.capacity(), 0);
 272 }
 273
 274 TEST(FBVector, zero_len) {
 275   fbvector<int> fb1(0);
 276   fbvector<int> fb2(0, 10);
 277   fbvector<int> fb3(std::move(fb1));
 278   fbvector<int> fb4;
 279   fb4 = std::move(fb2);
 280   fbvector<int> fb5 = fb3;
 281   fbvector<int> fb6;
 282   fb6 = fb4;
 283   std::initializer_list<int> il = {};
 284   fb6 = il;
 285   fbvector<int> fb7(fb6.begin(), fb6.end());
 286 }