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#include <folly/small_vector.h>
18#include <folly/sorted_vector_types.h>
19
20#include <iostream>
21#include <iterator>
22#include <limits>
23#include <memory>
24#include <sstream>
25#include <string>
26#include <vector>
27
28#include <boost/algorithm/string.hpp>
29
30#include <folly/Conv.h>
31#include <folly/Traits.h>
32#include <folly/portability/GTest.h>
33
34using folly::small_vector;
35using namespace folly::small_vector_policy;
36
37#if FOLLY_X64 || FOLLY_PPC64
38
39static_assert(
40 sizeof(small_vector<int>) == 16,
41 "Object size is not what we expect for small_vector<int>");
42static_assert(
43 sizeof(small_vector<int32_t, 2>) == 16,
44 "Object size is not what we expect for "
45 "small_vector<int32_t,2>");
46static_assert(
47 sizeof(small_vector<int, 10>) == 10 * sizeof(int) + sizeof(std::size_t),
48 "Object size is not what we expect for small_vector<int,10>");
49
50static_assert(
51 sizeof(small_vector<int32_t, 1, uint32_t>) == 8 + 4,
52 "small_vector<int32_t,1,uint32_t> is wrong size");
53
54// Extra 2 bytes needed for alignment.
55static_assert(
56 sizeof(small_vector<int32_t, 1, uint16_t>) == 8 + 2 + 2,
57 "small_vector<int32_t,1,uint16_t> is wrong size");
58static_assert(
59 alignof(small_vector<int32_t, 1, uint16_t>) >= 4,
60 "small_vector not aligned correctly");
61
62// Extra 3 bytes needed for alignment.
63static_assert(
64 sizeof(small_vector<int32_t, 1, uint8_t>) == 8 + 1 + 3,
65 "small_vector<int32_t,1,uint8_t> is wrong size");
66static_assert(
67 alignof(small_vector<int32_t, 1, uint8_t>) >= 4,
68 "small_vector not aligned correctly");
69
70static_assert(
71 sizeof(small_vector<int16_t, 4, uint16_t>) == 10,
72 "Sizeof unexpectedly large");
73
74#endif
75
76static_assert(
77 !folly::is_trivially_copyable<std::unique_ptr<int>>::value,
78 "std::unique_ptr<> is trivially copyable");
79
80static_assert(
81 alignof(small_vector<std::aligned_storage<32, 32>::type, 4>) == 32,
82 "small_vector not aligned correctly");
83
84namespace {
85
86template <typename Key, typename Value, size_t N>
87using small_sorted_vector_map = folly::sorted_vector_map<
88 Key,
89 Value,
90 std::less<Key>,
91 std::allocator<std::pair<Key, Value>>,
92 void,
93 folly::small_vector<std::pair<Key, Value>, N>>;
94
95template <typename Key, typename Value, size_t N>
96using noheap_sorted_vector_map = folly::sorted_vector_map<
97 Key,
98 Value,
99 std::less<Key>,
100 std::allocator<std::pair<Key, Value>>,
101 void,
102 folly::small_vector<
103 std::pair<Key, Value>,
104 N,
105 folly::small_vector_policy::NoHeap>>;
106
107template <typename T, size_t N>
108using small_sorted_vector_set = folly::sorted_vector_set<
109 T,
110 std::less<T>,
111 std::allocator<T>,
112 void,
113 folly::small_vector<T, N>>;
114
115template <typename T, size_t N>
116using noheap_sorted_vector_set = folly::sorted_vector_set<
117 T,
118 std::less<T>,
119 std::allocator<T>,
120 void,
121 folly::small_vector<T, N, folly::small_vector_policy::NoHeap>>;
122
123struct NontrivialType {
124 static int ctored;
125 explicit NontrivialType() : a(0) {}
126
127 /* implicit */ NontrivialType(int a_) : a(a_) {
128 ++ctored;
129 }
130
131 NontrivialType(NontrivialType const& /* s */) {
132 ++ctored;
133 }
134
135 NontrivialType& operator=(NontrivialType const& o) {
136 a = o.a;
137 return *this;
138 }
139
140 int32_t a;
141};
142static_assert(
143 !folly::is_trivially_copyable<NontrivialType>::value,
144 "NontrivialType is trivially copyable");
145
146int NontrivialType::ctored = 0;
147
148struct TestException {};
149
150int throwCounter = 1;
151void MaybeThrow() {
152 if (!--throwCounter) {
153 throw TestException();
154 }
155}
156
157const int kMagic = 0xdeadbeef;
158struct Thrower {
159 static int alive;
160
161 Thrower() : magic(kMagic) {
162 EXPECT_EQ(magic, kMagic);
163 MaybeThrow();
164 ++alive;
165 }
166 Thrower(Thrower const& other) : magic(other.magic) {
167 EXPECT_EQ(magic, kMagic);
168 MaybeThrow();
169 ++alive;
170 }
171 ~Thrower() noexcept {
172 EXPECT_EQ(magic, kMagic);
173 magic = 0;
174 --alive;
175 }
176
177 Thrower& operator=(Thrower const& /* other */) {
178 EXPECT_EQ(magic, kMagic);
179 MaybeThrow();
180 return *this;
181 }
182
183 // This is just to try to make sure we don't get our member
184 // functions called on uninitialized memory.
185 int magic;
186};
187
188int Thrower::alive = 0;
189
190// Type that counts how many exist and doesn't support copy
191// construction.
192struct NoncopyableCounter {
193 static int alive;
194 NoncopyableCounter() {
195 ++alive;
196 }
197 ~NoncopyableCounter() {
198 --alive;
199 }
200 NoncopyableCounter(NoncopyableCounter&&) noexcept {
201 ++alive;
202 }
203 NoncopyableCounter(NoncopyableCounter const&) = delete;
204 NoncopyableCounter& operator=(NoncopyableCounter const&) const = delete;
205 NoncopyableCounter& operator=(NoncopyableCounter&&) {
206 return *this;
207 }
208};
209int NoncopyableCounter::alive = 0;
210
211static_assert(
212 !folly::is_trivially_copyable<NoncopyableCounter>::value,
213 "NoncopyableCounter is trivially copyable");
214
215// Check that throws don't break the basic guarantee for some cases.
216// Uses the method for testing exception safety described at
217// http://www.boost.org/community/exception_safety.html, to force all
218// throwing code paths to occur.
219struct TestBasicGuarantee {
220 folly::small_vector<Thrower, 3> vec;
221 int const prepopulate;
222
223 explicit TestBasicGuarantee(int prepopulate_) : prepopulate(prepopulate_) {
224 throwCounter = 1000;
225 for (int i = 0; i < prepopulate; ++i) {
226 vec.emplace_back();
227 }
228 }
229
230 ~TestBasicGuarantee() {
231 throwCounter = 1000;
232 }
233
234 template <class Operation>
235 void operator()(int insertCount, Operation const& op) {
236 bool done = false;
237
238 std::unique_ptr<folly::small_vector<Thrower, 3>> workingVec;
239 for (int counter = 1; !done; ++counter) {
240 throwCounter = 1000;
241 workingVec = std::make_unique<folly::small_vector<Thrower, 3>>(vec);
242 throwCounter = counter;
243 EXPECT_EQ(Thrower::alive, prepopulate * 2);
244 try {
245 op(*workingVec);
246 done = true;
247 } catch (...) {
248 // Note that the size of the vector can change if we were
249 // inserting somewhere other than the end (it's a basic only
250 // guarantee). All we're testing here is that we have the
251 // right amount of uninitialized vs initialized memory.
252 EXPECT_EQ(Thrower::alive, workingVec->size() + vec.size());
253 continue;
254 }
255
256 // If things succeeded.
257 EXPECT_EQ(workingVec->size(), prepopulate + insertCount);
258 EXPECT_EQ(Thrower::alive, prepopulate * 2 + insertCount);
259 }
260 }
261};
262
263} // namespace
264
265TEST(small_vector, BasicGuarantee) {
266 for (int prepop = 1; prepop < 30; ++prepop) {
267 (TestBasicGuarantee(prepop))( // parens or a mildly vexing parse :(
268 1,
269 [&](folly::small_vector<Thrower, 3>& v) { v.emplace_back(); });
270
271 EXPECT_EQ(Thrower::alive, 0);
272
273 (TestBasicGuarantee(prepop))(1, [&](folly::small_vector<Thrower, 3>& v) {
274 v.insert(v.begin(), Thrower());
275 });
276
277 EXPECT_EQ(Thrower::alive, 0);
278
279 (TestBasicGuarantee(prepop))(1, [&](folly::small_vector<Thrower, 3>& v) {
280 v.insert(v.begin() + 1, Thrower());
281 });
282
283 EXPECT_EQ(Thrower::alive, 0);
284 }
285
286 TestBasicGuarantee(4)(3, [&](folly::small_vector<Thrower, 3>& v) {
287 std::vector<Thrower> b;
288 b.emplace_back();
289 b.emplace_back();
290 b.emplace_back();
291
292 /*
293 * Apparently if you do the following initializer_list instead
294 * of the above push_back's, and one of the Throwers throws,
295 * g++4.6 doesn't destruct the previous ones. Heh.
296 */
297 // b = { Thrower(), Thrower(), Thrower() };
298 v.insert(v.begin() + 1, b.begin(), b.end());
299 });
300
301 TestBasicGuarantee(2)(6, [&](folly::small_vector<Thrower, 3>& v) {
302 std::vector<Thrower> b;
303 for (int i = 0; i < 6; ++i) {
304 b.emplace_back();
305 }
306
307 v.insert(v.begin() + 1, b.begin(), b.end());
308 });
309
310 EXPECT_EQ(Thrower::alive, 0);
311 try {
312 throwCounter = 4;
313 folly::small_vector<Thrower, 1> p(14, Thrower());
314 } catch (...) {
315 }
316 EXPECT_EQ(Thrower::alive, 0);
317}
318
319// Run this with.
320// MALLOC_CONF=prof_leak:true
321// LD_PRELOAD=${JEMALLOC_PATH}/lib/libjemalloc.so.2
322// LD_PRELOAD="$LD_PRELOAD:"${UNWIND_PATH}/lib/libunwind.so.7
323TEST(small_vector, leak_test) {
324 for (int j = 0; j < 1000; ++j) {
325 folly::small_vector<int, 10> someVec(300);
326 for (int i = 0; i < 10000; ++i) {
327 someVec.push_back(12);
328 }
329 }
330}
331
332TEST(small_vector, Insert) {
333 folly::small_vector<int> someVec(3, 3);
334 someVec.insert(someVec.begin(), 12, 12);
335 EXPECT_EQ(someVec.size(), 15);
336 for (size_t i = 0; i < someVec.size(); ++i) {
337 if (i < 12) {
338 EXPECT_EQ(someVec[i], 12);
339 } else {
340 EXPECT_EQ(someVec[i], 3);
341 }
342 }
343
344 auto oldSize = someVec.size();
345 someVec.insert(someVec.begin() + 1, 12, 12);
346 EXPECT_EQ(someVec.size(), oldSize + 12);
347
348 folly::small_vector<std::string> v1(6, "asd"), v2(7, "wat");
349 v1.insert(v1.begin() + 1, v2.begin(), v2.end());
350 EXPECT_TRUE(v1.size() == 6 + 7);
351 EXPECT_EQ(v1.front(), "asd");
352 EXPECT_EQ(v1[1], "wat");
353}
354
355TEST(small_vector, Swap) {
356 folly::small_vector<int, 10> somethingVec, emptyVec;
357 somethingVec.push_back(1);
358 somethingVec.push_back(2);
359 somethingVec.push_back(3);
360 somethingVec.push_back(4);
361
362 // Swapping intern'd with intern'd.
363 auto vec = somethingVec;
364 EXPECT_TRUE(vec == somethingVec);
365 EXPECT_FALSE(vec == emptyVec);
366 EXPECT_FALSE(somethingVec == emptyVec);
367
368 // Swapping a heap vector with an intern vector.
369 folly::small_vector<int, 10> junkVec;
370 junkVec.assign(12, 12);
371 EXPECT_EQ(junkVec.size(), 12);
372 for (auto i : junkVec) {
373 EXPECT_EQ(i, 12);
374 }
375 swap(junkVec, vec);
376 EXPECT_TRUE(junkVec == somethingVec);
377 EXPECT_EQ(vec.size(), 12);
378 for (auto i : vec) {
379 EXPECT_EQ(i, 12);
380 }
381
382 // Swapping two heap vectors.
383 folly::small_vector<int, 10> moreJunk(15, 15);
384 EXPECT_EQ(moreJunk.size(), 15);
385 for (auto i : moreJunk) {
386 EXPECT_EQ(i, 15);
387 }
388 swap(vec, moreJunk);
389 EXPECT_EQ(moreJunk.size(), 12);
390 for (auto i : moreJunk) {
391 EXPECT_EQ(i, 12);
392 }
393 EXPECT_EQ(vec.size(), 15);
394 for (auto i : vec) {
395 EXPECT_EQ(i, 15);
396 }
397
398 // Making a vector heap, then smaller than another non-heap vector,
399 // then swapping.
400 folly::small_vector<int, 5> shrinker, other(4, 10);
401 shrinker = {0, 1, 2, 3, 4, 5, 6, 7, 8};
402 shrinker.erase(shrinker.begin() + 2, shrinker.end());
403 EXPECT_LT(shrinker.size(), other.size());
404 swap(shrinker, other);
405 EXPECT_EQ(shrinker.size(), 4);
406 EXPECT_TRUE(boost::all(shrinker, boost::is_any_of(std::vector<int>{10})));
407 EXPECT_TRUE((other == small_vector<int, 5>{0, 1}));
408}
409
410TEST(small_vector, Emplace) {
411 NontrivialType::ctored = 0;
412
413 folly::small_vector<NontrivialType> vec;
414 vec.reserve(1024);
415 vec.emplace_back(12);
416 EXPECT_EQ(NontrivialType::ctored, 1);
417 EXPECT_EQ(vec.front().a, 12);
418 vec.emplace_back(13);
419 EXPECT_EQ(vec.front().a, 12);
420 EXPECT_EQ(vec.back().a, 13);
421 EXPECT_EQ(NontrivialType::ctored, 2);
422
423 NontrivialType::ctored = 0;
424 for (int i = 0; i < 120; ++i) {
425 vec.emplace_back(i);
426 }
427 EXPECT_EQ(NontrivialType::ctored, 120);
428 EXPECT_EQ(vec[0].a, 12);
429 EXPECT_EQ(vec[1].a, 13);
430 EXPECT_EQ(vec.back().a, 119);
431
432 // We implement emplace() with a temporary (see the implementation
433 // for a comment about why), so this should make 2 ctor calls.
434 NontrivialType::ctored = 0;
435 vec.emplace(vec.begin(), 12);
436 EXPECT_EQ(NontrivialType::ctored, 2);
437}
438
439TEST(small_vector, Erase) {
440 folly::small_vector<int, 4> notherVec = {1, 2, 3, 4, 5};
441 EXPECT_EQ(notherVec.front(), 1);
442 EXPECT_EQ(notherVec.size(), 5);
443 notherVec.erase(notherVec.begin());
444 EXPECT_EQ(notherVec.front(), 2);
445 EXPECT_EQ(notherVec.size(), 4);
446 EXPECT_EQ(notherVec[2], 4);
447 EXPECT_EQ(notherVec[3], 5);
448 notherVec.erase(notherVec.begin() + 2);
449 EXPECT_EQ(notherVec.size(), 3);
450 EXPECT_EQ(notherVec[2], 5);
451
452 folly::small_vector<int, 2> vec2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
453 vec2.erase(vec2.begin() + 1, vec2.end() - 1);
454 folly::small_vector<int, 2> expected = {1, 10};
455 EXPECT_TRUE(vec2 == expected);
456
457 folly::small_vector<std::string, 3> v(102, "ASD");
458 v.resize(1024, "D");
459 EXPECT_EQ(v.size(), 1024);
460 EXPECT_EQ(v.back(), "D");
461 EXPECT_EQ(v.front(), "ASD");
462 v.resize(1);
463 EXPECT_EQ(v.front(), "ASD");
464 EXPECT_EQ(v.size(), 1);
465 v.resize(0);
466 EXPECT_TRUE(v.empty());
467}
468
469TEST(small_vector, GrowShrinkGrow) {
470 folly::small_vector<NontrivialType, 7> vec = {1, 2, 3, 4, 5};
471 std::generate_n(std::back_inserter(vec), 102, std::rand);
472
473 auto capacity = vec.capacity();
474
475 auto oldSize = vec.size();
476 for (size_t i = 0; i < oldSize; ++i) {
477 vec.erase(vec.begin() + (std::rand() % vec.size()));
478 EXPECT_EQ(vec.capacity(), capacity);
479 }
480 EXPECT_TRUE(vec.empty());
481
482 EXPECT_EQ(vec.capacity(), capacity);
483 std::generate_n(std::back_inserter(vec), 102, std::rand);
484 EXPECT_EQ(vec.capacity(), capacity);
485
486 std::generate_n(std::back_inserter(vec), 4096, std::rand);
487 EXPECT_GT(vec.capacity(), capacity);
488
489 vec.resize(10);
490 vec.shrink_to_fit();
491 EXPECT_LT(vec.capacity(), capacity);
492 vec.resize(4);
493 vec.shrink_to_fit();
494 EXPECT_EQ(vec.capacity(), 7); // in situ size
495}
496
497TEST(small_vector, Iteration) {
498 folly::small_vector<std::string, 3> vec = {"foo", "bar"};
499 vec.push_back("blah");
500 vec.push_back("blah2");
501 vec.push_back("blah3");
502 vec.erase(vec.begin() + 2);
503
504 std::vector<std::string> otherVec;
505 for (auto& s : vec) {
506 otherVec.push_back(s);
507 }
508 EXPECT_EQ(otherVec.size(), vec.size());
509 if (otherVec.size() == vec.size()) {
510 EXPECT_TRUE(std::equal(otherVec.begin(), otherVec.end(), vec.begin()));
511 }
512
513 std::reverse(otherVec.begin(), otherVec.end());
514 auto oit = otherVec.begin();
515 auto rit = vec.crbegin();
516 for (; rit != vec.crend(); ++oit, ++rit) {
517 EXPECT_EQ(*oit, *rit);
518 }
519}
520
521TEST(small_vector, NonCopyableType) {
522 folly::small_vector<NontrivialType, 2> vec;
523
524 for (int i = 0; i < 10; ++i) {
525 vec.emplace(vec.begin(), 13);
526 }
527 EXPECT_EQ(vec.size(), 10);
528 auto vec2 = std::move(vec);
529 EXPECT_EQ(vec.size(), 0);
530 EXPECT_EQ(vec2.size(), 10);
531 vec2.clear();
532
533 folly::small_vector<NoncopyableCounter, 3> vec3;
534 for (int i = 0; i < 10; ++i) {
535 EXPECT_EQ(vec3.size(), i);
536 EXPECT_EQ(NoncopyableCounter::alive, i);
537 vec3.insert(vec3.begin(), NoncopyableCounter());
538 }
539 EXPECT_EQ(vec3.size(), 10);
540 EXPECT_EQ(NoncopyableCounter::alive, 10);
541
542 vec3.insert(vec3.begin() + 3, NoncopyableCounter());
543 EXPECT_EQ(NoncopyableCounter::alive, 11);
544 auto vec4 = std::move(vec3);
545 EXPECT_EQ(NoncopyableCounter::alive, 11);
546 vec4.resize(30);
547 EXPECT_EQ(NoncopyableCounter::alive, 30);
548 vec4.erase(vec4.begin(), vec4.end());
549 EXPECT_EQ(vec4.size(), 0);
550 EXPECT_EQ(NoncopyableCounter::alive, 0);
551}
552
553TEST(small_vector, MoveConstructor) {
554 folly::small_vector<std::string, 10> v1;
555 v1.push_back("asd");
556 v1.push_back("bsd");
557 auto v2 = std::move(v1);
558 EXPECT_EQ(v2.size(), 2);
559 EXPECT_EQ(v2[0], "asd");
560 EXPECT_EQ(v2[1], "bsd");
561
562 v1 = std::move(v2);
563 EXPECT_EQ(v1.size(), 2);
564 EXPECT_EQ(v1[0], "asd");
565 EXPECT_EQ(v1[1], "bsd");
566}
567
568TEST(small_vector, NoHeap) {
569 typedef folly::small_vector<
570 std::string,
571 10,
572 std::size_t,
573 folly::small_vector_policy::NoHeap>
574 Vector;
575
576 Vector v;
577 static_assert(v.max_size() == 10, "max_size is incorrect");
578
579 for (int i = 0; i < 10; ++i) {
580 v.push_back(folly::to<std::string>(i));
581 EXPECT_EQ(v.size(), i + 1);
582 }
583
584 bool caught = false;
585 try {
586 v.insert(v.begin(), "ha");
587 } catch (const std::length_error&) {
588 caught = true;
589 }
590 EXPECT_TRUE(caught);
591
592 // Check max_size works right with various policy combinations.
593 folly::small_vector<std::string, 32, uint32_t> v4;
594 EXPECT_EQ(v4.max_size(), (1ul << 31) - 1);
595
596 /*
597 * Test that even when we ask for a small number inlined it'll still
598 * inline at least as much as it takes to store the value_type
599 * pointer.
600 */
601 folly::small_vector<char, 1, NoHeap> notsosmall;
602 static_assert(
603 notsosmall.max_size() == sizeof(char*), "max_size is incorrect");
604 caught = false;
605 try {
606 notsosmall.push_back(12);
607 notsosmall.push_back(13);
608 notsosmall.push_back(14);
609 } catch (const std::length_error&) {
610 caught = true;
611 }
612 EXPECT_FALSE(caught);
613}
614
615TEST(small_vector, MaxSize) {
616 folly::small_vector<int, 2, uint8_t> vec;
617 EXPECT_EQ(vec.max_size(), 127);
618 folly::small_vector<int, 2, uint16_t> vec2;
619 EXPECT_EQ(vec2.max_size(), (1 << 15) - 1);
620}
621
622TEST(small_vector, AllHeap) {
623 // Use something bigger than the pointer so it can't get inlined.
624 struct SomeObj {
625 double a, b, c, d, e;
626 int val;
627 SomeObj(int val_) : val(val_) {}
628 bool operator==(SomeObj const& o) const {
629 return o.val == val;
630 }
631 };
632
633 folly::small_vector<SomeObj, 0> vec = {1};
634 EXPECT_EQ(vec.size(), 1);
635 if (!vec.empty()) {
636 EXPECT_TRUE(vec[0] == 1);
637 }
638 vec.insert(vec.begin(), {0, 1, 2, 3});
639 EXPECT_EQ(vec.size(), 5);
640 EXPECT_TRUE((vec == folly::small_vector<SomeObj, 0>{0, 1, 2, 3, 1}));
641}
642
643TEST(small_vector, Basic) {
644 typedef folly::small_vector<int, 3, uint32_t> Vector;
645
646 Vector a;
647
648 a.push_back(12);
649 EXPECT_EQ(a.front(), 12);
650 EXPECT_EQ(a.size(), 1);
651 a.push_back(13);
652 EXPECT_EQ(a.size(), 2);
653 EXPECT_EQ(a.front(), 12);
654 EXPECT_EQ(a.back(), 13);
655
656 a.emplace(a.end(), 32);
657 EXPECT_EQ(a.back(), 32);
658
659 a.emplace(a.begin(), 12);
660 EXPECT_EQ(a.front(), 12);
661 EXPECT_EQ(a.back(), 32);
662 a.erase(a.end() - 1);
663 EXPECT_EQ(a.back(), 13);
664
665 a.push_back(12);
666 EXPECT_EQ(a.back(), 12);
667 a.pop_back();
668 EXPECT_EQ(a.back(), 13);
669
670 const int s = 12;
671 a.push_back(s); // lvalue reference
672
673 Vector b, c;
674 b = a;
675 EXPECT_TRUE(b == a);
676 c = std::move(b);
677 EXPECT_TRUE(c == a);
678 EXPECT_TRUE(c != b && b != a);
679
680 EXPECT_GT(c.size(), 0);
681 c.resize(1);
682 EXPECT_EQ(c.size(), 1);
683
684 Vector intCtor(12);
685}
686
687TEST(small_vector, Capacity) {
688 folly::small_vector<uint64_t, 1> vec;
689 EXPECT_EQ(vec.size(), 0);
690 EXPECT_EQ(vec.capacity(), 1);
691
692 vec.push_back(0);
693 EXPECT_EQ(vec.size(), 1);
694 EXPECT_EQ(vec.capacity(), 1);
695
696 vec.push_back(1);
697 EXPECT_EQ(vec.size(), 2);
698 EXPECT_GT(vec.capacity(), 1);
699
700 folly::small_vector<uint64_t, 2> vec2;
701 EXPECT_EQ(vec2.size(), 0);
702 EXPECT_EQ(vec2.capacity(), 2);
703
704 vec2.push_back(0);
705 vec2.push_back(1);
706 EXPECT_EQ(vec2.size(), 2);
707 EXPECT_EQ(vec2.capacity(), 2);
708
709 vec2.push_back(2);
710 EXPECT_EQ(vec2.size(), 3);
711 EXPECT_GT(vec2.capacity(), 2);
712
713 // Test capacity heapifying logic
714 folly::small_vector<unsigned char, 1> vec3;
715 const size_t hc_size = 100000;
716 for (size_t i = 0; i < hc_size; ++i) {
717 auto v = (unsigned char)i;
718 vec3.push_back(v);
719 EXPECT_EQ(vec3[i], v);
720 EXPECT_EQ(vec3.size(), i + 1);
721 EXPECT_GT(vec3.capacity(), i);
722 }
723 for (auto i = hc_size; i > 0; --i) {
724 auto v = (unsigned char)(i - 1);
725 EXPECT_EQ(vec3.back(), v);
726 vec3.pop_back();
727 EXPECT_EQ(vec3.size(), i - 1);
728 }
729}
730
731TEST(small_vector, SelfPushBack) {
732 for (int i = 1; i < 33; ++i) {
733 folly::small_vector<std::string> vec;
734 for (int j = 0; j < i; ++j) {
735 vec.push_back("abc");
736 }
737 EXPECT_EQ(vec.size(), i);
738 vec.push_back(std::move(vec[0]));
739 EXPECT_EQ(vec.size(), i + 1);
740
741 EXPECT_EQ(vec[i], "abc");
742 }
743}
744
745TEST(small_vector, SelfEmplaceBack) {
746 for (int i = 1; i < 33; ++i) {
747 folly::small_vector<std::string> vec;
748 for (int j = 0; j < i; ++j) {
749 vec.emplace_back("abc");
750 }
751 EXPECT_EQ(vec.size(), i);
752 vec.emplace_back(std::move(vec[0]));
753 EXPECT_EQ(vec.size(), i + 1);
754
755 EXPECT_EQ(vec[i], "abc");
756 }
757}
758
759TEST(small_vector, SelfInsert) {
760 // end insert
761 for (int i = 1; i < 33; ++i) {
762 folly::small_vector<std::string> vec;
763 for (int j = 0; j < i; ++j) {
764 vec.push_back("abc");
765 }
766 EXPECT_EQ(vec.size(), i);
767 vec.insert(vec.end(), std::move(vec[0]));
768 EXPECT_EQ(vec.size(), i + 1);
769
770 EXPECT_EQ(vec[i], "abc");
771 EXPECT_EQ(vec[vec.size() - 1], "abc");
772 }
773
774 // middle insert
775 for (int i = 2; i < 33; ++i) {
776 folly::small_vector<std::string> vec;
777 for (int j = 0; j < i; ++j) {
778 vec.push_back("abc");
779 }
780 EXPECT_EQ(vec.size(), i);
781 vec.insert(vec.end() - 1, std::move(vec[0]));
782 EXPECT_EQ(vec.size(), i + 1);
783
784 EXPECT_EQ(vec[i - 1], "abc");
785 EXPECT_EQ(vec[i], "abc");
786 }
787}
788
789struct CheckedInt {
790 static const int DEFAULT_VALUE = (int)0xdeadbeef;
791 CheckedInt() : value(DEFAULT_VALUE) {}
792 explicit CheckedInt(int value_) : value(value_) {}
793 CheckedInt(const CheckedInt& rhs, int) : value(rhs.value) {}
794 CheckedInt(const CheckedInt& rhs) : value(rhs.value) {}
795 CheckedInt(CheckedInt&& rhs) noexcept : value(rhs.value) {
796 rhs.value = DEFAULT_VALUE;
797 }
798 CheckedInt& operator=(const CheckedInt& rhs) {
799 value = rhs.value;
800 return *this;
801 }
802 CheckedInt& operator=(CheckedInt&& rhs) noexcept {
803 value = rhs.value;
804 rhs.value = DEFAULT_VALUE;
805 return *this;
806 }
807 ~CheckedInt() {}
808 int value;
809};
810
811TEST(small_vector, ForwardingEmplaceInsideVector) {
812 folly::small_vector<CheckedInt> v;
813 v.push_back(CheckedInt(1));
814 for (int i = 1; i < 20; ++i) {
815 v.emplace_back(v[0], 42);
816 ASSERT_EQ(1, v.back().value);
817 }
818}
819
820TEST(small_vector, LVEmplaceInsideVector) {
821 folly::small_vector<CheckedInt> v;
822 v.push_back(CheckedInt(1));
823 for (int i = 1; i < 20; ++i) {
824 v.emplace_back(v[0]);
825 ASSERT_EQ(1, v.back().value);
826 }
827}
828
829TEST(small_vector, CLVEmplaceInsideVector) {
830 folly::small_vector<CheckedInt> v;
831 const folly::small_vector<CheckedInt>& cv = v;
832 v.push_back(CheckedInt(1));
833 for (int i = 1; i < 20; ++i) {
834 v.emplace_back(cv[0]);
835 ASSERT_EQ(1, v.back().value);
836 }
837}
838
839TEST(small_vector, RVEmplaceInsideVector) {
840 folly::small_vector<CheckedInt> v;
841 v.push_back(CheckedInt(0));
842 for (int i = 1; i < 20; ++i) {
843 v[0] = CheckedInt(1);
844 v.emplace_back(std::move(v[0]));
845 ASSERT_EQ(1, v.back().value);
846 }
847}
848
849TEST(small_vector, LVPushValueInsideVector) {
850 folly::small_vector<CheckedInt> v;
851 v.push_back(CheckedInt(1));
852 for (int i = 1; i < 20; ++i) {
853 v.push_back(v[0]);
854 ASSERT_EQ(1, v.back().value);
855 }
856}
857
858TEST(small_vector, RVPushValueInsideVector) {
859 folly::small_vector<CheckedInt> v;
860 v.push_back(CheckedInt(0));
861 for (int i = 1; i < 20; ++i) {
862 v[0] = CheckedInt(1);
863 v.push_back(v[0]);
864 ASSERT_EQ(1, v.back().value);
865 }
866}
867
868TEST(small_vector, EmplaceIterCtor) {
869 std::vector<int*> v{new int(1), new int(2)};
870 std::vector<std::unique_ptr<int>> uv(v.begin(), v.end());
871
872 std::vector<int*> w{new int(1), new int(2)};
873 small_vector<std::unique_ptr<int>> uw(w.begin(), w.end());
874}
875
876TEST(small_vector, InputIterator) {
877 std::vector<int> expected{125, 320, 512, 750, 333};
878 std::string values = "125 320 512 750 333";
879 std::istringstream is1(values);
880 std::istringstream is2(values);
881
882 std::vector<int> stdV{std::istream_iterator<int>(is1),
883 std::istream_iterator<int>()};
884 ASSERT_EQ(stdV.size(), expected.size());
885 for (size_t i = 0; i < expected.size(); i++) {
886 ASSERT_EQ(stdV[i], expected[i]);
887 }
888
889 small_vector<int> smallV{std::istream_iterator<int>(is2),
890 std::istream_iterator<int>()};
891 ASSERT_EQ(smallV.size(), expected.size());
892 for (size_t i = 0; i < expected.size(); i++) {
893 ASSERT_EQ(smallV[i], expected[i]);
894 }
895}
896
897TEST(small_vector, NoCopyCtor) {
898 struct Tester {
899 Tester() = default;
900 Tester(const Tester&) = delete;
901 Tester(Tester&&) = default;
902
903 int field = 42;
904 };
905
906 small_vector<Tester> test(10);
907 ASSERT_EQ(test.size(), 10);
908 for (const auto& element : test) {
909 EXPECT_EQ(element.field, 42);
910 }
911}
912
913TEST(small_vector, ZeroInitializable) {
914 small_vector<int> test(10);
915 ASSERT_EQ(test.size(), 10);
916 for (const auto& element : test) {
917 EXPECT_EQ(element, 0);
918 }
919}
920
921TEST(small_vector, InsertMoreThanGrowth) {
922 small_vector<int, 10> test;
923 test.insert(test.end(), 30, 0);
924 for (auto element : test) {
925 EXPECT_EQ(element, 0);
926 }
927}
928
929TEST(small_vector, EmplaceBackExponentialGrowth) {
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.emplace_back(0, 0);
935 if (test.capacity() != capacities.back()) {
936 capacities.push_back(test.capacity());
937 }
938 }
939 EXPECT_LE(capacities.size(), 25);
940}
941
942TEST(small_vector, InsertExponentialGrowth) {
943 small_vector<std::pair<int, 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(), std::make_pair(0, 0));
948 if (test.capacity() != capacities.back()) {
949 capacities.push_back(test.capacity());
950 }
951 }
952 EXPECT_LE(capacities.size(), 25);
953}
954
955TEST(small_vector, InsertNExponentialGrowth) {
956 small_vector<int> test;
957 std::vector<size_t> capacities;
958 capacities.push_back(test.capacity());
959 for (int i = 0; i < 10000; ++i) {
960 test.insert(test.begin(), 100, 0);
961 if (test.capacity() != capacities.back()) {
962 capacities.push_back(test.capacity());
963 }
964 }
965 EXPECT_LE(capacities.size(), 25);
966}
967
968namespace {
969struct Counts {
970 size_t copyCount{0};
971 size_t moveCount{0};
972};
973
974class Counter {
975 Counts* counts;
976
977 public:
978 explicit Counter(Counts& counts_) : counts(&counts_) {}
979 Counter(Counter const& other) noexcept : counts(other.counts) {
980 ++counts->copyCount;
981 }
982 Counter(Counter&& other) noexcept : counts(other.counts) {
983 ++counts->moveCount;
984 }
985 Counter& operator=(Counter const& rhs) noexcept {
986 EXPECT_EQ(counts, rhs.counts);
987 ++counts->copyCount;
988 return *this;
989 }
990 Counter& operator=(Counter&& rhs) noexcept {
991 EXPECT_EQ(counts, rhs.counts);
992 ++counts->moveCount;
993 return *this;
994 }
995};
996} // namespace
997
998TEST(small_vector, EmplaceBackEfficiency) {
999 small_vector<Counter, 2> test;
1000 Counts counts;
1001 for (size_t i = 1; i <= test.capacity(); ++i) {
1002 test.emplace_back(counts);
1003 EXPECT_EQ(0, counts.copyCount);
1004 EXPECT_EQ(0, counts.moveCount);
1005 }
1006 EXPECT_EQ(test.size(), test.capacity());
1007 test.emplace_back(counts);
1008 // Every element except the last has to be moved to the new position
1009 EXPECT_EQ(0, counts.copyCount);
1010 EXPECT_EQ(test.size() - 1, counts.moveCount);
1011 EXPECT_LT(test.size(), test.capacity());
1012}
1013
1014TEST(small_vector, RVPushBackEfficiency) {
1015 small_vector<Counter, 2> test;
1016 Counts counts;
1017 for (size_t i = 1; i <= test.capacity(); ++i) {
1018 test.push_back(Counter(counts));
1019 // 1 copy for each push_back()
1020 EXPECT_EQ(0, counts.copyCount);
1021 EXPECT_EQ(i, counts.moveCount);
1022 }
1023 EXPECT_EQ(test.size(), test.capacity());
1024 test.push_back(Counter(counts));
1025 // 1 move for each push_back()
1026 // Every element except the last has to be moved to the new position
1027 EXPECT_EQ(0, counts.copyCount);
1028 EXPECT_EQ(test.size() + test.size() - 1, counts.moveCount);
1029 EXPECT_LT(test.size(), test.capacity());
1030}
1031
1032TEST(small_vector, CLVPushBackEfficiency) {
1033 small_vector<Counter, 2> test;
1034 Counts counts;
1035 Counter const counter(counts);
1036 for (size_t i = 1; i <= test.capacity(); ++i) {
1037 test.push_back(counter);
1038 // 1 copy for each push_back()
1039 EXPECT_EQ(i, counts.copyCount);
1040 EXPECT_EQ(0, counts.moveCount);
1041 }
1042 EXPECT_EQ(test.size(), test.capacity());
1043 test.push_back(counter);
1044 // 1 copy for each push_back()
1045 EXPECT_EQ(test.size(), counts.copyCount);
1046 // Every element except the last has to be moved to the new position
1047 EXPECT_EQ(test.size() - 1, counts.moveCount);
1048 EXPECT_LT(test.size(), test.capacity());
1049}
1050
1051TEST(small_vector, StorageForSortedVectorMap) {
1052 small_sorted_vector_map<int32_t, int32_t, 2> test;
1053 test.insert(std::make_pair(10, 10));
1054 EXPECT_EQ(test.size(), 1);
1055 test.insert(std::make_pair(10, 10));
1056 EXPECT_EQ(test.size(), 1);
1057 test.insert(std::make_pair(20, 10));
1058 EXPECT_EQ(test.size(), 2);
1059 test.insert(std::make_pair(30, 10));
1060 EXPECT_EQ(test.size(), 3);
1061}
1062
1063TEST(small_vector, NoHeapStorageForSortedVectorMap) {
1064 noheap_sorted_vector_map<int32_t, int32_t, 2> test;
1065 test.insert(std::make_pair(10, 10));
1066 EXPECT_EQ(test.size(), 1);
1067 test.insert(std::make_pair(10, 10));
1068 EXPECT_EQ(test.size(), 1);
1069 test.insert(std::make_pair(20, 10));
1070 EXPECT_EQ(test.size(), 2);
1071 EXPECT_THROW(test.insert(std::make_pair(30, 10)), std::length_error);
1072 EXPECT_EQ(test.size(), 2);
1073}
1074
1075TEST(small_vector, StorageForSortedVectorSet) {
1076 small_sorted_vector_set<int32_t, 2> test;
1077 test.insert(10);
1078 EXPECT_EQ(test.size(), 1);
1079 test.insert(10);
1080 EXPECT_EQ(test.size(), 1);
1081 test.insert(20);
1082 EXPECT_EQ(test.size(), 2);
1083 test.insert(30);
1084 EXPECT_EQ(test.size(), 3);
1085}
1086
1087TEST(small_vector, NoHeapStorageForSortedVectorSet) {
1088 noheap_sorted_vector_set<int32_t, 2> test;
1089 test.insert(10);
1090 EXPECT_EQ(test.size(), 1);
1091 test.insert(10);
1092 EXPECT_EQ(test.size(), 1);
1093 test.insert(20);
1094 EXPECT_EQ(test.size(), 2);
1095 EXPECT_THROW(test.insert(30), std::length_error);
1096 EXPECT_EQ(test.size(), 2);
1097}
1098
1099TEST(small_vector, SelfMoveAssignmentForVectorOfPair) {
1100 folly::small_vector<std::pair<int, int>, 2> test;
1101 test.emplace_back(13, 2);
1102 EXPECT_EQ(test.size(), 1);
1103 EXPECT_EQ(test[0].first, 13);
1104 test = static_cast<decltype(test)&&>(test); // suppress self-move warning
1105 EXPECT_EQ(test.size(), 1);
1106 EXPECT_EQ(test[0].first, 13);
1107}
1108
1109TEST(small_vector, SelfCopyAssignmentForVectorOfPair) {
1110 folly::small_vector<std::pair<int, int>, 2> test;
1111 test.emplace_back(13, 2);
1112 EXPECT_EQ(test.size(), 1);
1113 EXPECT_EQ(test[0].first, 13);
1114 test = static_cast<decltype(test)&>(test); // suppress self-assign warning
1115 EXPECT_EQ(test.size(), 1);
1116 EXPECT_EQ(test[0].first, 13);
1117}
1118