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