2 * Copyright 2011-present 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>
18 #include <folly/sorted_vector_types.h>
28 #include <boost/algorithm/string.hpp>
30 #include <folly/Conv.h>
31 #include <folly/portability/GTest.h>
32 #include <folly/portability/TypeTraits.h>
34 using folly::small_vector;
35 using namespace folly::small_vector_policy;
37 #if FOLLY_X64 || FOLLY_PPC64
39 static_assert(sizeof(small_vector<int>) == 16,
40 "Object size is not what we expect for small_vector<int>");
41 static_assert(sizeof(small_vector<int32_t,2>) == 16,
42 "Object size is not what we expect for "
43 "small_vector<int32_t,2>");
44 static_assert(sizeof(small_vector<int,10>) ==
45 10 * sizeof(int) + sizeof(std::size_t),
46 "Object size is not what we expect for small_vector<int,10>");
48 static_assert(sizeof(small_vector<int32_t,1,uint32_t>) ==
50 "small_vector<int32_t,1,uint32_t> is wrong size");
51 static_assert(sizeof(small_vector<int32_t,1,uint16_t>) ==
53 "small_vector<int32_t,1,uint32_t> is wrong size");
54 static_assert(sizeof(small_vector<int32_t,1,uint8_t>) ==
56 "small_vector<int32_t,1,uint32_t> is wrong size");
58 static_assert(sizeof(small_vector<int16_t,4,uint16_t>) == 10,
59 "Sizeof unexpectedly large");
63 static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(std::unique_ptr<int>),
64 "std::unique_ptr<> is trivially copyable");
68 template <typename Key, typename Value, size_t N>
69 using small_sorted_vector_map = folly::sorted_vector_map<
73 std::allocator<std::pair<Key, Value>>,
75 folly::small_vector<std::pair<Key, Value>, N>>;
77 template <typename Key, typename Value, size_t N>
78 using noheap_sorted_vector_map = folly::sorted_vector_map<
82 std::allocator<std::pair<Key, Value>>,
85 std::pair<Key, Value>,
87 folly::small_vector_policy::NoHeap>>;
89 template <typename T, size_t N>
90 using small_sorted_vector_set = folly::sorted_vector_set<
95 folly::small_vector<T, N>>;
97 template <typename T, size_t N>
98 using noheap_sorted_vector_set = folly::sorted_vector_set<
103 folly::small_vector<T, N, folly::small_vector_policy::NoHeap>>;
105 struct NontrivialType {
107 explicit NontrivialType() : a(0) {}
109 /* implicit */ NontrivialType(int a) : a(a) {
113 NontrivialType(NontrivialType const& /* s */) { ++ctored; }
115 NontrivialType& operator=(NontrivialType const& o) {
122 static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(NontrivialType),
123 "NontrivialType is trivially copyable");
125 int NontrivialType::ctored = 0;
127 struct TestException {};
129 int throwCounter = 1;
131 if (!--throwCounter) {
132 throw TestException();
136 const int kMagic = 0xdeadbeef;
140 Thrower() : magic(kMagic) {
141 EXPECT_EQ(magic, kMagic);
145 Thrower(Thrower const& other) : magic(other.magic) {
146 EXPECT_EQ(magic, kMagic);
150 ~Thrower() noexcept {
151 EXPECT_EQ(magic, kMagic);
156 Thrower& operator=(Thrower const& /* other */) {
157 EXPECT_EQ(magic, kMagic);
162 // This is just to try to make sure we don't get our member
163 // functions called on uninitialized memory.
167 int Thrower::alive = 0;
169 // Type that counts how many exist and doesn't support copy
171 struct NoncopyableCounter {
173 NoncopyableCounter() {
176 ~NoncopyableCounter() {
179 NoncopyableCounter(NoncopyableCounter&&) noexcept { ++alive; }
180 NoncopyableCounter(NoncopyableCounter const&) = delete;
181 NoncopyableCounter& operator=(NoncopyableCounter const&) const = delete;
182 NoncopyableCounter& operator=(NoncopyableCounter&&) { return *this; }
184 int NoncopyableCounter::alive = 0;
186 static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(NoncopyableCounter),
187 "NoncopyableCounter is trivially copyable");
189 // Check that throws don't break the basic guarantee for some cases.
190 // Uses the method for testing exception safety described at
191 // http://www.boost.org/community/exception_safety.html, to force all
192 // throwing code paths to occur.
193 struct TestBasicGuarantee {
194 folly::small_vector<Thrower,3> vec;
195 int const prepopulate;
197 explicit TestBasicGuarantee(int prepopulate)
198 : prepopulate(prepopulate)
201 for (int i = 0; i < prepopulate; ++i) {
206 ~TestBasicGuarantee() {
210 template <class Operation>
211 void operator()(int insertCount, Operation const& op) {
214 std::unique_ptr<folly::small_vector<Thrower,3> > workingVec;
215 for (int counter = 1; !done; ++counter) {
217 workingVec = std::make_unique<folly::small_vector<Thrower, 3>>(vec);
218 throwCounter = counter;
219 EXPECT_EQ(Thrower::alive, prepopulate * 2);
224 // Note that the size of the vector can change if we were
225 // inserting somewhere other than the end (it's a basic only
226 // guarantee). All we're testing here is that we have the
227 // right amount of uninitialized vs initialized memory.
228 EXPECT_EQ(Thrower::alive, workingVec->size() + vec.size());
232 // If things succeeded.
233 EXPECT_EQ(workingVec->size(), prepopulate + insertCount);
234 EXPECT_EQ(Thrower::alive, prepopulate * 2 + insertCount);
241 TEST(small_vector, BasicGuarantee) {
242 for (int prepop = 1; prepop < 30; ++prepop) {
243 (TestBasicGuarantee(prepop))( // parens or a mildly vexing parse :(
245 [&] (folly::small_vector<Thrower,3>& v) {
250 EXPECT_EQ(Thrower::alive, 0);
252 (TestBasicGuarantee(prepop))(
254 [&] (folly::small_vector<Thrower,3>& v) {
255 v.insert(v.begin(), Thrower());
259 EXPECT_EQ(Thrower::alive, 0);
261 (TestBasicGuarantee(prepop))(
263 [&] (folly::small_vector<Thrower,3>& v) {
264 v.insert(v.begin() + 1, Thrower());
268 EXPECT_EQ(Thrower::alive, 0);
271 TestBasicGuarantee(4)(
273 [&] (folly::small_vector<Thrower,3>& v) {
274 std::vector<Thrower> b;
280 * Apparently if you do the following initializer_list instead
281 * of the above push_back's, and one of the Throwers throws,
282 * g++4.6 doesn't destruct the previous ones. Heh.
284 //b = { Thrower(), Thrower(), Thrower() };
285 v.insert(v.begin() + 1, b.begin(), b.end());
289 TestBasicGuarantee(2)(
291 [&] (folly::small_vector<Thrower,3>& v) {
292 std::vector<Thrower> b;
293 for (int i = 0; i < 6; ++i) {
297 v.insert(v.begin() + 1, b.begin(), b.end());
301 EXPECT_EQ(Thrower::alive, 0);
304 folly::small_vector<Thrower,1> p(14, Thrower());
307 EXPECT_EQ(Thrower::alive, 0);
311 // MALLOC_CONF=prof_leak:true
312 // LD_PRELOAD=${JEMALLOC_PATH}/lib/libjemalloc.so.2
313 // LD_PRELOAD="$LD_PRELOAD:"${UNWIND_PATH}/lib/libunwind.so.7
314 TEST(small_vector, leak_test) {
315 for (int j = 0; j < 1000; ++j) {
316 folly::small_vector<int, 10> someVec(300);
317 for (int i = 0; i < 10000; ++i) {
318 someVec.push_back(12);
323 TEST(small_vector, Insert) {
324 folly::small_vector<int> someVec(3, 3);
325 someVec.insert(someVec.begin(), 12, 12);
326 EXPECT_EQ(someVec.size(), 15);
327 for (size_t i = 0; i < someVec.size(); ++i) {
329 EXPECT_EQ(someVec[i], 12);
331 EXPECT_EQ(someVec[i], 3);
335 auto oldSize = someVec.size();
336 someVec.insert(someVec.begin() + 1, 12, 12);
337 EXPECT_EQ(someVec.size(), oldSize + 12);
339 folly::small_vector<std::string> v1(6, "asd"), v2(7, "wat");
340 v1.insert(v1.begin() + 1, v2.begin(), v2.end());
341 EXPECT_TRUE(v1.size() == 6 + 7);
342 EXPECT_EQ(v1.front(), "asd");
343 EXPECT_EQ(v1[1], "wat");
346 TEST(small_vector, Swap) {
347 folly::small_vector<int,10> somethingVec, emptyVec;
348 somethingVec.push_back(1);
349 somethingVec.push_back(2);
350 somethingVec.push_back(3);
351 somethingVec.push_back(4);
353 // Swapping intern'd with intern'd.
354 auto vec = somethingVec;
355 EXPECT_TRUE(vec == somethingVec);
356 EXPECT_FALSE(vec == emptyVec);
357 EXPECT_FALSE(somethingVec == emptyVec);
359 // Swapping a heap vector with an intern vector.
360 folly::small_vector<int,10> junkVec;
361 junkVec.assign(12, 12);
362 EXPECT_EQ(junkVec.size(), 12);
363 for (auto i : junkVec) {
367 EXPECT_TRUE(junkVec == somethingVec);
368 EXPECT_EQ(vec.size(), 12);
373 // Swapping two heap vectors.
374 folly::small_vector<int,10> moreJunk(15, 15);
375 EXPECT_EQ(moreJunk.size(), 15);
376 for (auto i : moreJunk) {
380 EXPECT_EQ(moreJunk.size(), 12);
381 for (auto i : moreJunk) {
384 EXPECT_EQ(vec.size(), 15);
389 // Making a vector heap, then smaller than another non-heap vector,
391 folly::small_vector<int,5> shrinker, other(4, 10);
392 shrinker = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
393 shrinker.erase(shrinker.begin() + 2, shrinker.end());
394 EXPECT_LT(shrinker.size(), other.size());
395 swap(shrinker, other);
396 EXPECT_EQ(shrinker.size(), 4);
397 EXPECT_TRUE(boost::all(shrinker, boost::is_any_of(std::vector<int>{10})));
398 EXPECT_TRUE((other == small_vector<int,5>{ 0, 1 }));
401 TEST(small_vector, Emplace) {
402 NontrivialType::ctored = 0;
404 folly::small_vector<NontrivialType> vec;
406 vec.emplace_back(12);
407 EXPECT_EQ(NontrivialType::ctored, 1);
408 EXPECT_EQ(vec.front().a, 12);
409 vec.emplace_back(13);
410 EXPECT_EQ(vec.front().a, 12);
411 EXPECT_EQ(vec.back().a, 13);
412 EXPECT_EQ(NontrivialType::ctored, 2);
414 NontrivialType::ctored = 0;
415 for (int i = 0; i < 120; ++i) {
418 EXPECT_EQ(NontrivialType::ctored, 120);
419 EXPECT_EQ(vec[0].a, 12);
420 EXPECT_EQ(vec[1].a, 13);
421 EXPECT_EQ(vec.back().a, 119);
423 // We implement emplace() with a temporary (see the implementation
424 // for a comment about why), so this should make 2 ctor calls.
425 NontrivialType::ctored = 0;
426 vec.emplace(vec.begin(), 12);
427 EXPECT_EQ(NontrivialType::ctored, 2);
430 TEST(small_vector, Erase) {
431 folly::small_vector<int,4> notherVec = { 1, 2, 3, 4, 5 };
432 EXPECT_EQ(notherVec.front(), 1);
433 EXPECT_EQ(notherVec.size(), 5);
434 notherVec.erase(notherVec.begin());
435 EXPECT_EQ(notherVec.front(), 2);
436 EXPECT_EQ(notherVec.size(), 4);
437 EXPECT_EQ(notherVec[2], 4);
438 EXPECT_EQ(notherVec[3], 5);
439 notherVec.erase(notherVec.begin() + 2);
440 EXPECT_EQ(notherVec.size(), 3);
441 EXPECT_EQ(notherVec[2], 5);
443 folly::small_vector<int,2> vec2 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
444 vec2.erase(vec2.begin() + 1, vec2.end() - 1);
445 folly::small_vector<int,2> expected = { 1, 10 };
446 EXPECT_TRUE(vec2 == expected);
448 folly::small_vector<std::string,3> v(102, "ASD");
450 EXPECT_EQ(v.size(), 1024);
451 EXPECT_EQ(v.back(), "D");
452 EXPECT_EQ(v.front(), "ASD");
454 EXPECT_EQ(v.front(), "ASD");
455 EXPECT_EQ(v.size(), 1);
457 EXPECT_TRUE(v.empty());
460 TEST(small_vector, GrowShrinkGrow) {
461 folly::small_vector<NontrivialType,7> vec = { 1, 2, 3, 4, 5 };
462 std::generate_n(std::back_inserter(vec), 102, std::rand);
464 auto capacity = vec.capacity();
466 auto oldSize = vec.size();
467 for (size_t i = 0; i < oldSize; ++i) {
468 vec.erase(vec.begin() + (std::rand() % vec.size()));
469 EXPECT_EQ(vec.capacity(), capacity);
471 EXPECT_TRUE(vec.empty());
473 EXPECT_EQ(vec.capacity(), capacity);
474 std::generate_n(std::back_inserter(vec), 102, std::rand);
475 EXPECT_EQ(vec.capacity(), capacity);
477 std::generate_n(std::back_inserter(vec), 4096, std::rand);
478 EXPECT_GT(vec.capacity(), capacity);
482 EXPECT_LT(vec.capacity(), capacity);
485 EXPECT_EQ(vec.capacity(), 7); // in situ size
488 TEST(small_vector, Iteration) {
489 folly::small_vector<std::string,3> vec = { "foo", "bar" };
490 vec.push_back("blah");
491 vec.push_back("blah2");
492 vec.push_back("blah3");
493 vec.erase(vec.begin() + 2);
495 std::vector<std::string> otherVec;
496 for (auto& s : vec) {
497 otherVec.push_back(s);
499 EXPECT_EQ(otherVec.size(), vec.size());
500 if (otherVec.size() == vec.size()) {
501 EXPECT_TRUE(std::equal(otherVec.begin(), otherVec.end(), vec.begin()));
504 std::reverse(otherVec.begin(), otherVec.end());
505 auto oit = otherVec.begin();
506 auto rit = vec.crbegin();
507 for (; rit != vec.crend(); ++oit, ++rit) {
508 EXPECT_EQ(*oit, *rit);
512 TEST(small_vector, NonCopyableType) {
513 folly::small_vector<NontrivialType,2> vec;
515 for (int i = 0; i < 10; ++i) {
516 vec.emplace(vec.begin(), 13);
518 EXPECT_EQ(vec.size(), 10);
519 auto vec2 = std::move(vec);
520 EXPECT_EQ(vec.size(), 0);
521 EXPECT_EQ(vec2.size(), 10);
524 folly::small_vector<NoncopyableCounter,3> vec3;
525 for (int i = 0; i < 10; ++i) {
526 EXPECT_EQ(vec3.size(), i);
527 EXPECT_EQ(NoncopyableCounter::alive, i);
528 vec3.insert(vec3.begin(), NoncopyableCounter());
530 EXPECT_EQ(vec3.size(), 10);
531 EXPECT_EQ(NoncopyableCounter::alive, 10);
533 vec3.insert(vec3.begin() + 3, NoncopyableCounter());
534 EXPECT_EQ(NoncopyableCounter::alive, 11);
535 auto vec4 = std::move(vec3);
536 EXPECT_EQ(NoncopyableCounter::alive, 11);
538 EXPECT_EQ(NoncopyableCounter::alive, 30);
539 vec4.erase(vec4.begin(), vec4.end());
540 EXPECT_EQ(vec4.size(), 0);
541 EXPECT_EQ(NoncopyableCounter::alive, 0);
544 TEST(small_vector, MoveConstructor) {
545 folly::small_vector<std::string,10> v1;
548 auto v2 = std::move(v1);
549 EXPECT_EQ(v2.size(), 2);
550 EXPECT_EQ(v2[0], "asd");
551 EXPECT_EQ(v2[1], "bsd");
554 EXPECT_EQ(v1.size(), 2);
555 EXPECT_EQ(v1[0], "asd");
556 EXPECT_EQ(v1[1], "bsd");
559 TEST(small_vector, NoHeap) {
560 typedef folly::small_vector<std::string,10,
561 std::size_t,folly::small_vector_policy::NoHeap> Vector;
564 static_assert(v.max_size() == 10, "max_size is incorrect");
566 for (int i = 0; i < 10; ++i) {
567 v.push_back(folly::to<std::string>(i));
568 EXPECT_EQ(v.size(), i + 1);
573 v.insert(v.begin(), "ha");
574 } catch (const std::length_error&) {
579 // Check max_size works right with various policy combinations.
580 folly::small_vector<std::string,32,uint32_t> v4;
581 EXPECT_EQ(v4.max_size(), (1ul << 31) - 1);
584 * Test that even when we ask for a small number inlined it'll still
585 * inline at least as much as it takes to store the value_type
588 folly::small_vector<char,1,NoHeap> notsosmall;
589 static_assert(notsosmall.max_size() == sizeof(char*),
590 "max_size is incorrect");
593 notsosmall.push_back(12);
594 notsosmall.push_back(13);
595 notsosmall.push_back(14);
596 } catch (const std::length_error&) {
599 EXPECT_FALSE(caught);
602 TEST(small_vector, MaxSize) {
603 folly::small_vector<int,2,uint8_t> vec;
604 EXPECT_EQ(vec.max_size(), 127);
605 folly::small_vector<int,2,uint16_t> vec2;
606 EXPECT_EQ(vec2.max_size(), (1 << 15) - 1);
609 TEST(small_vector, AllHeap) {
610 // Use something bigger than the pointer so it can't get inlined.
612 double a, b, c, d, e; int val;
613 SomeObj(int val) : val(val) {}
614 bool operator==(SomeObj const& o) const {
619 folly::small_vector<SomeObj,0> vec = { 1 };
620 EXPECT_EQ(vec.size(), 1);
622 EXPECT_TRUE(vec[0] == 1);
624 vec.insert(vec.begin(), { 0, 1, 2, 3 });
625 EXPECT_EQ(vec.size(), 5);
626 EXPECT_TRUE((vec == folly::small_vector<SomeObj,0>{ 0, 1, 2, 3, 1 }));
629 TEST(small_vector, Basic) {
630 typedef folly::small_vector<int,3,uint32_t
636 EXPECT_EQ(a.front(), 12);
637 EXPECT_EQ(a.size(), 1);
639 EXPECT_EQ(a.size(), 2);
640 EXPECT_EQ(a.front(), 12);
641 EXPECT_EQ(a.back(), 13);
643 a.emplace(a.end(), 32);
644 EXPECT_EQ(a.back(), 32);
646 a.emplace(a.begin(), 12);
647 EXPECT_EQ(a.front(), 12);
648 EXPECT_EQ(a.back(), 32);
649 a.erase(a.end() - 1);
650 EXPECT_EQ(a.back(), 13);
653 EXPECT_EQ(a.back(), 12);
655 EXPECT_EQ(a.back(), 13);
658 a.push_back(s); // lvalue reference
665 EXPECT_TRUE(c != b && b != a);
667 EXPECT_GT(c.size(), 0);
669 EXPECT_EQ(c.size(), 1);
674 TEST(small_vector, Capacity) {
675 folly::small_vector<uint64_t, 1> vec;
676 EXPECT_EQ(vec.size(), 0);
677 EXPECT_EQ(vec.capacity(), 1);
680 EXPECT_EQ(vec.size(), 1);
681 EXPECT_EQ(vec.capacity(), 1);
684 EXPECT_EQ(vec.size(), 2);
685 EXPECT_GT(vec.capacity(), 1);
687 folly::small_vector<uint64_t, 2> vec2;
688 EXPECT_EQ(vec2.size(), 0);
689 EXPECT_EQ(vec2.capacity(), 2);
693 EXPECT_EQ(vec2.size(), 2);
694 EXPECT_EQ(vec2.capacity(), 2);
697 EXPECT_EQ(vec2.size(), 3);
698 EXPECT_GT(vec2.capacity(), 2);
700 // Test capacity heapifying logic
701 folly::small_vector<unsigned char, 1> vec3;
702 const size_t hc_size = 100000;
703 for (size_t i = 0; i < hc_size; ++i) {
704 auto v = (unsigned char)i;
706 EXPECT_EQ(vec3[i], v);
707 EXPECT_EQ(vec3.size(), i + 1);
708 EXPECT_GT(vec3.capacity(), i);
710 for (auto i = hc_size; i > 0; --i) {
711 auto v = (unsigned char)(i - 1);
712 EXPECT_EQ(vec3.back(), v);
714 EXPECT_EQ(vec3.size(), i - 1);
718 TEST(small_vector, SelfPushBack) {
719 for (int i = 1; i < 33; ++i) {
720 folly::small_vector<std::string> vec;
721 for (int j = 0; j < i; ++j) {
722 vec.push_back("abc");
724 EXPECT_EQ(vec.size(), i);
725 vec.push_back(std::move(vec[0]));
726 EXPECT_EQ(vec.size(), i + 1);
728 EXPECT_EQ(vec[i], "abc");
732 TEST(small_vector, SelfEmplaceBack) {
733 for (int i = 1; i < 33; ++i) {
734 folly::small_vector<std::string> vec;
735 for (int j = 0; j < i; ++j) {
736 vec.emplace_back("abc");
738 EXPECT_EQ(vec.size(), i);
739 vec.emplace_back(std::move(vec[0]));
740 EXPECT_EQ(vec.size(), i + 1);
742 EXPECT_EQ(vec[i], "abc");
746 TEST(small_vector, SelfInsert) {
748 for (int i = 1; i < 33; ++i) {
749 folly::small_vector<std::string> vec;
750 for (int j = 0; j < i; ++j) {
751 vec.push_back("abc");
753 EXPECT_EQ(vec.size(), i);
754 vec.insert(vec.end(), std::move(vec[0]));
755 EXPECT_EQ(vec.size(), i + 1);
757 EXPECT_EQ(vec[i], "abc");
758 EXPECT_EQ(vec[vec.size() - 1], "abc");
762 for (int i = 2; i < 33; ++i) {
763 folly::small_vector<std::string> vec;
764 for (int j = 0; j < i; ++j) {
765 vec.push_back("abc");
767 EXPECT_EQ(vec.size(), i);
768 vec.insert(vec.end()-1, std::move(vec[0]));
769 EXPECT_EQ(vec.size(), i + 1);
771 EXPECT_EQ(vec[i-1], "abc");
772 EXPECT_EQ(vec[i], "abc");
777 static const int DEFAULT_VALUE = (int)0xdeadbeef;
778 CheckedInt(): value(DEFAULT_VALUE) {}
779 explicit CheckedInt(int value): value(value) {}
780 CheckedInt(const CheckedInt& rhs, int) : value(rhs.value) {}
781 CheckedInt(const CheckedInt& rhs): value(rhs.value) {}
782 CheckedInt(CheckedInt&& rhs) noexcept: value(rhs.value) {
783 rhs.value = DEFAULT_VALUE;
785 CheckedInt& operator= (const CheckedInt& rhs) {
789 CheckedInt& operator= (CheckedInt&& rhs) noexcept {
791 rhs.value = DEFAULT_VALUE;
798 TEST(small_vector, ForwardingEmplaceInsideVector) {
799 folly::small_vector<CheckedInt> v;
800 v.push_back(CheckedInt(1));
801 for (int i = 1; i < 20; ++i) {
802 v.emplace_back(v[0], 42);
803 ASSERT_EQ(1, v.back().value);
807 TEST(small_vector, LVEmplaceInsideVector) {
808 folly::small_vector<CheckedInt> v;
809 v.push_back(CheckedInt(1));
810 for (int i = 1; i < 20; ++i) {
811 v.emplace_back(v[0]);
812 ASSERT_EQ(1, v.back().value);
816 TEST(small_vector, CLVEmplaceInsideVector) {
817 folly::small_vector<CheckedInt> v;
818 const folly::small_vector<CheckedInt>& cv = v;
819 v.push_back(CheckedInt(1));
820 for (int i = 1; i < 20; ++i) {
821 v.emplace_back(cv[0]);
822 ASSERT_EQ(1, v.back().value);
826 TEST(small_vector, RVEmplaceInsideVector) {
827 folly::small_vector<CheckedInt> v;
828 v.push_back(CheckedInt(0));
829 for (int i = 1; i < 20; ++i) {
830 v[0] = CheckedInt(1);
831 v.emplace_back(std::move(v[0]));
832 ASSERT_EQ(1, v.back().value);
836 TEST(small_vector, LVPushValueInsideVector) {
837 folly::small_vector<CheckedInt> v;
838 v.push_back(CheckedInt(1));
839 for (int i = 1; i < 20; ++i) {
841 ASSERT_EQ(1, v.back().value);
845 TEST(small_vector, RVPushValueInsideVector) {
846 folly::small_vector<CheckedInt> v;
847 v.push_back(CheckedInt(0));
848 for (int i = 1; i < 20; ++i) {
849 v[0] = CheckedInt(1);
851 ASSERT_EQ(1, v.back().value);
855 TEST(small_vector, EmplaceIterCtor) {
856 std::vector<int*> v{new int(1), new int(2)};
857 std::vector<std::unique_ptr<int>> uv(v.begin(), v.end());
859 std::vector<int*> w{new int(1), new int(2)};
860 small_vector<std::unique_ptr<int>> uw(w.begin(), w.end());
863 TEST(small_vector, InputIterator) {
864 std::vector<int> expected{125, 320, 512, 750, 333};
865 std::string values = "125 320 512 750 333";
866 std::istringstream is1(values);
867 std::istringstream is2(values);
869 std::vector<int> stdV{std::istream_iterator<int>(is1),
870 std::istream_iterator<int>()};
871 ASSERT_EQ(stdV.size(), expected.size());
872 for (size_t i = 0; i < expected.size(); i++) {
873 ASSERT_EQ(stdV[i], expected[i]);
876 small_vector<int> smallV{std::istream_iterator<int>(is2),
877 std::istream_iterator<int>()};
878 ASSERT_EQ(smallV.size(), expected.size());
879 for (size_t i = 0; i < expected.size(); i++) {
880 ASSERT_EQ(smallV[i], expected[i]);
884 TEST(small_vector, NoCopyCtor) {
887 Test(const Test&) = delete;
888 Test(Test&&) = default;
893 small_vector<Test> test(10);
894 ASSERT_EQ(test.size(), 10);
895 for (const auto& element : test) {
896 EXPECT_EQ(element.field, 42);
900 TEST(small_vector, ZeroInitializable) {
901 small_vector<int> test(10);
902 ASSERT_EQ(test.size(), 10);
903 for (const auto& element : test) {
904 EXPECT_EQ(element, 0);
908 TEST(small_vector, InsertMoreThanGrowth) {
909 small_vector<int, 10> test;
910 test.insert(test.end(), 30, 0);
911 for (auto element : test) {
912 EXPECT_EQ(element, 0);
916 TEST(small_vector, EmplaceBackExponentialGrowth) {
917 small_vector<std::pair<int, int>> test;
918 std::vector<size_t> capacities;
919 capacities.push_back(test.capacity());
920 for (int i = 0; i < 10000; ++i) {
921 test.emplace_back(0, 0);
922 if (test.capacity() != capacities.back()) {
923 capacities.push_back(test.capacity());
926 EXPECT_LE(capacities.size(), 25);
929 TEST(small_vector, InsertExponentialGrowth) {
930 small_vector<std::pair<int, int>> test;
931 std::vector<size_t> capacities;
932 capacities.push_back(test.capacity());
933 for (int i = 0; i < 10000; ++i) {
934 test.insert(test.begin(), std::make_pair(0, 0));
935 if (test.capacity() != capacities.back()) {
936 capacities.push_back(test.capacity());
939 EXPECT_LE(capacities.size(), 25);
942 TEST(small_vector, InsertNExponentialGrowth) {
943 small_vector<int> test;
944 std::vector<size_t> capacities;
945 capacities.push_back(test.capacity());
946 for (int i = 0; i < 10000; ++i) {
947 test.insert(test.begin(), 100, 0);
948 if (test.capacity() != capacities.back()) {
949 capacities.push_back(test.capacity());
952 EXPECT_LE(capacities.size(), 25);
965 explicit Counter(Counts& counts) : counts(&counts) {}
966 Counter(Counter const& other) noexcept : counts(other.counts) {
969 Counter(Counter&& other) noexcept : counts(other.counts) {
972 Counter& operator=(Counter const& rhs) noexcept {
973 EXPECT_EQ(counts, rhs.counts);
977 Counter& operator=(Counter&& rhs) noexcept {
978 EXPECT_EQ(counts, rhs.counts);
985 TEST(small_vector, EmplaceBackEfficiency) {
986 small_vector<Counter, 2> test;
988 for (size_t i = 1; i <= test.capacity(); ++i) {
989 test.emplace_back(counts);
990 EXPECT_EQ(0, counts.copyCount);
991 EXPECT_EQ(0, counts.moveCount);
993 EXPECT_EQ(test.size(), test.capacity());
994 test.emplace_back(counts);
995 // Every element except the last has to be moved to the new position
996 EXPECT_EQ(0, counts.copyCount);
997 EXPECT_EQ(test.size() - 1, counts.moveCount);
998 EXPECT_LT(test.size(), test.capacity());
1001 TEST(small_vector, RVPushBackEfficiency) {
1002 small_vector<Counter, 2> test;
1004 for (size_t i = 1; i <= test.capacity(); ++i) {
1005 test.push_back(Counter(counts));
1006 // 1 copy for each push_back()
1007 EXPECT_EQ(0, counts.copyCount);
1008 EXPECT_EQ(i, counts.moveCount);
1010 EXPECT_EQ(test.size(), test.capacity());
1011 test.push_back(Counter(counts));
1012 // 1 move for each push_back()
1013 // Every element except the last has to be moved to the new position
1014 EXPECT_EQ(0, counts.copyCount);
1015 EXPECT_EQ(test.size() + test.size() - 1, counts.moveCount);
1016 EXPECT_LT(test.size(), test.capacity());
1019 TEST(small_vector, CLVPushBackEfficiency) {
1020 small_vector<Counter, 2> test;
1022 Counter const counter(counts);
1023 for (size_t i = 1; i <= test.capacity(); ++i) {
1024 test.push_back(counter);
1025 // 1 copy for each push_back()
1026 EXPECT_EQ(i, counts.copyCount);
1027 EXPECT_EQ(0, counts.moveCount);
1029 EXPECT_EQ(test.size(), test.capacity());
1030 test.push_back(counter);
1031 // 1 copy for each push_back()
1032 EXPECT_EQ(test.size(), counts.copyCount);
1033 // Every element except the last has to be moved to the new position
1034 EXPECT_EQ(test.size() - 1, counts.moveCount);
1035 EXPECT_LT(test.size(), test.capacity());
1038 TEST(small_vector, StorageForSortedVectorMap) {
1039 small_sorted_vector_map<int32_t, int32_t, 2> test;
1040 test.insert(std::make_pair(10, 10));
1041 EXPECT_EQ(test.size(), 1);
1042 test.insert(std::make_pair(10, 10));
1043 EXPECT_EQ(test.size(), 1);
1044 test.insert(std::make_pair(20, 10));
1045 EXPECT_EQ(test.size(), 2);
1046 test.insert(std::make_pair(30, 10));
1047 EXPECT_EQ(test.size(), 3);
1050 TEST(small_vector, NoHeapStorageForSortedVectorMap) {
1051 noheap_sorted_vector_map<int32_t, int32_t, 2> test;
1052 test.insert(std::make_pair(10, 10));
1053 EXPECT_EQ(test.size(), 1);
1054 test.insert(std::make_pair(10, 10));
1055 EXPECT_EQ(test.size(), 1);
1056 test.insert(std::make_pair(20, 10));
1057 EXPECT_EQ(test.size(), 2);
1058 EXPECT_THROW(test.insert(std::make_pair(30, 10)), std::length_error);
1059 EXPECT_EQ(test.size(), 2);
1062 TEST(small_vector, StorageForSortedVectorSet) {
1063 small_sorted_vector_set<int32_t, 2> test;
1065 EXPECT_EQ(test.size(), 1);
1067 EXPECT_EQ(test.size(), 1);
1069 EXPECT_EQ(test.size(), 2);
1071 EXPECT_EQ(test.size(), 3);
1074 TEST(small_vector, NoHeapStorageForSortedVectorSet) {
1075 noheap_sorted_vector_set<int32_t, 2> test;
1077 EXPECT_EQ(test.size(), 1);
1079 EXPECT_EQ(test.size(), 1);
1081 EXPECT_EQ(test.size(), 2);
1082 EXPECT_THROW(test.insert(30), std::length_error);
1083 EXPECT_EQ(test.size(), 2);