folly/small_vector.h

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