folly/small_vector.h

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