folly/test/FBVectorTest.cpp

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