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