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