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