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