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 | |
34 | using folly::small_vector; |
35 | using namespace folly::small_vector_policy; |
36 | |
37 | #if FOLLY_X64 || FOLLY_PPC64 |
38 | |
39 | static_assert( |
40 | sizeof(small_vector<int>) == 16, |
41 | "Object size is not what we expect for small_vector<int>" ); |
42 | static_assert( |
43 | sizeof(small_vector<int32_t, 2>) == 16, |
44 | "Object size is not what we expect for " |
45 | "small_vector<int32_t,2>" ); |
46 | static_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 | |
50 | static_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. |
55 | static_assert( |
56 | sizeof(small_vector<int32_t, 1, uint16_t>) == 8 + 2 + 2, |
57 | "small_vector<int32_t,1,uint16_t> is wrong size" ); |
58 | static_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. |
63 | static_assert( |
64 | sizeof(small_vector<int32_t, 1, uint8_t>) == 8 + 1 + 3, |
65 | "small_vector<int32_t,1,uint8_t> is wrong size" ); |
66 | static_assert( |
67 | alignof(small_vector<int32_t, 1, uint8_t>) >= 4, |
68 | "small_vector not aligned correctly" ); |
69 | |
70 | static_assert( |
71 | sizeof(small_vector<int16_t, 4, uint16_t>) == 10, |
72 | "Sizeof unexpectedly large" ); |
73 | |
74 | #endif |
75 | |
76 | static_assert( |
77 | !folly::is_trivially_copyable<std::unique_ptr<int>>::value, |
78 | "std::unique_ptr<> is trivially copyable" ); |
79 | |
80 | static_assert( |
81 | alignof(small_vector<std::aligned_storage<32, 32>::type, 4>) == 32, |
82 | "small_vector not aligned correctly" ); |
83 | |
84 | namespace { |
85 | |
86 | template <typename Key, typename Value, size_t N> |
87 | using 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 | |
95 | template <typename Key, typename Value, size_t N> |
96 | using 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 | |
107 | template <typename T, size_t N> |
108 | using 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 | |
115 | template <typename T, size_t N> |
116 | using 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 | |
123 | struct 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 | }; |
142 | static_assert( |
143 | !folly::is_trivially_copyable<NontrivialType>::value, |
144 | "NontrivialType is trivially copyable" ); |
145 | |
146 | int NontrivialType::ctored = 0; |
147 | |
148 | struct TestException {}; |
149 | |
150 | int throwCounter = 1; |
151 | void MaybeThrow() { |
152 | if (!--throwCounter) { |
153 | throw TestException(); |
154 | } |
155 | } |
156 | |
157 | const int kMagic = 0xdeadbeef; |
158 | struct 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 | |
188 | int Thrower::alive = 0; |
189 | |
190 | // Type that counts how many exist and doesn't support copy |
191 | // construction. |
192 | struct 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 | }; |
209 | int NoncopyableCounter::alive = 0; |
210 | |
211 | static_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. |
219 | struct 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 | |
265 | TEST(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 |
323 | TEST(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 | |
332 | TEST(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 | |
355 | TEST(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 | |
410 | TEST(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 | |
439 | TEST(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 | |
469 | TEST(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 | |
497 | TEST(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 | |
521 | TEST(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 | |
553 | TEST(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 | |
568 | TEST(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 | |
615 | TEST(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 | |
622 | TEST(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 | |
643 | TEST(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 | |
687 | TEST(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 | |
731 | TEST(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 | |
745 | TEST(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 | |
759 | TEST(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 | |
789 | struct 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 | |
811 | TEST(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 | |
820 | TEST(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 | |
829 | TEST(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 | |
839 | TEST(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 | |
849 | TEST(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 | |
858 | TEST(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 | |
868 | TEST(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 | |
876 | TEST(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 | |
897 | TEST(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 | |
913 | TEST(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 | |
921 | TEST(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 | |
929 | TEST(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 | |
942 | TEST(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 | |
955 | TEST(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 | |
968 | namespace { |
969 | struct Counts { |
970 | size_t copyCount{0}; |
971 | size_t moveCount{0}; |
972 | }; |
973 | |
974 | class 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 | |
998 | TEST(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 | |
1014 | TEST(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 | |
1032 | TEST(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 | |
1051 | TEST(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 | |
1063 | TEST(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 | |
1075 | TEST(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 | |
1087 | TEST(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 | |
1099 | TEST(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 | |
1109 | TEST(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 | |