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