folly/FBVector.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  * Nicholas Ormrod      (njormrod)
  19  * Andrei Alexandrescu  (aalexandre)
  20  *
  21  * FBVector is Facebook's drop-in implementation of std::vector. It has special
  22  * optimizations for use with relocatable types and jemalloc.
  23  */
  24
  25 #pragma once
  26
  27 //=============================================================================
  28 // headers
  29
  30 #include <algorithm>
  31 #include <cassert>
  32 #include <iterator>
  33 #include <memory>
  34 #include <stdexcept>
  35 #include <type_traits>
  36 #include <utility>
  37
  38 #include <folly/FormatTraits.h>
  39 #include <folly/Likely.h>
  40 #include <folly/Malloc.h>
  41 #include <folly/Traits.h>
  42 #include <folly/portability/BitsFunctexcept.h>
  43
  44 //=============================================================================
  45 // forward declaration
  46
  47 namespace folly {
  48   template <class T, class Allocator = std::allocator<T>>
  49   class fbvector;
  50 }
  51
  52 //=============================================================================
  53 // unrolling
  54
  55 #define FOLLY_FBV_UNROLL_PTR(first, last, OP) do {  \
  56   for (; (last) - (first) >= 4; (first) += 4) {     \
  57     OP(((first) + 0));                              \
  58     OP(((first) + 1));                              \
  59     OP(((first) + 2));                              \
  60     OP(((first) + 3));                              \
  61   }                                                 \
  62   for (; (first) != (last); ++(first)) OP((first)); \
  63 } while(0);
  64
  65 //=============================================================================
  66 ///////////////////////////////////////////////////////////////////////////////
  67 //                                                                           //
  68 //                              fbvector class                               //
  69 //                                                                           //
  70 ///////////////////////////////////////////////////////////////////////////////
  71
  72 namespace folly {
  73
  74 template <class T, class Allocator>
  75 class fbvector {
  76
  77   //===========================================================================
  78   //---------------------------------------------------------------------------
  79   // implementation
  80  private:
  81   typedef std::allocator_traits<Allocator> A;
  82
  83   struct Impl : public Allocator {
  84     // typedefs
  85     typedef typename A::pointer pointer;
  86     typedef typename A::size_type size_type;
  87
  88     // data
  89     pointer b_, e_, z_;
  90
  91     // constructors
  92     Impl() : Allocator(), b_(nullptr), e_(nullptr), z_(nullptr) {}
  93     /* implicit */ Impl(const Allocator& a)
  94       : Allocator(a), b_(nullptr), e_(nullptr), z_(nullptr) {}
  95     /* implicit */ Impl(Allocator&& a)
  96       : Allocator(std::move(a)), b_(nullptr), e_(nullptr), z_(nullptr) {}
  97
  98     /* implicit */ Impl(size_type n, const Allocator& a = Allocator())
  99       : Allocator(a)
 100       { init(n); }
 101
 102     Impl(Impl&& other) noexcept
 103       : Allocator(std::move(other)),
 104         b_(other.b_), e_(other.e_), z_(other.z_)
 105       { other.b_ = other.e_ = other.z_ = nullptr; }
 106
 107     // destructor
 108     ~Impl() {
 109       destroy();
 110     }
 111
 112     // allocation
 113     // note that 'allocate' and 'deallocate' are inherited from Allocator
 114     T* D_allocate(size_type n) {
 115       if (usingStdAllocator::value) {
 116         return static_cast<T*>(malloc(n * sizeof(T)));
 117       } else {
 118         return std::allocator_traits<Allocator>::allocate(*this, n);
 119       }
 120     }
 121
 122     void D_deallocate(T* p, size_type n) noexcept {
 123       if (usingStdAllocator::value) {
 124         free(p);
 125       } else {
 126         std::allocator_traits<Allocator>::deallocate(*this, p, n);
 127       }
 128     }
 129
 130     // helpers
 131     void swapData(Impl& other) {
 132       std::swap(b_, other.b_);
 133       std::swap(e_, other.e_);
 134       std::swap(z_, other.z_);
 135     }
 136
 137     // data ops
 138     inline void destroy() noexcept {
 139       if (b_) {
 140         // THIS DISPATCH CODE IS DUPLICATED IN fbvector::D_destroy_range_a.
 141         // It has been inlined here for speed. It calls the static fbvector
 142         //  methods to perform the actual destruction.
 143         if (usingStdAllocator::value) {
 144           S_destroy_range(b_, e_);
 145         } else {
 146           S_destroy_range_a(*this, b_, e_);
 147         }
 148
 149         D_deallocate(b_, size_type(z_ - b_));
 150       }
 151     }
 152
 153     void init(size_type n) {
 154       if (UNLIKELY(n == 0)) {
 155         b_ = e_ = z_ = nullptr;
 156       } else {
 157         size_type sz = folly::goodMallocSize(n * sizeof(T)) / sizeof(T);
 158         b_ = D_allocate(sz);
 159         e_ = b_;
 160         z_ = b_ + sz;
 161       }
 162     }
 163
 164     void set(pointer newB, size_type newSize, size_type newCap) {
 165       z_ = newB + newCap;
 166       e_ = newB + newSize;
 167       b_ = newB;
 168     }
 169
 170     void reset(size_type newCap) {
 171       destroy();
 172       try {
 173         init(newCap);
 174       } catch (...) {
 175         init(0);
 176         throw;
 177       }
 178     }
 179     void reset() { // same as reset(0)
 180       destroy();
 181       b_ = e_ = z_ = nullptr;
 182     }
 183   } impl_;
 184
 185   static void swap(Impl& a, Impl& b) {
 186     using std::swap;
 187     if (!usingStdAllocator::value) swap<Allocator>(a, b);
 188     a.swapData(b);
 189   }
 190
 191   //===========================================================================
 192   //---------------------------------------------------------------------------
 193   // types and constants
 194  public:
 195   typedef T                                           value_type;
 196   typedef value_type&                                 reference;
 197   typedef const value_type&                           const_reference;
 198   typedef T*                                          iterator;
 199   typedef const T*                                    const_iterator;
 200   typedef size_t                                      size_type;
 201   typedef typename std::make_signed<size_type>::type  difference_type;
 202   typedef Allocator                                   allocator_type;
 203   typedef typename A::pointer                         pointer;
 204   typedef typename A::const_pointer                   const_pointer;
 205   typedef std::reverse_iterator<iterator>             reverse_iterator;
 206   typedef std::reverse_iterator<const_iterator>       const_reverse_iterator;
 207
 208  private:
 209   typedef std::integral_constant<bool,
 210       IsTriviallyCopyable<T>::value &&
 211       sizeof(T) <= 16 // don't force large structures to be passed by value
 212     > should_pass_by_value;
 213   typedef typename std::conditional<
 214       should_pass_by_value::value, T, const T&>::type VT;
 215   typedef typename std::conditional<
 216       should_pass_by_value::value, T, T&&>::type MT;
 217
 218   typedef std::integral_constant<bool,
 219       std::is_same<Allocator, std::allocator<T>>::value> usingStdAllocator;
 220   typedef std::integral_constant<bool,
 221       usingStdAllocator::value ||
 222       A::propagate_on_container_move_assignment::value> moveIsSwap;
 223
 224   //===========================================================================
 225   //---------------------------------------------------------------------------
 226   // allocator helpers
 227  private:
 228   //---------------------------------------------------------------------------
 229   // allocate
 230
 231   T* M_allocate(size_type n) {
 232     return impl_.D_allocate(n);
 233   }
 234
 235   //---------------------------------------------------------------------------
 236   // deallocate
 237
 238   void M_deallocate(T* p, size_type n) noexcept {
 239     impl_.D_deallocate(p, n);
 240   }
 241
 242   //---------------------------------------------------------------------------
 243   // construct
 244
 245   // GCC is very sensitive to the exact way that construct is called. For
 246   //  that reason there are several different specializations of construct.
 247
 248   template <typename U, typename... Args>
 249   void M_construct(U* p, Args&&... args) {
 250     if (usingStdAllocator::value) {
 251       new (p) U(std::forward<Args>(args)...);
 252     } else {
 253       std::allocator_traits<Allocator>::construct(
 254         impl_, p, std::forward<Args>(args)...);
 255     }
 256   }
 257
 258   template <typename U, typename... Args>
 259   static void S_construct(U* p, Args&&... args) {
 260     new (p) U(std::forward<Args>(args)...);
 261   }
 262
 263   template <typename U, typename... Args>
 264   static void S_construct_a(Allocator& a, U* p, Args&&... args) {
 265     std::allocator_traits<Allocator>::construct(
 266       a, p, std::forward<Args>(args)...);
 267   }
 268
 269   // scalar optimization
 270   // TODO we can expand this optimization to: default copyable and assignable
 271   template <typename U, typename Enable = typename
 272     std::enable_if<std::is_scalar<U>::value>::type>
 273   void M_construct(U* p, U arg) {
 274     if (usingStdAllocator::value) {
 275       *p = arg;
 276     } else {
 277       std::allocator_traits<Allocator>::construct(impl_, p, arg);
 278     }
 279   }
 280
 281   template <typename U, typename Enable = typename
 282     std::enable_if<std::is_scalar<U>::value>::type>
 283   static void S_construct(U* p, U arg) {
 284     *p = arg;
 285   }
 286
 287   template <typename U, typename Enable = typename
 288     std::enable_if<std::is_scalar<U>::value>::type>
 289   static void S_construct_a(Allocator& a, U* p, U arg) {
 290     std::allocator_traits<Allocator>::construct(a, p, arg);
 291   }
 292
 293   // const& optimization
 294   template <typename U, typename Enable = typename
 295     std::enable_if<!std::is_scalar<U>::value>::type>
 296   void M_construct(U* p, const U& value) {
 297     if (usingStdAllocator::value) {
 298       new (p) U(value);
 299     } else {
 300       std::allocator_traits<Allocator>::construct(impl_, p, value);
 301     }
 302   }
 303
 304   template <typename U, typename Enable = typename
 305     std::enable_if<!std::is_scalar<U>::value>::type>
 306   static void S_construct(U* p, const U& value) {
 307     new (p) U(value);
 308   }
 309
 310   template <typename U, typename Enable = typename
 311     std::enable_if<!std::is_scalar<U>::value>::type>
 312   static void S_construct_a(Allocator& a, U* p, const U& value) {
 313     std::allocator_traits<Allocator>::construct(a, p, value);
 314   }
 315
 316   //---------------------------------------------------------------------------
 317   // destroy
 318
 319   void M_destroy(T* p) noexcept {
 320     if (usingStdAllocator::value) {
 321       if (!std::is_trivially_destructible<T>::value)
 322         p->~T();
 323     } else {
 324       std::allocator_traits<Allocator>::destroy(impl_, p);
 325     }
 326   }
 327
 328   //===========================================================================
 329   //---------------------------------------------------------------------------
 330   // algorithmic helpers
 331  private:
 332   //---------------------------------------------------------------------------
 333   // destroy_range
 334
 335   // wrappers
 336   void M_destroy_range_e(T* pos) noexcept {
 337     D_destroy_range_a(pos, impl_.e_);
 338     impl_.e_ = pos;
 339   }
 340
 341   // dispatch
 342   // THIS DISPATCH CODE IS DUPLICATED IN IMPL. SEE IMPL FOR DETAILS.
 343   void D_destroy_range_a(T* first, T* last) noexcept {
 344     if (usingStdAllocator::value) {
 345       S_destroy_range(first, last);
 346     } else {
 347       S_destroy_range_a(impl_, first, last);
 348     }
 349   }
 350
 351   // allocator
 352   static void S_destroy_range_a(Allocator& a, T* first, T* last) noexcept {
 353     for (; first != last; ++first)
 354       std::allocator_traits<Allocator>::destroy(a, first);
 355   }
 356
 357   // optimized
 358   static void S_destroy_range(T* first, T* last) noexcept {
 359     if (!std::is_trivially_destructible<T>::value) {
 360       // EXPERIMENTAL DATA on fbvector<vector<int>> (where each vector<int> has
 361       //  size 0).
 362       // The unrolled version seems to work faster for small to medium sized
 363       //  fbvectors. It gets a 10% speedup on fbvectors of size 1024, 64, and
 364       //  16.
 365       // The simple loop version seems to work faster for large fbvectors. The
 366       //  unrolled version is about 6% slower on fbvectors on size 16384.
 367       // The two methods seem tied for very large fbvectors. The unrolled
 368       //  version is about 0.5% slower on size 262144.
 369
 370       // for (; first != last; ++first) first->~T();
 371       #define FOLLY_FBV_OP(p) (p)->~T()
 372       FOLLY_FBV_UNROLL_PTR(first, last, FOLLY_FBV_OP)
 373       #undef FOLLY_FBV_OP
 374     }
 375   }
 376
 377   //---------------------------------------------------------------------------
 378   // uninitialized_fill_n
 379
 380   // wrappers
 381   void M_uninitialized_fill_n_e(size_type sz) {
 382     D_uninitialized_fill_n_a(impl_.e_, sz);
 383     impl_.e_ += sz;
 384   }
 385
 386   void M_uninitialized_fill_n_e(size_type sz, VT value) {
 387     D_uninitialized_fill_n_a(impl_.e_, sz, value);
 388     impl_.e_ += sz;
 389   }
 390
 391   // dispatch
 392   void D_uninitialized_fill_n_a(T* dest, size_type sz) {
 393     if (usingStdAllocator::value) {
 394       S_uninitialized_fill_n(dest, sz);
 395     } else {
 396       S_uninitialized_fill_n_a(impl_, dest, sz);
 397     }
 398   }
 399
 400   void D_uninitialized_fill_n_a(T* dest, size_type sz, VT value) {
 401     if (usingStdAllocator::value) {
 402       S_uninitialized_fill_n(dest, sz, value);
 403     } else {
 404       S_uninitialized_fill_n_a(impl_, dest, sz, value);
 405     }
 406   }
 407
 408   // allocator
 409   template <typename... Args>
 410   static void S_uninitialized_fill_n_a(Allocator& a, T* dest,
 411                                        size_type sz, Args&&... args) {
 412     auto b = dest;
 413     auto e = dest + sz;
 414     try {
 415       for (; b != e; ++b)
 416         std::allocator_traits<Allocator>::construct(a, b,
 417           std::forward<Args>(args)...);
 418     } catch (...) {
 419       S_destroy_range_a(a, dest, b);
 420       throw;
 421     }
 422   }
 423
 424   // optimized
 425   static void S_uninitialized_fill_n(T* dest, size_type n) {
 426     if (folly::IsZeroInitializable<T>::value) {
 427       if (LIKELY(n != 0)) {
 428         std::memset(dest, 0, sizeof(T) * n);
 429       }
 430     } else {
 431       auto b = dest;
 432       auto e = dest + n;
 433       try {
 434         for (; b != e; ++b) S_construct(b);
 435       } catch (...) {
 436         --b;
 437         for (; b >= dest; --b) b->~T();
 438         throw;
 439       }
 440     }
 441   }
 442
 443   static void S_uninitialized_fill_n(T* dest, size_type n, const T& value) {
 444     auto b = dest;
 445     auto e = dest + n;
 446     try {
 447       for (; b != e; ++b) S_construct(b, value);
 448     } catch (...) {
 449       S_destroy_range(dest, b);
 450       throw;
 451     }
 452   }
 453
 454   //---------------------------------------------------------------------------
 455   // uninitialized_copy
 456
 457   // it is possible to add an optimization for the case where
 458   // It = move(T*) and IsRelocatable<T> and Is0Initiailizable<T>
 459
 460   // wrappers
 461   template <typename It>
 462   void M_uninitialized_copy_e(It first, It last) {
 463     D_uninitialized_copy_a(impl_.e_, first, last);
 464     impl_.e_ += std::distance(first, last);
 465   }
 466
 467   template <typename It>
 468   void M_uninitialized_move_e(It first, It last) {
 469     D_uninitialized_move_a(impl_.e_, first, last);
 470     impl_.e_ += std::distance(first, last);
 471   }
 472
 473   // dispatch
 474   template <typename It>
 475   void D_uninitialized_copy_a(T* dest, It first, It last) {
 476     if (usingStdAllocator::value) {
 477       if (folly::IsTriviallyCopyable<T>::value) {
 478         S_uninitialized_copy_bits(dest, first, last);
 479       } else {
 480         S_uninitialized_copy(dest, first, last);
 481       }
 482     } else {
 483       S_uninitialized_copy_a(impl_, dest, first, last);
 484     }
 485   }
 486
 487   template <typename It>
 488   void D_uninitialized_move_a(T* dest, It first, It last) {
 489     D_uninitialized_copy_a(dest,
 490       std::make_move_iterator(first), std::make_move_iterator(last));
 491   }
 492
 493   // allocator
 494   template <typename It>
 495   static void
 496   S_uninitialized_copy_a(Allocator& a, T* dest, It first, It last) {
 497     auto b = dest;
 498     try {
 499       for (; first != last; ++first, ++b)
 500         std::allocator_traits<Allocator>::construct(a, b, *first);
 501     } catch (...) {
 502       S_destroy_range_a(a, dest, b);
 503       throw;
 504     }
 505   }
 506
 507   // optimized
 508   template <typename It>
 509   static void S_uninitialized_copy(T* dest, It first, It last) {
 510     auto b = dest;
 511     try {
 512       for (; first != last; ++first, ++b)
 513         S_construct(b, *first);
 514     } catch (...) {
 515       S_destroy_range(dest, b);
 516       throw;
 517     }
 518   }
 519
 520   static void
 521   S_uninitialized_copy_bits(T* dest, const T* first, const T* last) {
 522     if (last != first) {
 523       std::memcpy((void*)dest, (void*)first, (last - first) * sizeof(T));
 524     }
 525   }
 526
 527   static void
 528   S_uninitialized_copy_bits(T* dest, std::move_iterator<T*> first,
 529                        std::move_iterator<T*> last) {
 530     T* bFirst = first.base();
 531     T* bLast = last.base();
 532     if (bLast != bFirst) {
 533       std::memcpy((void*)dest, (void*)bFirst, (bLast - bFirst) * sizeof(T));
 534     }
 535   }
 536
 537   template <typename It>
 538   static void
 539   S_uninitialized_copy_bits(T* dest, It first, It last) {
 540     S_uninitialized_copy(dest, first, last);
 541   }
 542
 543   //---------------------------------------------------------------------------
 544   // copy_n
 545
 546   // This function is "unsafe": it assumes that the iterator can be advanced at
 547   //  least n times. However, as a private function, that unsafety is managed
 548   //  wholly by fbvector itself.
 549
 550   template <typename It>
 551   static It S_copy_n(T* dest, It first, size_type n) {
 552     auto e = dest + n;
 553     for (; dest != e; ++dest, ++first) *dest = *first;
 554     return first;
 555   }
 556
 557   static const T* S_copy_n(T* dest, const T* first, size_type n) {
 558     if (folly::IsTriviallyCopyable<T>::value) {
 559       std::memcpy((void*)dest, (void*)first, n * sizeof(T));
 560       return first + n;
 561     } else {
 562       return S_copy_n<const T*>(dest, first, n);
 563     }
 564   }
 565
 566   static std::move_iterator<T*>
 567   S_copy_n(T* dest, std::move_iterator<T*> mIt, size_type n) {
 568     if (folly::IsTriviallyCopyable<T>::value) {
 569       T* first = mIt.base();
 570       std::memcpy((void*)dest, (void*)first, n * sizeof(T));
 571       return std::make_move_iterator(first + n);
 572     } else {
 573       return S_copy_n<std::move_iterator<T*>>(dest, mIt, n);
 574     }
 575   }
 576
 577   //===========================================================================
 578   //---------------------------------------------------------------------------
 579   // relocation helpers
 580  private:
 581   // Relocation is divided into three parts:
 582   //
 583   //  1: relocate_move
 584   //     Performs the actual movement of data from point a to point b.
 585   //
 586   //  2: relocate_done
 587   //     Destroys the old data.
 588   //
 589   //  3: relocate_undo
 590   //     Destoys the new data and restores the old data.
 591   //
 592   // The three steps are used because there may be an exception after part 1
 593   //  has completed. If that is the case, then relocate_undo can nullify the
 594   //  initial move. Otherwise, relocate_done performs the last bit of tidying
 595   //  up.
 596   //
 597   // The relocation trio may use either memcpy, move, or copy. It is decided
 598   //  by the following case statement:
 599   //
 600   //  IsRelocatable && usingStdAllocator    -> memcpy
 601   //  has_nothrow_move && usingStdAllocator -> move
 602   //  cannot copy                           -> move
 603   //  default                               -> copy
 604   //
 605   // If the class is non-copyable then it must be movable. However, if the
 606   //  move constructor is not noexcept, i.e. an error could be thrown, then
 607   //  relocate_undo will be unable to restore the old data, for fear of a
 608   //  second exception being thrown. This is a known and unavoidable
 609   //  deficiency. In lieu of a strong exception guarantee, relocate_undo does
 610   //  the next best thing: it provides a weak exception guarantee by
 611   //  destorying the new data, but leaving the old data in an indeterminate
 612   //  state. Note that that indeterminate state will be valid, since the
 613   //  old data has not been destroyed; it has merely been the source of a
 614   //  move, which is required to leave the source in a valid state.
 615
 616   // wrappers
 617   void M_relocate(T* newB) {
 618     relocate_move(newB, impl_.b_, impl_.e_);
 619     relocate_done(newB, impl_.b_, impl_.e_);
 620   }
 621
 622   // dispatch type trait
 623   typedef std::integral_constant<bool,
 624       folly::IsRelocatable<T>::value && usingStdAllocator::value
 625     > relocate_use_memcpy;
 626
 627   typedef std::integral_constant<bool,
 628       (std::is_nothrow_move_constructible<T>::value
 629        && usingStdAllocator::value)
 630       || !std::is_copy_constructible<T>::value
 631     > relocate_use_move;
 632
 633   // move
 634   void relocate_move(T* dest, T* first, T* last) {
 635     relocate_move_or_memcpy(dest, first, last, relocate_use_memcpy());
 636   }
 637
 638   void relocate_move_or_memcpy(T* dest, T* first, T* last, std::true_type) {
 639     if (first != nullptr) {
 640       std::memcpy((void*)dest, (void*)first, (last - first) * sizeof(T));
 641     }
 642   }
 643
 644   void relocate_move_or_memcpy(T* dest, T* first, T* last, std::false_type) {
 645     relocate_move_or_copy(dest, first, last, relocate_use_move());
 646   }
 647
 648   void relocate_move_or_copy(T* dest, T* first, T* last, std::true_type) {
 649     D_uninitialized_move_a(dest, first, last);
 650   }
 651
 652   void relocate_move_or_copy(T* dest, T* first, T* last, std::false_type) {
 653     D_uninitialized_copy_a(dest, first, last);
 654   }
 655
 656   // done
 657   void relocate_done(T* /*dest*/, T* first, T* last) noexcept {
 658     if (folly::IsRelocatable<T>::value && usingStdAllocator::value) {
 659       // used memcpy; data has been relocated, do not call destructor
 660     } else {
 661       D_destroy_range_a(first, last);
 662     }
 663   }
 664
 665   // undo
 666   void relocate_undo(T* dest, T* first, T* last) noexcept {
 667     if (folly::IsRelocatable<T>::value && usingStdAllocator::value) {
 668       // used memcpy, old data is still valid, nothing to do
 669     } else if (std::is_nothrow_move_constructible<T>::value &&
 670                usingStdAllocator::value) {
 671       // noexcept move everything back, aka relocate_move
 672       relocate_move(first, dest, dest + (last - first));
 673     } else if (!std::is_copy_constructible<T>::value) {
 674       // weak guarantee
 675       D_destroy_range_a(dest, dest + (last - first));
 676     } else {
 677       // used copy, old data is still valid
 678       D_destroy_range_a(dest, dest + (last - first));
 679     }
 680   }
 681
 682
 683   //===========================================================================
 684   //---------------------------------------------------------------------------
 685   // construct/copy/destroy
 686  public:
 687   fbvector() = default;
 688
 689   explicit fbvector(const Allocator& a) : impl_(a) {}
 690
 691   explicit fbvector(size_type n, const Allocator& a = Allocator())
 692     : impl_(n, a)
 693     { M_uninitialized_fill_n_e(n); }
 694
 695   fbvector(size_type n, VT value, const Allocator& a = Allocator())
 696     : impl_(n, a)
 697     { M_uninitialized_fill_n_e(n, value); }
 698
 699   template <class It, class Category = typename
 700             std::iterator_traits<It>::iterator_category>
 701   fbvector(It first, It last, const Allocator& a = Allocator())
 702     : fbvector(first, last, a, Category()) {}
 703
 704   fbvector(const fbvector& other)
 705     : impl_(other.size(), A::select_on_container_copy_construction(other.impl_))
 706     { M_uninitialized_copy_e(other.begin(), other.end()); }
 707
 708   fbvector(fbvector&& other) noexcept : impl_(std::move(other.impl_)) {}
 709
 710   fbvector(const fbvector& other, const Allocator& a)
 711     : fbvector(other.begin(), other.end(), a) {}
 712
 713   /* may throw */ fbvector(fbvector&& other, const Allocator& a) : impl_(a) {
 714     if (impl_ == other.impl_) {
 715       impl_.swapData(other.impl_);
 716     } else {
 717       impl_.init(other.size());
 718       M_uninitialized_move_e(other.begin(), other.end());
 719     }
 720   }
 721
 722   fbvector(std::initializer_list<T> il, const Allocator& a = Allocator())
 723     : fbvector(il.begin(), il.end(), a) {}
 724
 725   ~fbvector() = default; // the cleanup occurs in impl_
 726
 727   fbvector& operator=(const fbvector& other) {
 728     if (UNLIKELY(this == &other)) return *this;
 729
 730     if (!usingStdAllocator::value &&
 731         A::propagate_on_container_copy_assignment::value) {
 732       if (impl_ != other.impl_) {
 733         // can't use other's different allocator to clean up self
 734         impl_.reset();
 735       }
 736       (Allocator&)impl_ = (Allocator&)other.impl_;
 737     }
 738
 739     assign(other.begin(), other.end());
 740     return *this;
 741   }
 742
 743   fbvector& operator=(fbvector&& other) {
 744     if (UNLIKELY(this == &other)) return *this;
 745     moveFrom(std::move(other), moveIsSwap());
 746     return *this;
 747   }
 748
 749   fbvector& operator=(std::initializer_list<T> il) {
 750     assign(il.begin(), il.end());
 751     return *this;
 752   }
 753
 754   template <class It, class Category = typename
 755             std::iterator_traits<It>::iterator_category>
 756   void assign(It first, It last) {
 757     assign(first, last, Category());
 758   }
 759
 760   void assign(size_type n, VT value) {
 761     if (n > capacity()) {
 762       // Not enough space. Do not reserve in place, since we will
 763       // discard the old values anyways.
 764       if (dataIsInternalAndNotVT(value)) {
 765         T copy(std::move(value));
 766         impl_.reset(n);
 767         M_uninitialized_fill_n_e(n, copy);
 768       } else {
 769         impl_.reset(n);
 770         M_uninitialized_fill_n_e(n, value);
 771       }
 772     } else if (n <= size()) {
 773       auto newE = impl_.b_ + n;
 774       std::fill(impl_.b_, newE, value);
 775       M_destroy_range_e(newE);
 776     } else {
 777       std::fill(impl_.b_, impl_.e_, value);
 778       M_uninitialized_fill_n_e(n - size(), value);
 779     }
 780   }
 781
 782   void assign(std::initializer_list<T> il) {
 783     assign(il.begin(), il.end());
 784   }
 785
 786   allocator_type get_allocator() const noexcept {
 787     return impl_;
 788   }
 789
 790  private:
 791   // contract dispatch for iterator types fbvector(It first, It last)
 792   template <class ForwardIterator>
 793   fbvector(ForwardIterator first, ForwardIterator last,
 794            const Allocator& a, std::forward_iterator_tag)
 795     : impl_(size_type(std::distance(first, last)), a)
 796     { M_uninitialized_copy_e(first, last); }
 797
 798   template <class InputIterator>
 799   fbvector(InputIterator first, InputIterator last,
 800            const Allocator& a, std::input_iterator_tag)
 801     : impl_(a)
 802     { for (; first != last; ++first) emplace_back(*first); }
 803
 804   // contract dispatch for allocator movement in operator=(fbvector&&)
 805   void
 806   moveFrom(fbvector&& other, std::true_type) {
 807     swap(impl_, other.impl_);
 808   }
 809   void moveFrom(fbvector&& other, std::false_type) {
 810     if (impl_ == other.impl_) {
 811       impl_.swapData(other.impl_);
 812     } else {
 813       impl_.reset(other.size());
 814       M_uninitialized_move_e(other.begin(), other.end());
 815     }
 816   }
 817
 818   // contract dispatch for iterator types in assign(It first, It last)
 819   template <class ForwardIterator>
 820   void assign(ForwardIterator first, ForwardIterator last,
 821               std::forward_iterator_tag) {
 822     const auto newSize = size_type(std::distance(first, last));
 823     if (newSize > capacity()) {
 824       impl_.reset(newSize);
 825       M_uninitialized_copy_e(first, last);
 826     } else if (newSize <= size()) {
 827       auto newEnd = std::copy(first, last, impl_.b_);
 828       M_destroy_range_e(newEnd);
 829     } else {
 830       auto mid = S_copy_n(impl_.b_, first, size());
 831       M_uninitialized_copy_e<decltype(last)>(mid, last);
 832     }
 833   }
 834
 835   template <class InputIterator>
 836   void assign(InputIterator first, InputIterator last,
 837               std::input_iterator_tag) {
 838     auto p = impl_.b_;
 839     for (; first != last && p != impl_.e_; ++first, ++p) {
 840       *p = *first;
 841     }
 842     if (p != impl_.e_) {
 843       M_destroy_range_e(p);
 844     } else {
 845       for (; first != last; ++first) emplace_back(*first);
 846     }
 847   }
 848
 849   // contract dispatch for aliasing under VT optimization
 850   bool dataIsInternalAndNotVT(const T& t) {
 851     if (should_pass_by_value::value) return false;
 852     return dataIsInternal(t);
 853   }
 854   bool dataIsInternal(const T& t) {
 855     return UNLIKELY(impl_.b_ <= std::addressof(t) &&
 856                     std::addressof(t) < impl_.e_);
 857   }
 858
 859
 860   //===========================================================================
 861   //---------------------------------------------------------------------------
 862   // iterators
 863  public:
 864   iterator begin() noexcept {
 865     return impl_.b_;
 866   }
 867   const_iterator begin() const noexcept {
 868     return impl_.b_;
 869   }
 870   iterator end() noexcept {
 871     return impl_.e_;
 872   }
 873   const_iterator end() const noexcept {
 874     return impl_.e_;
 875   }
 876   reverse_iterator rbegin() noexcept {
 877     return reverse_iterator(end());
 878   }
 879   const_reverse_iterator rbegin() const noexcept {
 880     return const_reverse_iterator(end());
 881   }
 882   reverse_iterator rend() noexcept {
 883     return reverse_iterator(begin());
 884   }
 885   const_reverse_iterator rend() const noexcept {
 886     return const_reverse_iterator(begin());
 887   }
 888
 889   const_iterator cbegin() const noexcept {
 890     return impl_.b_;
 891   }
 892   const_iterator cend() const noexcept {
 893     return impl_.e_;
 894   }
 895   const_reverse_iterator crbegin() const noexcept {
 896     return const_reverse_iterator(end());
 897   }
 898   const_reverse_iterator crend() const noexcept {
 899     return const_reverse_iterator(begin());
 900   }
 901
 902   //===========================================================================
 903   //---------------------------------------------------------------------------
 904   // capacity
 905  public:
 906   size_type size() const noexcept {
 907     return size_type(impl_.e_ - impl_.b_);
 908   }
 909
 910   size_type max_size() const noexcept {
 911     // good luck gettin' there
 912     return ~size_type(0);
 913   }
 914
 915   void resize(size_type n) {
 916     if (n <= size()) {
 917       M_destroy_range_e(impl_.b_ + n);
 918     } else {
 919       reserve(n);
 920       M_uninitialized_fill_n_e(n - size());
 921     }
 922   }
 923
 924   void resize(size_type n, VT t) {
 925     if (n <= size()) {
 926       M_destroy_range_e(impl_.b_ + n);
 927     } else if (dataIsInternalAndNotVT(t) && n > capacity()) {
 928       T copy(t);
 929       reserve(n);
 930       M_uninitialized_fill_n_e(n - size(), copy);
 931     } else {
 932       reserve(n);
 933       M_uninitialized_fill_n_e(n - size(), t);
 934     }
 935   }
 936
 937   size_type capacity() const noexcept {
 938     return size_type(impl_.z_ - impl_.b_);
 939   }
 940
 941   bool empty() const noexcept {
 942     return impl_.b_ == impl_.e_;
 943   }
 944
 945   void reserve(size_type n) {
 946     if (n <= capacity()) return;
 947     if (impl_.b_ && reserve_in_place(n)) return;
 948
 949     auto newCap = folly::goodMallocSize(n * sizeof(T)) / sizeof(T);
 950     auto newB = M_allocate(newCap);
 951     try {
 952       M_relocate(newB);
 953     } catch (...) {
 954       M_deallocate(newB, newCap);
 955       throw;
 956     }
 957     if (impl_.b_)
 958       M_deallocate(impl_.b_, size_type(impl_.z_ - impl_.b_));
 959     impl_.z_ = newB + newCap;
 960     impl_.e_ = newB + (impl_.e_ - impl_.b_);
 961     impl_.b_ = newB;
 962   }
 963
 964   void shrink_to_fit() noexcept {
 965     if (empty()) {
 966       impl_.reset();
 967       return;
 968     }
 969
 970     auto const newCapacityBytes = folly::goodMallocSize(size() * sizeof(T));
 971     auto const newCap = newCapacityBytes / sizeof(T);
 972     auto const oldCap = capacity();
 973
 974     if (newCap >= oldCap) return;
 975
 976     void* p = impl_.b_;
 977     // xallocx() will shrink to precisely newCapacityBytes (which was generated
 978     // by goodMallocSize()) if it successfully shrinks in place.
 979     if ((usingJEMalloc() && usingStdAllocator::value) &&
 980         newCapacityBytes >= folly::jemallocMinInPlaceExpandable &&
 981         xallocx(p, newCapacityBytes, 0, 0) == newCapacityBytes) {
 982       impl_.z_ += newCap - oldCap;
 983     } else {
 984       T* newB; // intentionally uninitialized
 985       try {
 986         newB = M_allocate(newCap);
 987         try {
 988           M_relocate(newB);
 989         } catch (...) {
 990           M_deallocate(newB, newCap);
 991           return; // swallow the error
 992         }
 993       } catch (...) {
 994         return;
 995       }
 996       if (impl_.b_)
 997         M_deallocate(impl_.b_, size_type(impl_.z_ - impl_.b_));
 998       impl_.z_ = newB + newCap;
 999       impl_.e_ = newB + (impl_.e_ - impl_.b_);
1000       impl_.b_ = newB;
1001     }
1002   }
1003
1004  private:
1005   bool reserve_in_place(size_type n) {
1006     if (!usingStdAllocator::value || !usingJEMalloc()) return false;
1007
1008     // jemalloc can never grow in place blocks smaller than 4096 bytes.
1009     if ((impl_.z_ - impl_.b_) * sizeof(T) <
1010       folly::jemallocMinInPlaceExpandable) return false;
1011
1012     auto const newCapacityBytes = folly::goodMallocSize(n * sizeof(T));
1013     void* p = impl_.b_;
1014     if (xallocx(p, newCapacityBytes, 0, 0) == newCapacityBytes) {
1015       impl_.z_ = impl_.b_ + newCapacityBytes / sizeof(T);
1016       return true;
1017     }
1018     return false;
1019   }
1020
1021   //===========================================================================
1022   //---------------------------------------------------------------------------
1023   // element access
1024  public:
1025   reference operator[](size_type n) {
1026     assert(n < size());
1027     return impl_.b_[n];
1028   }
1029   const_reference operator[](size_type n) const {
1030     assert(n < size());
1031     return impl_.b_[n];
1032   }
1033   const_reference at(size_type n) const {
1034     if (UNLIKELY(n >= size())) {
1035       std::__throw_out_of_range("fbvector: index is greater than size.");
1036     }
1037     return (*this)[n];
1038   }
1039   reference at(size_type n) {
1040     auto const& cThis = *this;
1041     return const_cast<reference>(cThis.at(n));
1042   }
1043   reference front() {
1044     assert(!empty());
1045     return *impl_.b_;
1046   }
1047   const_reference front() const {
1048     assert(!empty());
1049     return *impl_.b_;
1050   }
1051   reference back()  {
1052     assert(!empty());
1053     return impl_.e_[-1];
1054   }
1055   const_reference back() const {
1056     assert(!empty());
1057     return impl_.e_[-1];
1058   }
1059
1060   //===========================================================================
1061   //---------------------------------------------------------------------------
1062   // data access
1063  public:
1064   T* data() noexcept {
1065     return impl_.b_;
1066   }
1067   const T* data() const noexcept {
1068     return impl_.b_;
1069   }
1070
1071   //===========================================================================
1072   //---------------------------------------------------------------------------
1073   // modifiers (common)
1074  public:
1075   template <class... Args>
1076   void emplace_back(Args&&... args)  {
1077     if (impl_.e_ != impl_.z_) {
1078       M_construct(impl_.e_, std::forward<Args>(args)...);
1079       ++impl_.e_;
1080     } else {
1081       emplace_back_aux(std::forward<Args>(args)...);
1082     }
1083   }
1084
1085   void
1086   push_back(const T& value) {
1087     if (impl_.e_ != impl_.z_) {
1088       M_construct(impl_.e_, value);
1089       ++impl_.e_;
1090     } else {
1091       emplace_back_aux(value);
1092     }
1093   }
1094
1095   void
1096   push_back(T&& value) {
1097     if (impl_.e_ != impl_.z_) {
1098       M_construct(impl_.e_, std::move(value));
1099       ++impl_.e_;
1100     } else {
1101       emplace_back_aux(std::move(value));
1102     }
1103   }
1104
1105   void pop_back() {
1106     assert(!empty());
1107     --impl_.e_;
1108     M_destroy(impl_.e_);
1109   }
1110
1111   void swap(fbvector& other) noexcept {
1112     if (!usingStdAllocator::value &&
1113         A::propagate_on_container_swap::value)
1114       swap(impl_, other.impl_);
1115     else impl_.swapData(other.impl_);
1116   }
1117
1118   void clear() noexcept {
1119     M_destroy_range_e(impl_.b_);
1120   }
1121
1122  private:
1123   // std::vector implements a similar function with a different growth
1124   //  strategy: empty() ? 1 : capacity() * 2.
1125   //
1126   // fbvector grows differently on two counts:
1127   //
1128   // (1) initial size
1129   //     Instead of growing to size 1 from empty, fbvector allocates at least
1130   //     64 bytes. You may still use reserve to reserve a lesser amount of
1131   //     memory.
1132   // (2) 1.5x
1133   //     For medium-sized vectors, the growth strategy is 1.5x. See the docs
1134   //     for details.
1135   //     This does not apply to very small or very large fbvectors. This is a
1136   //     heuristic.
1137   //     A nice addition to fbvector would be the capability of having a user-
1138   //     defined growth strategy, probably as part of the allocator.
1139   //
1140
1141   size_type computePushBackCapacity() const {
1142     if (capacity() == 0) {
1143       return std::max(64 / sizeof(T), size_type(1));
1144     }
1145     if (capacity() < folly::jemallocMinInPlaceExpandable / sizeof(T)) {
1146       return capacity() * 2;
1147     }
1148     if (capacity() > 4096 * 32 / sizeof(T)) {
1149       return capacity() * 2;
1150     }
1151     return (capacity() * 3 + 1) / 2;
1152   }
1153
1154   template <class... Args>
1155   void emplace_back_aux(Args&&... args);
1156
1157   //===========================================================================
1158   //---------------------------------------------------------------------------
1159   // modifiers (erase)
1160  public:
1161   iterator erase(const_iterator position) {
1162     return erase(position, position + 1);
1163   }
1164
1165   iterator erase(const_iterator first, const_iterator last) {
1166     assert(isValid(first) && isValid(last));
1167     assert(first <= last);
1168     if (first != last) {
1169       if (last == end()) {
1170         M_destroy_range_e((iterator)first);
1171       } else {
1172         if (folly::IsRelocatable<T>::value && usingStdAllocator::value) {
1173           D_destroy_range_a((iterator)first, (iterator)last);
1174           if (last - first >= cend() - last) {
1175             std::memcpy((void*)first, (void*)last, (cend() - last) * sizeof(T));
1176           } else {
1177             std::memmove((iterator)first, last, (cend() - last) * sizeof(T));
1178           }
1179           impl_.e_ -= (last - first);
1180         } else {
1181           std::copy(std::make_move_iterator((iterator)last),
1182                     std::make_move_iterator(end()), (iterator)first);
1183           auto newEnd = impl_.e_ - std::distance(first, last);
1184           M_destroy_range_e(newEnd);
1185         }
1186       }
1187     }
1188     return (iterator)first;
1189   }
1190
1191   //===========================================================================
1192   //---------------------------------------------------------------------------
1193   // modifiers (insert)
1194  private: // we have the private section first because it defines some macros
1195   bool isValid(const_iterator it) {
1196     return cbegin() <= it && it <= cend();
1197   }
1198
1199   size_type computeInsertCapacity(size_type n) {
1200     size_type nc = std::max(computePushBackCapacity(), size() + n);
1201     size_type ac = folly::goodMallocSize(nc * sizeof(T)) / sizeof(T);
1202     return ac;
1203   }
1204
1205   //---------------------------------------------------------------------------
1206   //
1207   // make_window takes an fbvector, and creates an uninitialized gap (a
1208   //  window) at the given position, of the given size. The fbvector must
1209   //  have enough capacity.
1210   //
1211   // Explanation by picture.
1212   //
1213   //    123456789______
1214   //        ^
1215   //        make_window here of size 3
1216   //
1217   //    1234___56789___
1218   //
1219   // If something goes wrong and the window must be destroyed, use
1220   //  undo_window to provide a weak exception guarantee. It destroys
1221   //  the right ledge.
1222   //
1223   //    1234___________
1224   //
1225   //---------------------------------------------------------------------------
1226   //
1227   // wrap_frame takes an inverse window and relocates an fbvector around it.
1228   //  The fbvector must have at least as many elements as the left ledge.
1229   //
1230   // Explanation by picture.
1231   //
1232   //        START
1233   //    fbvector:             inverse window:
1234   //    123456789______       _____abcde_______
1235   //                          [idx][ n ]
1236   //
1237   //        RESULT
1238   //    _______________       12345abcde6789___
1239   //
1240   //---------------------------------------------------------------------------
1241   //
1242   // insert_use_fresh_memory returns true iff the fbvector should use a fresh
1243   //  block of memory for the insertion. If the fbvector does not have enough
1244   //  spare capacity, then it must return true. Otherwise either true or false
1245   //  may be returned.
1246   //
1247   //---------------------------------------------------------------------------
1248   //
1249   // These three functions, make_window, wrap_frame, and
1250   //  insert_use_fresh_memory, can be combined into a uniform interface.
1251   // Since that interface involves a lot of case-work, it is built into
1252   //  some macros: FOLLY_FBVECTOR_INSERT_(PRE|START|TRY|END)
1253   // Macros are used in an attempt to let GCC perform better optimizations,
1254   //  especially control flow optimization.
1255   //
1256
1257   //---------------------------------------------------------------------------
1258   // window
1259
1260   void make_window(iterator position, size_type n) {
1261     // The result is guaranteed to be non-negative, so use an unsigned type:
1262     size_type tail = size_type(std::distance(position, impl_.e_));
1263
1264     if (tail <= n) {
1265       relocate_move(position + n, position, impl_.e_);
1266       relocate_done(position + n, position, impl_.e_);
1267       impl_.e_ += n;
1268     } else {
1269       if (folly::IsRelocatable<T>::value && usingStdAllocator::value) {
1270         std::memmove(position + n, position, tail * sizeof(T));
1271         impl_.e_ += n;
1272       } else {
1273         D_uninitialized_move_a(impl_.e_, impl_.e_ - n, impl_.e_);
1274         try {
1275           std::copy_backward(std::make_move_iterator(position),
1276                              std::make_move_iterator(impl_.e_ - n), impl_.e_);
1277         } catch (...) {
1278           D_destroy_range_a(impl_.e_ - n, impl_.e_ + n);
1279           impl_.e_ -= n;
1280           throw;
1281         }
1282         impl_.e_ += n;
1283         D_destroy_range_a(position, position + n);
1284       }
1285     }
1286   }
1287
1288   void undo_window(iterator position, size_type n) noexcept {
1289     D_destroy_range_a(position + n, impl_.e_);
1290     impl_.e_ = position;
1291   }
1292
1293   //---------------------------------------------------------------------------
1294   // frame
1295
1296   void wrap_frame(T* ledge, size_type idx, size_type n) {
1297     assert(size() >= idx);
1298     assert(n != 0);
1299
1300     relocate_move(ledge, impl_.b_, impl_.b_ + idx);
1301     try {
1302       relocate_move(ledge + idx + n, impl_.b_ + idx, impl_.e_);
1303     } catch (...) {
1304       relocate_undo(ledge, impl_.b_, impl_.b_ + idx);
1305       throw;
1306     }
1307     relocate_done(ledge, impl_.b_, impl_.b_ + idx);
1308     relocate_done(ledge + idx + n, impl_.b_ + idx, impl_.e_);
1309   }
1310
1311   //---------------------------------------------------------------------------
1312   // use fresh?
1313
1314   bool insert_use_fresh(bool at_end, size_type n) {
1315     if (at_end) {
1316       if (size() + n <= capacity()) return false;
1317       if (reserve_in_place(size() + n)) return false;
1318       return true;
1319     }
1320
1321     if (size() + n > capacity()) return true;
1322
1323     return false;
1324   }
1325
1326   //---------------------------------------------------------------------------
1327   // interface
1328
1329   template <
1330       typename IsInternalFunc,
1331       typename InsertInternalFunc,
1332       typename ConstructFunc,
1333       typename DestroyFunc>
1334   iterator do_real_insert(
1335       const_iterator cpos,
1336       size_type n,
1337       IsInternalFunc&& isInternalFunc,
1338       InsertInternalFunc&& insertInternalFunc,
1339       ConstructFunc&& constructFunc,
1340       DestroyFunc&& destroyFunc) {
1341     if (n == 0) {
1342       return iterator(cpos);
1343     }
1344     bool at_end = cpos == cend();
1345     bool fresh = insert_use_fresh(at_end, n);
1346     if (!at_end) {
1347       if (!fresh && isInternalFunc()) {
1348         // check for internal data (technically not required by the standard)
1349         return insertInternalFunc();
1350       }
1351       assert(isValid(cpos));
1352     }
1353     T* position = const_cast<T*>(cpos);
1354     size_type idx = size_type(std::distance(impl_.b_, position));
1355     T* b;
1356     size_type newCap; /* intentionally uninitialized */
1357
1358     if (fresh) {
1359       newCap = computeInsertCapacity(n);
1360       b = M_allocate(newCap);
1361     } else {
1362       if (!at_end) {
1363         make_window(position, n);
1364       } else {
1365         impl_.e_ += n;
1366       }
1367       b = impl_.b_;
1368     }
1369
1370     T* start = b + idx;
1371     try {
1372       // construct the inserted elements
1373       constructFunc(start);
1374     } catch (...) {
1375       if (fresh) {
1376         M_deallocate(b, newCap);
1377       } else {
1378         if (!at_end) {
1379           undo_window(position, n);
1380         } else {
1381           impl_.e_ -= n;
1382         }
1383       }
1384       throw;
1385     }
1386
1387     if (fresh) {
1388       try {
1389         wrap_frame(b, idx, n);
1390       } catch (...) {
1391         // delete the inserted elements (exception has been thrown)
1392         destroyFunc(start);
1393         M_deallocate(b, newCap);
1394         throw;
1395       }
1396       if (impl_.b_) {
1397         M_deallocate(impl_.b_, capacity());
1398       }
1399       impl_.set(b, size() + n, newCap);
1400       return impl_.b_ + idx;
1401     } else {
1402       return position;
1403     }
1404   }
1405
1406  public:
1407   template <class... Args>
1408   iterator emplace(const_iterator cpos, Args&&... args) {
1409     return do_real_insert(
1410         cpos,
1411         1,
1412         [&] { return false; },
1413         [&] { return iterator{}; },
1414         [&](iterator start) {
1415           M_construct(start, std::forward<Args>(args)...);
1416         },
1417         [&](iterator start) { M_destroy(start); });
1418   }
1419
1420   iterator insert(const_iterator cpos, const T& value) {
1421     return do_real_insert(
1422         cpos,
1423         1,
1424         [&] { return dataIsInternal(value); },
1425         [&] { return insert(cpos, T(value)); },
1426         [&](iterator start) { M_construct(start, value); },
1427         [&](iterator start) { M_destroy(start); });
1428   }
1429
1430   iterator insert(const_iterator cpos, T&& value) {
1431     return do_real_insert(
1432         cpos,
1433         1,
1434         [&] { return dataIsInternal(value); },
1435         [&] { return insert(cpos, T(std::move(value))); },
1436         [&](iterator start) { M_construct(start, std::move(value)); },
1437         [&](iterator start) { M_destroy(start); });
1438   }
1439
1440   iterator insert(const_iterator cpos, size_type n, VT value) {
1441     return do_real_insert(
1442         cpos,
1443         n,
1444         [&] { return dataIsInternalAndNotVT(value); },
1445         [&] { return insert(cpos, n, T(value)); },
1446         [&](iterator start) { D_uninitialized_fill_n_a(start, n, value); },
1447         [&](iterator start) { D_destroy_range_a(start, start + n); });
1448   }
1449
1450   template <class It, class Category = typename
1451             std::iterator_traits<It>::iterator_category>
1452   iterator insert(const_iterator cpos, It first, It last) {
1453     return insert(cpos, first, last, Category());
1454   }
1455
1456   iterator insert(const_iterator cpos, std::initializer_list<T> il) {
1457     return insert(cpos, il.begin(), il.end());
1458   }
1459
1460   //---------------------------------------------------------------------------
1461   // insert dispatch for iterator types
1462  private:
1463   template <class FIt>
1464   iterator insert(const_iterator cpos, FIt first, FIt last,
1465                   std::forward_iterator_tag) {
1466     size_type n = size_type(std::distance(first, last));
1467     return do_real_insert(
1468         cpos,
1469         n,
1470         [&] { return false; },
1471         [&] { return iterator{}; },
1472         [&](iterator start) { D_uninitialized_copy_a(start, first, last); },
1473         [&](iterator start) { D_destroy_range_a(start, start + n); });
1474   }
1475
1476   template <class IIt>
1477   iterator insert(const_iterator cpos, IIt first, IIt last,
1478                   std::input_iterator_tag) {
1479     T* position = const_cast<T*>(cpos);
1480     assert(isValid(position));
1481     size_type idx = std::distance(begin(), position);
1482
1483     fbvector storage(std::make_move_iterator(position),
1484                      std::make_move_iterator(end()),
1485                      A::select_on_container_copy_construction(impl_));
1486     M_destroy_range_e(position);
1487     for (; first != last; ++first) emplace_back(*first);
1488     insert(cend(), std::make_move_iterator(storage.begin()),
1489            std::make_move_iterator(storage.end()));
1490     return impl_.b_ + idx;
1491   }
1492
1493   //===========================================================================
1494   //---------------------------------------------------------------------------
1495   // lexicographical functions
1496  public:
1497   bool operator==(const fbvector& other) const {
1498     return size() == other.size() && std::equal(begin(), end(), other.begin());
1499   }
1500
1501   bool operator!=(const fbvector& other) const {
1502     return !(*this == other);
1503   }
1504
1505   bool operator<(const fbvector& other) const {
1506     return std::lexicographical_compare(
1507       begin(), end(), other.begin(), other.end());
1508   }
1509
1510   bool operator>(const fbvector& other) const {
1511     return other < *this;
1512   }
1513
1514   bool operator<=(const fbvector& other) const {
1515     return !(*this > other);
1516   }
1517
1518   bool operator>=(const fbvector& other) const {
1519     return !(*this < other);
1520   }
1521
1522   //===========================================================================
1523   //---------------------------------------------------------------------------
1524   // friends
1525  private:
1526   template <class _T, class _A>
1527   friend _T* relinquish(fbvector<_T, _A>&);
1528
1529   template <class _T, class _A>
1530   friend void attach(fbvector<_T, _A>&, _T* data, size_t sz, size_t cap);
1531
1532 }; // class fbvector
1533
1534
1535 //=============================================================================
1536 //-----------------------------------------------------------------------------
1537 // outlined functions (gcc, you finicky compiler you)
1538
1539 template <typename T, typename Allocator>
1540 template <class... Args>
1541 void fbvector<T, Allocator>::emplace_back_aux(Args&&... args) {
1542   size_type byte_sz = folly::goodMallocSize(
1543     computePushBackCapacity() * sizeof(T));
1544   if (usingStdAllocator::value
1545       && usingJEMalloc()
1546       && ((impl_.z_ - impl_.b_) * sizeof(T) >=
1547           folly::jemallocMinInPlaceExpandable)) {
1548     // Try to reserve in place.
1549     // Ask xallocx to allocate in place at least size()+1 and at most sz space.
1550     // xallocx will allocate as much as possible within that range, which
1551     //  is the best possible outcome: if sz space is available, take it all,
1552     //  otherwise take as much as possible. If nothing is available, then fail.
1553     // In this fashion, we never relocate if there is a possibility of
1554     //  expanding in place, and we never reallocate by less than the desired
1555     //  amount unless we cannot expand further. Hence we will not reallocate
1556     //  sub-optimally twice in a row (modulo the blocking memory being freed).
1557     size_type lower = folly::goodMallocSize(sizeof(T) + size() * sizeof(T));
1558     size_type upper = byte_sz;
1559     size_type extra = upper - lower;
1560
1561     void* p = impl_.b_;
1562     size_t actual;
1563
1564     if ((actual = xallocx(p, lower, extra, 0)) >= lower) {
1565       impl_.z_ = impl_.b_ + actual / sizeof(T);
1566       M_construct(impl_.e_, std::forward<Args>(args)...);
1567       ++impl_.e_;
1568       return;
1569     }
1570   }
1571
1572   // Reallocation failed. Perform a manual relocation.
1573   size_type sz = byte_sz / sizeof(T);
1574   auto newB = M_allocate(sz);
1575   auto newE = newB + size();
1576   try {
1577     if (folly::IsRelocatable<T>::value && usingStdAllocator::value) {
1578       // For linear memory access, relocate before construction.
1579       // By the test condition, relocate is noexcept.
1580       // Note that there is no cleanup to do if M_construct throws - that's
1581       //  one of the beauties of relocation.
1582       // Benchmarks for this code have high variance, and seem to be close.
1583       relocate_move(newB, impl_.b_, impl_.e_);
1584       M_construct(newE, std::forward<Args>(args)...);
1585       ++newE;
1586     } else {
1587       M_construct(newE, std::forward<Args>(args)...);
1588       ++newE;
1589       try {
1590         M_relocate(newB);
1591       } catch (...) {
1592         M_destroy(newE - 1);
1593         throw;
1594       }
1595     }
1596   } catch (...) {
1597     M_deallocate(newB, sz);
1598     throw;
1599   }
1600   if (impl_.b_) M_deallocate(impl_.b_, size());
1601   impl_.b_ = newB;
1602   impl_.e_ = newE;
1603   impl_.z_ = newB + sz;
1604 }
1605
1606 //=============================================================================
1607 //-----------------------------------------------------------------------------
1608 // specialized functions
1609
1610 template <class T, class A>
1611 void swap(fbvector<T, A>& lhs, fbvector<T, A>& rhs) noexcept {
1612   lhs.swap(rhs);
1613 }
1614
1615 //=============================================================================
1616 //-----------------------------------------------------------------------------
1617 // other
1618
1619 namespace detail {
1620
1621 // Format support.
1622 template <class T, class A>
1623 struct IndexableTraits<fbvector<T, A>>
1624   : public IndexableTraitsSeq<fbvector<T, A>> {
1625 };
1626
1627 } // namespace detail
1628
1629 template <class T, class A>
1630 void compactResize(fbvector<T, A>* v, size_t sz) {
1631   v->resize(sz);
1632   v->shrink_to_fit();
1633 }
1634
1635 // DANGER
1636 //
1637 // relinquish and attach are not a members function specifically so that it is
1638 //  awkward to call them. It is very easy to shoot yourself in the foot with
1639 //  these functions.
1640 //
1641 // If you call relinquish, then it is your responsibility to free the data
1642 //  and the storage, both of which may have been generated in a non-standard
1643 //  way through the fbvector's allocator.
1644 //
1645 // If you call attach, it is your responsibility to ensure that the fbvector
1646 //  is fresh (size and capacity both zero), and that the supplied data is
1647 //  capable of being manipulated by the allocator.
1648 // It is acceptable to supply a stack pointer IF:
1649 //  (1) The vector's data does not outlive the stack pointer. This includes
1650 //      extension of the data's life through a move operation.
1651 //  (2) The pointer has enough capacity that the vector will never be
1652 //      relocated.
1653 //  (3) Insert is not called on the vector; these functions have leeway to
1654 //      relocate the vector even if there is enough capacity.
1655 //  (4) A stack pointer is compatible with the fbvector's allocator.
1656 //
1657
1658 template <class T, class A>
1659 T* relinquish(fbvector<T, A>& v) {
1660   T* ret = v.data();
1661   v.impl_.b_ = v.impl_.e_ = v.impl_.z_ = nullptr;
1662   return ret;
1663 }
1664
1665 template <class T, class A>
1666 void attach(fbvector<T, A>& v, T* data, size_t sz, size_t cap) {
1667   assert(v.data() == nullptr);
1668   v.impl_.b_ = data;
1669   v.impl_.e_ = data + sz;
1670   v.impl_.z_ = data + cap;
1671 }
1672
1673 } // namespace folly