2 * Copyright 2017 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
18 * For high-level documentation and usage examples see
19 * folly/docs/small_vector.md
21 * @author Jordan DeLong <delong.j@fb.com>
32 #include <type_traits>
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 #include <boost/type_traits.hpp>
48 #include <folly/ConstexprMath.h>
49 #include <folly/FormatTraits.h>
50 #include <folly/Portability.h>
51 #include <folly/SmallLocks.h>
52 #include <folly/Traits.h>
53 #include <folly/lang/Assume.h>
54 #include <folly/memory/Malloc.h>
55 #include <folly/portability/BitsFunctexcept.h>
56 #include <folly/portability/Malloc.h>
57 #include <folly/portability/TypeTraits.h>
59 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
61 FOLLY_GCC_DISABLE_WARNING("-Wshadow")
65 //////////////////////////////////////////////////////////////////////
67 namespace small_vector_policy {
69 //////////////////////////////////////////////////////////////////////
72 * A flag which makes us refuse to use the heap at all. If we
73 * overflow the in situ capacity we throw an exception.
77 //////////////////////////////////////////////////////////////////////
79 } // namespace small_vector_policy
81 //////////////////////////////////////////////////////////////////////
83 template <class T, std::size_t M, class A, class B, class C>
86 //////////////////////////////////////////////////////////////////////
91 * Move objects in memory to the right into some uninitialized
92 * memory, where the region overlaps. This doesn't just use
93 * std::move_backward because move_backward only works if all the
94 * memory is initialized to type T already.
97 typename std::enable_if<!FOLLY_IS_TRIVIALLY_COPYABLE(T)>::type
98 moveObjectsRight(T* first, T* lastConstructed, T* realLast) {
99 if (lastConstructed == realLast) {
103 T* end = first - 1; // Past the end going backwards.
104 T* out = realLast - 1;
105 T* in = lastConstructed - 1;
107 for (; in != end && out >= lastConstructed; --in, --out) {
108 new (out) T(std::move(*in));
110 for (; in != end; --in, --out) {
111 *out = std::move(*in);
113 for (; out >= lastConstructed; --out) {
117 // We want to make sure the same stuff is uninitialized memory
118 // if we exit via an exception (this is to make sure we provide
119 // the basic exception safety guarantee for insert functions).
120 if (out < lastConstructed) {
121 out = lastConstructed - 1;
123 for (auto it = out + 1; it != realLast; ++it) {
130 // Specialization for trivially copyable types. The call to
131 // std::move_backward here will just turn into a memmove. (TODO:
132 // change to std::is_trivially_copyable when that works.)
134 typename std::enable_if<FOLLY_IS_TRIVIALLY_COPYABLE(T)>::type
135 moveObjectsRight(T* first, T* lastConstructed, T* realLast) {
136 std::move_backward(first, lastConstructed, realLast);
140 * Populate a region of memory using `op' to construct elements. If
141 * anything throws, undo what we did.
143 template <class T, class Function>
144 void populateMemForward(T* mem, std::size_t n, Function const& op) {
147 for (size_t i = 0; i < n; ++i) {
152 for (std::size_t i = 0; i < idx; ++i) {
159 template <class SizeType, bool ShouldUseHeap>
160 struct IntegralSizePolicyBase {
161 typedef SizeType InternalSizeType;
163 IntegralSizePolicyBase() : size_(0) {}
166 static constexpr std::size_t policyMaxSize() {
167 return SizeType(~kExternMask);
170 std::size_t doSize() const {
171 return size_ & ~kExternMask;
174 std::size_t isExtern() const {
175 return kExternMask & size_;
178 void setExtern(bool b) {
180 size_ |= kExternMask;
182 size_ &= ~kExternMask;
186 void setSize(std::size_t sz) {
187 assert(sz <= policyMaxSize());
188 size_ = (kExternMask & size_) | SizeType(sz);
191 void swapSizePolicy(IntegralSizePolicyBase& o) {
192 std::swap(size_, o.size_);
196 static bool constexpr kShouldUseHeap = ShouldUseHeap;
199 static SizeType constexpr kExternMask =
200 kShouldUseHeap ? SizeType(1) << (sizeof(SizeType) * 8 - 1) : 0;
205 template <class SizeType, bool ShouldUseHeap>
206 struct IntegralSizePolicy;
208 template <class SizeType>
209 struct IntegralSizePolicy<SizeType, true>
210 : public IntegralSizePolicyBase<SizeType, true> {
213 * Move a range to a range of uninitialized memory. Assumes the
214 * ranges don't overlap.
217 typename std::enable_if<!FOLLY_IS_TRIVIALLY_COPYABLE(T)>::type
218 moveToUninitialized(T* first, T* last, T* out) {
221 for (; first != last; ++first, ++idx) {
222 new (&out[idx]) T(std::move(*first));
225 // Even for callers trying to give the strong guarantee
226 // (e.g. push_back) it's ok to assume here that we don't have to
227 // move things back and that it was a copy constructor that
228 // threw: if someone throws from a move constructor the effects
230 for (std::size_t i = 0; i < idx; ++i) {
237 // Specialization for trivially copyable types.
239 typename std::enable_if<FOLLY_IS_TRIVIALLY_COPYABLE(T)>::type
240 moveToUninitialized(T* first, T* last, T* out) {
241 std::memmove(out, first, (last - first) * sizeof *first);
245 * Move a range to a range of uninitialized memory. Assumes the
246 * ranges don't overlap. Inserts an element at out + pos using
247 * emplaceFunc(). out will contain (end - begin) + 1 elements on success and
248 * none on failure. If emplaceFunc() throws [begin, end) is unmodified.
250 template <class T, class EmplaceFunc>
251 void moveToUninitializedEmplace(
256 EmplaceFunc&& emplaceFunc) {
257 // Must be called first so that if it throws [begin, end) is unmodified.
258 // We have to support the strong exception guarantee for emplace_back().
259 emplaceFunc(out + pos);
260 // move old elements to the left of the new one
262 this->moveToUninitialized(begin, begin + pos, out);
267 // move old elements to the right of the new one
269 if (begin + pos < end) {
270 this->moveToUninitialized(begin + pos, end, out + pos + 1);
273 for (SizeType i = 0; i <= pos; ++i) {
281 template <class SizeType>
282 struct IntegralSizePolicy<SizeType, false>
283 : public IntegralSizePolicyBase<SizeType, false> {
286 void moveToUninitialized(T* /*first*/, T* /*last*/, T* /*out*/) {
287 assume_unreachable();
289 template <class T, class EmplaceFunc>
290 void moveToUninitializedEmplace(
295 EmplaceFunc&& /* emplaceFunc */) {
296 assume_unreachable();
301 * If you're just trying to use this class, ignore everything about
302 * this next small_vector_base class thing.
304 * The purpose of this junk is to minimize sizeof(small_vector<>)
305 * and allow specifying the template parameters in whatever order is
306 * convenient for the user. There's a few extra steps here to try
307 * to keep the error messages at least semi-reasonable.
309 * Apologies for all the black magic.
311 namespace mpl = boost::mpl;
314 std::size_t RequestedMaxInline,
318 struct small_vector_base {
319 typedef mpl::vector<InPolicyA, InPolicyB, InPolicyC> PolicyList;
322 * Determine the size type
324 typedef typename mpl::filter_view<
326 boost::is_integral<mpl::placeholders::_1>>::type Integrals;
327 typedef typename mpl::eval_if<
328 mpl::empty<Integrals>,
329 mpl::identity<std::size_t>,
330 mpl::front<Integrals>>::type SizeType;
333 std::is_unsigned<SizeType>::value,
334 "Size type should be an unsigned integral type");
336 mpl::size<Integrals>::value == 0 || mpl::size<Integrals>::value == 1,
337 "Multiple size types specified in small_vector<>");
340 * Determine whether we should allow spilling to the heap or not.
342 typedef typename mpl::count<PolicyList, small_vector_policy::NoHeap>::type
346 HasNoHeap::value == 0 || HasNoHeap::value == 1,
347 "Multiple copies of small_vector_policy::NoHeap "
348 "supplied; this is probably a mistake");
351 * Make the real policy base classes.
353 typedef IntegralSizePolicy<SizeType, !HasNoHeap::value> ActualSizePolicy;
356 * Now inherit from them all. This is done in such a convoluted
357 * way to make sure we get the empty base optimizaton on all these
358 * types to keep sizeof(small_vector<>) minimal.
360 typedef boost::totally_ordered1<
361 small_vector<Value, RequestedMaxInline, InPolicyA, InPolicyB, InPolicyC>,
367 T* pointerFlagSet(T* p) {
368 return reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(p) | 1);
371 bool pointerFlagGet(T* p) {
372 return reinterpret_cast<uintptr_t>(p) & 1;
375 T* pointerFlagClear(T* p) {
376 return reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(p) & ~uintptr_t(1));
378 inline void* shiftPointer(void* p, size_t sizeBytes) {
379 return static_cast<char*>(p) + sizeBytes;
381 } // namespace detail
383 //////////////////////////////////////////////////////////////////////
387 std::size_t RequestedMaxInline = 1,
388 class PolicyA = void,
389 class PolicyB = void,
390 class PolicyC = void>
391 class small_vector : public detail::small_vector_base<
397 typedef typename detail::
398 small_vector_base<Value, RequestedMaxInline, PolicyA, PolicyB, PolicyC>::
400 typedef typename BaseType::InternalSizeType InternalSizeType;
403 * Figure out the max number of elements we should inline. (If
404 * the user asks for less inlined elements than we can fit unioned
405 * into our value_type*, we will inline more than they asked.)
407 static constexpr std::size_t MaxInline{
408 constexpr_max(sizeof(Value*) / sizeof(Value), RequestedMaxInline)};
411 typedef std::size_t size_type;
412 typedef Value value_type;
413 typedef value_type& reference;
414 typedef value_type const& const_reference;
415 typedef value_type* iterator;
416 typedef value_type* pointer;
417 typedef value_type const* const_iterator;
418 typedef std::ptrdiff_t difference_type;
420 typedef std::reverse_iterator<iterator> reverse_iterator;
421 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
423 small_vector() = default;
424 // Allocator is unused here. It is taken in for compatibility with std::vector
425 // interface, but it will be ignored.
426 small_vector(const std::allocator<Value>&) {}
428 small_vector(small_vector const& o) {
432 std::uninitialized_copy(o.begin(), o.end(), begin());
434 if (this->isExtern()) {
442 small_vector(small_vector&& o) noexcept(
443 std::is_nothrow_move_constructible<Value>::value) {
447 std::uninitialized_copy(
448 std::make_move_iterator(o.begin()),
449 std::make_move_iterator(o.end()),
451 this->setSize(o.size());
455 small_vector(std::initializer_list<value_type> il) {
456 constructImpl(il.begin(), il.end(), std::false_type());
459 explicit small_vector(size_type n) {
460 doConstruct(n, [&](void* p) { new (p) value_type(); });
463 small_vector(size_type n, value_type const& t) {
464 doConstruct(n, [&](void* p) { new (p) value_type(t); });
468 explicit small_vector(Arg arg1, Arg arg2) {
469 // Forward using std::is_arithmetic to get to the proper
470 // implementation; this disambiguates between the iterators and
471 // (size_t, value_type) meaning for this constructor.
472 constructImpl(arg1, arg2, std::is_arithmetic<Arg>());
476 for (auto& t : *this) {
479 if (this->isExtern()) {
484 small_vector& operator=(small_vector const& o) {
485 assign(o.begin(), o.end());
489 small_vector& operator=(small_vector&& o) {
490 // TODO: optimization:
491 // if both are internal, use move assignment where possible
500 bool operator==(small_vector const& o) const {
501 return size() == o.size() && std::equal(begin(), end(), o.begin());
504 bool operator<(small_vector const& o) const {
505 return std::lexicographical_compare(begin(), end(), o.begin(), o.end());
508 static constexpr size_type max_size() {
509 return !BaseType::kShouldUseHeap ? static_cast<size_type>(MaxInline)
510 : BaseType::policyMaxSize();
513 size_type size() const {
514 return this->doSize();
524 return data() + size();
526 const_iterator begin() const {
529 const_iterator end() const {
530 return data() + size();
532 const_iterator cbegin() const {
535 const_iterator cend() const {
539 reverse_iterator rbegin() {
540 return reverse_iterator(end());
542 reverse_iterator rend() {
543 return reverse_iterator(begin());
546 const_reverse_iterator rbegin() const {
547 return const_reverse_iterator(end());
550 const_reverse_iterator rend() const {
551 return const_reverse_iterator(begin());
554 const_reverse_iterator crbegin() const {
557 const_reverse_iterator crend() const {
562 * Usually one of the simplest functions in a Container-like class
563 * but a bit more complex here. We have to handle all combinations
564 * of in-place vs. heap between this and o.
566 * Basic guarantee only. Provides the nothrow guarantee iff our
567 * value_type has a nothrow move or copy constructor.
569 void swap(small_vector& o) {
570 using std::swap; // Allow ADL on swap for our value_type.
572 if (this->isExtern() && o.isExtern()) {
573 this->swapSizePolicy(o);
575 auto thisCapacity = this->capacity();
576 auto oCapacity = o.capacity();
578 auto* tmp = u.pdata_.heap_;
579 u.pdata_.heap_ = o.u.pdata_.heap_;
580 o.u.pdata_.heap_ = tmp;
582 this->setCapacity(oCapacity);
583 o.setCapacity(thisCapacity);
588 if (!this->isExtern() && !o.isExtern()) {
589 auto& oldSmall = size() < o.size() ? *this : o;
590 auto& oldLarge = size() < o.size() ? o : *this;
592 for (size_type i = 0; i < oldSmall.size(); ++i) {
593 swap(oldSmall[i], oldLarge[i]);
596 size_type i = oldSmall.size();
597 const size_type ci = i;
599 for (; i < oldLarge.size(); ++i) {
600 auto addr = oldSmall.begin() + i;
601 new (addr) value_type(std::move(oldLarge[i]));
602 oldLarge[i].~value_type();
606 for (; i < oldLarge.size(); ++i) {
607 oldLarge[i].~value_type();
609 oldLarge.setSize(ci);
613 oldLarge.setSize(ci);
617 // isExtern != o.isExtern()
618 auto& oldExtern = o.isExtern() ? o : *this;
619 auto& oldIntern = o.isExtern() ? *this : o;
621 auto oldExternCapacity = oldExtern.capacity();
622 auto oldExternHeap = oldExtern.u.pdata_.heap_;
624 auto buff = oldExtern.u.buffer();
627 for (; i < oldIntern.size(); ++i) {
628 new (&buff[i]) value_type(std::move(oldIntern[i]));
629 oldIntern[i].~value_type();
632 for (size_type kill = 0; kill < i; ++kill) {
633 buff[kill].~value_type();
635 for (; i < oldIntern.size(); ++i) {
636 oldIntern[i].~value_type();
638 oldIntern.setSize(0);
639 oldExtern.u.pdata_.heap_ = oldExternHeap;
640 oldExtern.setCapacity(oldExternCapacity);
643 oldIntern.u.pdata_.heap_ = oldExternHeap;
644 this->swapSizePolicy(o);
645 oldIntern.setCapacity(oldExternCapacity);
648 void resize(size_type sz) {
650 erase(begin() + sz, end());
654 detail::populateMemForward(
655 begin() + size(), sz - size(), [&](void* p) { new (p) value_type(); });
659 void resize(size_type sz, value_type const& v) {
661 erase(begin() + sz, end());
665 detail::populateMemForward(
666 begin() + size(), sz - size(), [&](void* p) { new (p) value_type(v); });
670 value_type* data() noexcept {
671 return this->isExtern() ? u.heap() : u.buffer();
674 value_type const* data() const noexcept {
675 return this->isExtern() ? u.heap() : u.buffer();
678 template <class... Args>
679 iterator emplace(const_iterator p, Args&&... args) {
681 emplace_back(std::forward<Args>(args)...);
686 * We implement emplace at places other than at the back with a
687 * temporary for exception safety reasons. It is possible to
688 * avoid having to do this, but it becomes hard to maintain the
689 * basic exception safety guarantee (unless you respond to a copy
690 * constructor throwing by clearing the whole vector).
692 * The reason for this is that otherwise you have to destruct an
693 * element before constructing this one in its place---if the
694 * constructor throws, you either need a nothrow default
695 * constructor or a nothrow copy/move to get something back in the
696 * "gap", and the vector requirements don't guarantee we have any
697 * of these. Clearing the whole vector is a legal response in
698 * this situation, but it seems like this implementation is easy
699 * enough and probably better.
701 return insert(p, value_type(std::forward<Args>(args)...));
704 void reserve(size_type sz) {
708 size_type capacity() const {
709 if (this->isExtern()) {
710 if (u.hasCapacity()) {
711 return u.getCapacity();
713 return malloc_usable_size(u.pdata_.heap_) / sizeof(value_type);
718 void shrink_to_fit() {
719 if (!this->isExtern()) {
723 small_vector tmp(begin(), end());
727 template <class... Args>
728 void emplace_back(Args&&... args) {
729 if (capacity() == size()) {
730 // Any of args may be references into the vector.
731 // When we are reallocating, we have to be careful to construct the new
732 // element before modifying the data in the old buffer.
735 [&](void* p) { new (p) value_type(std::forward<Args>(args)...); },
738 new (end()) value_type(std::forward<Args>(args)...);
740 this->setSize(size() + 1);
743 void push_back(value_type&& t) {
744 return emplace_back(std::move(t));
747 void push_back(value_type const& t) {
755 iterator insert(const_iterator constp, value_type&& t) {
756 iterator p = unconst(constp);
759 push_back(std::move(t));
763 auto offset = p - begin();
765 if (capacity() == size()) {
768 [&t](void* ptr) { new (ptr) value_type(std::move(t)); },
770 this->setSize(this->size() + 1);
772 detail::moveObjectsRight(
773 data() + offset, data() + size(), data() + size() + 1);
774 this->setSize(size() + 1);
775 data()[offset] = std::move(t);
777 return begin() + offset;
780 iterator insert(const_iterator p, value_type const& t) {
781 // Make a copy and forward to the rvalue value_type&& overload
783 return insert(p, value_type(t));
786 iterator insert(const_iterator pos, size_type n, value_type const& val) {
787 auto offset = pos - begin();
788 makeSize(size() + n);
789 detail::moveObjectsRight(
790 data() + offset, data() + size(), data() + size() + n);
791 this->setSize(size() + n);
792 std::generate_n(begin() + offset, n, [&] { return val; });
793 return begin() + offset;
797 iterator insert(const_iterator p, Arg arg1, Arg arg2) {
798 // Forward using std::is_arithmetic to get to the proper
799 // implementation; this disambiguates between the iterators and
800 // (size_t, value_type) meaning for this function.
801 return insertImpl(unconst(p), arg1, arg2, std::is_arithmetic<Arg>());
804 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
805 return insert(p, il.begin(), il.end());
808 iterator erase(const_iterator q) {
809 std::move(unconst(q) + 1, end(), unconst(q));
810 (data() + size() - 1)->~value_type();
811 this->setSize(size() - 1);
815 iterator erase(const_iterator q1, const_iterator q2) {
819 std::move(unconst(q2), end(), unconst(q1));
820 for (auto it = (end() - std::distance(q1, q2)); it != end(); ++it) {
823 this->setSize(size() - (q2 - q1));
828 erase(begin(), end());
832 void assign(Arg first, Arg last) {
834 insert(end(), first, last);
837 void assign(std::initializer_list<value_type> il) {
838 assign(il.begin(), il.end());
841 void assign(size_type n, const value_type& t) {
854 const_reference front() const {
858 const_reference back() const {
863 reference operator[](size_type i) {
865 return *(begin() + i);
868 const_reference operator[](size_type i) const {
870 return *(begin() + i);
873 reference at(size_type i) {
875 std::__throw_out_of_range("index out of range");
880 const_reference at(size_type i) const {
882 std::__throw_out_of_range("index out of range");
888 static iterator unconst(const_iterator it) {
889 return const_cast<iterator>(it);
892 // The std::false_type argument is part of disambiguating the
893 // iterator insert functions from integral types (see insert().)
895 iterator insertImpl(iterator pos, It first, It last, std::false_type) {
896 typedef typename std::iterator_traits<It>::iterator_category categ;
897 if (std::is_same<categ, std::input_iterator_tag>::value) {
898 auto offset = pos - begin();
899 while (first != last) {
900 pos = insert(pos, *first++);
903 return begin() + offset;
906 auto distance = std::distance(first, last);
907 auto offset = pos - begin();
908 makeSize(size() + distance);
909 detail::moveObjectsRight(
910 data() + offset, data() + size(), data() + size() + distance);
911 this->setSize(size() + distance);
912 std::copy_n(first, distance, begin() + offset);
913 return begin() + offset;
917 insertImpl(iterator pos, size_type n, const value_type& val, std::true_type) {
918 // The true_type means this should call the size_t,value_type
919 // overload. (See insert().)
920 return insert(pos, n, val);
923 // The std::false_type argument came from std::is_arithmetic as part
924 // of disambiguating an overload (see the comment in the
927 void constructImpl(It first, It last, std::false_type) {
928 typedef typename std::iterator_traits<It>::iterator_category categ;
929 if (std::is_same<categ, std::input_iterator_tag>::value) {
930 // With iterators that only allow a single pass, we can't really
931 // do anything sane here.
932 while (first != last) {
933 emplace_back(*first++);
938 auto distance = std::distance(first, last);
940 this->setSize(distance);
942 detail::populateMemForward(
943 data(), distance, [&](void* p) { new (p) value_type(*first++); });
945 if (this->isExtern()) {
952 template <typename InitFunc>
953 void doConstruct(size_type n, InitFunc&& func) {
957 detail::populateMemForward(data(), n, std::forward<InitFunc>(func));
959 if (this->isExtern()) {
966 // The true_type means we should forward to the size_t,value_type
968 void constructImpl(size_type n, value_type const& val, std::true_type) {
969 doConstruct(n, [&](void* p) { new (p) value_type(val); });
973 * Compute the size after growth.
975 size_type computeNewSize() const {
976 return std::min((3 * capacity()) / 2 + 1, max_size());
979 void makeSize(size_type newSize) {
980 makeSizeInternal(newSize, false, [](void*) { assume_unreachable(); }, 0);
983 template <typename EmplaceFunc>
984 void makeSize(size_type newSize, EmplaceFunc&& emplaceFunc, size_type pos) {
985 assert(size() == capacity());
987 newSize, true, std::forward<EmplaceFunc>(emplaceFunc), pos);
991 * Ensure we have a large enough memory region to be size `newSize'.
992 * Will move/copy elements if we are spilling to heap_ or needed to
993 * allocate a new region, but if resized in place doesn't initialize
994 * anything in the new region. In any case doesn't change size().
995 * Supports insertion of new element during reallocation by given
996 * pointer to new element and position of new element.
997 * NOTE: If reallocation is not needed, insert must be false,
998 * because we only know how to emplace elements into new memory.
1000 template <typename EmplaceFunc>
1001 void makeSizeInternal(
1004 EmplaceFunc&& emplaceFunc,
1006 if (newSize > max_size()) {
1007 throw std::length_error("max_size exceeded in small_vector");
1009 if (newSize <= capacity()) {
1014 assert(this->kShouldUseHeap);
1015 // This branch isn't needed for correctness, but allows the optimizer to
1016 // skip generating code for the rest of this function in NoHeap
1018 if (!this->kShouldUseHeap) {
1022 newSize = std::max(newSize, computeNewSize());
1024 auto needBytes = newSize * sizeof(value_type);
1025 // If the capacity isn't explicitly stored inline, but the heap
1026 // allocation is grown to over some threshold, we should store
1027 // a capacity at the front of the heap allocation.
1028 bool heapifyCapacity =
1029 !kHasInlineCapacity && needBytes > kHeapifyCapacityThreshold;
1030 if (heapifyCapacity) {
1031 needBytes += kHeapifyCapacitySize;
1033 auto const sizeBytes = goodMallocSize(needBytes);
1034 void* newh = checkedMalloc(sizeBytes);
1035 // We expect newh to be at least 2-aligned, because we want to
1036 // use its least significant bit as a flag.
1037 assert(!detail::pointerFlagGet(newh));
1039 value_type* newp = static_cast<value_type*>(
1040 heapifyCapacity ? detail::shiftPointer(newh, kHeapifyCapacitySize)
1045 // move and insert the new element
1046 this->moveToUninitializedEmplace(
1047 begin(), end(), newp, pos, std::forward<EmplaceFunc>(emplaceFunc));
1049 // move without inserting new element
1050 this->moveToUninitialized(begin(), end(), newp);
1056 for (auto& val : *this) {
1060 if (this->isExtern()) {
1063 auto availableSizeBytes = sizeBytes;
1064 if (heapifyCapacity) {
1065 u.pdata_.heap_ = detail::pointerFlagSet(newh);
1066 availableSizeBytes -= kHeapifyCapacitySize;
1068 u.pdata_.heap_ = newh;
1070 this->setExtern(true);
1071 this->setCapacity(availableSizeBytes / sizeof(value_type));
1075 * This will set the capacity field, stored inline in the storage_ field
1076 * if there is sufficient room to store it.
1078 void setCapacity(size_type newCapacity) {
1079 assert(this->isExtern());
1080 if (u.hasCapacity()) {
1081 assert(newCapacity < std::numeric_limits<InternalSizeType>::max());
1082 u.setCapacity(newCapacity);
1087 struct HeapPtrWithCapacity {
1089 InternalSizeType capacity_;
1091 InternalSizeType getCapacity() const {
1094 void setCapacity(InternalSizeType c) {
1100 // Lower order bit of heap_ is used as flag to indicate whether capacity is
1101 // stored at the front of the heap allocation.
1104 InternalSizeType getCapacity() const {
1105 assert(detail::pointerFlagGet(heap_));
1106 return *static_cast<InternalSizeType*>(detail::pointerFlagClear(heap_));
1108 void setCapacity(InternalSizeType c) {
1109 *static_cast<InternalSizeType*>(detail::pointerFlagClear(heap_)) = c;
1113 #if (FOLLY_X64 || FOLLY_PPC64)
1114 typedef unsigned char InlineStorageDataType[sizeof(value_type) * MaxInline];
1116 typedef typename std::aligned_storage<
1117 sizeof(value_type) * MaxInline,
1118 alignof(value_type)>::type InlineStorageDataType;
1121 typedef typename std::conditional<
1122 sizeof(value_type) * MaxInline != 0,
1123 InlineStorageDataType,
1124 void*>::type InlineStorageType;
1126 static bool constexpr kHasInlineCapacity =
1127 sizeof(HeapPtrWithCapacity) < sizeof(InlineStorageType);
1129 // This value should we multiple of word size.
1130 static size_t constexpr kHeapifyCapacitySize = sizeof(
1132 aligned_storage<sizeof(InternalSizeType), alignof(value_type)>::type);
1134 // Threshold to control capacity heapifying.
1135 static size_t constexpr kHeapifyCapacityThreshold =
1136 100 * kHeapifyCapacitySize;
1138 typedef typename std::
1139 conditional<kHasInlineCapacity, HeapPtrWithCapacity, HeapPtr>::type
1144 pdata_.heap_ = nullptr;
1148 InlineStorageType storage_;
1150 value_type* buffer() noexcept {
1151 void* vp = &storage_;
1152 return static_cast<value_type*>(vp);
1154 value_type const* buffer() const noexcept {
1155 return const_cast<Data*>(this)->buffer();
1157 value_type* heap() noexcept {
1158 if (kHasInlineCapacity || !detail::pointerFlagGet(pdata_.heap_)) {
1159 return static_cast<value_type*>(pdata_.heap_);
1161 return static_cast<value_type*>(detail::shiftPointer(
1162 detail::pointerFlagClear(pdata_.heap_), kHeapifyCapacitySize));
1165 value_type const* heap() const noexcept {
1166 return const_cast<Data*>(this)->heap();
1169 bool hasCapacity() const {
1170 return kHasInlineCapacity || detail::pointerFlagGet(pdata_.heap_);
1172 InternalSizeType getCapacity() const {
1173 return pdata_.getCapacity();
1175 void setCapacity(InternalSizeType c) {
1176 pdata_.setCapacity(c);
1180 auto vp = detail::pointerFlagClear(pdata_.heap_);
1183 } FOLLY_PACK_ATTR u;
1187 //////////////////////////////////////////////////////////////////////
1189 // Basic guarantee only, or provides the nothrow guarantee iff T has a
1190 // nothrow move or copy constructor.
1191 template <class T, std::size_t MaxInline, class A, class B, class C>
1193 small_vector<T, MaxInline, A, B, C>& a,
1194 small_vector<T, MaxInline, A, B, C>& b) {
1198 //////////////////////////////////////////////////////////////////////
1203 template <class T, size_t M, class A, class B, class C>
1204 struct IndexableTraits<small_vector<T, M, A, B, C>>
1205 : public IndexableTraitsSeq<small_vector<T, M, A, B, C>> {};
1207 } // namespace detail
1209 } // namespace folly