2 * Copyright 2014 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include "folly/small_vector.h"
19 #include <gtest/gtest.h>
25 #include <boost/algorithm/string.hpp>
27 #include "folly/Conv.h"
29 using folly::small_vector;
30 using namespace folly::small_vector_policy;
34 static_assert(sizeof(small_vector<int>) == 16,
35 "Object size is not what we expect for small_vector<int>");
36 static_assert(sizeof(small_vector<int32_t,2>) == 16,
37 "Object size is not what we expect for "
38 "small_vector<int32_t,2>");
39 static_assert(sizeof(small_vector<int,10>) ==
40 10 * sizeof(int) + sizeof(std::size_t),
41 "Object size is not what we expect for small_vector<int,10>");
43 static_assert(sizeof(small_vector<int32_t,1,uint32_t>) ==
45 "small_vector<int32_t,1,uint32_t> is wrong size");
46 static_assert(sizeof(small_vector<int32_t,1,uint16_t>) ==
48 "small_vector<int32_t,1,uint32_t> is wrong size");
49 static_assert(sizeof(small_vector<int32_t,1,uint8_t>) ==
51 "small_vector<int32_t,1,uint32_t> is wrong size");
53 static_assert(sizeof(small_vector<int32_t,1,OneBitMutex>) == 16,
54 "OneBitMutex took more space than expected");
56 static_assert(sizeof(small_vector<int16_t,4,uint16_t>) == 10,
57 "Sizeof unexpectedly large");
58 static_assert(sizeof(small_vector<int16_t,4,uint16_t,OneBitMutex>) == 10,
59 "Sizeof unexpectedly large");
60 static_assert(sizeof(small_vector<int16_t,4,NoHeap,uint16_t,
62 "Sizeof unexpectedly large");
66 static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(std::unique_ptr<int>),
67 "std::unique_ptr<> is trivially copyable");
71 struct NontrivialType {
73 explicit NontrivialType() : a(0) {}
75 /* implicit */ NontrivialType(int a) : a(a) {
79 NontrivialType(NontrivialType const& s) {
83 NontrivialType& operator=(NontrivialType const& o) {
90 static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(NontrivialType),
91 "NontrivialType is trivially copyable");
93 int NontrivialType::ctored = 0;
95 struct TestException {};
99 if (!--throwCounter) {
100 throw TestException();
104 const int kMagic = 0xdeadbeef;
108 Thrower() : magic(kMagic) {
109 EXPECT_EQ(magic, kMagic);
113 Thrower(Thrower const& other) : magic(other.magic) {
114 EXPECT_EQ(magic, kMagic);
118 ~Thrower() noexcept {
119 EXPECT_EQ(magic, kMagic);
124 Thrower& operator=(Thrower const& other) {
125 EXPECT_EQ(magic, kMagic);
130 // This is just to try to make sure we don't get our member
131 // functions called on uninitialized memory.
135 int Thrower::alive = 0;
137 // Type that counts how many exist and doesn't support copy
139 struct NoncopyableCounter {
141 NoncopyableCounter() {
144 ~NoncopyableCounter() {
147 NoncopyableCounter(NoncopyableCounter&&) { ++alive; }
148 NoncopyableCounter(NoncopyableCounter const&) = delete;
149 NoncopyableCounter& operator=(NoncopyableCounter const&) const = delete;
150 NoncopyableCounter& operator=(NoncopyableCounter&&) { return *this; }
152 int NoncopyableCounter::alive = 0;
154 static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(NoncopyableCounter),
155 "NoncopyableCounter is trivially copyable");
157 // Check that throws don't break the basic guarantee for some cases.
158 // Uses the method for testing exception safety described at
159 // http://www.boost.org/community/exception_safety.html, to force all
160 // throwing code paths to occur.
161 struct TestBasicGuarantee {
162 folly::small_vector<Thrower,3> vec;
163 int const prepopulate;
165 explicit TestBasicGuarantee(int prepopulate)
166 : prepopulate(prepopulate)
169 for (int i = 0; i < prepopulate; ++i) {
170 vec.push_back(Thrower());
174 ~TestBasicGuarantee() {
178 template<class Operation>
179 void operator()(int insertCount, Operation const& op) {
182 std::unique_ptr<folly::small_vector<Thrower,3> > workingVec;
183 for (int counter = 1; !done; ++counter) {
185 workingVec.reset(new folly::small_vector<Thrower,3>(vec));
186 throwCounter = counter;
187 EXPECT_EQ(Thrower::alive, prepopulate * 2);
192 // Note that the size of the vector can change if we were
193 // inserting somewhere other than the end (it's a basic only
194 // guarantee). All we're testing here is that we have the
195 // right amount of uninitialized vs initialized memory.
196 EXPECT_EQ(Thrower::alive, workingVec->size() + vec.size());
200 // If things succeeded.
201 EXPECT_EQ(workingVec->size(), prepopulate + insertCount);
202 EXPECT_EQ(Thrower::alive, prepopulate * 2 + insertCount);
209 TEST(small_vector, BasicGuarantee) {
210 for (int prepop = 1; prepop < 30; ++prepop) {
211 (TestBasicGuarantee(prepop))( // parens or a mildly vexing parse :(
213 [&] (folly::small_vector<Thrower,3>& v) {
214 v.push_back(Thrower());
218 EXPECT_EQ(Thrower::alive, 0);
220 (TestBasicGuarantee(prepop))(
222 [&] (folly::small_vector<Thrower,3>& v) {
223 v.insert(v.begin(), Thrower());
227 EXPECT_EQ(Thrower::alive, 0);
229 (TestBasicGuarantee(prepop))(
231 [&] (folly::small_vector<Thrower,3>& v) {
232 v.insert(v.begin() + 1, Thrower());
236 EXPECT_EQ(Thrower::alive, 0);
239 TestBasicGuarantee(4)(
241 [&] (folly::small_vector<Thrower,3>& v) {
242 std::vector<Thrower> b;
243 b.push_back(Thrower());
244 b.push_back(Thrower());
245 b.push_back(Thrower());
248 * Apparently if you do the following initializer_list instead
249 * of the above push_back's, and one of the Throwers throws,
250 * g++4.6 doesn't destruct the previous ones. Heh.
252 //b = { Thrower(), Thrower(), Thrower() };
253 v.insert(v.begin() + 1, b.begin(), b.end());
257 TestBasicGuarantee(2)(
259 [&] (folly::small_vector<Thrower,3>& v) {
260 std::vector<Thrower> b;
261 for (int i = 0; i < 6; ++i) {
262 b.push_back(Thrower());
265 v.insert(v.begin() + 1, b.begin(), b.end());
269 EXPECT_EQ(Thrower::alive, 0);
272 folly::small_vector<Thrower,1> p(14, Thrower());
275 EXPECT_EQ(Thrower::alive, 0);
279 // MALLOC_CONF=prof_leak:true
280 // LD_PRELOAD=${JEMALLOC_PATH}/lib/libjemalloc.so.1
281 // LD_PRELOAD="$LD_PRELOAD:"${UNWIND_PATH}/lib/libunwind.so.7
282 TEST(small_vector, leak_test) {
283 for (int j = 0; j < 1000; ++j) {
284 folly::small_vector<int, 10> someVec(300);
285 for (int i = 0; i < 10000; ++i) {
286 someVec.push_back(12);
291 TEST(small_vector, Insert) {
292 folly::small_vector<int> someVec(3, 3);
293 someVec.insert(someVec.begin(), 12, 12);
294 EXPECT_EQ(someVec.size(), 15);
295 for (int i = 0; i < someVec.size(); ++i) {
297 EXPECT_EQ(someVec[i], 12);
299 EXPECT_EQ(someVec[i], 3);
303 auto oldSize = someVec.size();
304 someVec.insert(someVec.begin() + 1, 12, 12);
305 EXPECT_EQ(someVec.size(), oldSize + 12);
307 folly::small_vector<std::string> v1(6, "asd"), v2(7, "wat");
308 v1.insert(v1.begin() + 1, v2.begin(), v2.end());
309 EXPECT_TRUE(v1.size() == 6 + 7);
310 EXPECT_EQ(v1.front(), "asd");
311 EXPECT_EQ(v1[1], "wat");
314 TEST(small_vector, Swap) {
315 folly::small_vector<int,10> somethingVec, emptyVec;
316 somethingVec.push_back(1);
317 somethingVec.push_back(2);
318 somethingVec.push_back(3);
319 somethingVec.push_back(4);
321 // Swapping intern'd with intern'd.
322 auto vec = somethingVec;
323 EXPECT_TRUE(vec == somethingVec);
324 EXPECT_FALSE(vec == emptyVec);
325 EXPECT_FALSE(somethingVec == emptyVec);
327 // Swapping a heap vector with an intern vector.
328 folly::small_vector<int,10> junkVec;
329 junkVec.assign(12, 12);
330 EXPECT_EQ(junkVec.size(), 12);
331 for (auto i : junkVec) {
335 EXPECT_TRUE(junkVec == somethingVec);
336 EXPECT_EQ(vec.size(), 12);
341 // Swapping two heap vectors.
342 folly::small_vector<int,10> moreJunk(15, 15);
343 EXPECT_EQ(moreJunk.size(), 15);
344 for (auto i : moreJunk) {
348 EXPECT_EQ(moreJunk.size(), 12);
349 for (auto i : moreJunk) {
352 EXPECT_EQ(vec.size(), 15);
357 // Making a vector heap, then smaller than another non-heap vector,
359 folly::small_vector<int,5> shrinker, other(4, 10);
360 shrinker = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
361 shrinker.erase(shrinker.begin() + 2, shrinker.end());
362 EXPECT_LT(shrinker.size(), other.size());
363 swap(shrinker, other);
364 EXPECT_EQ(shrinker.size(), 4);
365 EXPECT_TRUE(boost::all(shrinker, boost::is_any_of(std::vector<int>{10})));
366 EXPECT_TRUE((other == small_vector<int,5>{ 0, 1 }));
369 TEST(small_vector, Emplace) {
370 NontrivialType::ctored = 0;
372 folly::small_vector<NontrivialType> vec;
374 vec.emplace_back(12);
375 EXPECT_EQ(NontrivialType::ctored, 1);
376 EXPECT_EQ(vec.front().a, 12);
377 vec.emplace_back(13);
378 EXPECT_EQ(vec.front().a, 12);
379 EXPECT_EQ(vec.back().a, 13);
380 EXPECT_EQ(NontrivialType::ctored, 2);
382 NontrivialType::ctored = 0;
383 for (int i = 0; i < 120; ++i) {
386 EXPECT_EQ(NontrivialType::ctored, 120);
387 EXPECT_EQ(vec[0].a, 12);
388 EXPECT_EQ(vec[1].a, 13);
389 EXPECT_EQ(vec.back().a, 119);
391 // We implement emplace() with a temporary (see the implementation
392 // for a comment about why), so this should make 2 ctor calls.
393 NontrivialType::ctored = 0;
394 vec.emplace(vec.begin(), 12);
395 EXPECT_EQ(NontrivialType::ctored, 2);
398 TEST(small_vector, Erase) {
399 folly::small_vector<int,4> notherVec = { 1, 2, 3, 4, 5 };
400 EXPECT_EQ(notherVec.front(), 1);
401 EXPECT_EQ(notherVec.size(), 5);
402 notherVec.erase(notherVec.begin());
403 EXPECT_EQ(notherVec.front(), 2);
404 EXPECT_EQ(notherVec.size(), 4);
405 EXPECT_EQ(notherVec[2], 4);
406 EXPECT_EQ(notherVec[3], 5);
407 notherVec.erase(notherVec.begin() + 2);
408 EXPECT_EQ(notherVec.size(), 3);
409 EXPECT_EQ(notherVec[2], 5);
411 folly::small_vector<int,2> vec2 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
412 vec2.erase(vec2.begin() + 1, vec2.end() - 1);
413 folly::small_vector<int,2> expected = { 1, 10 };
414 EXPECT_TRUE(vec2 == expected);
416 folly::small_vector<std::string,3> v(102, "ASD");
418 EXPECT_EQ(v.size(), 1024);
419 EXPECT_EQ(v.back(), "D");
420 EXPECT_EQ(v.front(), "ASD");
422 EXPECT_EQ(v.front(), "ASD");
423 EXPECT_EQ(v.size(), 1);
425 EXPECT_TRUE(v.empty());
428 TEST(small_vector, GrowShrinkGrow) {
429 folly::small_vector<NontrivialType,7> vec = { 1, 2, 3, 4, 5 };
430 std::generate_n(std::back_inserter(vec), 102, std::rand);
432 auto capacity = vec.capacity();
434 auto oldSize = vec.size();
435 for (int i = 0; i < oldSize; ++i) {
436 vec.erase(vec.begin() + (std::rand() % vec.size()));
437 EXPECT_EQ(vec.capacity(), capacity);
439 EXPECT_TRUE(vec.empty());
441 EXPECT_EQ(vec.capacity(), capacity);
442 std::generate_n(std::back_inserter(vec), 102, std::rand);
443 EXPECT_EQ(vec.capacity(), capacity);
445 std::generate_n(std::back_inserter(vec), 4096, std::rand);
446 EXPECT_GT(vec.capacity(), capacity);
450 EXPECT_LT(vec.capacity(), capacity);
453 EXPECT_EQ(vec.capacity(), 7); // in situ size
456 TEST(small_vector, Iteration) {
457 folly::small_vector<std::string,3> vec = { "foo", "bar" };
458 vec.push_back("blah");
459 vec.push_back("blah2");
460 vec.push_back("blah3");
461 vec.erase(vec.begin() + 2);
463 std::vector<std::string> otherVec;
464 for (auto& s : vec) {
465 otherVec.push_back(s);
467 EXPECT_EQ(otherVec.size(), vec.size());
468 if (otherVec.size() == vec.size()) {
469 EXPECT_TRUE(std::equal(otherVec.begin(), otherVec.end(), vec.begin()));
472 std::reverse(otherVec.begin(), otherVec.end());
473 auto oit = otherVec.begin();
474 auto rit = vec.crbegin();
475 for (; rit != vec.crend(); ++oit, ++rit) {
476 EXPECT_EQ(*oit, *rit);
480 TEST(small_vector, NonCopyableType) {
481 folly::small_vector<NontrivialType,2> vec;
483 for (int i = 0; i < 10; ++i) {
484 vec.emplace(vec.begin(), 13);
486 EXPECT_EQ(vec.size(), 10);
487 auto vec2 = std::move(vec);
488 EXPECT_EQ(vec.size(), 0);
489 EXPECT_EQ(vec2.size(), 10);
492 folly::small_vector<NoncopyableCounter,3> vec3;
493 for (int i = 0; i < 10; ++i) {
494 EXPECT_EQ(vec3.size(), i);
495 EXPECT_EQ(NoncopyableCounter::alive, i);
496 vec3.insert(vec3.begin(), NoncopyableCounter());
498 EXPECT_EQ(vec3.size(), 10);
499 EXPECT_EQ(NoncopyableCounter::alive, 10);
501 vec3.insert(vec3.begin() + 3, NoncopyableCounter());
502 EXPECT_EQ(NoncopyableCounter::alive, 11);
503 auto vec4 = std::move(vec3);
504 EXPECT_EQ(NoncopyableCounter::alive, 11);
506 EXPECT_EQ(NoncopyableCounter::alive, 30);
507 vec4.erase(vec4.begin(), vec4.end());
508 EXPECT_EQ(vec4.size(), 0);
509 EXPECT_EQ(NoncopyableCounter::alive, 0);
512 TEST(small_vector, MoveConstructor) {
513 folly::small_vector<std::string,10> v1;
516 auto v2 = std::move(v1);
517 EXPECT_EQ(v2.size(), 2);
518 EXPECT_EQ(v2[0], "asd");
519 EXPECT_EQ(v2[1], "bsd");
522 EXPECT_EQ(v1.size(), 2);
523 EXPECT_EQ(v1[0], "asd");
524 EXPECT_EQ(v1[1], "bsd");
527 TEST(small_vector, NoHeap) {
528 typedef folly::small_vector<std::string,10,
529 std::size_t,folly::small_vector_policy::NoHeap> Vector;
532 static_assert(v.max_size() == 10, "max_size is incorrect");
534 for (int i = 0; i < 10; ++i) {
535 v.push_back(folly::to<std::string>(i));
536 EXPECT_EQ(v.size(), i + 1);
541 v.insert(v.begin(), "ha");
542 } catch (const std::length_error&) {
547 // Check max_size works right with various policy combinations.
548 folly::small_vector<std::string,32,uint32_t,NoHeap,OneBitMutex> v2;
549 static_assert(v2.max_size() == 32, "max_size is incorrect");
550 folly::small_vector<std::string,32,uint32_t,OneBitMutex> v3;
551 EXPECT_EQ(v3.max_size(), (1ul << 30) - 1);
552 folly::small_vector<std::string,32,uint32_t> v4;
553 EXPECT_EQ(v4.max_size(), (1ul << 31) - 1);
556 * Test that even when we ask for a small number inlined it'll still
557 * inline at least as much as it takes to store the value_type
560 folly::small_vector<char,1,NoHeap> notsosmall;
561 static_assert(notsosmall.max_size() == sizeof(char*),
562 "max_size is incorrect");
565 notsosmall.push_back(12);
566 notsosmall.push_back(13);
567 notsosmall.push_back(14);
568 } catch (const std::length_error&) {
571 EXPECT_FALSE(caught);
574 TEST(small_vector, MaxSize) {
575 folly::small_vector<int,2,uint8_t> vec;
576 EXPECT_EQ(vec.max_size(), 127);
577 folly::small_vector<int,2,uint16_t> vec2;
578 EXPECT_EQ(vec2.max_size(), (1 << 15) - 1);
579 folly::small_vector<int,2,uint16_t,OneBitMutex> vec3;
580 EXPECT_EQ(vec3.max_size(), (1 << 14) - 1);
583 TEST(small_vector, AllHeap) {
584 // Use something bigger than the pointer so it can't get inlined.
586 double a, b, c, d, e; int val;
587 SomeObj(int val) : val(val) {}
588 bool operator==(SomeObj const& o) const {
593 folly::small_vector<SomeObj,0> vec = { 1 };
594 EXPECT_EQ(vec.size(), 1);
596 EXPECT_TRUE(vec[0] == 1);
598 vec.insert(vec.begin(), { 0, 1, 2, 3 });
599 EXPECT_EQ(vec.size(), 5);
600 EXPECT_TRUE((vec == folly::small_vector<SomeObj,0>{ 0, 1, 2, 3, 1 }));
603 TEST(small_vector, Basic) {
604 typedef folly::small_vector<int,3,uint32_t
618 EXPECT_EQ(a.front(), 12);
619 EXPECT_EQ(a.size(), 1);
621 EXPECT_EQ(a.size(), 2);
622 EXPECT_EQ(a.front(), 12);
623 EXPECT_EQ(a.back(), 13);
625 a.emplace(a.end(), 32);
626 EXPECT_EQ(a.back(), 32);
628 a.emplace(a.begin(), 12);
629 EXPECT_EQ(a.front(), 12);
630 EXPECT_EQ(a.back(), 32);
631 a.erase(a.end() - 1);
632 EXPECT_EQ(a.back(), 13);
635 EXPECT_EQ(a.back(), 12);
637 EXPECT_EQ(a.back(), 13);
640 a.push_back(s); // lvalue reference
647 EXPECT_TRUE(c != b && b != a);
649 EXPECT_GT(c.size(), 0);
651 EXPECT_EQ(c.size(), 1);
656 TEST(small_vector, Capacity) {
657 folly::small_vector<unsigned long, 1> vec;
658 EXPECT_EQ(vec.size(), 0);
659 EXPECT_EQ(vec.capacity(), 1);
662 EXPECT_EQ(vec.size(), 1);
663 EXPECT_EQ(vec.capacity(), 1);
666 EXPECT_EQ(vec.size(), 2);
667 EXPECT_GT(vec.capacity(), 1);
670 folly::small_vector<unsigned long, 2> vec2;
671 EXPECT_EQ(vec2.size(), 0);
672 EXPECT_EQ(vec2.capacity(), 2);
676 EXPECT_EQ(vec2.size(), 2);
677 EXPECT_EQ(vec2.capacity(), 2);
680 EXPECT_EQ(vec2.size(), 3);
681 EXPECT_GT(vec2.capacity(), 2);
683 // Test capacity heapifying logic
684 folly::small_vector<unsigned char, 1> vec3;
685 const size_t hc_size = 1000000;
686 for (size_t i = 0; i < hc_size; ++i) {
687 auto v = (unsigned char)i;
689 EXPECT_EQ(vec3[i], v);
690 EXPECT_EQ(vec3.size(), i + 1);
691 EXPECT_GT(vec3.capacity(), i);
693 for (auto i = hc_size; i > 0; --i) {
694 auto v = (unsigned char)(i - 1);
695 EXPECT_EQ(vec3.back(), v);
697 EXPECT_EQ(vec3.size(), i - 1);
701 TEST(small_vector, SelfPushBack) {
702 for (int i = 1; i < 33; ++i) {
703 folly::small_vector<std::string> vec;
704 for (int j = 0; j < i; ++j) {
705 vec.push_back("abc");
707 EXPECT_EQ(vec.size(), i);
708 vec.push_back(std::move(vec[0]));
709 EXPECT_EQ(vec.size(), i + 1);
711 EXPECT_EQ(vec[i], "abc");
715 TEST(small_vector, SelfEmplaceBack) {
716 for (int i = 1; i < 33; ++i) {
717 folly::small_vector<std::string> vec;
718 for (int j = 0; j < i; ++j) {
719 vec.emplace_back("abc");
721 EXPECT_EQ(vec.size(), i);
722 vec.emplace_back(std::move(vec[0]));
723 EXPECT_EQ(vec.size(), i + 1);
725 EXPECT_EQ(vec[i], "abc");
729 TEST(small_vector, SelfInsert) {
731 for (int i = 1; i < 33; ++i) {
732 folly::small_vector<std::string> vec;
733 for (int j = 0; j < i; ++j) {
734 vec.push_back("abc");
736 EXPECT_EQ(vec.size(), i);
737 vec.insert(vec.end(), std::move(vec[0]));
738 EXPECT_EQ(vec.size(), i + 1);
740 EXPECT_EQ(vec[i], "abc");
741 EXPECT_EQ(vec[vec.size() - 1], "abc");
745 for (int i = 2; i < 33; ++i) {
746 folly::small_vector<std::string> vec;
747 for (int j = 0; j < i; ++j) {
748 vec.push_back("abc");
750 EXPECT_EQ(vec.size(), i);
751 vec.insert(vec.end()-1, std::move(vec[0]));
752 EXPECT_EQ(vec.size(), i + 1);
754 EXPECT_EQ(vec[i-1], "abc");
755 EXPECT_EQ(vec[i], "abc");