folly/small_vector.h

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