2 * Copyright 2014 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>
23 #ifndef FOLLY_SMALL_VECTOR_H_
24 #define FOLLY_SMALL_VECTOR_H_
26 #include "Portability.h"
30 #include <type_traits>
35 #include <boost/operators.hpp>
36 #include <boost/type_traits.hpp>
37 #include <boost/mpl/if.hpp>
38 #include <boost/mpl/eval_if.hpp>
39 #include <boost/mpl/vector.hpp>
40 #include <boost/mpl/front.hpp>
41 #include <boost/mpl/filter_view.hpp>
42 #include <boost/mpl/identity.hpp>
43 #include <boost/mpl/placeholders.hpp>
44 #include <boost/mpl/empty.hpp>
45 #include <boost/mpl/size.hpp>
46 #include <boost/mpl/count.hpp>
47 #include <boost/mpl/max.hpp>
49 #include "folly/Malloc.h"
51 #if defined(__GNUC__) && FOLLY_X64
52 # include "folly/SmallLocks.h"
53 # define FB_PACK_ATTR FOLLY_PACK_ATTR
54 # define FB_PACK_PUSH FOLLY_PACK_PUSH
55 # define FB_PACK_POP FOLLY_PACK_POP
62 #if FOLLY_HAVE_MALLOC_SIZE
63 extern "C" std::size_t malloc_size(const void*);
64 # if !FOLLY_HAVE_MALLOC_USABLE_SIZE
65 # define malloc_usable_size malloc_size
67 # ifndef malloc_usable_size
68 # define malloc_usable_size malloc_size
72 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
73 #pragma GCC diagnostic push
74 #pragma GCC diagnostic ignored "-Wshadow"
78 //////////////////////////////////////////////////////////////////////
80 namespace small_vector_policy {
82 //////////////////////////////////////////////////////////////////////
85 * A flag which makes us refuse to use the heap at all. If we
86 * overflow the in situ capacity we throw an exception.
90 //////////////////////////////////////////////////////////////////////
92 } // small_vector_policy
94 //////////////////////////////////////////////////////////////////////
96 template<class T, std::size_t M, class A, class B, class C>
99 //////////////////////////////////////////////////////////////////////
104 * Move a range to a range of uninitialized memory. Assumes the
105 * ranges don't overlap.
108 typename std::enable_if<
109 !FOLLY_IS_TRIVIALLY_COPYABLE(T)
111 moveToUninitialized(T* first, T* last, T* out) {
112 auto const count = last - first;
115 for (; idx < count; ++first, ++idx) {
116 new (&out[idx]) T(std::move(*first));
119 // Even for callers trying to give the strong guarantee
120 // (e.g. push_back) it's ok to assume here that we don't have to
121 // move things back and that it was a copy constructor that
122 // threw: if someone throws from a move constructor the effects
124 for (std::size_t i = 0; i < idx; ++i) {
131 // Specialization for trivially copyable types.
133 typename std::enable_if<
134 FOLLY_IS_TRIVIALLY_COPYABLE(T)
136 moveToUninitialized(T* first, T* last, T* out) {
137 std::memmove(out, first, (last - first) * sizeof *first);
141 * Move objects in memory to the right into some uninitialized
142 * memory, where the region overlaps. This doesn't just use
143 * std::move_backward because move_backward only works if all the
144 * memory is initialized to type T already.
147 typename std::enable_if<
148 !FOLLY_IS_TRIVIALLY_COPYABLE(T)
150 moveObjectsRight(T* first, T* lastConstructed, T* realLast) {
151 if (lastConstructed == realLast) {
155 T* end = first - 1; // Past the end going backwards.
156 T* out = realLast - 1;
157 T* in = lastConstructed - 1;
159 for (; in != end && out >= lastConstructed; --in, --out) {
160 new (out) T(std::move(*in));
162 for (; in != end; --in, --out) {
163 *out = std::move(*in);
165 for (; out >= lastConstructed; --out) {
169 // We want to make sure the same stuff is uninitialized memory
170 // if we exit via an exception (this is to make sure we provide
171 // the basic exception safety guarantee for insert functions).
172 if (out < lastConstructed) {
173 out = lastConstructed - 1;
175 for (auto it = out + 1; it != realLast; ++it) {
182 // Specialization for trivially copyable types. The call to
183 // std::move_backward here will just turn into a memmove. (TODO:
184 // change to std::is_trivially_copyable when that works.)
186 typename std::enable_if<
187 FOLLY_IS_TRIVIALLY_COPYABLE(T)
189 moveObjectsRight(T* first, T* lastConstructed, T* realLast) {
190 std::move_backward(first, lastConstructed, realLast);
194 * Populate a region of memory using `op' to construct elements. If
195 * anything throws, undo what we did.
197 template<class T, class Function>
198 void populateMemForward(T* mem, std::size_t n, Function const& op) {
201 for (size_t i = 0; i < n; ++i) {
206 for (std::size_t i = 0; i < idx; ++i) {
213 template<class SizeType, bool ShouldUseHeap>
214 struct IntegralSizePolicy {
215 typedef SizeType InternalSizeType;
217 IntegralSizePolicy() : size_(0) {}
220 static constexpr std::size_t policyMaxSize() {
221 return SizeType(~kExternMask);
224 std::size_t doSize() const {
225 return size_ & ~kExternMask;
228 std::size_t isExtern() const {
229 return kExternMask & size_;
232 void setExtern(bool b) {
234 size_ |= kExternMask;
236 size_ &= ~kExternMask;
240 void setSize(std::size_t sz) {
241 assert(sz <= policyMaxSize());
242 size_ = (kExternMask & size_) | SizeType(sz);
245 void swapSizePolicy(IntegralSizePolicy& o) {
246 std::swap(size_, o.size_);
250 static bool const kShouldUseHeap = ShouldUseHeap;
253 static SizeType const kExternMask =
254 kShouldUseHeap ? SizeType(1) << (sizeof(SizeType) * 8 - 1)
261 * If you're just trying to use this class, ignore everything about
262 * this next small_vector_base class thing.
264 * The purpose of this junk is to minimize sizeof(small_vector<>)
265 * and allow specifying the template parameters in whatever order is
266 * convenient for the user. There's a few extra steps here to try
267 * to keep the error messages at least semi-reasonable.
269 * Apologies for all the black magic.
271 namespace mpl = boost::mpl;
272 template<class Value,
273 std::size_t RequestedMaxInline,
277 struct small_vector_base {
278 typedef mpl::vector<InPolicyA,InPolicyB,InPolicyC> PolicyList;
281 * Determine the size type
283 typedef typename mpl::filter_view<
285 boost::is_integral<mpl::placeholders::_1>
287 typedef typename mpl::eval_if<
288 mpl::empty<Integrals>,
289 mpl::identity<std::size_t>,
290 mpl::front<Integrals>
293 static_assert(std::is_unsigned<SizeType>::value,
294 "Size type should be an unsigned integral type");
295 static_assert(mpl::size<Integrals>::value == 0 ||
296 mpl::size<Integrals>::value == 1,
297 "Multiple size types specified in small_vector<>");
300 * Determine whether we should allow spilling to the heap or not.
302 typedef typename mpl::count<
303 PolicyList,small_vector_policy::NoHeap
306 static_assert(HasNoHeap::value == 0 || HasNoHeap::value == 1,
307 "Multiple copies of small_vector_policy::NoHeap "
308 "supplied; this is probably a mistake");
311 * Make the real policy base classes.
313 typedef IntegralSizePolicy<SizeType,!HasNoHeap::value>
317 * Now inherit from them all. This is done in such a convoluted
318 * way to make sure we get the empty base optimizaton on all these
319 * types to keep sizeof(small_vector<>) minimal.
321 typedef boost::totally_ordered1<
322 small_vector<Value,RequestedMaxInline,InPolicyA,InPolicyB,InPolicyC>,
328 T* pointerFlagSet(T* p) {
329 return reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(p) | 1);
332 bool pointerFlagGet(T* p) {
333 return reinterpret_cast<uintptr_t>(p) & 1;
336 T* pointerFlagClear(T* p) {
337 return reinterpret_cast<T*>(
338 reinterpret_cast<uintptr_t>(p) & ~uintptr_t(1));
340 inline void* shiftPointer(void* p, size_t sizeBytes) {
341 return static_cast<char*>(p) + sizeBytes;
345 //////////////////////////////////////////////////////////////////////
347 template<class Value,
348 std::size_t RequestedMaxInline = 1,
349 class PolicyA = void,
350 class PolicyB = void,
351 class PolicyC = void>
353 : public detail::small_vector_base<
354 Value,RequestedMaxInline,PolicyA,PolicyB,PolicyC
357 typedef typename detail::small_vector_base<
358 Value,RequestedMaxInline,PolicyA,PolicyB,PolicyC
360 typedef typename BaseType::InternalSizeType InternalSizeType;
363 * Figure out the max number of elements we should inline. (If
364 * the user asks for less inlined elements than we can fit unioned
365 * into our value_type*, we will inline more than they asked.)
368 MaxInline = boost::mpl::max<
369 boost::mpl::int_<sizeof(Value*) / sizeof(Value)>,
370 boost::mpl::int_<RequestedMaxInline>
375 typedef std::size_t size_type;
376 typedef Value value_type;
377 typedef value_type& reference;
378 typedef value_type const& const_reference;
379 typedef value_type* iterator;
380 typedef value_type const* const_iterator;
381 typedef std::ptrdiff_t difference_type;
383 typedef std::reverse_iterator<iterator> reverse_iterator;
384 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
386 explicit small_vector() {}
388 small_vector(small_vector const& o) {
389 assign(o.begin(), o.end());
392 small_vector(small_vector&& o) {
393 *this = std::move(o);
396 small_vector(std::initializer_list<value_type> il) {
397 constructImpl(il.begin(), il.end(), std::false_type());
400 explicit small_vector(size_type n, value_type const& t = value_type()) {
405 explicit small_vector(Arg arg1, Arg arg2) {
406 // Forward using std::is_arithmetic to get to the proper
407 // implementation; this disambiguates between the iterators and
408 // (size_t, value_type) meaning for this constructor.
409 constructImpl(arg1, arg2, std::is_arithmetic<Arg>());
413 for (auto& t : *this) {
416 if (this->isExtern()) {
421 small_vector& operator=(small_vector const& o) {
422 assign(o.begin(), o.end());
426 small_vector& operator=(small_vector&& o) {
430 for (std::size_t i = 0; i < o.size(); ++i) {
431 new (data() + i) value_type(std::move(o[i]));
433 this->setSize(o.size());
440 bool operator==(small_vector const& o) const {
441 return size() == o.size() && std::equal(begin(), end(), o.begin());
444 bool operator<(small_vector const& o) const {
445 return std::lexicographical_compare(begin(), end(), o.begin(), o.end());
448 static constexpr size_type max_size() {
449 return !BaseType::kShouldUseHeap ? MaxInline
450 : BaseType::policyMaxSize();
453 size_type size() const { return this->doSize(); }
454 bool empty() const { return !size(); }
456 iterator begin() { return data(); }
457 iterator end() { return data() + size(); }
458 const_iterator begin() const { return data(); }
459 const_iterator end() const { return data() + size(); }
460 const_iterator cbegin() const { return begin(); }
461 const_iterator cend() const { return end(); }
463 reverse_iterator rbegin() { return reverse_iterator(end()); }
464 reverse_iterator rend() { return reverse_iterator(begin()); }
466 const_reverse_iterator rbegin() const {
467 return const_reverse_iterator(end());
470 const_reverse_iterator rend() const {
471 return const_reverse_iterator(begin());
474 const_reverse_iterator crbegin() const { return rbegin(); }
475 const_reverse_iterator crend() const { return rend(); }
478 * Usually one of the simplest functions in a Container-like class
479 * but a bit more complex here. We have to handle all combinations
480 * of in-place vs. heap between this and o.
482 * Basic guarantee only. Provides the nothrow guarantee iff our
483 * value_type has a nothrow move or copy constructor.
485 void swap(small_vector& o) {
486 using std::swap; // Allow ADL on swap for our value_type.
488 if (this->isExtern() && o.isExtern()) {
489 this->swapSizePolicy(o);
491 auto thisCapacity = this->capacity();
492 auto oCapacity = o.capacity();
494 std::swap(unpackHack(&u.pdata_.heap_), unpackHack(&o.u.pdata_.heap_));
496 this->setCapacity(oCapacity);
497 o.setCapacity(thisCapacity);
502 if (!this->isExtern() && !o.isExtern()) {
503 auto& oldSmall = size() < o.size() ? *this : o;
504 auto& oldLarge = size() < o.size() ? o : *this;
506 for (size_type i = 0; i < oldSmall.size(); ++i) {
507 swap(oldSmall[i], oldLarge[i]);
510 size_type i = oldSmall.size();
512 for (; i < oldLarge.size(); ++i) {
513 new (&oldSmall[i]) value_type(std::move(oldLarge[i]));
514 oldLarge[i].~value_type();
517 for (; i < oldLarge.size(); ++i) {
518 oldLarge[i].~value_type();
520 oldLarge.setSize(oldSmall.size());
523 this->swapSizePolicy(o);
527 // isExtern != o.isExtern()
528 auto& oldExtern = o.isExtern() ? o : *this;
529 auto& oldIntern = o.isExtern() ? *this : o;
531 auto oldExternCapacity = oldExtern.capacity();
532 auto oldExternHeap = oldExtern.u.pdata_.heap_;
534 auto buff = oldExtern.u.buffer();
537 for (; i < oldIntern.size(); ++i) {
538 new (&buff[i]) value_type(std::move(oldIntern[i]));
539 oldIntern[i].~value_type();
542 for (size_type kill = 0; kill < i; ++kill) {
543 buff[kill].~value_type();
545 for (; i < oldIntern.size(); ++i) {
546 oldIntern[i].~value_type();
548 oldIntern.setSize(0);
549 oldExtern.u.pdata_.heap_ = oldExternHeap;
550 oldExtern.setCapacity(oldExternCapacity);
553 oldIntern.u.pdata_.heap_ = oldExternHeap;
554 this->swapSizePolicy(o);
555 oldIntern.setCapacity(oldExternCapacity);
558 void resize(size_type sz) {
560 erase(begin() + sz, end());
564 detail::populateMemForward(begin() + size(), sz - size(),
565 [&] (void* p) { new (p) value_type(); }
570 void resize(size_type sz, value_type const& v) {
572 erase(begin() + sz, end());
576 detail::populateMemForward(begin() + size(), sz - size(),
577 [&] (void* p) { new (p) value_type(v); }
582 value_type* data() noexcept {
583 return this->isExtern() ? u.heap() : u.buffer();
586 value_type const* data() const noexcept {
587 return this->isExtern() ? u.heap() : u.buffer();
590 template<class ...Args>
591 iterator emplace(const_iterator p, Args&&... args) {
593 emplace_back(std::forward<Args>(args)...);
598 * We implement emplace at places other than at the back with a
599 * temporary for exception safety reasons. It is possible to
600 * avoid having to do this, but it becomes hard to maintain the
601 * basic exception safety guarantee (unless you respond to a copy
602 * constructor throwing by clearing the whole vector).
604 * The reason for this is that otherwise you have to destruct an
605 * element before constructing this one in its place---if the
606 * constructor throws, you either need a nothrow default
607 * constructor or a nothrow copy/move to get something back in the
608 * "gap", and the vector requirements don't guarantee we have any
609 * of these. Clearing the whole vector is a legal response in
610 * this situation, but it seems like this implementation is easy
611 * enough and probably better.
613 return insert(p, value_type(std::forward<Args>(args)...));
616 void reserve(size_type sz) {
620 size_type capacity() const {
621 if (this->isExtern()) {
622 if (u.hasCapacity()) {
623 return *u.getCapacity();
625 return malloc_usable_size(u.pdata_.heap_) / sizeof(value_type);
630 void shrink_to_fit() {
631 if (!this->isExtern()) {
635 small_vector tmp(begin(), end());
639 template<class ...Args>
640 void emplace_back(Args&&... args) {
641 // call helper function for static dispatch of special cases
642 emplaceBack(std::forward<Args>(args)...);
645 void push_back(value_type&& t) {
646 if (capacity() == size()) {
647 makeSize(std::max(size_type(2), 3 * size() / 2), &t, size());
649 new (end()) value_type(std::move(t));
651 this->setSize(size() + 1);
654 void push_back(value_type const& t) {
655 // Make a copy and forward to the rvalue value_type&& overload
657 push_back(value_type(t));
664 iterator insert(const_iterator constp, value_type&& t) {
665 iterator p = unconst(constp);
668 push_back(std::move(t));
672 auto offset = p - begin();
674 if (capacity() == size()) {
675 makeSize(size() + 1, &t, offset);
676 this->setSize(this->size() + 1);
678 makeSize(size() + 1);
679 detail::moveObjectsRight(data() + offset,
681 data() + size() + 1);
682 this->setSize(size() + 1);
683 data()[offset] = std::move(t);
685 return begin() + offset;
689 iterator insert(const_iterator p, value_type const& t) {
690 // Make a copy and forward to the rvalue value_type&& overload
692 return insert(p, value_type(t));
695 iterator insert(const_iterator pos, size_type n, value_type const& val) {
696 auto offset = pos - begin();
697 makeSize(size() + n);
698 detail::moveObjectsRight(data() + offset,
700 data() + size() + n);
701 this->setSize(size() + n);
702 std::generate_n(begin() + offset, n, [&] { return val; });
703 return begin() + offset;
707 iterator insert(const_iterator p, Arg arg1, Arg arg2) {
708 // Forward using std::is_arithmetic to get to the proper
709 // implementation; this disambiguates between the iterators and
710 // (size_t, value_type) meaning for this function.
711 return insertImpl(unconst(p), arg1, arg2, std::is_arithmetic<Arg>());
714 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
715 return insert(p, il.begin(), il.end());
718 iterator erase(const_iterator q) {
719 std::move(unconst(q) + 1, end(), unconst(q));
720 (data() + size() - 1)->~value_type();
721 this->setSize(size() - 1);
725 iterator erase(const_iterator q1, const_iterator q2) {
726 std::move(unconst(q2), end(), unconst(q1));
727 for (auto it = q1; it != end(); ++it) {
730 this->setSize(size() - (q2 - q1));
735 erase(begin(), end());
739 void assign(Arg first, Arg last) {
741 insert(end(), first, last);
744 void assign(std::initializer_list<value_type> il) {
745 assign(il.begin(), il.end());
748 void assign(size_type n, const value_type& t) {
753 reference front() { assert(!empty()); return *begin(); }
754 reference back() { assert(!empty()); return *(end() - 1); }
755 const_reference front() const { assert(!empty()); return *begin(); }
756 const_reference back() const { assert(!empty()); return *(end() - 1); }
758 reference operator[](size_type i) {
760 return *(begin() + i);
763 const_reference operator[](size_type i) const {
765 return *(begin() + i);
768 reference at(size_type i) {
770 throw std::out_of_range("index out of range");
775 const_reference at(size_type i) const {
777 throw std::out_of_range("index out of range");
785 * This is doing the same like emplace_back, but we need this helper
786 * to catch the special case - see the next overload function..
788 template<class ...Args>
789 void emplaceBack(Args&&... args) {
790 makeSize(size() + 1);
791 new (end()) value_type(std::forward<Args>(args)...);
792 this->setSize(size() + 1);
796 * Special case of emplaceBack for rvalue
798 void emplaceBack(value_type&& t) {
799 push_back(std::move(t));
802 static iterator unconst(const_iterator it) {
803 return const_cast<iterator>(it);
807 * g++ doesn't allow you to bind a non-const reference to a member
808 * of a packed structure, presumably because it would make it too
809 * easy to accidentally make an unaligned memory access?
811 template<class T> static T& unpackHack(T* p) {
815 // The std::false_type argument is part of disambiguating the
816 // iterator insert functions from integral types (see insert().)
818 iterator insertImpl(iterator pos, It first, It last, std::false_type) {
819 typedef typename std::iterator_traits<It>::iterator_category categ;
820 if (std::is_same<categ,std::input_iterator_tag>::value) {
821 auto offset = pos - begin();
822 while (first != last) {
823 pos = insert(pos, *first++);
826 return begin() + offset;
829 auto distance = std::distance(first, last);
830 auto offset = pos - begin();
831 makeSize(size() + distance);
832 detail::moveObjectsRight(data() + offset,
834 data() + size() + distance);
835 this->setSize(size() + distance);
836 std::copy_n(first, distance, begin() + offset);
837 return begin() + offset;
840 iterator insertImpl(iterator pos, size_type n, const value_type& val,
842 // The true_type means this should call the size_t,value_type
843 // overload. (See insert().)
844 return insert(pos, n, val);
847 // The std::false_type argument came from std::is_arithmetic as part
848 // of disambiguating an overload (see the comment in the
851 void constructImpl(It first, It last, std::false_type) {
852 typedef typename std::iterator_traits<It>::iterator_category categ;
853 if (std::is_same<categ,std::input_iterator_tag>::value) {
854 // With iterators that only allow a single pass, we can't really
855 // do anything sane here.
856 while (first != last) {
862 auto distance = std::distance(first, last);
864 this->setSize(distance);
866 detail::populateMemForward(data(), distance,
867 [&] (void* p) { new (p) value_type(*first++); }
871 void doConstruct(size_type n, value_type const& val) {
874 detail::populateMemForward(data(), n,
875 [&] (void* p) { new (p) value_type(val); }
879 // The true_type means we should forward to the size_t,value_type
881 void constructImpl(size_type n, value_type const& val, std::true_type) {
885 void makeSize(size_type size, value_type* v = nullptr) {
886 makeSize(size, v, size - 1);
890 * Ensure we have a large enough memory region to be size `size'.
891 * Will move/copy elements if we are spilling to heap_ or needed to
892 * allocate a new region, but if resized in place doesn't initialize
893 * anything in the new region. In any case doesn't change size().
894 * Supports insertion of new element during reallocation by given
895 * pointer to new element and position of new element.
896 * NOTE: If reallocation is not needed, and new element should be
897 * inserted in the middle of vector (not at the end), do the move
898 * objects and insertion outside the function, otherwise exception is thrown.
900 void makeSize(size_type size, value_type* v, size_type pos) {
901 if (size > this->max_size()) {
902 throw std::length_error("max_size exceeded in small_vector");
904 if (size <= this->capacity()) {
908 auto needBytes = size * sizeof(value_type);
909 // If the capacity isn't explicitly stored inline, but the heap
910 // allocation is grown to over some threshold, we should store
911 // a capacity at the front of the heap allocation.
912 bool heapifyCapacity =
913 !kHasInlineCapacity && needBytes > kHeapifyCapacityThreshold;
914 if (heapifyCapacity) {
915 needBytes += kHeapifyCapacitySize;
917 auto const sizeBytes = goodMallocSize(needBytes);
918 void* newh = checkedMalloc(sizeBytes);
919 // We expect newh to be at least 2-aligned, because we want to
920 // use its least significant bit as a flag.
921 assert(!detail::pointerFlagGet(newh));
923 value_type* newp = static_cast<value_type*>(
925 detail::shiftPointer(newh, kHeapifyCapacitySize) :
931 new (&newp[pos]) value_type(std::move(*v));
937 // move old elements to the left of the new one
939 detail::moveToUninitialized(begin(), begin() + pos, newp);
941 newp[pos].~value_type();
946 // move old elements to the right of the new one
949 detail::moveToUninitialized(begin() + pos, end(), newp + pos + 1);
952 for (size_type i = 0; i <= pos; ++i) {
953 newp[i].~value_type();
959 // move without inserting new element
961 detail::moveToUninitialized(begin(), end(), newp);
967 for (auto& val : *this) {
971 if (this->isExtern()) {
974 auto availableSizeBytes = sizeBytes;
975 if (heapifyCapacity) {
976 u.pdata_.heap_ = detail::pointerFlagSet(newh);
977 availableSizeBytes -= kHeapifyCapacitySize;
979 u.pdata_.heap_ = newh;
981 this->setExtern(true);
982 this->setCapacity(availableSizeBytes / sizeof(value_type));
986 * This will set the capacity field, stored inline in the storage_ field
987 * if there is sufficient room to store it.
989 void setCapacity(size_type newCapacity) {
990 assert(this->isExtern());
991 if (u.hasCapacity()) {
992 assert(newCapacity < std::numeric_limits<InternalSizeType>::max());
993 *u.getCapacity() = InternalSizeType(newCapacity);
998 struct HeapPtrWithCapacity {
1000 InternalSizeType capacity_;
1002 InternalSizeType* getCapacity() {
1008 // Lower order bit of heap_ is used as flag to indicate whether capacity is
1009 // stored at the front of the heap allocation.
1012 InternalSizeType* getCapacity() {
1013 assert(detail::pointerFlagGet(heap_));
1014 return static_cast<InternalSizeType*>(
1015 detail::pointerFlagClear(heap_));
1020 typedef unsigned char InlineStorageType[sizeof(value_type) * MaxInline];
1022 typedef typename std::aligned_storage<
1023 sizeof(value_type) * MaxInline,
1025 >::type InlineStorageType;
1028 static bool const kHasInlineCapacity =
1029 sizeof(HeapPtrWithCapacity) < sizeof(InlineStorageType);
1031 // This value should we multiple of word size.
1032 static size_t const kHeapifyCapacitySize = sizeof(
1033 typename std::aligned_storage<
1034 sizeof(InternalSizeType),
1037 // Threshold to control capacity heapifying.
1038 static size_t const kHeapifyCapacityThreshold =
1039 100 * kHeapifyCapacitySize;
1041 typedef typename std::conditional<
1043 HeapPtrWithCapacity,
1045 >::type PointerType;
1048 explicit Data() { pdata_.heap_ = 0; }
1051 InlineStorageType storage_;
1053 value_type* buffer() noexcept {
1054 void* vp = &storage_;
1055 return static_cast<value_type*>(vp);
1057 value_type const* buffer() const noexcept {
1058 return const_cast<Data*>(this)->buffer();
1060 value_type* heap() noexcept {
1061 if (kHasInlineCapacity || !detail::pointerFlagGet(pdata_.heap_)) {
1062 return static_cast<value_type*>(pdata_.heap_);
1064 return static_cast<value_type*>(
1065 detail::shiftPointer(
1066 detail::pointerFlagClear(pdata_.heap_), kHeapifyCapacitySize));
1068 value_type const* heap() const noexcept {
1069 return const_cast<Data*>(this)->heap();
1072 bool hasCapacity() const {
1073 return kHasInlineCapacity || detail::pointerFlagGet(pdata_.heap_);
1075 InternalSizeType* getCapacity() {
1076 return pdata_.getCapacity();
1078 InternalSizeType* getCapacity() const {
1079 return const_cast<Data*>(this)->getCapacity();
1083 auto vp = detail::pointerFlagClear(pdata_.heap_);
1090 //////////////////////////////////////////////////////////////////////
1092 // Basic guarantee only, or provides the nothrow guarantee iff T has a
1093 // nothrow move or copy constructor.
1094 template<class T, std::size_t MaxInline, class A, class B, class C>
1095 void swap(small_vector<T,MaxInline,A,B,C>& a,
1096 small_vector<T,MaxInline,A,B,C>& b) {
1100 //////////////////////////////////////////////////////////////////////
1104 #pragma GCC diagnostic pop
1107 # undef FB_PACK_ATTR
1108 # undef FB_PACK_PUSH