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