folly/small_vector.h

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