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>
28 #include <type_traits>
33 #include <boost/operators.hpp>
34 #include <boost/type_traits.hpp>
35 #include <boost/mpl/if.hpp>
36 #include <boost/mpl/eval_if.hpp>
37 #include <boost/mpl/vector.hpp>
38 #include <boost/mpl/front.hpp>
39 #include <boost/mpl/filter_view.hpp>
40 #include <boost/mpl/identity.hpp>
41 #include <boost/mpl/placeholders.hpp>
42 #include <boost/mpl/empty.hpp>
43 #include <boost/mpl/size.hpp>
44 #include <boost/mpl/count.hpp>
46 #include <folly/FormatTraits.h>
47 #include <folly/Malloc.h>
48 #include <folly/Portability.h>
49 #include <folly/SmallLocks.h>
50 #include <folly/Traits.h>
51 #include <folly/portability/BitsFunctexcept.h>
52 #include <folly/portability/Constexpr.h>
53 #include <folly/portability/Malloc.h>
54 #include <folly/portability/TypeTraits.h>
56 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
57 #pragma GCC diagnostic push
58 #pragma GCC diagnostic ignored "-Wshadow"
62 //////////////////////////////////////////////////////////////////////
64 namespace small_vector_policy {
66 //////////////////////////////////////////////////////////////////////
69 * A flag which makes us refuse to use the heap at all. If we
70 * overflow the in situ capacity we throw an exception.
74 //////////////////////////////////////////////////////////////////////
76 } // small_vector_policy
78 //////////////////////////////////////////////////////////////////////
80 template<class T, std::size_t M, class A, class B, class C>
83 //////////////////////////////////////////////////////////////////////
88 * Move a range to a range of uninitialized memory. Assumes the
89 * ranges don't overlap.
92 typename std::enable_if<
93 !FOLLY_IS_TRIVIALLY_COPYABLE(T)
95 moveToUninitialized(T* first, T* last, T* out) {
98 for (; first != last; ++first, ++idx) {
99 new (&out[idx]) T(std::move(*first));
102 // Even for callers trying to give the strong guarantee
103 // (e.g. push_back) it's ok to assume here that we don't have to
104 // move things back and that it was a copy constructor that
105 // threw: if someone throws from a move constructor the effects
107 for (std::size_t i = 0; i < idx; ++i) {
114 // Specialization for trivially copyable types.
116 typename std::enable_if<
117 FOLLY_IS_TRIVIALLY_COPYABLE(T)
119 moveToUninitialized(T* first, T* last, T* out) {
120 std::memmove(out, first, (last - first) * sizeof *first);
124 * Move objects in memory to the right into some uninitialized
125 * memory, where the region overlaps. This doesn't just use
126 * std::move_backward because move_backward only works if all the
127 * memory is initialized to type T already.
130 typename std::enable_if<
131 !FOLLY_IS_TRIVIALLY_COPYABLE(T)
133 moveObjectsRight(T* first, T* lastConstructed, T* realLast) {
134 if (lastConstructed == realLast) {
138 T* end = first - 1; // Past the end going backwards.
139 T* out = realLast - 1;
140 T* in = lastConstructed - 1;
142 for (; in != end && out >= lastConstructed; --in, --out) {
143 new (out) T(std::move(*in));
145 for (; in != end; --in, --out) {
146 *out = std::move(*in);
148 for (; out >= lastConstructed; --out) {
152 // We want to make sure the same stuff is uninitialized memory
153 // if we exit via an exception (this is to make sure we provide
154 // the basic exception safety guarantee for insert functions).
155 if (out < lastConstructed) {
156 out = lastConstructed - 1;
158 for (auto it = out + 1; it != realLast; ++it) {
165 // Specialization for trivially copyable types. The call to
166 // std::move_backward here will just turn into a memmove. (TODO:
167 // change to std::is_trivially_copyable when that works.)
169 typename std::enable_if<
170 FOLLY_IS_TRIVIALLY_COPYABLE(T)
172 moveObjectsRight(T* first, T* lastConstructed, T* realLast) {
173 std::move_backward(first, lastConstructed, realLast);
177 * Populate a region of memory using `op' to construct elements. If
178 * anything throws, undo what we did.
180 template<class T, class Function>
181 void populateMemForward(T* mem, std::size_t n, Function const& op) {
184 for (size_t i = 0; i < n; ++i) {
189 for (std::size_t i = 0; i < idx; ++i) {
196 template<class SizeType, bool ShouldUseHeap>
197 struct IntegralSizePolicy {
198 typedef SizeType InternalSizeType;
200 IntegralSizePolicy() : size_(0) {}
203 static constexpr std::size_t policyMaxSize() {
204 return SizeType(~kExternMask);
207 std::size_t doSize() const {
208 return size_ & ~kExternMask;
211 std::size_t isExtern() const {
212 return kExternMask & size_;
215 void setExtern(bool b) {
217 size_ |= kExternMask;
219 size_ &= ~kExternMask;
223 void setSize(std::size_t sz) {
224 assert(sz <= policyMaxSize());
225 size_ = (kExternMask & size_) | SizeType(sz);
228 void swapSizePolicy(IntegralSizePolicy& o) {
229 std::swap(size_, o.size_);
233 static bool const kShouldUseHeap = ShouldUseHeap;
236 static SizeType const kExternMask =
237 kShouldUseHeap ? SizeType(1) << (sizeof(SizeType) * 8 - 1)
244 * If you're just trying to use this class, ignore everything about
245 * this next small_vector_base class thing.
247 * The purpose of this junk is to minimize sizeof(small_vector<>)
248 * and allow specifying the template parameters in whatever order is
249 * convenient for the user. There's a few extra steps here to try
250 * to keep the error messages at least semi-reasonable.
252 * Apologies for all the black magic.
254 namespace mpl = boost::mpl;
255 template<class Value,
256 std::size_t RequestedMaxInline,
260 struct small_vector_base {
261 typedef mpl::vector<InPolicyA,InPolicyB,InPolicyC> PolicyList;
264 * Determine the size type
266 typedef typename mpl::filter_view<
268 boost::is_integral<mpl::placeholders::_1>
270 typedef typename mpl::eval_if<
271 mpl::empty<Integrals>,
272 mpl::identity<std::size_t>,
273 mpl::front<Integrals>
276 static_assert(std::is_unsigned<SizeType>::value,
277 "Size type should be an unsigned integral type");
278 static_assert(mpl::size<Integrals>::value == 0 ||
279 mpl::size<Integrals>::value == 1,
280 "Multiple size types specified in small_vector<>");
283 * Determine whether we should allow spilling to the heap or not.
285 typedef typename mpl::count<
286 PolicyList,small_vector_policy::NoHeap
289 static_assert(HasNoHeap::value == 0 || HasNoHeap::value == 1,
290 "Multiple copies of small_vector_policy::NoHeap "
291 "supplied; this is probably a mistake");
294 * Make the real policy base classes.
296 typedef IntegralSizePolicy<SizeType,!HasNoHeap::value>
300 * Now inherit from them all. This is done in such a convoluted
301 * way to make sure we get the empty base optimizaton on all these
302 * types to keep sizeof(small_vector<>) minimal.
304 typedef boost::totally_ordered1<
305 small_vector<Value,RequestedMaxInline,InPolicyA,InPolicyB,InPolicyC>,
311 T* pointerFlagSet(T* p) {
312 return reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(p) | 1);
315 bool pointerFlagGet(T* p) {
316 return reinterpret_cast<uintptr_t>(p) & 1;
319 T* pointerFlagClear(T* p) {
320 return reinterpret_cast<T*>(
321 reinterpret_cast<uintptr_t>(p) & ~uintptr_t(1));
323 inline void* shiftPointer(void* p, size_t sizeBytes) {
324 return static_cast<char*>(p) + sizeBytes;
328 //////////////////////////////////////////////////////////////////////
330 template<class Value,
331 std::size_t RequestedMaxInline = 1,
332 class PolicyA = void,
333 class PolicyB = void,
334 class PolicyC = void>
336 : public detail::small_vector_base<
337 Value,RequestedMaxInline,PolicyA,PolicyB,PolicyC
340 typedef typename detail::small_vector_base<
341 Value,RequestedMaxInline,PolicyA,PolicyB,PolicyC
343 typedef typename BaseType::InternalSizeType InternalSizeType;
346 * Figure out the max number of elements we should inline. (If
347 * the user asks for less inlined elements than we can fit unioned
348 * into our value_type*, we will inline more than they asked.)
350 static constexpr std::size_t MaxInline{
351 constexpr_max(sizeof(Value*) / sizeof(Value), RequestedMaxInline)};
354 typedef std::size_t size_type;
355 typedef Value value_type;
356 typedef value_type& reference;
357 typedef value_type const& const_reference;
358 typedef value_type* iterator;
359 typedef value_type const* const_iterator;
360 typedef std::ptrdiff_t difference_type;
362 typedef std::reverse_iterator<iterator> reverse_iterator;
363 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
365 explicit small_vector() = default;
367 small_vector(small_vector const& o) {
371 std::uninitialized_copy(o.begin(), o.end(), begin());
373 if (this->isExtern()) {
381 small_vector(small_vector&& o)
382 noexcept(std::is_nothrow_move_constructible<Value>::value) {
386 std::uninitialized_copy(std::make_move_iterator(o.begin()),
387 std::make_move_iterator(o.end()),
389 this->setSize(o.size());
393 small_vector(std::initializer_list<value_type> il) {
394 constructImpl(il.begin(), il.end(), std::false_type());
397 explicit small_vector(size_type n) {
398 doConstruct(n, [&](void* p) { new (p) value_type(); });
401 small_vector(size_type n, value_type const& t) {
402 doConstruct(n, [&](void* p) { new (p) value_type(t); });
406 explicit small_vector(Arg arg1, Arg arg2) {
407 // Forward using std::is_arithmetic to get to the proper
408 // implementation; this disambiguates between the iterators and
409 // (size_t, value_type) meaning for this constructor.
410 constructImpl(arg1, arg2, std::is_arithmetic<Arg>());
414 for (auto& t : *this) {
417 if (this->isExtern()) {
422 small_vector& operator=(small_vector const& o) {
423 assign(o.begin(), o.end());
427 small_vector& operator=(small_vector&& o) {
428 // TODO: optimization:
429 // if both are internal, use move assignment where possible
430 if (this == &o) return *this;
436 bool operator==(small_vector const& o) const {
437 return size() == o.size() && std::equal(begin(), end(), o.begin());
440 bool operator<(small_vector const& o) const {
441 return std::lexicographical_compare(begin(), end(), o.begin(), o.end());
444 static constexpr size_type max_size() {
445 return !BaseType::kShouldUseHeap ? static_cast<size_type>(MaxInline)
446 : BaseType::policyMaxSize();
449 size_type size() const { return this->doSize(); }
450 bool empty() const { return !size(); }
452 iterator begin() { return data(); }
453 iterator end() { return data() + size(); }
454 const_iterator begin() const { return data(); }
455 const_iterator end() const { return data() + size(); }
456 const_iterator cbegin() const { return begin(); }
457 const_iterator cend() const { return end(); }
459 reverse_iterator rbegin() { return reverse_iterator(end()); }
460 reverse_iterator rend() { return reverse_iterator(begin()); }
462 const_reverse_iterator rbegin() const {
463 return const_reverse_iterator(end());
466 const_reverse_iterator rend() const {
467 return const_reverse_iterator(begin());
470 const_reverse_iterator crbegin() const { return rbegin(); }
471 const_reverse_iterator crend() const { return rend(); }
474 * Usually one of the simplest functions in a Container-like class
475 * but a bit more complex here. We have to handle all combinations
476 * of in-place vs. heap between this and o.
478 * Basic guarantee only. Provides the nothrow guarantee iff our
479 * value_type has a nothrow move or copy constructor.
481 void swap(small_vector& o) {
482 using std::swap; // Allow ADL on swap for our value_type.
484 if (this->isExtern() && o.isExtern()) {
485 this->swapSizePolicy(o);
487 auto thisCapacity = this->capacity();
488 auto oCapacity = o.capacity();
490 auto* tmp = u.pdata_.heap_;
491 u.pdata_.heap_ = o.u.pdata_.heap_;
492 o.u.pdata_.heap_ = tmp;
494 this->setCapacity(oCapacity);
495 o.setCapacity(thisCapacity);
500 if (!this->isExtern() && !o.isExtern()) {
501 auto& oldSmall = size() < o.size() ? *this : o;
502 auto& oldLarge = size() < o.size() ? o : *this;
504 for (size_type i = 0; i < oldSmall.size(); ++i) {
505 swap(oldSmall[i], oldLarge[i]);
508 size_type i = oldSmall.size();
509 const size_type ci = i;
511 for (; i < oldLarge.size(); ++i) {
512 auto addr = oldSmall.begin() + i;
513 new (addr) value_type(std::move(oldLarge[i]));
514 oldLarge[i].~value_type();
518 for (; i < oldLarge.size(); ++i) {
519 oldLarge[i].~value_type();
521 oldLarge.setSize(ci);
525 oldLarge.setSize(ci);
529 // isExtern != o.isExtern()
530 auto& oldExtern = o.isExtern() ? o : *this;
531 auto& oldIntern = o.isExtern() ? *this : o;
533 auto oldExternCapacity = oldExtern.capacity();
534 auto oldExternHeap = oldExtern.u.pdata_.heap_;
536 auto buff = oldExtern.u.buffer();
539 for (; i < oldIntern.size(); ++i) {
540 new (&buff[i]) value_type(std::move(oldIntern[i]));
541 oldIntern[i].~value_type();
544 for (size_type kill = 0; kill < i; ++kill) {
545 buff[kill].~value_type();
547 for (; i < oldIntern.size(); ++i) {
548 oldIntern[i].~value_type();
550 oldIntern.setSize(0);
551 oldExtern.u.pdata_.heap_ = oldExternHeap;
552 oldExtern.setCapacity(oldExternCapacity);
555 oldIntern.u.pdata_.heap_ = oldExternHeap;
556 this->swapSizePolicy(o);
557 oldIntern.setCapacity(oldExternCapacity);
560 void resize(size_type sz) {
562 erase(begin() + sz, end());
566 detail::populateMemForward(begin() + size(), sz - size(),
567 [&] (void* p) { new (p) value_type(); }
572 void resize(size_type sz, value_type const& v) {
574 erase(begin() + sz, end());
578 detail::populateMemForward(begin() + size(), sz - size(),
579 [&] (void* p) { new (p) value_type(v); }
584 value_type* data() noexcept {
585 return this->isExtern() ? u.heap() : u.buffer();
588 value_type const* data() const noexcept {
589 return this->isExtern() ? u.heap() : u.buffer();
592 template<class ...Args>
593 iterator emplace(const_iterator p, Args&&... args) {
595 emplace_back(std::forward<Args>(args)...);
600 * We implement emplace at places other than at the back with a
601 * temporary for exception safety reasons. It is possible to
602 * avoid having to do this, but it becomes hard to maintain the
603 * basic exception safety guarantee (unless you respond to a copy
604 * constructor throwing by clearing the whole vector).
606 * The reason for this is that otherwise you have to destruct an
607 * element before constructing this one in its place---if the
608 * constructor throws, you either need a nothrow default
609 * constructor or a nothrow copy/move to get something back in the
610 * "gap", and the vector requirements don't guarantee we have any
611 * of these. Clearing the whole vector is a legal response in
612 * this situation, but it seems like this implementation is easy
613 * enough and probably better.
615 return insert(p, value_type(std::forward<Args>(args)...));
618 void reserve(size_type sz) {
622 size_type capacity() const {
623 if (this->isExtern()) {
624 if (u.hasCapacity()) {
625 return u.getCapacity();
627 return malloc_usable_size(u.pdata_.heap_) / sizeof(value_type);
632 void shrink_to_fit() {
633 if (!this->isExtern()) {
637 small_vector tmp(begin(), end());
641 template<class ...Args>
642 void emplace_back(Args&&... args) {
643 // call helper function for static dispatch of special cases
644 emplaceBack(std::forward<Args>(args)...);
647 void emplace_back(const value_type& t) {
650 void emplace_back(value_type& t) {
654 void emplace_back(value_type&& t) {
655 push_back(std::move(t));
658 void push_back(value_type&& t) {
659 if (capacity() == size()) {
660 makeSize(std::max(size_type(2), 3 * size() / 2), &t, size());
662 new (end()) value_type(std::move(t));
664 this->setSize(size() + 1);
667 void push_back(value_type const& t) {
668 // TODO: we'd like to make use of makeSize (it can be optimized better,
669 // because it manipulates the internals)
670 // unfortunately the current implementation only supports moving from
671 // a supplied rvalue, and doing an extra move just to reuse it is a perf
673 if (size() == capacity()) {// && isInside(&t)) {
675 emplaceBack(std::move(tmp));
685 iterator insert(const_iterator constp, value_type&& t) {
686 iterator p = unconst(constp);
689 push_back(std::move(t));
693 auto offset = p - begin();
695 if (capacity() == size()) {
696 makeSize(size() + 1, &t, offset);
697 this->setSize(this->size() + 1);
699 makeSize(size() + 1);
700 detail::moveObjectsRight(data() + offset,
702 data() + size() + 1);
703 this->setSize(size() + 1);
704 data()[offset] = std::move(t);
706 return begin() + offset;
710 iterator insert(const_iterator p, value_type const& t) {
711 // Make a copy and forward to the rvalue value_type&& overload
713 return insert(p, value_type(t));
716 iterator insert(const_iterator pos, size_type n, value_type const& val) {
717 auto offset = pos - begin();
718 makeSize(size() + n);
719 detail::moveObjectsRight(data() + offset,
721 data() + size() + n);
722 this->setSize(size() + n);
723 std::generate_n(begin() + offset, n, [&] { return val; });
724 return begin() + offset;
728 iterator insert(const_iterator p, Arg arg1, Arg arg2) {
729 // Forward using std::is_arithmetic to get to the proper
730 // implementation; this disambiguates between the iterators and
731 // (size_t, value_type) meaning for this function.
732 return insertImpl(unconst(p), arg1, arg2, std::is_arithmetic<Arg>());
735 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
736 return insert(p, il.begin(), il.end());
739 iterator erase(const_iterator q) {
740 std::move(unconst(q) + 1, end(), unconst(q));
741 (data() + size() - 1)->~value_type();
742 this->setSize(size() - 1);
746 iterator erase(const_iterator q1, const_iterator q2) {
747 if (q1 == q2) return unconst(q1);
748 std::move(unconst(q2), end(), unconst(q1));
749 for (auto it = (end() - std::distance(q1, q2)); it != end(); ++it) {
752 this->setSize(size() - (q2 - q1));
757 erase(begin(), end());
761 void assign(Arg first, Arg last) {
763 insert(end(), first, last);
766 void assign(std::initializer_list<value_type> il) {
767 assign(il.begin(), il.end());
770 void assign(size_type n, const value_type& t) {
775 reference front() { assert(!empty()); return *begin(); }
776 reference back() { assert(!empty()); return *(end() - 1); }
777 const_reference front() const { assert(!empty()); return *begin(); }
778 const_reference back() const { assert(!empty()); return *(end() - 1); }
780 reference operator[](size_type i) {
782 return *(begin() + i);
785 const_reference operator[](size_type i) const {
787 return *(begin() + i);
790 reference at(size_type i) {
792 std::__throw_out_of_range("index out of range");
797 const_reference at(size_type i) const {
799 std::__throw_out_of_range("index out of range");
807 * This is doing the same like emplace_back, but we need this helper
808 * to catch the special case - see the next overload function..
810 template<class ...Args>
811 void emplaceBack(Args&&... args) {
812 makeSize(size() + 1);
813 new (end()) value_type(std::forward<Args>(args)...);
814 this->setSize(size() + 1);
817 static iterator unconst(const_iterator it) {
818 return const_cast<iterator>(it);
821 // The std::false_type argument is part of disambiguating the
822 // iterator insert functions from integral types (see insert().)
824 iterator insertImpl(iterator pos, It first, It last, std::false_type) {
825 typedef typename std::iterator_traits<It>::iterator_category categ;
826 if (std::is_same<categ,std::input_iterator_tag>::value) {
827 auto offset = pos - begin();
828 while (first != last) {
829 pos = insert(pos, *first++);
832 return begin() + offset;
835 auto distance = std::distance(first, last);
836 auto offset = pos - begin();
837 makeSize(size() + distance);
838 detail::moveObjectsRight(data() + offset,
840 data() + size() + distance);
841 this->setSize(size() + distance);
842 std::copy_n(first, distance, begin() + offset);
843 return begin() + offset;
846 iterator insertImpl(iterator pos, size_type n, const value_type& val,
848 // The true_type means this should call the size_t,value_type
849 // overload. (See insert().)
850 return insert(pos, n, val);
853 // The std::false_type argument came from std::is_arithmetic as part
854 // of disambiguating an overload (see the comment in the
857 void constructImpl(It first, It last, std::false_type) {
858 typedef typename std::iterator_traits<It>::iterator_category categ;
859 if (std::is_same<categ,std::input_iterator_tag>::value) {
860 // With iterators that only allow a single pass, we can't really
861 // do anything sane here.
862 while (first != last) {
863 emplace_back(*first++);
868 auto distance = std::distance(first, last);
870 this->setSize(distance);
872 detail::populateMemForward(data(), distance,
873 [&] (void* p) { new (p) value_type(*first++); }
876 if (this->isExtern()) {
883 template <typename InitFunc>
884 void doConstruct(size_type n, InitFunc&& func) {
888 detail::populateMemForward(data(), n, std::forward<InitFunc>(func));
890 if (this->isExtern()) {
897 // The true_type means we should forward to the size_t,value_type
899 void constructImpl(size_type n, value_type const& val, std::true_type) {
900 doConstruct(n, [&](void* p) { new (p) value_type(val); });
903 void makeSize(size_type size, value_type* v = nullptr) {
904 makeSize(size, v, size - 1);
908 * Ensure we have a large enough memory region to be size `size'.
909 * Will move/copy elements if we are spilling to heap_ or needed to
910 * allocate a new region, but if resized in place doesn't initialize
911 * anything in the new region. In any case doesn't change size().
912 * Supports insertion of new element during reallocation by given
913 * pointer to new element and position of new element.
914 * NOTE: If reallocation is not needed, and new element should be
915 * inserted in the middle of vector (not at the end), do the move
916 * objects and insertion outside the function, otherwise exception is thrown.
918 void makeSize(size_type size, value_type* v, size_type pos) {
919 if (size > this->max_size()) {
920 throw std::length_error("max_size exceeded in small_vector");
922 if (size <= this->capacity()) {
926 auto needBytes = size * sizeof(value_type);
927 // If the capacity isn't explicitly stored inline, but the heap
928 // allocation is grown to over some threshold, we should store
929 // a capacity at the front of the heap allocation.
930 bool heapifyCapacity =
931 !kHasInlineCapacity && needBytes > kHeapifyCapacityThreshold;
932 if (heapifyCapacity) {
933 needBytes += kHeapifyCapacitySize;
935 auto const sizeBytes = goodMallocSize(needBytes);
936 void* newh = checkedMalloc(sizeBytes);
937 // We expect newh to be at least 2-aligned, because we want to
938 // use its least significant bit as a flag.
939 assert(!detail::pointerFlagGet(newh));
941 value_type* newp = static_cast<value_type*>(
943 detail::shiftPointer(newh, kHeapifyCapacitySize) :
949 new (&newp[pos]) value_type(std::move(*v));
955 // move old elements to the left of the new one
957 detail::moveToUninitialized(begin(), begin() + pos, newp);
959 newp[pos].~value_type();
964 // move old elements to the right of the new one
967 detail::moveToUninitialized(begin() + pos, end(), newp + pos + 1);
970 for (size_type i = 0; i <= pos; ++i) {
971 newp[i].~value_type();
977 // move without inserting new element
979 detail::moveToUninitialized(begin(), end(), newp);
985 for (auto& val : *this) {
989 if (this->isExtern()) {
992 auto availableSizeBytes = sizeBytes;
993 if (heapifyCapacity) {
994 u.pdata_.heap_ = detail::pointerFlagSet(newh);
995 availableSizeBytes -= kHeapifyCapacitySize;
997 u.pdata_.heap_ = newh;
999 this->setExtern(true);
1000 this->setCapacity(availableSizeBytes / sizeof(value_type));
1004 * This will set the capacity field, stored inline in the storage_ field
1005 * if there is sufficient room to store it.
1007 void setCapacity(size_type newCapacity) {
1008 assert(this->isExtern());
1009 if (u.hasCapacity()) {
1010 assert(newCapacity < std::numeric_limits<InternalSizeType>::max());
1011 u.setCapacity(newCapacity);
1016 struct HeapPtrWithCapacity {
1018 InternalSizeType capacity_;
1020 InternalSizeType getCapacity() const {
1023 void setCapacity(InternalSizeType c) {
1029 // Lower order bit of heap_ is used as flag to indicate whether capacity is
1030 // stored at the front of the heap allocation.
1033 InternalSizeType getCapacity() const {
1034 assert(detail::pointerFlagGet(heap_));
1035 return *static_cast<InternalSizeType*>(detail::pointerFlagClear(heap_));
1037 void setCapacity(InternalSizeType c) {
1038 *static_cast<InternalSizeType*>(detail::pointerFlagClear(heap_)) = c;
1042 #if (FOLLY_X64 || FOLLY_PPC64)
1043 typedef unsigned char InlineStorageDataType[sizeof(value_type) * MaxInline];
1045 typedef typename std::aligned_storage<
1046 sizeof(value_type) * MaxInline,
1048 >::type InlineStorageDataType;
1051 typedef typename std::conditional<
1052 sizeof(value_type) * MaxInline != 0,
1053 InlineStorageDataType,
1055 >::type InlineStorageType;
1057 static bool const kHasInlineCapacity =
1058 sizeof(HeapPtrWithCapacity) < sizeof(InlineStorageType);
1060 // This value should we multiple of word size.
1061 static size_t const kHeapifyCapacitySize = sizeof(
1062 typename std::aligned_storage<
1063 sizeof(InternalSizeType),
1066 // Threshold to control capacity heapifying.
1067 static size_t const kHeapifyCapacityThreshold =
1068 100 * kHeapifyCapacitySize;
1070 typedef typename std::conditional<
1072 HeapPtrWithCapacity,
1074 >::type PointerType;
1077 explicit Data() { pdata_.heap_ = 0; }
1080 InlineStorageType storage_;
1082 value_type* buffer() noexcept {
1083 void* vp = &storage_;
1084 return static_cast<value_type*>(vp);
1086 value_type const* buffer() const noexcept {
1087 return const_cast<Data*>(this)->buffer();
1089 value_type* heap() noexcept {
1090 if (kHasInlineCapacity || !detail::pointerFlagGet(pdata_.heap_)) {
1091 return static_cast<value_type*>(pdata_.heap_);
1093 return static_cast<value_type*>(
1094 detail::shiftPointer(
1095 detail::pointerFlagClear(pdata_.heap_), kHeapifyCapacitySize));
1097 value_type const* heap() const noexcept {
1098 return const_cast<Data*>(this)->heap();
1101 bool hasCapacity() const {
1102 return kHasInlineCapacity || detail::pointerFlagGet(pdata_.heap_);
1104 InternalSizeType getCapacity() const {
1105 return pdata_.getCapacity();
1107 void setCapacity(InternalSizeType c) {
1108 pdata_.setCapacity(c);
1112 auto vp = detail::pointerFlagClear(pdata_.heap_);
1115 } FOLLY_PACK_ATTR u;
1119 //////////////////////////////////////////////////////////////////////
1121 // Basic guarantee only, or provides the nothrow guarantee iff T has a
1122 // nothrow move or copy constructor.
1123 template<class T, std::size_t MaxInline, class A, class B, class C>
1124 void swap(small_vector<T,MaxInline,A,B,C>& a,
1125 small_vector<T,MaxInline,A,B,C>& b) {
1129 //////////////////////////////////////////////////////////////////////
1134 template <class T, size_t M, class A, class B, class C>
1135 struct IndexableTraits<small_vector<T, M, A, B, C>>
1136 : public IndexableTraitsSeq<small_vector<T, M, A, B, C>> {
1139 } // namespace detail
1141 } // namespace folly
1143 #pragma GCC diagnostic pop