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