2 * Copyright 2013 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 folly/doc/small_vector.md
20 * @author Jordan DeLong <delong.j@fb.com>
22 #ifndef FOLLY_SMALL_VECTOR_H_
23 #define FOLLY_SMALL_VECTOR_H_
25 #include "Portability.h"
29 #include <type_traits>
34 #include <boost/operators.hpp>
35 #include <boost/type_traits.hpp>
36 #include <boost/mpl/if.hpp>
37 #include <boost/mpl/eval_if.hpp>
38 #include <boost/mpl/vector.hpp>
39 #include <boost/mpl/front.hpp>
40 #include <boost/mpl/filter_view.hpp>
41 #include <boost/mpl/identity.hpp>
42 #include <boost/mpl/placeholders.hpp>
43 #include <boost/mpl/empty.hpp>
44 #include <boost/mpl/size.hpp>
45 #include <boost/mpl/count.hpp>
46 #include <boost/mpl/max.hpp>
48 #include "folly/Malloc.h"
50 #if defined(__GNUC__) && defined(__x86_64__)
51 # include "folly/SmallLocks.h"
52 # define FB_PACKED __attribute__((packed))
57 #ifdef FOLLY_HAVE_MALLOC_SIZE
58 extern "C" std::size_t malloc_size(const void*);
59 # ifndef FOLLY_HAVE_MALLOC_USABLE_SIZE
60 # define malloc_usable_size malloc_size
62 # ifndef malloc_usable_size
63 # define malloc_usable_size malloc_size
69 //////////////////////////////////////////////////////////////////////
71 namespace small_vector_policy {
73 //////////////////////////////////////////////////////////////////////
76 * A flag which makes us refuse to use the heap at all. If we
77 * overflow the in situ capacity we throw an exception.
82 * Passing this policy will cause small_vector to provide lock() and
83 * unlock() functions using a 1-bit spin lock in the size value.
85 * Note that this is intended for a fairly specialized (although
86 * strangely common at facebook) use case, where you have billions of
87 * vectors in memory where none of them are "hot" and most of them are
88 * small. This allows you to get fine-grained locks without spending
89 * a lot of memory on mutexes (the alternative of a large hashtable of
90 * locks leads to extra cache misses in the lookup path).
96 //////////////////////////////////////////////////////////////////////
98 } // small_vector_policy
100 //////////////////////////////////////////////////////////////////////
102 template<class T, std::size_t M, class A, class B, class C>
105 //////////////////////////////////////////////////////////////////////
110 * Move a range to a range of uninitialized memory. Assumes the
111 * ranges don't overlap.
114 typename std::enable_if<
115 !boost::has_trivial_copy<T>::value
117 moveToUninitialized(T* first, T* last, T* out) {
118 auto const count = last - first;
121 for (; idx < count; ++first, ++idx) {
122 new (&out[idx]) T(std::move(*first));
125 // Even for callers trying to give the strong guarantee
126 // (e.g. push_back) it's ok to assume here that we don't have to
127 // move things back and that it was a copy constructor that
128 // threw: if someone throws from a move constructor the effects
130 for (std::size_t i = 0; i < idx; ++i) {
137 // Specialization for trivially copyable types. (TODO: change to
138 // std::is_trivially_copyable when that works.)
140 typename std::enable_if<
141 boost::has_trivial_copy<T>::value
143 moveToUninitialized(T* first, T* last, T* out) {
144 std::memmove(out, first, (last - first) * sizeof *first);
148 * Move objects in memory to the right into some uninitialized
149 * memory, where the region overlaps. This doesn't just use
150 * std::move_backward because move_backward only works if all the
151 * memory is initialized to type T already.
154 typename std::enable_if<
155 !boost::has_trivial_copy<T>::value
157 moveObjectsRight(T* first, T* lastConstructed, T* realLast) {
158 if (lastConstructed == realLast) {
162 T* end = first - 1; // Past the end going backwards.
163 T* out = realLast - 1;
164 T* in = lastConstructed - 1;
166 for (; in != end && out >= lastConstructed; --in, --out) {
167 new (out) T(std::move(*in));
169 for (; in != end; --in, --out) {
170 *out = std::move(*in);
172 for (; out >= lastConstructed; --out) {
176 // We want to make sure the same stuff is uninitialized memory
177 // if we exit via an exception (this is to make sure we provide
178 // the basic exception safety guarantee for insert functions).
179 if (out < lastConstructed) {
180 out = lastConstructed - 1;
182 for (auto it = out + 1; it != realLast; ++it) {
189 // Specialization for trivially copyable types. The call to
190 // std::move_backward here will just turn into a memmove. (TODO:
191 // change to std::is_trivially_copyable when that works.)
193 typename std::enable_if<
194 boost::has_trivial_copy<T>::value
196 moveObjectsRight(T* first, T* lastConstructed, T* realLast) {
197 std::move_backward(first, lastConstructed, realLast);
201 * Populate a region of memory using `op' to construct elements. If
202 * anything throws, undo what we did.
204 template<class T, class Function>
205 void populateMemForward(T* mem, std::size_t n, Function const& op) {
208 for (size_t i = 0; i < n; ++i) {
213 for (std::size_t i = 0; i < idx; ++i) {
220 template<class SizeType, bool ShouldUseHeap>
221 struct IntegralSizePolicy {
222 typedef SizeType InternalSizeType;
224 IntegralSizePolicy() : size_(0) {}
227 std::size_t policyMaxSize() const {
228 return SizeType(~kExternMask);
231 std::size_t doSize() const {
232 return size_ & ~kExternMask;
235 std::size_t isExtern() const {
236 return kExternMask & size_;
239 void setExtern(bool b) {
241 size_ |= kExternMask;
243 size_ &= ~kExternMask;
247 void setSize(std::size_t sz) {
248 assert(sz <= policyMaxSize());
249 size_ = (kExternMask & size_) | SizeType(sz);
252 void swapSizePolicy(IntegralSizePolicy& o) {
253 std::swap(size_, o.size_);
257 static bool const kShouldUseHeap = ShouldUseHeap;
260 static SizeType const kExternMask =
261 kShouldUseHeap ? SizeType(1) << (sizeof(SizeType) * 8 - 1)
268 template<class SizeType, bool ShouldUseHeap>
269 struct OneBitMutexImpl {
270 typedef SizeType InternalSizeType;
272 OneBitMutexImpl() { psl_.init(); }
274 void lock() const { psl_.lock(); }
275 void unlock() const { psl_.unlock(); }
276 bool try_lock() const { return psl_.try_lock(); }
279 static bool const kShouldUseHeap = ShouldUseHeap;
281 std::size_t policyMaxSize() const {
282 return SizeType(~(SizeType(1) << kLockBit | kExternMask));
285 std::size_t doSize() const {
286 return psl_.getData() & ~kExternMask;
289 std::size_t isExtern() const {
290 return psl_.getData() & kExternMask;
293 void setExtern(bool b) {
295 setSize(SizeType(doSize()) | kExternMask);
297 setSize(SizeType(doSize()) & ~kExternMask);
301 void setSize(std::size_t sz) {
302 assert(sz < (std::size_t(1) << kLockBit));
303 psl_.setData((kExternMask & psl_.getData()) | SizeType(sz));
306 void swapSizePolicy(OneBitMutexImpl& o) {
307 std::swap(psl_, o.psl_);
311 static SizeType const kLockBit = sizeof(SizeType) * 8 - 1;
312 static SizeType const kExternMask =
313 kShouldUseHeap ? SizeType(1) << (sizeof(SizeType) * 8 - 2)
316 PicoSpinLock<SizeType,kLockBit> psl_;
319 template<class SizeType, bool ShouldUseHeap>
320 struct OneBitMutexImpl {
321 static_assert(std::is_same<SizeType,void>::value,
322 "OneBitMutex only works on x86-64");
327 * If you're just trying to use this class, ignore everything about
328 * this next small_vector_base class thing.
330 * The purpose of this junk is to minimize sizeof(small_vector<>)
331 * and allow specifying the template parameters in whatever order is
332 * convenient for the user. There's a few extra steps here to try
333 * to keep the error messages at least semi-reasonable.
335 * Apologies for all the black magic.
337 namespace mpl = boost::mpl;
338 template<class Value,
339 std::size_t RequestedMaxInline,
343 struct small_vector_base {
344 typedef mpl::vector<InPolicyA,InPolicyB,InPolicyC> PolicyList;
347 * Determine the size type
349 typedef typename mpl::filter_view<
351 boost::is_integral<mpl::placeholders::_1>
353 typedef typename mpl::eval_if<
354 mpl::empty<Integrals>,
355 mpl::identity<std::size_t>,
356 mpl::front<Integrals>
359 static_assert(std::is_unsigned<SizeType>::value,
360 "Size type should be an unsigned integral type");
361 static_assert(mpl::size<Integrals>::value == 0 ||
362 mpl::size<Integrals>::value == 1,
363 "Multiple size types specified in small_vector<>");
366 * Figure out if we're supposed to supply a one-bit mutex. :)
368 typedef typename mpl::count<
369 PolicyList,small_vector_policy::OneBitMutex
372 static_assert(HasMutex::value == 0 || HasMutex::value == 1,
373 "Multiple copies of small_vector_policy::OneBitMutex "
374 "supplied; this is probably a mistake");
377 * Determine whether we should allow spilling to the heap or not.
379 typedef typename mpl::count<
380 PolicyList,small_vector_policy::NoHeap
383 static_assert(HasNoHeap::value == 0 || HasNoHeap::value == 1,
384 "Multiple copies of small_vector_policy::NoHeap "
385 "supplied; this is probably a mistake");
388 * Make the real policy base classes.
390 typedef typename mpl::if_<
392 OneBitMutexImpl<SizeType,!HasNoHeap::value>,
393 IntegralSizePolicy<SizeType,!HasNoHeap::value>
394 >::type ActualSizePolicy;
397 * Now inherit from them all. This is done in such a convoluted
398 * way to make sure we get the empty base optimizaton on all these
399 * types to keep sizeof(small_vector<>) minimal.
401 typedef boost::totally_ordered1<
402 small_vector<Value,RequestedMaxInline,InPolicyA,InPolicyB,InPolicyC>,
408 T* pointerFlagSet(T* p) {
409 return reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(p) | 1);
412 bool pointerFlagGet(T* p) {
413 return reinterpret_cast<uintptr_t>(p) & 1;
416 T* pointerFlagClear(T* p) {
417 return reinterpret_cast<T*>(
418 reinterpret_cast<uintptr_t>(p) & ~uintptr_t(1));
420 inline void* shiftPointer(void* p, size_t sizeBytes) {
421 return static_cast<char*>(p) + sizeBytes;
425 //////////////////////////////////////////////////////////////////////
427 template<class Value,
428 std::size_t RequestedMaxInline = 1,
429 class PolicyA = void,
430 class PolicyB = void,
431 class PolicyC = void>
433 : public detail::small_vector_base<
434 Value,RequestedMaxInline,PolicyA,PolicyB,PolicyC
437 typedef typename detail::small_vector_base<
438 Value,RequestedMaxInline,PolicyA,PolicyB,PolicyC
440 typedef typename BaseType::InternalSizeType InternalSizeType;
443 * Figure out the max number of elements we should inline. (If
444 * the user asks for less inlined elements than we can fit unioned
445 * into our value_type*, we will inline more than they asked.)
448 MaxInline = boost::mpl::max<
449 boost::mpl::int_<sizeof(Value*) / sizeof(Value)>,
450 boost::mpl::int_<RequestedMaxInline>
455 typedef std::size_t size_type;
456 typedef Value value_type;
457 typedef value_type& reference;
458 typedef value_type const& const_reference;
459 typedef value_type* iterator;
460 typedef value_type const* const_iterator;
461 typedef std::ptrdiff_t difference_type;
463 typedef std::reverse_iterator<iterator> reverse_iterator;
464 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
466 explicit small_vector() {}
468 small_vector(small_vector const& o) {
469 assign(o.begin(), o.end());
472 small_vector(small_vector&& o) {
473 *this = std::move(o);
476 small_vector(std::initializer_list<value_type> il) {
477 constructImpl(il.begin(), il.end(), std::false_type());
480 explicit small_vector(size_type n, value_type const& t = value_type()) {
485 explicit small_vector(Arg arg1, Arg arg2) {
486 // Forward using std::is_arithmetic to get to the proper
487 // implementation; this disambiguates between the iterators and
488 // (size_t, value_type) meaning for this constructor.
489 constructImpl(arg1, arg2, std::is_arithmetic<Arg>());
493 for (auto& t : *this) {
496 if (this->isExtern()) {
501 small_vector& operator=(small_vector const& o) {
502 assign(o.begin(), o.end());
506 small_vector& operator=(small_vector&& o) {
510 for (std::size_t i = 0; i < o.size(); ++i) {
511 new (data() + i) value_type(std::move(o[i]));
513 this->setSize(o.size());
520 bool operator==(small_vector const& o) const {
521 return size() == o.size() && std::equal(begin(), end(), o.begin());
524 bool operator<(small_vector const& o) const {
525 return std::lexicographical_compare(begin(), end(), o.begin(), o.end());
528 size_type max_size() const {
529 return !BaseType::kShouldUseHeap ? MaxInline
530 : this->policyMaxSize();
533 size_type size() const { return this->doSize(); }
534 bool empty() const { return !size(); }
536 iterator begin() { return data(); }
537 iterator end() { return data() + size(); }
538 const_iterator begin() const { return data(); }
539 const_iterator end() const { return data() + size(); }
540 const_iterator cbegin() const { return begin(); }
541 const_iterator cend() const { return end(); }
543 reverse_iterator rbegin() { return reverse_iterator(end()); }
544 reverse_iterator rend() { 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 { return rbegin(); }
555 const_reverse_iterator crend() const { return rend(); }
558 * Usually one of the simplest functions in a Container-like class
559 * but a bit more complex here. We have to handle all combinations
560 * of in-place vs. heap between this and o.
562 * Basic guarantee only. Provides the nothrow guarantee iff our
563 * value_type has a nothrow move or copy constructor.
565 void swap(small_vector& o) {
566 using std::swap; // Allow ADL on swap for our value_type.
568 if (this->isExtern() && o.isExtern()) {
569 this->swapSizePolicy(o);
571 auto thisCapacity = this->capacity();
572 auto oCapacity = o.capacity();
574 std::swap(unpackHack(&u.pdata_.heap_), unpackHack(&o.u.pdata_.heap_));
576 this->setCapacity(oCapacity);
577 o.setCapacity(thisCapacity);
582 if (!this->isExtern() && !o.isExtern()) {
583 auto& oldSmall = size() < o.size() ? *this : o;
584 auto& oldLarge = size() < o.size() ? o : *this;
586 for (size_type i = 0; i < oldSmall.size(); ++i) {
587 swap(oldSmall[i], oldLarge[i]);
590 size_type i = oldSmall.size();
592 for (; i < oldLarge.size(); ++i) {
593 new (&oldSmall[i]) value_type(std::move(oldLarge[i]));
594 oldLarge[i].~value_type();
597 for (; i < oldLarge.size(); ++i) {
598 oldLarge[i].~value_type();
600 oldLarge.setSize(oldSmall.size());
603 this->swapSizePolicy(o);
607 // isExtern != o.isExtern()
608 auto& oldExtern = o.isExtern() ? o : *this;
609 auto& oldIntern = o.isExtern() ? *this : o;
611 auto oldExternCapacity = oldExtern.capacity();
612 auto oldExternHeap = oldExtern.u.pdata_.heap_;
614 auto buff = oldExtern.u.buffer();
617 for (; i < oldIntern.size(); ++i) {
618 new (&buff[i]) value_type(std::move(oldIntern[i]));
619 oldIntern[i].~value_type();
622 for (size_type kill = 0; kill < i; ++kill) {
623 buff[kill].~value_type();
625 for (; i < oldIntern.size(); ++i) {
626 oldIntern[i].~value_type();
628 oldIntern.setSize(0);
629 oldExtern.u.pdata_.heap_ = oldExternHeap;
630 oldExtern.setCapacity(oldExternCapacity);
633 oldIntern.u.pdata_.heap_ = oldExternHeap;
634 this->swapSizePolicy(o);
635 oldIntern.setCapacity(oldExternCapacity);
638 void resize(size_type sz) {
640 erase(begin() + sz, end());
644 detail::populateMemForward(begin() + size(), sz - size(),
645 [&] (void* p) { new (p) value_type(); }
650 void resize(size_type sz, value_type const& v) {
652 erase(begin() + sz, end());
656 detail::populateMemForward(begin() + size(), sz - size(),
657 [&] (void* p) { new (p) value_type(v); }
662 value_type* data() noexcept {
663 return this->isExtern() ? u.heap() : u.buffer();
666 value_type const* data() const noexcept {
667 return this->isExtern() ? u.heap() : u.buffer();
670 template<class ...Args>
671 iterator emplace(const_iterator p, Args&&... args) {
673 emplace_back(std::forward<Args>(args)...);
678 * We implement emplace at places other than at the back with a
679 * temporary for exception safety reasons. It is possible to
680 * avoid having to do this, but it becomes hard to maintain the
681 * basic exception safety guarantee (unless you respond to a copy
682 * constructor throwing by clearing the whole vector).
684 * The reason for this is that otherwise you have to destruct an
685 * element before constructing this one in its place---if the
686 * constructor throws, you either need a nothrow default
687 * constructor or a nothrow copy/move to get something back in the
688 * "gap", and the vector requirements don't guarantee we have any
689 * of these. Clearing the whole vector is a legal response in
690 * this situation, but it seems like this implementation is easy
691 * enough and probably better.
693 return insert(p, value_type(std::forward<Args>(args)...));
696 void reserve(size_type sz) {
700 size_type capacity() const {
701 if (this->isExtern()) {
702 if (u.hasCapacity()) {
703 return *u.getCapacity();
705 return malloc_usable_size(u.pdata_.heap_) / sizeof(value_type);
710 void shrink_to_fit() {
711 if (!this->isExtern()) {
715 small_vector tmp(begin(), end());
719 template<class ...Args>
720 void emplace_back(Args&&... args) {
721 // call helper function for static dispatch of special cases
722 emplaceBack(std::forward<Args>(args)...);
725 void push_back(value_type&& t) {
726 if (capacity() == size()) {
727 makeSize(std::max(size_type(2), 3 * size() / 2), &t, size());
729 new (end()) value_type(std::move(t));
731 this->setSize(size() + 1);
734 void push_back(value_type const& t) {
735 // Make a copy and forward to the rvalue value_type&& overload
737 push_back(value_type(t));
744 iterator insert(const_iterator constp, value_type&& t) {
745 iterator p = unconst(constp);
748 push_back(std::move(t));
752 auto offset = p - begin();
754 if (capacity() == size()) {
755 makeSize(size() + 1, &t, offset);
756 this->setSize(this->size() + 1);
758 makeSize(size() + 1);
759 detail::moveObjectsRight(data() + offset,
761 data() + size() + 1);
762 this->setSize(size() + 1);
763 data()[offset] = std::move(t);
765 return begin() + offset;
769 iterator insert(const_iterator p, value_type const& t) {
770 // Make a copy and forward to the rvalue value_type&& overload
772 return insert(p, value_type(t));
775 iterator insert(const_iterator pos, size_type n, value_type const& val) {
776 auto offset = pos - begin();
777 makeSize(size() + n);
778 detail::moveObjectsRight(data() + offset,
780 data() + size() + n);
781 this->setSize(size() + n);
782 std::generate_n(begin() + offset, n, [&] { return val; });
783 return begin() + offset;
787 iterator insert(const_iterator p, Arg arg1, Arg arg2) {
788 // Forward using std::is_arithmetic to get to the proper
789 // implementation; this disambiguates between the iterators and
790 // (size_t, value_type) meaning for this function.
791 return insertImpl(unconst(p), arg1, arg2, std::is_arithmetic<Arg>());
794 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
795 return insert(p, il.begin(), il.end());
798 iterator erase(const_iterator q) {
799 std::move(unconst(q) + 1, end(), unconst(q));
800 (data() + size() - 1)->~value_type();
801 this->setSize(size() - 1);
805 iterator erase(const_iterator q1, const_iterator q2) {
806 std::move(unconst(q2), end(), unconst(q1));
807 for (auto it = q1; it != end(); ++it) {
810 this->setSize(size() - (q2 - q1));
815 erase(begin(), end());
819 void assign(Arg first, Arg last) {
821 insert(end(), first, last);
824 void assign(std::initializer_list<value_type> il) {
825 assign(il.begin(), il.end());
828 void assign(size_type n, const value_type& t) {
833 reference front() { assert(!empty()); return *begin(); }
834 reference back() { assert(!empty()); return *(end() - 1); }
835 const_reference front() const { assert(!empty()); return *begin(); }
836 const_reference back() const { assert(!empty()); return *(end() - 1); }
838 reference operator[](size_type i) {
840 return *(begin() + i);
843 const_reference operator[](size_type i) const {
845 return *(begin() + i);
848 reference at(size_type i) {
850 throw std::out_of_range("index out of range");
855 const_reference at(size_type i) const {
857 throw std::out_of_range("index out of range");
865 * This is doing the same like emplace_back, but we need this helper
866 * to catch the special case - see the next overload function..
868 template<class ...Args>
869 void emplaceBack(Args&&... args) {
870 makeSize(size() + 1);
871 new (end()) value_type(std::forward<Args>(args)...);
872 this->setSize(size() + 1);
876 * Special case of emplaceBack for rvalue
878 void emplaceBack(value_type&& t) {
879 push_back(std::move(t));
882 static iterator unconst(const_iterator it) {
883 return const_cast<iterator>(it);
887 * g++ doesn't allow you to bind a non-const reference to a member
888 * of a packed structure, presumably because it would make it too
889 * easy to accidentally make an unaligned memory access?
891 template<class T> static T& unpackHack(T* p) {
895 // The std::false_type argument is part of disambiguating the
896 // iterator insert functions from integral types (see insert().)
898 iterator insertImpl(iterator pos, It first, It last, std::false_type) {
899 typedef typename std::iterator_traits<It>::iterator_category categ;
900 if (std::is_same<categ,std::input_iterator_tag>::value) {
901 auto offset = pos - begin();
902 while (first != last) {
903 pos = insert(pos, *first++);
906 return begin() + offset;
909 auto distance = std::distance(first, last);
910 auto offset = pos - begin();
911 makeSize(size() + distance);
912 detail::moveObjectsRight(data() + offset,
914 data() + size() + distance);
915 this->setSize(size() + distance);
916 std::copy_n(first, distance, begin() + offset);
917 return begin() + offset;
920 iterator insertImpl(iterator pos, size_type n, const value_type& val,
922 // The true_type means this should call the size_t,value_type
923 // overload. (See insert().)
924 return insert(pos, n, val);
927 // The std::false_type argument came from std::is_arithmetic as part
928 // of disambiguating an overload (see the comment in the
931 void constructImpl(It first, It last, std::false_type) {
932 typedef typename std::iterator_traits<It>::iterator_category categ;
933 if (std::is_same<categ,std::input_iterator_tag>::value) {
934 // With iterators that only allow a single pass, we can't really
935 // do anything sane here.
936 while (first != last) {
942 auto distance = std::distance(first, last);
944 this->setSize(distance);
946 detail::populateMemForward(data(), distance,
947 [&] (void* p) { new (p) value_type(*first++); }
951 void doConstruct(size_type n, value_type const& val) {
954 detail::populateMemForward(data(), n,
955 [&] (void* p) { new (p) value_type(val); }
959 // The true_type means we should forward to the size_t,value_type
961 void constructImpl(size_type n, value_type const& val, std::true_type) {
965 void makeSize(size_type size, value_type* v = NULL) {
966 makeSize(size, v, size - 1);
970 * Ensure we have a large enough memory region to be size `size'.
971 * Will move/copy elements if we are spilling to heap_ or needed to
972 * allocate a new region, but if resized in place doesn't initialize
973 * anything in the new region. In any case doesn't change size().
974 * Supports insertion of new element during reallocation by given
975 * pointer to new element and position of new element.
976 * NOTE: If reallocation is not needed, and new element should be
977 * inserted in the middle of vector (not at the end), do the move
978 * objects and insertion outside the function, otherwise exception is thrown.
980 void makeSize(size_type size, value_type* v, size_type pos) {
981 if (size > this->max_size()) {
982 throw std::length_error("max_size exceeded in small_vector");
984 if (size <= this->capacity()) {
988 auto needBytes = size * sizeof(value_type);
989 // If the capacity isn't explicitly stored inline, but the heap
990 // allocation is grown to over some threshold, we should store
991 // a capacity at the front of the heap allocation.
992 bool heapifyCapacity =
993 !kHasInlineCapacity && needBytes > kHeapifyCapacityThreshold;
994 if (heapifyCapacity) {
995 needBytes += kHeapifyCapacitySize;
997 auto const sizeBytes = goodMallocSize(needBytes);
998 void* newh = checkedMalloc(sizeBytes);
999 // We expect newh to be at least 2-aligned, because we want to
1000 // use its least significant bit as a flag.
1001 assert(!detail::pointerFlagGet(newh));
1003 value_type* newp = static_cast<value_type*>(
1005 detail::shiftPointer(newh, kHeapifyCapacitySize) :
1011 new (&newp[pos]) value_type(std::move(*v));
1017 // move old elements to the left of the new one
1019 detail::moveToUninitialized(begin(), begin() + pos, newp);
1021 newp[pos].~value_type();
1026 // move old elements to the right of the new one
1029 detail::moveToUninitialized(begin() + pos, end(), newp + pos + 1);
1032 for (size_type i = 0; i <= pos; ++i) {
1033 newp[i].~value_type();
1039 // move without inserting new element
1041 detail::moveToUninitialized(begin(), end(), newp);
1047 for (auto& val : *this) {
1051 if (this->isExtern()) {
1054 auto availableSizeBytes = sizeBytes;
1055 if (heapifyCapacity) {
1056 u.pdata_.heap_ = detail::pointerFlagSet(newh);
1057 availableSizeBytes -= kHeapifyCapacitySize;
1059 u.pdata_.heap_ = newh;
1061 this->setExtern(true);
1062 this->setCapacity(availableSizeBytes / sizeof(value_type));
1066 * This will set the capacity field, stored inline in the storage_ field
1067 * if there is sufficient room to store it.
1069 void setCapacity(size_type newCapacity) {
1070 assert(this->isExtern());
1071 if (u.hasCapacity()) {
1072 assert(newCapacity < std::numeric_limits<InternalSizeType>::max());
1073 *u.getCapacity() = InternalSizeType(newCapacity);
1078 struct HeapPtrWithCapacity {
1080 InternalSizeType capacity_;
1082 InternalSizeType* getCapacity() {
1088 // Lower order bit of heap_ is used as flag to indicate whether capacity is
1089 // stored at the front of the heap allocation.
1092 InternalSizeType* getCapacity() {
1093 assert(detail::pointerFlagGet(heap_));
1094 return static_cast<InternalSizeType*>(
1095 detail::pointerFlagClear(heap_));
1099 #if defined(__x86_64_)
1100 typedef unsigned char InlineStorageType[sizeof(value_type) * MaxInline];
1102 typedef typename std::aligned_storage<
1103 sizeof(value_type) * MaxInline,
1105 >::type InlineStorageType;
1108 static bool const kHasInlineCapacity =
1109 sizeof(HeapPtrWithCapacity) < sizeof(InlineStorageType);
1111 // This value should we multiple of word size.
1112 static size_t const kHeapifyCapacitySize = sizeof(
1113 typename std::aligned_storage<
1114 sizeof(InternalSizeType),
1117 // Threshold to control capacity heapifying.
1118 static size_t const kHeapifyCapacityThreshold =
1119 100 * kHeapifyCapacitySize;
1121 typedef typename std::conditional<
1123 HeapPtrWithCapacity,
1125 >::type PointerType;
1128 explicit Data() { pdata_.heap_ = 0; }
1131 InlineStorageType storage_;
1133 value_type* buffer() noexcept {
1134 void* vp = &storage_;
1135 return static_cast<value_type*>(vp);
1137 value_type const* buffer() const noexcept {
1138 return const_cast<Data*>(this)->buffer();
1140 value_type* heap() noexcept {
1141 if (kHasInlineCapacity || !detail::pointerFlagGet(pdata_.heap_)) {
1142 return static_cast<value_type*>(pdata_.heap_);
1144 return static_cast<value_type*>(
1145 detail::shiftPointer(
1146 detail::pointerFlagClear(pdata_.heap_), kHeapifyCapacitySize));
1148 value_type const* heap() const noexcept {
1149 return const_cast<Data*>(this)->heap();
1152 bool hasCapacity() const {
1153 return kHasInlineCapacity || detail::pointerFlagGet(pdata_.heap_);
1155 InternalSizeType* getCapacity() {
1156 return pdata_.getCapacity();
1158 InternalSizeType* getCapacity() const {
1159 return const_cast<Data*>(this)->getCapacity();
1163 auto vp = detail::pointerFlagClear(pdata_.heap_);
1169 //////////////////////////////////////////////////////////////////////
1171 // Basic guarantee only, or provides the nothrow guarantee iff T has a
1172 // nothrow move or copy constructor.
1173 template<class T, std::size_t MaxInline, class A, class B, class C>
1174 void swap(small_vector<T,MaxInline,A,B,C>& a,
1175 small_vector<T,MaxInline,A,B,C>& b) {
1179 //////////////////////////////////////////////////////////////////////