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