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