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/ConstexprMath.h>
  49 #include <folly/FormatTraits.h>
  50 #include <folly/Portability.h>
  51 #include <folly/SmallLocks.h>
  52 #include <folly/Traits.h>
  53 #include <folly/lang/Assume.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* pointer;
 417   typedef value_type const* const_iterator;
 418   typedef std::ptrdiff_t difference_type;
 419
 420   typedef std::reverse_iterator<iterator> reverse_iterator;
 421   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 422
 423   small_vector() = default;
 424   // Allocator is unused here. It is taken in for compatibility with std::vector
 425   // interface, but it will be ignored.
 426   small_vector(const std::allocator<Value>&) {}
 427
 428   small_vector(small_vector const& o) {
 429     auto n = o.size();
 430     makeSize(n);
 431     try {
 432       std::uninitialized_copy(o.begin(), o.end(), begin());
 433     } catch (...) {
 434       if (this->isExtern()) {
 435         u.freeHeap();
 436       }
 437       throw;
 438     }
 439     this->setSize(n);
 440   }
 441
 442   small_vector(small_vector&& o) noexcept(
 443       std::is_nothrow_move_constructible<Value>::value) {
 444     if (o.isExtern()) {
 445       swap(o);
 446     } else {
 447       std::uninitialized_copy(
 448           std::make_move_iterator(o.begin()),
 449           std::make_move_iterator(o.end()),
 450           begin());
 451       this->setSize(o.size());
 452     }
 453   }
 454
 455   small_vector(std::initializer_list<value_type> il) {
 456     constructImpl(il.begin(), il.end(), std::false_type());
 457   }
 458
 459   explicit small_vector(size_type n) {
 460     doConstruct(n, [&](void* p) { new (p) value_type(); });
 461   }
 462
 463   small_vector(size_type n, value_type const& t) {
 464     doConstruct(n, [&](void* p) { new (p) value_type(t); });
 465   }
 466
 467   template <class Arg>
 468   explicit small_vector(Arg arg1, Arg arg2) {
 469     // Forward using std::is_arithmetic to get to the proper
 470     // implementation; this disambiguates between the iterators and
 471     // (size_t, value_type) meaning for this constructor.
 472     constructImpl(arg1, arg2, std::is_arithmetic<Arg>());
 473   }
 474
 475   ~small_vector() {
 476     for (auto& t : *this) {
 477       (&t)->~value_type();
 478     }
 479     if (this->isExtern()) {
 480       u.freeHeap();
 481     }
 482   }
 483
 484   small_vector& operator=(small_vector const& o) {
 485     assign(o.begin(), o.end());
 486     return *this;
 487   }
 488
 489   small_vector& operator=(small_vector&& o) {
 490     // TODO: optimization:
 491     // if both are internal, use move assignment where possible
 492     if (this == &o) {
 493       return *this;
 494     }
 495     clear();
 496     swap(o);
 497     return *this;
 498   }
 499
 500   bool operator==(small_vector const& o) const {
 501     return size() == o.size() && std::equal(begin(), end(), o.begin());
 502   }
 503
 504   bool operator<(small_vector const& o) const {
 505     return std::lexicographical_compare(begin(), end(), o.begin(), o.end());
 506   }
 507
 508   static constexpr size_type max_size() {
 509     return !BaseType::kShouldUseHeap ? static_cast<size_type>(MaxInline)
 510                                      : BaseType::policyMaxSize();
 511   }
 512
 513   size_type size() const {
 514     return this->doSize();
 515   }
 516   bool empty() const {
 517     return !size();
 518   }
 519
 520   iterator begin() {
 521     return data();
 522   }
 523   iterator end() {
 524     return data() + size();
 525   }
 526   const_iterator begin() const {
 527     return data();
 528   }
 529   const_iterator end() const {
 530     return data() + size();
 531   }
 532   const_iterator cbegin() const {
 533     return begin();
 534   }
 535   const_iterator cend() const {
 536     return end();
 537   }
 538
 539   reverse_iterator rbegin() {
 540     return reverse_iterator(end());
 541   }
 542   reverse_iterator rend() {
 543     return reverse_iterator(begin());
 544   }
 545
 546   const_reverse_iterator rbegin() const {
 547     return const_reverse_iterator(end());
 548   }
 549
 550   const_reverse_iterator rend() const {
 551     return const_reverse_iterator(begin());
 552   }
 553
 554   const_reverse_iterator crbegin() const {
 555     return rbegin();
 556   }
 557   const_reverse_iterator crend() const {
 558     return rend();
 559   }
 560
 561   /*
 562    * Usually one of the simplest functions in a Container-like class
 563    * but a bit more complex here.  We have to handle all combinations
 564    * of in-place vs. heap between this and o.
 565    *
 566    * Basic guarantee only.  Provides the nothrow guarantee iff our
 567    * value_type has a nothrow move or copy constructor.
 568    */
 569   void swap(small_vector& o) {
 570     using std::swap; // Allow ADL on swap for our value_type.
 571
 572     if (this->isExtern() && o.isExtern()) {
 573       this->swapSizePolicy(o);
 574
 575       auto thisCapacity = this->capacity();
 576       auto oCapacity = o.capacity();
 577
 578       auto* tmp = u.pdata_.heap_;
 579       u.pdata_.heap_ = o.u.pdata_.heap_;
 580       o.u.pdata_.heap_ = tmp;
 581
 582       this->setCapacity(oCapacity);
 583       o.setCapacity(thisCapacity);
 584
 585       return;
 586     }
 587
 588     if (!this->isExtern() && !o.isExtern()) {
 589       auto& oldSmall = size() < o.size() ? *this : o;
 590       auto& oldLarge = size() < o.size() ? o : *this;
 591
 592       for (size_type i = 0; i < oldSmall.size(); ++i) {
 593         swap(oldSmall[i], oldLarge[i]);
 594       }
 595
 596       size_type i = oldSmall.size();
 597       const size_type ci = i;
 598       try {
 599         for (; i < oldLarge.size(); ++i) {
 600           auto addr = oldSmall.begin() + i;
 601           new (addr) value_type(std::move(oldLarge[i]));
 602           oldLarge[i].~value_type();
 603         }
 604       } catch (...) {
 605         oldSmall.setSize(i);
 606         for (; i < oldLarge.size(); ++i) {
 607           oldLarge[i].~value_type();
 608         }
 609         oldLarge.setSize(ci);
 610         throw;
 611       }
 612       oldSmall.setSize(i);
 613       oldLarge.setSize(ci);
 614       return;
 615     }
 616
 617     // isExtern != o.isExtern()
 618     auto& oldExtern = o.isExtern() ? o : *this;
 619     auto& oldIntern = o.isExtern() ? *this : o;
 620
 621     auto oldExternCapacity = oldExtern.capacity();
 622     auto oldExternHeap = oldExtern.u.pdata_.heap_;
 623
 624     auto buff = oldExtern.u.buffer();
 625     size_type i = 0;
 626     try {
 627       for (; i < oldIntern.size(); ++i) {
 628         new (&buff[i]) value_type(std::move(oldIntern[i]));
 629         oldIntern[i].~value_type();
 630       }
 631     } catch (...) {
 632       for (size_type kill = 0; kill < i; ++kill) {
 633         buff[kill].~value_type();
 634       }
 635       for (; i < oldIntern.size(); ++i) {
 636         oldIntern[i].~value_type();
 637       }
 638       oldIntern.setSize(0);
 639       oldExtern.u.pdata_.heap_ = oldExternHeap;
 640       oldExtern.setCapacity(oldExternCapacity);
 641       throw;
 642     }
 643     oldIntern.u.pdata_.heap_ = oldExternHeap;
 644     this->swapSizePolicy(o);
 645     oldIntern.setCapacity(oldExternCapacity);
 646   }
 647
 648   void resize(size_type sz) {
 649     if (sz < size()) {
 650       erase(begin() + sz, end());
 651       return;
 652     }
 653     makeSize(sz);
 654     detail::populateMemForward(
 655         begin() + size(), sz - size(), [&](void* p) { new (p) value_type(); });
 656     this->setSize(sz);
 657   }
 658
 659   void resize(size_type sz, value_type const& v) {
 660     if (sz < size()) {
 661       erase(begin() + sz, end());
 662       return;
 663     }
 664     makeSize(sz);
 665     detail::populateMemForward(
 666         begin() + size(), sz - size(), [&](void* p) { new (p) value_type(v); });
 667     this->setSize(sz);
 668   }
 669
 670   value_type* data() noexcept {
 671     return this->isExtern() ? u.heap() : u.buffer();
 672   }
 673
 674   value_type const* data() const noexcept {
 675     return this->isExtern() ? u.heap() : u.buffer();
 676   }
 677
 678   template <class... Args>
 679   iterator emplace(const_iterator p, Args&&... args) {
 680     if (p == cend()) {
 681       emplace_back(std::forward<Args>(args)...);
 682       return end() - 1;
 683     }
 684
 685     /*
 686      * We implement emplace at places other than at the back with a
 687      * temporary for exception safety reasons.  It is possible to
 688      * avoid having to do this, but it becomes hard to maintain the
 689      * basic exception safety guarantee (unless you respond to a copy
 690      * constructor throwing by clearing the whole vector).
 691      *
 692      * The reason for this is that otherwise you have to destruct an
 693      * element before constructing this one in its place---if the
 694      * constructor throws, you either need a nothrow default
 695      * constructor or a nothrow copy/move to get something back in the
 696      * "gap", and the vector requirements don't guarantee we have any
 697      * of these.  Clearing the whole vector is a legal response in
 698      * this situation, but it seems like this implementation is easy
 699      * enough and probably better.
 700      */
 701     return insert(p, value_type(std::forward<Args>(args)...));
 702   }
 703
 704   void reserve(size_type sz) {
 705     makeSize(sz);
 706   }
 707
 708   size_type capacity() const {
 709     if (this->isExtern()) {
 710       if (u.hasCapacity()) {
 711         return u.getCapacity();
 712       }
 713       return malloc_usable_size(u.pdata_.heap_) / sizeof(value_type);
 714     }
 715     return MaxInline;
 716   }
 717
 718   void shrink_to_fit() {
 719     if (!this->isExtern()) {
 720       return;
 721     }
 722
 723     small_vector tmp(begin(), end());
 724     tmp.swap(*this);
 725   }
 726
 727   template <class... Args>
 728   void emplace_back(Args&&... args) {
 729     if (capacity() == size()) {
 730       // Any of args may be references into the vector.
 731       // When we are reallocating, we have to be careful to construct the new
 732       // element before modifying the data in the old buffer.
 733       makeSize(
 734           size() + 1,
 735           [&](void* p) { new (p) value_type(std::forward<Args>(args)...); },
 736           size());
 737     } else {
 738       new (end()) value_type(std::forward<Args>(args)...);
 739     }
 740     this->setSize(size() + 1);
 741   }
 742
 743   void push_back(value_type&& t) {
 744     return emplace_back(std::move(t));
 745   }
 746
 747   void push_back(value_type const& t) {
 748     emplace_back(t);
 749   }
 750
 751   void pop_back() {
 752     erase(end() - 1);
 753   }
 754
 755   iterator insert(const_iterator constp, value_type&& t) {
 756     iterator p = unconst(constp);
 757
 758     if (p == end()) {
 759       push_back(std::move(t));
 760       return end() - 1;
 761     }
 762
 763     auto offset = p - begin();
 764
 765     if (capacity() == size()) {
 766       makeSize(
 767           size() + 1,
 768           [&t](void* ptr) { new (ptr) value_type(std::move(t)); },
 769           offset);
 770       this->setSize(this->size() + 1);
 771     } else {
 772       detail::moveObjectsRight(
 773           data() + offset, data() + size(), data() + size() + 1);
 774       this->setSize(size() + 1);
 775       data()[offset] = std::move(t);
 776     }
 777     return begin() + offset;
 778   }
 779
 780   iterator insert(const_iterator p, value_type const& t) {
 781     // Make a copy and forward to the rvalue value_type&& overload
 782     // above.
 783     return insert(p, value_type(t));
 784   }
 785
 786   iterator insert(const_iterator pos, size_type n, value_type const& val) {
 787     auto offset = pos - begin();
 788     makeSize(size() + n);
 789     detail::moveObjectsRight(
 790         data() + offset, data() + size(), data() + size() + n);
 791     this->setSize(size() + n);
 792     std::generate_n(begin() + offset, n, [&] { return val; });
 793     return begin() + offset;
 794   }
 795
 796   template <class Arg>
 797   iterator insert(const_iterator p, Arg arg1, Arg arg2) {
 798     // Forward using std::is_arithmetic to get to the proper
 799     // implementation; this disambiguates between the iterators and
 800     // (size_t, value_type) meaning for this function.
 801     return insertImpl(unconst(p), arg1, arg2, std::is_arithmetic<Arg>());
 802   }
 803
 804   iterator insert(const_iterator p, std::initializer_list<value_type> il) {
 805     return insert(p, il.begin(), il.end());
 806   }
 807
 808   iterator erase(const_iterator q) {
 809     std::move(unconst(q) + 1, end(), unconst(q));
 810     (data() + size() - 1)->~value_type();
 811     this->setSize(size() - 1);
 812     return unconst(q);
 813   }
 814
 815   iterator erase(const_iterator q1, const_iterator q2) {
 816     if (q1 == q2) {
 817       return unconst(q1);
 818     }
 819     std::move(unconst(q2), end(), unconst(q1));
 820     for (auto it = (end() - std::distance(q1, q2)); it != end(); ++it) {
 821       it->~value_type();
 822     }
 823     this->setSize(size() - (q2 - q1));
 824     return unconst(q1);
 825   }
 826
 827   void clear() {
 828     erase(begin(), end());
 829   }
 830
 831   template <class Arg>
 832   void assign(Arg first, Arg last) {
 833     clear();
 834     insert(end(), first, last);
 835   }
 836
 837   void assign(std::initializer_list<value_type> il) {
 838     assign(il.begin(), il.end());
 839   }
 840
 841   void assign(size_type n, const value_type& t) {
 842     clear();
 843     insert(end(), n, t);
 844   }
 845
 846   reference front() {
 847     assert(!empty());
 848     return *begin();
 849   }
 850   reference back() {
 851     assert(!empty());
 852     return *(end() - 1);
 853   }
 854   const_reference front() const {
 855     assert(!empty());
 856     return *begin();
 857   }
 858   const_reference back() const {
 859     assert(!empty());
 860     return *(end() - 1);
 861   }
 862
 863   reference operator[](size_type i) {
 864     assert(i < size());
 865     return *(begin() + i);
 866   }
 867
 868   const_reference operator[](size_type i) const {
 869     assert(i < size());
 870     return *(begin() + i);
 871   }
 872
 873   reference at(size_type i) {
 874     if (i >= size()) {
 875       std::__throw_out_of_range("index out of range");
 876     }
 877     return (*this)[i];
 878   }
 879
 880   const_reference at(size_type i) const {
 881     if (i >= size()) {
 882       std::__throw_out_of_range("index out of range");
 883     }
 884     return (*this)[i];
 885   }
 886
 887  private:
 888   static iterator unconst(const_iterator it) {
 889     return const_cast<iterator>(it);
 890   }
 891
 892   // The std::false_type argument is part of disambiguating the
 893   // iterator insert functions from integral types (see insert().)
 894   template <class It>
 895   iterator insertImpl(iterator pos, It first, It last, std::false_type) {
 896     typedef typename std::iterator_traits<It>::iterator_category categ;
 897     if (std::is_same<categ, std::input_iterator_tag>::value) {
 898       auto offset = pos - begin();
 899       while (first != last) {
 900         pos = insert(pos, *first++);
 901         ++pos;
 902       }
 903       return begin() + offset;
 904     }
 905
 906     auto distance = std::distance(first, last);
 907     auto offset = pos - begin();
 908     makeSize(size() + distance);
 909     detail::moveObjectsRight(
 910         data() + offset, data() + size(), data() + size() + distance);
 911     this->setSize(size() + distance);
 912     std::copy_n(first, distance, begin() + offset);
 913     return begin() + offset;
 914   }
 915
 916   iterator
 917   insertImpl(iterator pos, size_type n, const value_type& val, std::true_type) {
 918     // The true_type means this should call the size_t,value_type
 919     // overload.  (See insert().)
 920     return insert(pos, n, val);
 921   }
 922
 923   // The std::false_type argument came from std::is_arithmetic as part
 924   // of disambiguating an overload (see the comment in the
 925   // constructor).
 926   template <class It>
 927   void constructImpl(It first, It last, std::false_type) {
 928     typedef typename std::iterator_traits<It>::iterator_category categ;
 929     if (std::is_same<categ, std::input_iterator_tag>::value) {
 930       // With iterators that only allow a single pass, we can't really
 931       // do anything sane here.
 932       while (first != last) {
 933         emplace_back(*first++);
 934       }
 935       return;
 936     }
 937
 938     auto distance = std::distance(first, last);
 939     makeSize(distance);
 940     this->setSize(distance);
 941     try {
 942       detail::populateMemForward(
 943           data(), distance, [&](void* p) { new (p) value_type(*first++); });
 944     } catch (...) {
 945       if (this->isExtern()) {
 946         u.freeHeap();
 947       }
 948       throw;
 949     }
 950   }
 951
 952   template <typename InitFunc>
 953   void doConstruct(size_type n, InitFunc&& func) {
 954     makeSize(n);
 955     this->setSize(n);
 956     try {
 957       detail::populateMemForward(data(), n, std::forward<InitFunc>(func));
 958     } catch (...) {
 959       if (this->isExtern()) {
 960         u.freeHeap();
 961       }
 962       throw;
 963     }
 964   }
 965
 966   // The true_type means we should forward to the size_t,value_type
 967   // overload.
 968   void constructImpl(size_type n, value_type const& val, std::true_type) {
 969     doConstruct(n, [&](void* p) { new (p) value_type(val); });
 970   }
 971
 972   /*
 973    * Compute the size after growth.
 974    */
 975   size_type computeNewSize() const {
 976     return std::min((3 * capacity()) / 2 + 1, max_size());
 977   }
 978
 979   void makeSize(size_type newSize) {
 980     makeSizeInternal(newSize, false, [](void*) { assume_unreachable(); }, 0);
 981   }
 982
 983   template <typename EmplaceFunc>
 984   void makeSize(size_type newSize, EmplaceFunc&& emplaceFunc, size_type pos) {
 985     assert(size() == capacity());
 986     makeSizeInternal(
 987         newSize, true, std::forward<EmplaceFunc>(emplaceFunc), pos);
 988   }
 989
 990   /*
 991    * Ensure we have a large enough memory region to be size `newSize'.
 992    * Will move/copy elements if we are spilling to heap_ or needed to
 993    * allocate a new region, but if resized in place doesn't initialize
 994    * anything in the new region.  In any case doesn't change size().
 995    * Supports insertion of new element during reallocation by given
 996    * pointer to new element and position of new element.
 997    * NOTE: If reallocation is not needed, insert must be false,
 998    * because we only know how to emplace elements into new memory.
 999    */
