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