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/*
18 * For high-level documentation and usage examples see
19 * folly/docs/small_vector.md
20 *
21 * @author Jordan DeLong <delong.j@fb.com>
22 */
23
24#pragma once
25
26#include <algorithm>
27#include <cassert>
28#include <cstdlib>
29#include <cstring>
30#include <iterator>
31#include <stdexcept>
32#include <type_traits>
33#include <utility>
34
35#include <boost/mpl/count.hpp>
36#include <boost/mpl/empty.hpp>
37#include <boost/mpl/eval_if.hpp>
38#include <boost/mpl/filter_view.hpp>
39#include <boost/mpl/front.hpp>
40#include <boost/mpl/identity.hpp>
41#include <boost/mpl/if.hpp>
42#include <boost/mpl/placeholders.hpp>
43#include <boost/mpl/size.hpp>
44#include <boost/mpl/vector.hpp>
45#include <boost/operators.hpp>
46
47#include <folly/ConstexprMath.h>
48#include <folly/FormatTraits.h>
49#include <folly/Likely.h>
50#include <folly/Portability.h>
51#include <folly/ScopeGuard.h>
52#include <folly/Traits.h>
53#include <folly/lang/Assume.h>
54#include <folly/lang/Exception.h>
55#include <folly/memory/Malloc.h>
56#include <folly/portability/Malloc.h>
57
58#if (FOLLY_X64 || FOLLY_PPC64)
59#define FOLLY_SV_PACK_ATTR FOLLY_PACK_ATTR
60#define FOLLY_SV_PACK_PUSH FOLLY_PACK_PUSH
61#define FOLLY_SV_PACK_POP FOLLY_PACK_POP
62#else
63#define FOLLY_SV_PACK_ATTR
64#define FOLLY_SV_PACK_PUSH
65#define FOLLY_SV_PACK_POP
66#endif
67
68// Ignore shadowing warnings within this file, so includers can use -Wshadow.
69FOLLY_PUSH_WARNING
70FOLLY_GNU_DISABLE_WARNING("-Wshadow")
71
72namespace folly {
73
74//////////////////////////////////////////////////////////////////////
75
76namespace small_vector_policy {
77
78//////////////////////////////////////////////////////////////////////
79
80/*
81 * A flag which makes us refuse to use the heap at all. If we
82 * overflow the in situ capacity we throw an exception.
83 */
84struct NoHeap;
85
86//////////////////////////////////////////////////////////////////////
87
88} // namespace small_vector_policy
89
90//////////////////////////////////////////////////////////////////////
91
92template <class T, std::size_t M, class A, class B, class C>
93class small_vector;
94
95//////////////////////////////////////////////////////////////////////
96
97namespace detail {
98
99/*
100 * Move objects in memory to the right into some uninitialized
101 * memory, where the region overlaps. This doesn't just use
102 * std::move_backward because move_backward only works if all the
103 * memory is initialized to type T already.
104 */
105template <class T>
106typename std::enable_if<
107 std::is_default_constructible<T>::value &&
108 !folly::is_trivially_copyable<T>::value>::type
109moveObjectsRight(T* first, T* lastConstructed, T* realLast) {
110 if (lastConstructed == realLast) {
111 return;
112 }
113
114 T* end = first - 1; // Past the end going backwards.
115 T* out = realLast - 1;
116 T* in = lastConstructed - 1;
117 {
118 auto rollback = makeGuard([&] {
119 // We want to make sure the same stuff is uninitialized memory
120 // if we exit via an exception (this is to make sure we provide
121 // the basic exception safety guarantee for insert functions).
122 if (out < lastConstructed) {
123 out = lastConstructed - 1;
124 }
125 for (auto it = out + 1; it != realLast; ++it) {
126 it->~T();
127 }
128 });
129 for (; in != end && out >= lastConstructed; --in, --out) {
130 new (out) T(std::move(*in));
131 }
132 for (; in != end; --in, --out) {
133 *out = std::move(*in);
134 }
135 for (; out >= lastConstructed; --out) {
136 new (out) T();
137 }
138 rollback.dismiss();
139 }
140}
141
142// Specialization for trivially copyable types. The call to
143// std::move_backward here will just turn into a memmove. (TODO:
144// change to std::is_trivially_copyable when that works.)
145template <class T>
146typename std::enable_if<
147 !std::is_default_constructible<T>::value ||
148 folly::is_trivially_copyable<T>::value>::type
149moveObjectsRight(T* first, T* lastConstructed, T* realLast) {
150 std::move_backward(first, lastConstructed, realLast);
151}
152
153/*
154 * Populate a region of memory using `op' to construct elements. If
155 * anything throws, undo what we did.
156 */
157template <class T, class Function>
158void populateMemForward(T* mem, std::size_t n, Function const& op) {
159 std::size_t idx = 0;
160 {
161 auto rollback = makeGuard([&] {
162 for (std::size_t i = 0; i < idx; ++i) {
163 mem[i].~T();
164 }
165 });
166 for (size_t i = 0; i < n; ++i) {
167 op(&mem[idx]);
168 ++idx;
169 }
170 rollback.dismiss();
171 }
172}
173
174template <class SizeType, bool ShouldUseHeap>
175struct IntegralSizePolicyBase {
176 typedef SizeType InternalSizeType;
177
178 IntegralSizePolicyBase() : size_(0) {}
179
180 protected:
181 static constexpr std::size_t policyMaxSize() {
182 return SizeType(~kExternMask);
183 }
184
185 std::size_t doSize() const {
186 return size_ & ~kExternMask;
187 }
188
189 std::size_t isExtern() const {
190 return kExternMask & size_;
191 }
192
193 void setExtern(bool b) {
194 if (b) {
195 size_ |= kExternMask;
196 } else {
197 size_ &= ~kExternMask;
198 }
199 }
200
201 void setSize(std::size_t sz) {
202 assert(sz <= policyMaxSize());
203 size_ = (kExternMask & size_) | SizeType(sz);
204 }
205
206 void swapSizePolicy(IntegralSizePolicyBase& o) {
207 std::swap(size_, o.size_);
208 }
209
210 protected:
211 static bool constexpr kShouldUseHeap = ShouldUseHeap;
212
213 private:
214 static SizeType constexpr kExternMask =
215 kShouldUseHeap ? SizeType(1) << (sizeof(SizeType) * 8 - 1) : 0;
216
217 SizeType size_;
218};
219
220template <class SizeType, bool ShouldUseHeap>
221struct IntegralSizePolicy;
222
223template <class SizeType>
224struct IntegralSizePolicy<SizeType, true>
225 : public IntegralSizePolicyBase<SizeType, true> {
226 public:
227 /*
228 * Move a range to a range of uninitialized memory. Assumes the
229 * ranges don't overlap.
230 */
231 template <class T>
232 typename std::enable_if<!folly::is_trivially_copyable<T>::value>::type
233 moveToUninitialized(T* first, T* last, T* out) {
234 std::size_t idx = 0;
235 {
236 auto rollback = makeGuard([&] {
237 // Even for callers trying to give the strong guarantee
238 // (e.g. push_back) it's ok to assume here that we don't have to
239 // move things back and that it was a copy constructor that
240 // threw: if someone throws from a move constructor the effects
241 // are unspecified.
242 for (std::size_t i = 0; i < idx; ++i) {
243 out[i].~T();
244 }
245 });
246 for (; first != last; ++first, ++idx) {
247 new (&out[idx]) T(std::move(*first));
248 }
249 rollback.dismiss();
250 }
251 }
252
253 // Specialization for trivially copyable types.
254 template <class T>
255 typename std::enable_if<folly::is_trivially_copyable<T>::value>::type
256 moveToUninitialized(T* first, T* last, T* out) {
257 std::memmove(
258 static_cast<void*>(out),
259 static_cast<void const*>(first),
260 (last - first) * sizeof *first);
261 }
262
263 /*
264 * Move a range to a range of uninitialized memory. Assumes the
265 * ranges don't overlap. Inserts an element at out + pos using
266 * emplaceFunc(). out will contain (end - begin) + 1 elements on success and
267 * none on failure. If emplaceFunc() throws [begin, end) is unmodified.
268 */
269 template <class T, class EmplaceFunc>
270 void moveToUninitializedEmplace(
271 T* begin,
272 T* end,
273 T* out,
274 SizeType pos,
275 EmplaceFunc&& emplaceFunc) {
276 // Must be called first so that if it throws [begin, end) is unmodified.
277 // We have to support the strong exception guarantee for emplace_back().
278 emplaceFunc(out + pos);
279 // move old elements to the left of the new one
280 {
281 auto rollback = makeGuard([&] { //
282 out[pos].~T();
283 });
284 this->moveToUninitialized(begin, begin + pos, out);
285 rollback.dismiss();
286 }
287 // move old elements to the right of the new one
288 {
289 auto rollback = makeGuard([&] {
290 for (SizeType i = 0; i <= pos; ++i) {
291 out[i].~T();
292 }
293 });
294 if (begin + pos < end) {
295 this->moveToUninitialized(begin + pos, end, out + pos + 1);
296 }
297 rollback.dismiss();
298 }
299 }
300};
301
302template <class SizeType>
303struct IntegralSizePolicy<SizeType, false>
304 : public IntegralSizePolicyBase<SizeType, false> {
305 public:
306 template <class T>
307 void moveToUninitialized(T* /*first*/, T* /*last*/, T* /*out*/) {
308 assume_unreachable();
309 }
310 template <class T, class EmplaceFunc>
311 void moveToUninitializedEmplace(
312 T* /* begin */,
313 T* /* end */,
314 T* /* out */,
315 SizeType /* pos */,
316 EmplaceFunc&& /* emplaceFunc */) {
317 assume_unreachable();
318 }
319};
320
321/*
322 * If you're just trying to use this class, ignore everything about
323 * this next small_vector_base class thing.
324 *
325 * The purpose of this junk is to minimize sizeof(small_vector<>)
326 * and allow specifying the template parameters in whatever order is
327 * convenient for the user. There's a few extra steps here to try
328 * to keep the error messages at least semi-reasonable.
329 *
330 * Apologies for all the black magic.
331 */
332namespace mpl = boost::mpl;
333template <
334 class Value,
335 std::size_t RequestedMaxInline,
336 class InPolicyA,
337 class InPolicyB,
338 class InPolicyC>
339struct small_vector_base {
340 typedef mpl::vector<InPolicyA, InPolicyB, InPolicyC> PolicyList;
341
342 /*
343 * Determine the size type
344 */
345 typedef typename mpl::filter_view<
346 PolicyList,
347 std::is_integral<mpl::placeholders::_1>>::type Integrals;
348 typedef typename mpl::eval_if<
349 mpl::empty<Integrals>,
350 mpl::identity<std::size_t>,
351 mpl::front<Integrals>>::type SizeType;
352
353 static_assert(
354 std::is_unsigned<SizeType>::value,
355 "Size type should be an unsigned integral type");
356 static_assert(
357 mpl::size<Integrals>::value == 0 || mpl::size<Integrals>::value == 1,
358 "Multiple size types specified in small_vector<>");
359
360 /*
361 * Determine whether we should allow spilling to the heap or not.
362 */
363 typedef typename mpl::count<PolicyList, small_vector_policy::NoHeap>::type
364 HasNoHeap;
365
366 static_assert(
367 HasNoHeap::value == 0 || HasNoHeap::value == 1,
368 "Multiple copies of small_vector_policy::NoHeap "
369 "supplied; this is probably a mistake");
370
371 /*
372 * Make the real policy base classes.
373 */
374 typedef IntegralSizePolicy<SizeType, !HasNoHeap::value> ActualSizePolicy;
375
376 /*
377 * Now inherit from them all. This is done in such a convoluted
378 * way to make sure we get the empty base optimizaton on all these
379 * types to keep sizeof(small_vector<>) minimal.
380 */
381 typedef boost::totally_ordered1<
382 small_vector<Value, RequestedMaxInline, InPolicyA, InPolicyB, InPolicyC>,
383 ActualSizePolicy>
384 type;
385};
386
387template <class T>
388T* pointerFlagSet(T* p) {
389 return reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(p) | 1);
390}
391template <class T>
392bool pointerFlagGet(T* p) {
393 return reinterpret_cast<uintptr_t>(p) & 1;
394}
395template <class T>
396T* pointerFlagClear(T* p) {
397 return reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(p) & ~uintptr_t(1));
398}
399inline void* shiftPointer(void* p, size_t sizeBytes) {
400 return static_cast<char*>(p) + sizeBytes;
401}
402} // namespace detail
403
404//////////////////////////////////////////////////////////////////////
405FOLLY_SV_PACK_PUSH
406template <
407 class Value,
408 std::size_t RequestedMaxInline = 1,
409 class PolicyA = void,
410 class PolicyB = void,
411 class PolicyC = void>
412class small_vector : public detail::small_vector_base<
413 Value,
414 RequestedMaxInline,
415 PolicyA,
416 PolicyB,
417 PolicyC>::type {
418 typedef typename detail::
419 small_vector_base<Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC>::
420 type BaseType;
421 typedef typename BaseType::InternalSizeType InternalSizeType;
422
423 /*
424 * Figure out the max number of elements we should inline. (If
425 * the user asks for less inlined elements than we can fit unioned
426 * into our value_type*, we will inline more than they asked.)
427 */
428 static constexpr std::size_t MaxInline{
429 constexpr_max(sizeof(Value*) / sizeof(Value), RequestedMaxInline)};
430
431 public:
432 typedef std::size_t size_type;
433 typedef Value value_type;
434 typedef value_type& reference;
435 typedef value_type const& const_reference;
436 typedef value_type* iterator;
437 typedef value_type* pointer;
438 typedef value_type const* const_iterator;
439 typedef value_type const* const_pointer;
440 typedef std::ptrdiff_t difference_type;
441
442 typedef std::reverse_iterator<iterator> reverse_iterator;
443 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
444
445 small_vector() = default;
446 // Allocator is unused here. It is taken in for compatibility with std::vector
447 // interface, but it will be ignored.
448 small_vector(const std::allocator<Value>&) {}
449
450 small_vector(small_vector const& o) {
451 auto n = o.size();
452 makeSize(n);
453 {
454 auto rollback = makeGuard([&] {
455 if (this->isExtern()) {
456 u.freeHeap();
457 }
458 });
459 std::uninitialized_copy(o.begin(), o.end(), begin());
460 rollback.dismiss();
461 }
462 this->setSize(n);
463 }
464
465 small_vector(small_vector&& o) noexcept(
466 std::is_nothrow_move_constructible<Value>::value) {
467 if (o.isExtern()) {
468 swap(o);
469 } else {
470 std::uninitialized_copy(
471 std::make_move_iterator(o.begin()),
472 std::make_move_iterator(o.end()),
473 begin());
474 this->setSize(o.size());
475 }
476 }
477
478 small_vector(std::initializer_list<value_type> il) {
479 constructImpl(il.begin(), il.end(), std::false_type());
480 }
481
482 explicit small_vector(size_type n) {
483 doConstruct(n, [&](void* p) { new (p) value_type(); });
484 }
485
486 small_vector(size_type n, value_type const& t) {
487 doConstruct(n, [&](void* p) { new (p) value_type(t); });
488 }
489
490 template <class Arg>
491 explicit small_vector(Arg arg1, Arg arg2) {
492 // Forward using std::is_arithmetic to get to the proper
493 // implementation; this disambiguates between the iterators and
494 // (size_t, value_type) meaning for this constructor.
495 constructImpl(arg1, arg2, std::is_arithmetic<Arg>());
496 }
497
498 ~small_vector() {
499 for (auto& t : *this) {
500 (&t)->~value_type();
501 }
502 if (this->isExtern()) {
503 u.freeHeap();
504 }
505 }
506
507 small_vector& operator=(small_vector const& o) {
508 if (FOLLY_LIKELY(this != &o)) {
509 assign(o.begin(), o.end());
510 }
511 return *this;
512 }
513
514 small_vector& operator=(small_vector&& o) {
515 // TODO: optimization:
516 // if both are internal, use move assignment where possible
517 if (FOLLY_LIKELY(this != &o)) {
518 clear();
519 swap(o);
520 }
521 return *this;
522 }
523
524 bool operator==(small_vector const& o) const {
525 return size() == o.size() && std::equal(begin(), end(), o.begin());
526 }
527
528 bool operator<(small_vector const& o) const {
529 return std::lexicographical_compare(begin(), end(), o.begin(), o.end());
530 }
531
532 static constexpr size_type max_size() {
533 return !BaseType::kShouldUseHeap ? static_cast<size_type>(MaxInline)
534 : BaseType::policyMaxSize();
535 }
536
537 size_type size() const {
538 return this->doSize();
539 }
540 bool empty() const {
541 return !size();
542 }
543
544 iterator begin() {
545 return data();
546 }
547 iterator end() {
548 return data() + size();
549 }
550 const_iterator begin() const {
551 return data();
552 }
553 const_iterator end() const {
554 return data() + size();
555 }
556 const_iterator cbegin() const {
557 return begin();
558 }
559 const_iterator cend() const {
560 return end();
561 }
562
563 reverse_iterator rbegin() {
564 return reverse_iterator(end());
565 }
566 reverse_iterator rend() {
567 return reverse_iterator(begin());
568 }
569
570 const_reverse_iterator rbegin() const {
571 return const_reverse_iterator(end());
572 }
573
574 const_reverse_iterator rend() const {
575 return const_reverse_iterator(begin());
576 }
577
578 const_reverse_iterator crbegin() const {
579 return rbegin();
580 }
581 const_reverse_iterator crend() const {
582 return rend();
583 }
584
585 /*
586 * Usually one of the simplest functions in a Container-like class
587 * but a bit more complex here. We have to handle all combinations
588 * of in-place vs. heap between this and o.
589 *
590 * Basic guarantee only. Provides the nothrow guarantee iff our
591 * value_type has a nothrow move or copy constructor.
592 */
593 void swap(small_vector& o) {
594 using std::swap; // Allow ADL on swap for our value_type.
595
596 if (this->isExtern() && o.isExtern()) {
597 this->swapSizePolicy(o);
598
599 auto thisCapacity = this->capacity();
600 auto oCapacity = o.capacity();
601
602 auto* tmp = u.pdata_.heap_;
603 u.pdata_.heap_ = o.u.pdata_.heap_;
604 o.u.pdata_.heap_ = tmp;
605
606 this->setCapacity(oCapacity);
607 o.setCapacity(thisCapacity);
608
609 return;
610 }
611
612 if (!this->isExtern() && !o.isExtern()) {
613 auto& oldSmall = size() < o.size() ? *this : o;
614 auto& oldLarge = size() < o.size() ? o : *this;
615
616 for (size_type i = 0; i < oldSmall.size(); ++i) {
617 swap(oldSmall[i], oldLarge[i]);
618 }
619
620 size_type i = oldSmall.size();
621 const size_type ci = i;
622 {
623 auto rollback = makeGuard([&] {
624 oldSmall.setSize(i);
625 for (; i < oldLarge.size(); ++i) {
626 oldLarge[i].~value_type();
627 }
628 oldLarge.setSize(ci);
629 });
630 for (; i < oldLarge.size(); ++i) {
631 auto addr = oldSmall.begin() + i;
632 new (addr) value_type(std::move(oldLarge[i]));
633 oldLarge[i].~value_type();
634 }
635 rollback.dismiss();
636 }
637 oldSmall.setSize(i);
638 oldLarge.setSize(ci);
639 return;
640 }
641
642 // isExtern != o.isExtern()
643 auto& oldExtern = o.isExtern() ? o : *this;
644 auto& oldIntern = o.isExtern() ? *this : o;
645
646 auto oldExternCapacity = oldExtern.capacity();
647 auto oldExternHeap = oldExtern.u.pdata_.heap_;
648
649 auto buff = oldExtern.u.buffer();
650 size_type i = 0;
651 {
652 auto rollback = makeGuard([&] {
653 for (size_type kill = 0; kill < i; ++kill) {
654 buff[kill].~value_type();
655 }
656 for (; i < oldIntern.size(); ++i) {
657 oldIntern[i].~value_type();
658 }
659 oldIntern.setSize(0);
660 oldExtern.u.pdata_.heap_ = oldExternHeap;
661 oldExtern.setCapacity(oldExternCapacity);
662 });
663 for (; i < oldIntern.size(); ++i) {
664 new (&buff[i]) value_type(std::move(oldIntern[i]));
665 oldIntern[i].~value_type();
666 }
667 rollback.dismiss();
668 }
669 oldIntern.u.pdata_.heap_ = oldExternHeap;
670 this->swapSizePolicy(o);
671 oldIntern.setCapacity(oldExternCapacity);
672 }
673
674 void resize(size_type sz) {
675 if (sz < size()) {
676 erase(begin() + sz, end());
677 return;
678 }
679 makeSize(sz);
680 detail::populateMemForward(
681 begin() + size(), sz - size(), [&](void* p) { new (p) value_type(); });
682 this->setSize(sz);
683 }
684
685 void resize(size_type sz, value_type const& v) {
686 if (sz < size()) {
687 erase(begin() + sz, end());
688 return;
689 }
690 makeSize(sz);
691 detail::populateMemForward(
692 begin() + size(), sz - size(), [&](void* p) { new (p) value_type(v); });
693 this->setSize(sz);
694 }
695
696 value_type* data() noexcept {
697 return this->isExtern() ? u.heap() : u.buffer();
698 }
699
700 value_type const* data() const noexcept {
701 return this->isExtern() ? u.heap() : u.buffer();
702 }
703
704 template <class... Args>
705 iterator emplace(const_iterator p, Args&&... args) {
706 if (p == cend()) {
707 emplace_back(std::forward<Args>(args)...);
708 return end() - 1;
709 }
710
711 /*
712 * We implement emplace at places other than at the back with a
713 * temporary for exception safety reasons. It is possible to
714 * avoid having to do this, but it becomes hard to maintain the
715 * basic exception safety guarantee (unless you respond to a copy
716 * constructor throwing by clearing the whole vector).
717 *
718 * The reason for this is that otherwise you have to destruct an
719 * element before constructing this one in its place---if the
720 * constructor throws, you either need a nothrow default
721 * constructor or a nothrow copy/move to get something back in the
722 * "gap", and the vector requirements don't guarantee we have any
723 * of these. Clearing the whole vector is a legal response in
724 * this situation, but it seems like this implementation is easy
725 * enough and probably better.
726 */
727 return insert(p, value_type(std::forward<Args>(args)...));
728 }
729
730 void reserve(size_type sz) {
731 makeSize(sz);
732 }
733
734 size_type capacity() const {
735 if (this->isExtern()) {
736 if (u.hasCapacity()) {
737 return u.getCapacity();
738 }
739 return malloc_usable_size(u.pdata_.heap_) / sizeof(value_type);
740 }
741 return MaxInline;
742 }
743
744 void shrink_to_fit() {
745 if (!this->isExtern()) {
746 return;
747 }
748
749 small_vector tmp(begin(), end());
750 tmp.swap(*this);
751 }
752
753 template <class... Args>
754 void emplace_back(Args&&... args) {
755 if (capacity() == size()) {
756 // Any of args may be references into the vector.
757 // When we are reallocating, we have to be careful to construct the new
758 // element before modifying the data in the old buffer.
759 makeSize(
760 size() + 1,
761 [&](void* p) { new (p) value_type(std::forward<Args>(args)...); },
762 size());
763 } else {
764 new (end()) value_type(std::forward<Args>(args)...);
765 }
766 this->setSize(size() + 1);
767 }
768
769 void push_back(value_type&& t) {
770 return emplace_back(std::move(t));
771 }
772
773 void push_back(value_type const& t) {
774 emplace_back(t);
775 }
776
777 void pop_back() {
778 erase(end() - 1);
779 }
780
781 iterator insert(const_iterator constp, value_type&& t) {
782 iterator p = unconst(constp);
783
784 if (p == end()) {
785 push_back(std::move(t));
786 return end() - 1;
787 }
788
789 auto offset = p - begin();
790
791 if (capacity() == size()) {
792 makeSize(
793 size() + 1,
794 [&t](void* ptr) { new (ptr) value_type(std::move(t)); },
795 offset);
796 this->setSize(this->size() + 1);
797 } else {
798 detail::moveObjectsRight(
799 data() + offset, data() + size(), data() + size() + 1);
800 this->setSize(size() + 1);
801 data()[offset] = std::move(t);
802 }
803 return begin() + offset;
804 }
805
806 iterator insert(const_iterator p, value_type const& t) {
807 // Make a copy and forward to the rvalue value_type&& overload
808 // above.
809 return insert(p, value_type(t));
810 }
811
812 iterator insert(const_iterator pos, size_type n, value_type const& val) {
813 auto offset = pos - begin();
814 makeSize(size() + n);
815 detail::moveObjectsRight(
816 data() + offset, data() + size(), data() + size() + n);
817 this->setSize(size() + n);
818 std::generate_n(begin() + offset, n, [&] { return val; });
819 return begin() + offset;
820 }
821
822 template <class Arg>
823 iterator insert(const_iterator p, Arg arg1, Arg arg2) {
824 // Forward using std::is_arithmetic to get to the proper
825 // implementation; this disambiguates between the iterators and
826 // (size_t, value_type) meaning for this function.
827 return insertImpl(unconst(p), arg1, arg2, std::is_arithmetic<Arg>());
828 }
829
830 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
831 return insert(p, il.begin(), il.end());
832 }
833
834 iterator erase(const_iterator q) {
835 std::move(unconst(q) + 1, end(), unconst(q));
836 (data() + size() - 1)->~value_type();
837 this->setSize(size() - 1);
838 return unconst(q);
839 }
840
841 iterator erase(const_iterator q1, const_iterator q2) {
842 if (q1 == q2) {
843 return unconst(q1);
844 }
845 std::move(unconst(q2), end(), unconst(q1));
846 for (auto it = (end() - std::distance(q1, q2)); it != end(); ++it) {
847 it->~value_type();
848 }
849 this->setSize(size() - (q2 - q1));
850 return unconst(q1);
851 }
852
853 void clear() {
854 erase(begin(), end());
855 }
856
857 template <class Arg>
858 void assign(Arg first, Arg last) {
859 clear();
860 insert(end(), first, last);
861 }
862
863 void assign(std::initializer_list<value_type> il) {
864 assign(il.begin(), il.end());
865 }
866
867 void assign(size_type n, const value_type& t) {
868 clear();
869 insert(end(), n, t);
870 }
871
872 reference front() {
873 assert(!empty());
874 return *begin();
875 }
876 reference back() {
877 assert(!empty());
878 return *(end() - 1);
879 }
880 const_reference front() const {
881 assert(!empty());
882 return *begin();
883 }
884 const_reference back() const {
885 assert(!empty());
886 return *(end() - 1);
887 }
888
889 reference operator[](size_type i) {
890 assert(i < size());
891 return *(begin() + i);
892 }
893
894 const_reference operator[](size_type i) const {
895 assert(i < size());
896 return *(begin() + i);
897 }
898
899 reference at(size_type i) {
900 if (i >= size()) {
901 throw_exception<std::out_of_range>("index out of range");
902 }
903 return (*this)[i];
904 }
905
906 const_reference at(size_type i) const {
907 if (i >= size()) {
908 throw_exception<std::out_of_range>("index out of range");
909 }
910 return (*this)[i];
911 }
912
913 private:
914 static iterator unconst(const_iterator it) {
915 return const_cast<iterator>(it);
916 }
917
918 // The std::false_type argument is part of disambiguating the
919 // iterator insert functions from integral types (see insert().)
920 template <class It>
921 iterator insertImpl(iterator pos, It first, It last, std::false_type) {
922 typedef typename std::iterator_traits<It>::iterator_category categ;
923 if (std::is_same<categ, std::input_iterator_tag>::value) {
924 auto offset = pos - begin();
925 while (first != last) {
926 pos = insert(pos, *first++);
927 ++pos;
928 }
929 return begin() + offset;
930 }
931
932 auto distance = std::distance(first, last);
933 auto offset = pos - begin();
934 makeSize(size() + distance);
935 detail::moveObjectsRight(
936 data() + offset, data() + size(), data() + size() + distance);
937 this->setSize(size() + distance);
938 std::copy_n(first, distance, begin() + offset);
939 return begin() + offset;
940 }
941
942 iterator
943 insertImpl(iterator pos, size_type n, const value_type& val, std::true_type) {
944 // The true_type means this should call the size_t,value_type
945 // overload. (See insert().)
946 return insert(pos, n, val);
947 }
948
949 // The std::false_type argument came from std::is_arithmetic as part
950 // of disambiguating an overload (see the comment in the
951 // constructor).
952 template <class It>
953 void constructImpl(It first, It last, std::false_type) {
954 typedef typename std::iterator_traits<It>::iterator_category categ;
955 if (std::is_same<categ, std::input_iterator_tag>::value) {
956 // With iterators that only allow a single pass, we can't really
957 // do anything sane here.
958 while (first != last) {
959 emplace_back(*first++);
960 }
961 return;
962 }
963
964 auto distance = std::distance(first, last);
965 makeSize(distance);
966 this->setSize(distance);
967 {
968 auto rollback = makeGuard([&] {
969 if (this->isExtern()) {
970 u.freeHeap();
971 }
972 });
973 detail::populateMemForward(
974 data(), distance, [&](void* p) { new (p) value_type(*first++); });
975 rollback.dismiss();
976 }
977 }
978
979 template <typename InitFunc>
980 void doConstruct(size_type n, InitFunc&& func) {
981 makeSize(n);
982 this->setSize(n);
983 {
984 auto rollback = makeGuard([&] {
985 if (this->isExtern()) {
986 u.freeHeap();
987 }
988 });
989 detail::populateMemForward(data(), n, std::forward<InitFunc>(func));
990 rollback.dismiss();
991 }
992 }
993
994 // The true_type means we should forward to the size_t,value_type
995 // overload.
996 void constructImpl(size_type n, value_type const& val, std::true_type) {
997 doConstruct(n, [&](void* p) { new (p) value_type(val); });
998 }
999
1000 /*
1001 * Compute the size after growth.
1002 */
1003 size_type computeNewSize() const {
1004 return std::min((3 * capacity()) / 2 + 1, max_size());
1005 }
1006
1007 void makeSize(size_type newSize) {
1008 makeSizeInternal(newSize, false, [](void*) { assume_unreachable(); }, 0);
1009 }
1010
1011 template <typename EmplaceFunc>
1012 void makeSize(size_type newSize, EmplaceFunc&& emplaceFunc, size_type pos) {
1013 assert(size() == capacity());
1014 makeSizeInternal(
1015 newSize, true, std::forward<EmplaceFunc>(emplaceFunc), pos);
1016 }
1017
1018 /*
1019 * Ensure we have a large enough memory region to be size `newSize'.
1020 * Will move/copy elements if we are spilling to heap_ or needed to
1021 * allocate a new region, but if resized in place doesn't initialize
1022 * anything in the new region. In any case doesn't change size().
1023 * Supports insertion of new element during reallocation by given
1024 * pointer to new element and position of new element.
1025 * NOTE: If reallocation is not needed, insert must be false,
1026 * because we only know how to emplace elements into new memory.
1027 */
1028 template <typename EmplaceFunc>
1029 void makeSizeInternal(
1030 size_type newSize,
1031 bool insert,
1032 EmplaceFunc&& emplaceFunc,
1033 size_type pos) {
1034 if (newSize > max_size()) {
1035 throw_exception<std::length_error>("max_size exceeded in small_vector");
1036 }
1037 if (newSize <= capacity()) {
1038 assert(!insert);
1039 return;
1040 }
1041
1042 assert(this->kShouldUseHeap);
1043 // This branch isn't needed for correctness, but allows the optimizer to
1044 // skip generating code for the rest of this function in NoHeap
1045 // small_vectors.
1046 if (!this->kShouldUseHeap) {
1047 return;
1048 }
1049
1050 newSize = std::max(newSize, computeNewSize());
1051
1052 auto needBytes = newSize * sizeof(value_type);
1053 // If the capacity isn't explicitly stored inline, but the heap
1054 // allocation is grown to over some threshold, we should store
1055 // a capacity at the front of the heap allocation.
1056 bool heapifyCapacity =
1057 !kHasInlineCapacity && needBytes > kHeapifyCapacityThreshold;
1058 if (heapifyCapacity) {
1059 needBytes += kHeapifyCapacitySize;
1060 }
1061 auto const sizeBytes = goodMallocSize(needBytes);
1062 void* newh = checkedMalloc(sizeBytes);
1063 // We expect newh to be at least 2-aligned, because we want to
1064 // use its least significant bit as a flag.
1065 assert(!detail::pointerFlagGet(newh));
1066
1067 value_type* newp = static_cast<value_type*>(
1068 heapifyCapacity ? detail::shiftPointer(newh, kHeapifyCapacitySize)
1069 : newh);
1070
1071 {
1072 auto rollback = makeGuard([&] { //
1073 free(newh);
1074 });
1075 if (insert) {
1076 // move and insert the new element
1077 this->moveToUninitializedEmplace(
1078 begin(), end(), newp, pos, std::forward<EmplaceFunc>(emplaceFunc));
1079 } else {
1080 // move without inserting new element
1081 this->moveToUninitialized(begin(), end(), newp);
1082 }
1083 rollback.dismiss();
1084 }
1085 for (auto& val : *this) {
1086 val.~value_type();
1087 }
1088
1089 if (this->isExtern()) {
1090 u.freeHeap();
1091 }
1092 auto availableSizeBytes = sizeBytes;
1093 if (heapifyCapacity) {
1094 u.pdata_.heap_ = detail::pointerFlagSet(newh);
1095 availableSizeBytes -= kHeapifyCapacitySize;
1096 } else {
1097 u.pdata_.heap_ = newh;
1098 }
1099 this->setExtern(true);
1100 this->setCapacity(availableSizeBytes / sizeof(value_type));
1101 }
1102
1103 /*
1104 * This will set the capacity field, stored inline in the storage_ field
1105 * if there is sufficient room to store it.
1106 */
1107 void setCapacity(size_type newCapacity) {
1108 assert(this->isExtern());
1109 if (u.hasCapacity()) {
1110 assert(newCapacity < std::numeric_limits<InternalSizeType>::max());
1111 u.setCapacity(newCapacity);
1112 }
1113 }
1114
1115 private:
1116 struct HeapPtrWithCapacity {
1117 void* heap_;
1118 InternalSizeType capacity_;
1119
1120 InternalSizeType getCapacity() const {
1121 return capacity_;
1122 }
1123 void setCapacity(InternalSizeType c) {
1124 capacity_ = c;
1125 }
1126 } FOLLY_SV_PACK_ATTR;
1127
1128 struct HeapPtr {
1129 // Lower order bit of heap_ is used as flag to indicate whether capacity is
1130 // stored at the front of the heap allocation.
1131 void* heap_;
1132
1133 InternalSizeType getCapacity() const {
1134 assert(detail::pointerFlagGet(heap_));
1135 return *static_cast<InternalSizeType*>(detail::pointerFlagClear(heap_));
1136 }
1137 void setCapacity(InternalSizeType c) {
1138 *static_cast<InternalSizeType*>(detail::pointerFlagClear(heap_)) = c;
1139 }
1140 } FOLLY_SV_PACK_ATTR;
1141
1142 typedef aligned_storage_for_t<value_type[MaxInline]> InlineStorageDataType;
1143
1144 typedef typename std::conditional<
1145 sizeof(value_type) * MaxInline != 0,
1146 InlineStorageDataType,
1147 void*>::type InlineStorageType;
1148
1149 static bool constexpr kHasInlineCapacity =
1150 sizeof(HeapPtrWithCapacity) < sizeof(InlineStorageType);
1151
1152 // This value should we multiple of word size.
1153 static size_t constexpr kHeapifyCapacitySize = sizeof(
1154 typename std::
1155 aligned_storage<sizeof(InternalSizeType), alignof(value_type)>::type);
1156
1157 // Threshold to control capacity heapifying.
1158 static size_t constexpr kHeapifyCapacityThreshold =
1159 100 * kHeapifyCapacitySize;
1160
1161 typedef typename std::
1162 conditional<kHasInlineCapacity, HeapPtrWithCapacity, HeapPtr>::type
1163 PointerType;
1164
1165 union Data {
1166 explicit Data() {
1167 pdata_.heap_ = nullptr;
1168 }
1169
1170 PointerType pdata_;
1171 InlineStorageType storage_;
1172
1173 value_type* buffer() noexcept {
1174 void* vp = &storage_;
1175 return static_cast<value_type*>(vp);
1176 }
1177 value_type const* buffer() const noexcept {
1178 return const_cast<Data*>(this)->buffer();
1179 }
1180 value_type* heap() noexcept {
1181 if (kHasInlineCapacity || !detail::pointerFlagGet(pdata_.heap_)) {
1182 return static_cast<value_type*>(pdata_.heap_);
1183 } else {
1184 return static_cast<value_type*>(detail::shiftPointer(
1185 detail::pointerFlagClear(pdata_.heap_), kHeapifyCapacitySize));
1186 }
1187 }
1188 value_type const* heap() const noexcept {
1189 return const_cast<Data*>(this)->heap();
1190 }
1191
1192 bool hasCapacity() const {
1193 return kHasInlineCapacity || detail::pointerFlagGet(pdata_.heap_);
1194 }
1195 InternalSizeType getCapacity() const {
1196 return pdata_.getCapacity();
1197 }
1198 void setCapacity(InternalSizeType c) {
1199 pdata_.setCapacity(c);
1200 }
1201
1202 void freeHeap() {
1203 auto vp = detail::pointerFlagClear(pdata_.heap_);
1204 free(vp);
1205 }
1206 } u;
1207};
1208FOLLY_SV_PACK_POP
1209
1210//////////////////////////////////////////////////////////////////////
1211
1212// Basic guarantee only, or provides the nothrow guarantee iff T has a
1213// nothrow move or copy constructor.
1214template <class T, std::size_t MaxInline, class A, class B, class C>
1215void swap(
1216 small_vector<T, MaxInline, A, B, C>& a,
1217 small_vector<T, MaxInline, A, B, C>& b) {
1218 a.swap(b);
1219}
1220
1221//////////////////////////////////////////////////////////////////////
1222
1223namespace detail {
1224
1225// Format support.
1226template <class T, size_t M, class A, class B, class C>
1227struct IndexableTraits<small_vector<T, M, A, B, C>>
1228 : public IndexableTraitsSeq<small_vector<T, M, A, B, C>> {};
1229
1230} // namespace detail
1231
1232} // namespace folly
1233
1234FOLLY_POP_WARNING
1235
1236#undef FOLLY_SV_PACK_ATTR
1237#undef FOLLY_SV_PACK_PUSH
1238#undef FOLLY_SV_PACK_POP
1239