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