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