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