1000   template <typename EmplaceFunc>
1001   void makeSizeInternal(
1002       size_type newSize,
1003       bool insert,
1004       EmplaceFunc&& emplaceFunc,
1005       size_type pos) {
1006     if (newSize > max_size()) {
1007       throw std::length_error("max_size exceeded in small_vector");
1008     }
1009     if (newSize <= capacity()) {
1010       assert(!insert);
1011       return;
1012     }
1013
1014     assert(this->kShouldUseHeap);
1015     // This branch isn't needed for correctness, but allows the optimizer to
1016     // skip generating code for the rest of this function in NoHeap
1017     // small_vectors.
1018     if (!this->kShouldUseHeap) {
1019       return;
1020     }
1021
1022     newSize = std::max(newSize, computeNewSize());
1023
1024     auto needBytes = newSize * sizeof(value_type);
1025     // If the capacity isn't explicitly stored inline, but the heap
1026     // allocation is grown to over some threshold, we should store
1027     // a capacity at the front of the heap allocation.
1028     bool heapifyCapacity =
1029         !kHasInlineCapacity && needBytes > kHeapifyCapacityThreshold;
1030     if (heapifyCapacity) {
1031       needBytes += kHeapifyCapacitySize;
1032     }
1033     auto const sizeBytes = goodMallocSize(needBytes);
1034     void* newh = checkedMalloc(sizeBytes);
1035     // We expect newh to be at least 2-aligned, because we want to
1036     // use its least significant bit as a flag.
1037     assert(!detail::pointerFlagGet(newh));
1038
1039     value_type* newp = static_cast<value_type*>(
1040         heapifyCapacity ? detail::shiftPointer(newh, kHeapifyCapacitySize)
1041                         : newh);
1042
1043     try {
1044       if (insert) {
1045         // move and insert the new element
1046         this->moveToUninitializedEmplace(
1047             begin(), end(), newp, pos, std::forward<EmplaceFunc>(emplaceFunc));
1048       } else {
1049         // move without inserting new element
1050         this->moveToUninitialized(begin(), end(), newp);
1051       }
1052     } catch (...) {
1053       free(newh);
1054       throw;
1055     }
1056     for (auto& val : *this) {
1057       val.~value_type();
1058     }
1059
1060     if (this->isExtern()) {
1061       u.freeHeap();
1062     }
1063     auto availableSizeBytes = sizeBytes;
1064     if (heapifyCapacity) {
1065       u.pdata_.heap_ = detail::pointerFlagSet(newh);
1066       availableSizeBytes -= kHeapifyCapacitySize;
1067     } else {
1068       u.pdata_.heap_ = newh;
1069     }
1070     this->setExtern(true);
1071     this->setCapacity(availableSizeBytes / sizeof(value_type));
1072   }
1073
1074   /*
1075    * This will set the capacity field, stored inline in the storage_ field
1076    * if there is sufficient room to store it.
1077    */
1078   void setCapacity(size_type newCapacity) {
1079     assert(this->isExtern());
1080     if (u.hasCapacity()) {
1081       assert(newCapacity < std::numeric_limits<InternalSizeType>::max());
1082       u.setCapacity(newCapacity);
1083     }
1084   }
1085
1086  private:
1087   struct HeapPtrWithCapacity {
1088     void* heap_;
1089     InternalSizeType capacity_;
1090
1091     InternalSizeType getCapacity() const {
1092       return capacity_;
1093     }
1094     void setCapacity(InternalSizeType c) {
1095       capacity_ = c;
1096     }
1097   } FOLLY_PACK_ATTR;
1098
1099   struct HeapPtr {
1100     // Lower order bit of heap_ is used as flag to indicate whether capacity is
1101     // stored at the front of the heap allocation.
1102     void* heap_;
1103
1104     InternalSizeType getCapacity() const {
1105       assert(detail::pointerFlagGet(heap_));
1106       return *static_cast<InternalSizeType*>(detail::pointerFlagClear(heap_));
1107     }
1108     void setCapacity(InternalSizeType c) {
1109       *static_cast<InternalSizeType*>(detail::pointerFlagClear(heap_)) = c;
1110     }
1111   } FOLLY_PACK_ATTR;
1112
1113 #if (FOLLY_X64 || FOLLY_PPC64)
1114   typedef unsigned char InlineStorageDataType[sizeof(value_type) * MaxInline];
1115 #else
1116   typedef typename std::aligned_storage<
1117       sizeof(value_type) * MaxInline,
1118       alignof(value_type)>::type InlineStorageDataType;
1119 #endif
1120
1121   typedef typename std::conditional<
1122       sizeof(value_type) * MaxInline != 0,
1123       InlineStorageDataType,
1124       void*>::type InlineStorageType;
1125
1126   static bool constexpr kHasInlineCapacity =
1127       sizeof(HeapPtrWithCapacity) < sizeof(InlineStorageType);
1128
1129   // This value should we multiple of word size.
1130   static size_t constexpr kHeapifyCapacitySize = sizeof(
1131       typename std::
1132           aligned_storage<sizeof(InternalSizeType), alignof(value_type)>::type);
1133
1134   // Threshold to control capacity heapifying.
1135   static size_t constexpr kHeapifyCapacityThreshold =
1136       100 * kHeapifyCapacitySize;
1137
1138   typedef typename std::
1139       conditional<kHasInlineCapacity, HeapPtrWithCapacity, HeapPtr>::type
1140           PointerType;
1141
1142   union Data {
1143     explicit Data() {
1144       pdata_.heap_ = nullptr;
1145     }
1146
1147     PointerType pdata_;
1148     InlineStorageType storage_;
1149
1150     value_type* buffer() noexcept {
1151       void* vp = &storage_;
1152       return static_cast<value_type*>(vp);
1153     }
1154     value_type const* buffer() const noexcept {
1155       return const_cast<Data*>(this)->buffer();
1156     }
1157     value_type* heap() noexcept {
1158       if (kHasInlineCapacity || !detail::pointerFlagGet(pdata_.heap_)) {
1159         return static_cast<value_type*>(pdata_.heap_);
1160       } else {
1161         return static_cast<value_type*>(detail::shiftPointer(
1162             detail::pointerFlagClear(pdata_.heap_), kHeapifyCapacitySize));
1163       }
1164     }
1165     value_type const* heap() const noexcept {
1166       return const_cast<Data*>(this)->heap();
1167     }
1168
1169     bool hasCapacity() const {
1170       return kHasInlineCapacity || detail::pointerFlagGet(pdata_.heap_);
1171     }
1172     InternalSizeType getCapacity() const {
1173       return pdata_.getCapacity();
1174     }
1175     void setCapacity(InternalSizeType c) {
1176       pdata_.setCapacity(c);
1177     }
1178
1179     void freeHeap() {
1180       auto vp = detail::pointerFlagClear(pdata_.heap_);
1181       free(vp);
1182     }
1183   } FOLLY_PACK_ATTR u;
1184 } FOLLY_PACK_ATTR;
1185 FOLLY_PACK_POP
1186
1187 //////////////////////////////////////////////////////////////////////
1188
1189 // Basic guarantee only, or provides the nothrow guarantee iff T has a
1190 // nothrow move or copy constructor.
1191 template <class T, std::size_t MaxInline, class A, class B, class C>
1192 void swap(
1193     small_vector<T, MaxInline, A, B, C>& a,
1194     small_vector<T, MaxInline, A, B, C>& b) {
1195   a.swap(b);
1196 }
1197
1198 //////////////////////////////////////////////////////////////////////
1199
1200 namespace detail {
1201
1202 // Format support.
1203 template <class T, size_t M, class A, class B, class C>
1204 struct IndexableTraits<small_vector<T, M, A, B, C>>
1205     : public IndexableTraitsSeq<small_vector<T, M, A, B, C>> {};
1206
1207 } // namespace detail
1208
1209 } // namespace folly
1210
1211 FOLLY_POP_WARNING