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 class 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 (size_t 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*>(
 418       reinterpret_cast<uintptr_t>(p) & ~uintptr_t(1));
 419   }
 420   inline void* shiftPointer(void* p, size_t sizeBytes) {
 421     return static_cast<char*>(p) + sizeBytes;
 422   }
 423 }
 424
 425 //////////////////////////////////////////////////////////////////////
 426
 427 template<class Value,
 428          std::size_t RequestedMaxInline    = 1,
 429          class PolicyA                     = void,
 430          class PolicyB                     = void,
 431          class PolicyC                     = void>
 432 class small_vector
 433   : public detail::small_vector_base<
 434       Value,RequestedMaxInline,PolicyA,PolicyB,PolicyC
 435     >::type
 436 {
 437   typedef typename detail::small_vector_base<
 438     Value,RequestedMaxInline,PolicyA,PolicyB,PolicyC
 439   >::type BaseType;
 440   typedef typename BaseType::InternalSizeType InternalSizeType;
 441
 442   /*
 443    * Figure out the max number of elements we should inline.  (If
 444    * the user asks for less inlined elements than we can fit unioned
 445    * into our value_type*, we will inline more than they asked.)
 446    */
 447   enum {
 448     MaxInline = boost::mpl::max<
 449                   boost::mpl::int_<sizeof(Value*) / sizeof(Value)>,
 450                   boost::mpl::int_<RequestedMaxInline>
 451                 >::type::value
 452   };
 453
 454 public:
 455   typedef std::size_t size_type;
 456   typedef Value              value_type;
 457   typedef value_type&        reference;
 458   typedef value_type const&  const_reference;
 459   typedef value_type*        iterator;
 460   typedef value_type const*  const_iterator;
 461   typedef std::ptrdiff_t     difference_type;
 462
 463   typedef std::reverse_iterator<iterator>       reverse_iterator;
 464   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 465
 466   explicit small_vector() {}
 467
 468   small_vector(small_vector const& o) {
 469     assign(o.begin(), o.end());
 470   }
 471
 472   small_vector(small_vector&& o) {
 473     *this = std::move(o);
 474   }
 475
 476   small_vector(std::initializer_list<value_type> il) {
 477     constructImpl(il.begin(), il.end(), std::false_type());
 478   }
 479
 480   explicit small_vector(size_type n, value_type const& t = value_type()) {
 481     doConstruct(n, t);
 482   }
 483
 484   template<class Arg>
 485   explicit small_vector(Arg arg1, Arg arg2)  {
 486     // Forward using std::is_arithmetic to get to the proper
 487     // implementation; this disambiguates between the iterators and
 488     // (size_t, value_type) meaning for this constructor.
 489     constructImpl(arg1, arg2, std::is_arithmetic<Arg>());
 490   }
 491
 492   ~small_vector() {
 493     for (auto& t : *this) {
 494       (&t)->~value_type();
 495     }
 496     if (this->isExtern()) {
 497       u.freeHeap();
 498     }
 499   }
 500
 501   small_vector& operator=(small_vector const& o) {
 502     assign(o.begin(), o.end());
 503     return *this;
 504   }
 505
 506   small_vector& operator=(small_vector&& o) {
 507     clear();
 508     if (!o.isExtern()) {
 509       makeSize(o.size());
 510       for (std::size_t i = 0; i < o.size(); ++i) {
 511         new (data() + i) value_type(std::move(o[i]));
 512       }
 513       this->setSize(o.size());
 514     } else {
 515       swap(o);
 516     }
 517     return *this;
 518   }
 519
 520   bool operator==(small_vector const& o) const {
 521     return size() == o.size() && std::equal(begin(), end(), o.begin());
 522   }
 523
 524   bool operator<(small_vector const& o) const {
 525     return std::lexicographical_compare(begin(), end(), o.begin(), o.end());
 526   }
 527
 528   size_type max_size() const {
 529     return !BaseType::kShouldUseHeap ? MaxInline
 530                                      : this->policyMaxSize();
 531   }
 532
 533   size_type size()         const { return this->doSize(); }
 534   bool      empty()        const { return !size(); }
 535
 536   iterator       begin()         { return data(); }
 537   iterator       end()           { return data() + size(); }
 538   const_iterator begin()   const { return data(); }
 539   const_iterator end()     const { return data() + size(); }
 540   const_iterator cbegin()  const { return begin(); }
 541   const_iterator cend()    const { return end(); }
 542
 543   reverse_iterator       rbegin()        { return reverse_iterator(end()); }
 544   reverse_iterator       rend()          { return reverse_iterator(begin()); }
 545
 546   const_reverse_iterator rbegin() const {
 547     return const_reverse_iterator(end());
 548   }
 549
 550   const_reverse_iterator rend() const {
 551     return const_reverse_iterator(begin());
 552   }
 553
 554   const_reverse_iterator crbegin() const { return rbegin(); }
 555   const_reverse_iterator crend()   const { return rend(); }
 556
 557   /*
 558    * Usually one of the simplest functions in a Container-like class
 559    * but a bit more complex here.  We have to handle all combinations
 560    * of in-place vs. heap between this and o.
 561    *
 562    * Basic guarantee only.  Provides the nothrow guarantee iff our
 563    * value_type has a nothrow move or copy constructor.
 564    */
 565   void swap(small_vector& o) {
 566     using std::swap; // Allow ADL on swap for our value_type.
 567
 568     if (this->isExtern() && o.isExtern()) {
 569       this->swapSizePolicy(o);
 570
 571       auto thisCapacity = this->capacity();
 572       auto oCapacity = o.capacity();
 573
 574       std::swap(unpackHack(&u.pdata_.heap_), unpackHack(&o.u.pdata_.heap_));
 575
 576       this->setCapacity(oCapacity);
 577       o.setCapacity(thisCapacity);
 578
 579       return;
 580     }
 581
 582     if (!this->isExtern() && !o.isExtern()) {
 583       auto& oldSmall = size() < o.size() ? *this : o;
 584       auto& oldLarge = size() < o.size() ? o : *this;
 585
 586       for (size_type i = 0; i < oldSmall.size(); ++i) {
 587         swap(oldSmall[i], oldLarge[i]);
 588       }
 589
 590       size_type i = oldSmall.size();
 591       try {
 592         for (; i < oldLarge.size(); ++i) {
 593           new (&oldSmall[i]) value_type(std::move(oldLarge[i]));
 594           oldLarge[i].~value_type();
 595         }
 596       } catch (...) {
 597         for (; i < oldLarge.size(); ++i) {
 598           oldLarge[i].~value_type();
 599         }
 600         oldLarge.setSize(oldSmall.size());
 601         throw;
 602       }
 603       this->swapSizePolicy(o);
 604       return;
 605     }
 606
 607     // isExtern != o.isExtern()
 608     auto& oldExtern = o.isExtern() ? o : *this;
 609     auto& oldIntern = o.isExtern() ? *this : o;
 610
 611     auto oldExternCapacity = oldExtern.capacity();
 612     auto oldExternHeap     = oldExtern.u.pdata_.heap_;
 613
 614     auto buff = oldExtern.u.buffer();
 615     size_type i = 0;
 616     try {
 617       for (; i < oldIntern.size(); ++i) {
 618         new (&buff[i]) value_type(std::move(oldIntern[i]));
 619         oldIntern[i].~value_type();
 620       }
 621     } catch (...) {
 622       for (size_type kill = 0; kill < i; ++kill) {
 623         buff[kill].~value_type();
 624       }
 625       for (; i < oldIntern.size(); ++i) {
 626         oldIntern[i].~value_type();
 627       }
 628       oldIntern.setSize(0);
 629       oldExtern.u.pdata_.heap_ = oldExternHeap;
 630       oldExtern.setCapacity(oldExternCapacity);
 631       throw;
 632     }
 633     oldIntern.u.pdata_.heap_ = oldExternHeap;
 634     this->swapSizePolicy(o);
 635     oldIntern.setCapacity(oldExternCapacity);
 636   }
 637
 638   void resize(size_type sz) {
 639     if (sz < size()) {
 640       erase(begin() + sz, end());
 641       return;
 642     }
 643     makeSize(sz);
 644     detail::populateMemForward(begin() + size(), sz - size(),
 645       [&] (void* p) { new (p) value_type(); }
 646     );
 647     this->setSize(sz);
 648   }
 649
 650   void resize(size_type sz, value_type const& v) {
 651     if (sz < size()) {
 652       erase(begin() + sz, end());
 653       return;
 654     }
 655     makeSize(sz);
 656     detail::populateMemForward(begin() + size(), sz - size(),
 657       [&] (void* p) { new (p) value_type(v); }
 658     );
 659     this->setSize(sz);
 660   }
 661
 662   value_type* data() noexcept {
 663     return this->isExtern() ? u.heap() : u.buffer();
 664   }
 665
 666   value_type const* data() const noexcept {
 667     return this->isExtern() ? u.heap() : u.buffer();
 668   }
 669
 670   template<class ...Args>
 671   iterator emplace(const_iterator p, Args&&... args) {
 672     if (p == cend()) {
 673       emplace_back(std::forward<Args>(args)...);
 674       return end() - 1;
 675     }
 676
 677     /*
 678      * We implement emplace at places other than at the back with a
 679      * temporary for exception safety reasons.  It is possible to
 680      * avoid having to do this, but it becomes hard to maintain the
 681      * basic exception safety guarantee (unless you respond to a copy
 682      * constructor throwing by clearing the whole vector).
 683      *
 684      * The reason for this is that otherwise you have to destruct an
 685      * element before constructing this one in its place---if the
 686      * constructor throws, you either need a nothrow default
 687      * constructor or a nothrow copy/move to get something back in the
 688      * "gap", and the vector requirements don't guarantee we have any
 689      * of these.  Clearing the whole vector is a legal response in
 690      * this situation, but it seems like this implementation is easy
 691      * enough and probably better.
 692      */
 693     return insert(p, value_type(std::forward<Args>(args)...));
 694   }
 695
 696   void reserve(size_type sz) {
 697     makeSize(sz);
 698   }
 699
 700   size_type capacity() const {
 701     if (this->isExtern()) {
 702       if (u.hasCapacity()) {
 703         return *u.getCapacity();
 704       }
 705       return malloc_usable_size(u.pdata_.heap_) / sizeof(value_type);
 706     }
 707     return MaxInline;
 708   }
 709
 710   void shrink_to_fit() {
 711     if (!this->isExtern()) {
 712       return;
 713     }
 714
 715     small_vector tmp(begin(), end());
 716     tmp.swap(*this);
 717   }
 718
 719   template<class ...Args>
 720   void emplace_back(Args&&... args) {
 721     // call helper function for static dispatch of special cases
 722     emplaceBack(std::forward<Args>(args)...);
 723   }
 724
 725   void push_back(value_type&& t) {
 726     if (capacity() == size()) {
 727       makeSize(std::max(size_type(2), 3 * size() / 2), &t, size());
 728     } else {
 729       new (end()) value_type(std::move(t));
 730     }
 731     this->setSize(size() + 1);
 732   }
 733
 734   void push_back(value_type const& t) {
 735     // Make a copy and forward to the rvalue value_type&& overload
 736     // above.
 737     push_back(value_type(t));
 738   }
 739
 740   void pop_back() {
 741     erase(end() - 1);
 742   }
 743
 744   iterator insert(const_iterator constp, value_type&& t) {
 745     iterator p = unconst(constp);
 746
 747     if (p == end()) {
 748       push_back(std::move(t));
 749       return end() - 1;
 750     }
 751
 752     auto offset = p - begin();
 753
 754     if (capacity() == size()) {
 755       makeSize(size() + 1, &t, offset);
 756       this->setSize(this->size() + 1);
 757     } else {
 758       makeSize(size() + 1);
 759       detail::moveObjectsRight(data() + offset,
 760                                data() + size(),
 761                                data() + size() + 1);
 762       this->setSize(size() + 1);
 763       data()[offset] = std::move(t);
 764     }
 765     return begin() + offset;
 766
 767   }
 768
 769   iterator insert(const_iterator p, value_type const& t) {
 770     // Make a copy and forward to the rvalue value_type&& overload
 771     // above.
 772     return insert(p, value_type(t));
 773   }
 774
 775   iterator insert(const_iterator pos, size_type n, value_type const& val) {
 776     auto offset = pos - begin();
 777     makeSize(size() + n);
 778     detail::moveObjectsRight(data() + offset,
 779                              data() + size(),
 780                              data() + size() + n);
 781     this->setSize(size() + n);
 782     std::generate_n(begin() + offset, n, [&] { return val; });
 783     return begin() + offset;
 784   }
 785
 786   template<class Arg>
 787   iterator insert(const_iterator p, Arg arg1, Arg arg2) {
 788     // Forward using std::is_arithmetic to get to the proper
 789     // implementation; this disambiguates between the iterators and
 790     // (size_t, value_type) meaning for this function.
 791     return insertImpl(unconst(p), arg1, arg2, std::is_arithmetic<Arg>());
 792   }
 793
 794   iterator insert(const_iterator p, std::initializer_list<value_type> il) {
 795     return insert(p, il.begin(), il.end());
 796   }
 797
 798   iterator erase(const_iterator q) {
 799     std::move(unconst(q) + 1, end(), unconst(q));
 800     (data() + size() - 1)->~value_type();
 801     this->setSize(size() - 1);
 802     return unconst(q);
 803   }
 804
 805   iterator erase(const_iterator q1, const_iterator q2) {
 806     std::move(unconst(q2), end(), unconst(q1));
 807     for (auto it = q1; it != end(); ++it) {
 808       it->~value_type();
 809     }
 810     this->setSize(size() - (q2 - q1));
 811     return unconst(q1);
 812   }
 813
 814   void clear() {
 815     erase(begin(), end());
 816   }
 817
 818   template<class Arg>
 819   void assign(Arg first, Arg last) {
 820     clear();
 821     insert(end(), first, last);
 822   }
 823
 824   void assign(std::initializer_list<value_type> il) {
 825     assign(il.begin(), il.end());
 826   }
 827
 828   void assign(size_type n, const value_type& t) {
 829     clear();
 830     insert(end(), n, t);
 831   }
 832
 833   reference front()             { assert(!empty()); return *begin(); }
 834   reference back()              { assert(!empty()); return *(end() - 1); }
 835   const_reference front() const { assert(!empty()); return *begin(); }
 836   const_reference back() const  { assert(!empty()); return *(end() - 1); }
 837
 838   reference operator[](size_type i) {
 839     assert(i < size());
 840     return *(begin() + i);
 841   }
 842
 843   const_reference operator[](size_type i) const {
 844     assert(i < size());
 845     return *(begin() + i);
 846   }
 847
 848   reference at(size_type i) {
 849     if (i >= size()) {
 850       throw std::out_of_range("index out of range");
 851     }
 852     return (*this)[i];
 853   }
 854
 855   const_reference at(size_type i) const {
 856     if (i >= size()) {
 857       throw std::out_of_range("index out of range");
 858     }
 859     return (*this)[i];
 860   }
 861
 862 private:
 863
 864   /*
 865    * This is doing the same like emplace_back, but we need this helper
 866    * to catch the special case - see the next overload function..
 867    */
 868   template<class ...Args>
 869   void emplaceBack(Args&&... args) {
 870     makeSize(size() + 1);
 871     new (end()) value_type(std::forward<Args>(args)...);
 872     this->setSize(size() + 1);
 873   }
 874
 875   /*
 876    * Special case of emplaceBack for rvalue
 877    */
 878   void emplaceBack(value_type&& t) {
 879     push_back(std::move(t));
 880   }
 881
 882   static iterator unconst(const_iterator it) {
 883     return const_cast<iterator>(it);
 884   }
 885
 886   /*
 887    * g++ doesn't allow you to bind a non-const reference to a member
 888    * of a packed structure, presumably because it would make it too
 889    * easy to accidentally make an unaligned memory access?
 890    */
 891   template<class T> static T& unpackHack(T* p) {
 892     return *p;
 893   }
 894
 895   // The std::false_type argument is part of disambiguating the
 896   // iterator insert functions from integral types (see insert().)
 897   template<class It>
 898   iterator insertImpl(iterator pos, It first, It last, std::false_type) {
 899     typedef typename std::iterator_traits<It>::iterator_category categ;
 900     if (std::is_same<categ,std::input_iterator_tag>::value) {
 901       auto offset = pos - begin();
 902       while (first != last) {
 903         pos = insert(pos, *first++);
 904         ++pos;
 905       }
 906       return begin() + offset;
 907     }
 908
 909     auto distance = std::distance(first, last);
 910     auto offset = pos - begin();
 911     makeSize(size() + distance);
 912     detail::moveObjectsRight(data() + offset,
 913                              data() + size(),
 914                              data() + size() + distance);
 915     this->setSize(size() + distance);
 916     std::copy_n(first, distance, begin() + offset);
 917     return begin() + offset;
 918   }
 919
 920   iterator insertImpl(iterator pos, size_type n, const value_type& val,
 921       std::true_type) {
 922     // The true_type means this should call the size_t,value_type
 923     // overload.  (See insert().)
 924     return insert(pos, n, val);
 925   }
 926
 927   // The std::false_type argument came from std::is_arithmetic as part
 928   // of disambiguating an overload (see the comment in the
 929   // constructor).
 930   template<class It>
 931   void constructImpl(It first, It last, std::false_type) {
 932     typedef typename std::iterator_traits<It>::iterator_category categ;
 933     if (std::is_same<categ,std::input_iterator_tag>::value) {
 934       // With iterators that only allow a single pass, we can't really
 935       // do anything sane here.
 936       while (first != last) {
 937         push_back(*first++);
 938       }
 939       return;
 940     }
 941
 942     auto distance = std::distance(first, last);
 943     makeSize(distance);
 944     this->setSize(distance);
 945
 946     detail::populateMemForward(data(), distance,
 947       [&] (void* p) { new (p) value_type(*first++); }
 948     );
 949   }
 950
 951   void doConstruct(size_type n, value_type const& val) {
 952     makeSize(n);
 953     this->setSize(n);
 954     detail::populateMemForward(data(), n,
 955       [&] (void* p) { new (p) value_type(val); }
 956     );
 957   }
 958
 959   // The true_type means we should forward to the size_t,value_type
 960   // overload.
 961   void constructImpl(size_type n, value_type const& val, std::true_type) {
 962     doConstruct(n, val);
 963   }
 964
 965   void makeSize(size_type size, value_type* v = NULL) {
 966     makeSize(size, v, size - 1);
 967   }
 968
 969   /*
 970    * Ensure we have a large enough memory region to be size `size'.
 971    * Will move/copy elements if we are spilling to heap_ or needed to
 972    * allocate a new region, but if resized in place doesn't initialize
 973    * anything in the new region.  In any case doesn't change size().
 974    * Supports insertion of new element during reallocation by given
 975    * pointer to new element and position of new element.
 976    * NOTE: If reallocation is not needed, and new element should be
 977    * inserted in the middle of vector (not at the end), do the move
 978    * objects and insertion outside the function, otherwise exception is thrown.
 979    */
 980   void makeSize(size_type size, value_type* v, size_type pos) {
 981     if (size > this->max_size()) {
 982       throw std::length_error("max_size exceeded in small_vector");
 983     }
 984     if (size <= this->capacity()) {
 985       return;
 986     }
 987
 988     auto needBytes = size * sizeof(value_type);
 989     // If the capacity isn't explicitly stored inline, but the heap
 990     // allocation is grown to over some threshold, we should store
 991     // a capacity at the front of the heap allocation.
 992     bool heapifyCapacity =
 993       !kHasInlineCapacity && needBytes > kHeapifyCapacityThreshold;
 994     if (heapifyCapacity) {
 995       needBytes += kHeapifyCapacitySize;
 996     }
 997     auto const sizeBytes = goodMallocSize(needBytes);
 998     void* newh = checkedMalloc(sizeBytes);
 999     // We expect newh to be at least 2-aligned, because we want to
1000     // use its least significant bit as a flag.
1001     assert(!detail::pointerFlagGet(newh));
1002
1003     value_type* newp = static_cast<value_type*>(
1004       heapifyCapacity ?
1005         detail::shiftPointer(newh, kHeapifyCapacitySize) :
1006         newh);
1007
1008     if (v != NULL) {
1009       // move new element
1010       try {
1011         new (&newp[pos]) value_type(std::move(*v));
1012       } catch (...) {
1013         std::free(newh);
1014         throw;
1015       }
1016
1017       // move old elements to the left of the new one
1018       try {
1019         detail::moveToUninitialized(begin(), begin() + pos, newp);
1020       } catch (...) {
1021         newp[pos].~value_type();
1022         std::free(newh);
1023         throw;
1024       }
1025
1026       // move old elements to the right of the new one
1027       try {
1028         if (pos < size-1) {
1029           detail::moveToUninitialized(begin() + pos, end(), newp + pos + 1);
1030         }
1031       } catch (...) {
1032         for (size_type i = 0; i <= pos; ++i) {
1033           newp[i].~value_type();
1034         }
1035         std::free(newh);
1036         throw;
1037       }
1038     } else {
1039       // move without inserting new element
1040       try {
1041         detail::moveToUninitialized(begin(), end(), newp);
1042       } catch (...) {
1043         std::free(newh);
1044         throw;
1045       }
1046     }
1047     for (auto& val : *this) {
1048       val.~value_type();
1049     }
1050
1051     if (this->isExtern()) {
1052       u.freeHeap();
1053     }
1054     auto availableSizeBytes = sizeBytes;
1055     if (heapifyCapacity) {
1056       u.pdata_.heap_ = detail::pointerFlagSet(newh);
1057       availableSizeBytes -= kHeapifyCapacitySize;
1058     } else {
1059       u.pdata_.heap_ = newh;
1060     }
1061     this->setExtern(true);
1062     this->setCapacity(availableSizeBytes / sizeof(value_type));
1063   }
1064
1065   /*
1066    * This will set the capacity field, stored inline in the storage_ field
1067    * if there is sufficient room to store it.
1068    */
1069   void setCapacity(size_type newCapacity) {
1070     assert(this->isExtern());
1071     if (u.hasCapacity()) {
1072       assert(newCapacity < std::numeric_limits<InternalSizeType>::max());
1073       *u.getCapacity() = InternalSizeType(newCapacity);
1074     }
1075   }
1076
1077 private:
1078   struct HeapPtrWithCapacity {
1079     void* heap_;
1080     InternalSizeType capacity_;
1081
1082     InternalSizeType* getCapacity() {
1083       return &capacity_;
1084     }
1085   } FB_PACKED;
1086
1087   struct HeapPtr {
1088     // Lower order bit of heap_ is used as flag to indicate whether capacity is
1089     // stored at the front of the heap allocation.
1090     void* heap_;
1091
1092     InternalSizeType* getCapacity() {
1093       assert(detail::pointerFlagGet(heap_));
1094       return static_cast<InternalSizeType*>(
1095         detail::pointerFlagClear(heap_));
1096     }
1097   } FB_PACKED;
1098
1099 #if defined(__x86_64_)
1100   typedef unsigned char InlineStorageType[sizeof(value_type) * MaxInline];
1101 #else
1102   typedef typename std::aligned_storage<
1103     sizeof(value_type) * MaxInline,
1104     alignof(value_type)
1105   >::type InlineStorageType;
1106 #endif
1107
1108   static bool const kHasInlineCapacity =
1109     sizeof(HeapPtrWithCapacity) < sizeof(InlineStorageType);
1110
1111   // This value should we multiple of word size.
1112   static size_t const kHeapifyCapacitySize = sizeof(
1113     typename std::aligned_storage<
1114       sizeof(InternalSizeType),
1115       alignof(value_type)
1116     >::type);
1117   // Threshold to control capacity heapifying.
1118   static size_t const kHeapifyCapacityThreshold =
1119     100 * kHeapifyCapacitySize;
1120
1121   typedef typename std::conditional<
1122     kHasInlineCapacity,
1123     HeapPtrWithCapacity,
1124     HeapPtr
1125   >::type PointerType;
1126
1127   union Data {
1128     explicit Data() { pdata_.heap_ = 0; }
1129
1130     PointerType pdata_;
1131     InlineStorageType storage_;
1132
1133     value_type* buffer() noexcept {
1134       void* vp = &storage_;
1135       return static_cast<value_type*>(vp);
1136     }
1137     value_type const* buffer() const noexcept {
1138       return const_cast<Data*>(this)->buffer();
1139     }
1140     value_type* heap() noexcept {
1141       if (kHasInlineCapacity || !detail::pointerFlagGet(pdata_.heap_)) {
1142         return static_cast<value_type*>(pdata_.heap_);
1143       }
1144       return static_cast<value_type*>(
1145         detail::shiftPointer(
1146           detail::pointerFlagClear(pdata_.heap_), kHeapifyCapacitySize));
1147     }
1148     value_type const* heap() const noexcept {
1149       return const_cast<Data*>(this)->heap();
1150     }
1151
1152     bool hasCapacity() const {
1153       return kHasInlineCapacity || detail::pointerFlagGet(pdata_.heap_);
1154     }
1155     InternalSizeType* getCapacity() {
1156       return pdata_.getCapacity();
1157     }
1158     InternalSizeType* getCapacity() const {
1159       return const_cast<Data*>(this)->getCapacity();
1160     }
1161
1162     void freeHeap() {
1163       auto vp = detail::pointerFlagClear(pdata_.heap_);
1164       std::free(vp);
1165     }
1166   } FB_PACKED u;
1167 } FB_PACKED;
1168
1169 //////////////////////////////////////////////////////////////////////
1170
1171 // Basic guarantee only, or provides the nothrow guarantee iff T has a
1172 // nothrow move or copy constructor.
1173 template<class T, std::size_t MaxInline, class A, class B, class C>
1174 void swap(small_vector<T,MaxInline,A,B,C>& a,
1175           small_vector<T,MaxInline,A,B,C>& b) {
1176   a.swap(b);
1177 }
1178
1179 //////////////////////////////////////////////////////////////////////
1180
1181 }
1182
1183 #ifdef FB_PACKED
1184 # undef FB_PACKED
1185 #endif
1186
1187 #endif