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 //=============================================================================
  45 // forward declaration
  46
  47 namespace folly {
  48   template <class T, class Allocator = std::allocator<T>>
  49   class fbvector;
  50 }
  51
  52 //=============================================================================
  53 // unrolling
  54
  55 #define FOLLY_FBV_UNROLL_PTR(first, last, OP) do {  \
  56   for (; (last) - (first) >= 4; (first) += 4) {     \
  57     OP(((first) + 0));                              \
  58     OP(((first) + 1));                              \
  59     OP(((first) + 2));                              \
  60     OP(((first) + 3));                              \
  61   }                                                 \
  62   for (; (first) != (last); ++(first)) OP((first)); \
  63 } while(0);
  64
  65 //=============================================================================
  66 ///////////////////////////////////////////////////////////////////////////////
  67 //                                                                           //
  68 //                              fbvector class                               //
  69 //                                                                           //
  70 ///////////////////////////////////////////////////////////////////////////////
  71
  72 namespace folly {
  73
  74 template <class T, class Allocator>
  75 class fbvector {
  76
  77   //===========================================================================
  78   //---------------------------------------------------------------------------
  79   // implementation
  80 private:
  81
  82   typedef std::allocator_traits<Allocator> A;
  83
  84   struct Impl : public Allocator {
  85     // typedefs
  86     typedef typename A::pointer pointer;
  87     typedef typename A::size_type size_type;
  88
  89     // data
  90     pointer b_, e_, z_;
  91
  92     // constructors
  93     Impl() : Allocator(), b_(nullptr), e_(nullptr), z_(nullptr) {}
  94     /* implicit */ Impl(const Allocator& a)
  95       : Allocator(a), b_(nullptr), e_(nullptr), z_(nullptr) {}
  96     /* implicit */ Impl(Allocator&& a)
  97       : Allocator(std::move(a)), b_(nullptr), e_(nullptr), z_(nullptr) {}
  98
  99     /* implicit */ Impl(size_type n, const Allocator& a = Allocator())
 100       : Allocator(a)
 101       { init(n); }
 102
 103     Impl(Impl&& other) noexcept
 104       : Allocator(std::move(other)),
 105         b_(other.b_), e_(other.e_), z_(other.z_)
 106       { other.b_ = other.e_ = other.z_ = nullptr; }
 107
 108     // destructor
 109     ~Impl() {
 110       destroy();
 111     }
 112
 113     // allocation
 114     // note that 'allocate' and 'deallocate' are inherited from Allocator
 115     T* D_allocate(size_type n) {
 116       if (usingStdAllocator::value) {
 117         return static_cast<T*>(malloc(n * sizeof(T)));
 118       } else {
 119         return std::allocator_traits<Allocator>::allocate(*this, n);
 120       }
 121     }
 122
 123     void D_deallocate(T* p, size_type n) noexcept {
 124       if (usingStdAllocator::value) {
 125         free(p);
 126       } else {
 127         std::allocator_traits<Allocator>::deallocate(*this, p, n);
 128       }
 129     }
 130
 131     // helpers
 132     void swapData(Impl& other) {
 133       std::swap(b_, other.b_);
 134       std::swap(e_, other.e_);
 135       std::swap(z_, other.z_);
 136     }
 137
 138     // data ops
 139     inline void destroy() noexcept {
 140       if (b_) {
 141         // THIS DISPATCH CODE IS DUPLICATED IN fbvector::D_destroy_range_a.
 142         // It has been inlined here for speed. It calls the static fbvector
 143         //  methods to perform the actual destruction.
 144         if (usingStdAllocator::value) {
 145           S_destroy_range(b_, e_);
 146         } else {
 147           S_destroy_range_a(*this, b_, e_);
 148         }
 149
 150         D_deallocate(b_, size_type(z_ - b_));
 151       }
 152     }
 153
 154     void init(size_type n) {
 155       if (UNLIKELY(n == 0)) {
 156         b_ = e_ = z_ = nullptr;
 157       } else {
 158         size_type sz = folly::goodMallocSize(n * sizeof(T)) / sizeof(T);
 159         b_ = D_allocate(sz);
 160         e_ = b_;
 161         z_ = b_ + sz;
 162       }
 163     }
 164
 165     void set(pointer newB, size_type newSize, size_type newCap) {
 166       z_ = newB + newCap;
 167       e_ = newB + newSize;
 168       b_ = newB;
 169     }
 170
 171     void reset(size_type newCap) {
 172       destroy();
 173       try {
 174         init(newCap);
 175       } catch (...) {
 176         init(0);
 177         throw;
 178       }
 179     }
 180     void reset() { // same as reset(0)
 181       destroy();
 182       b_ = e_ = z_ = nullptr;
 183     }
 184   } impl_;
 185
 186   static void swap(Impl& a, Impl& b) {
 187     using std::swap;
 188     if (!usingStdAllocator::value) swap<Allocator>(a, b);
 189     a.swapData(b);
 190   }
 191
 192   //===========================================================================
 193   //---------------------------------------------------------------------------
 194   // types and constants
 195 public:
 196
 197   typedef T                                           value_type;
 198   typedef value_type&                                 reference;
 199   typedef const value_type&                           const_reference;
 200   typedef T*                                          iterator;
 201   typedef const T*                                    const_iterator;
 202   typedef size_t                                      size_type;
 203   typedef typename std::make_signed<size_type>::type  difference_type;
 204   typedef Allocator                                   allocator_type;
 205   typedef typename A::pointer                         pointer;
 206   typedef typename A::const_pointer                   const_pointer;
 207   typedef std::reverse_iterator<iterator>             reverse_iterator;
 208   typedef std::reverse_iterator<const_iterator>       const_reverse_iterator;
 209
 210 private:
 211
 212   typedef std::integral_constant<bool,
 213       boost::has_trivial_copy_constructor<T>::value &&
 214       sizeof(T) <= 16 // don't force large structures to be passed by value
 215     > should_pass_by_value;
 216   typedef typename std::conditional<
 217       should_pass_by_value::value, T, const T&>::type VT;
 218   typedef typename std::conditional<
 219       should_pass_by_value::value, T, T&&>::type MT;
 220
 221   typedef std::integral_constant<bool,
 222       std::is_same<Allocator, std::allocator<T>>::value> usingStdAllocator;
 223   typedef std::integral_constant<bool,
 224       usingStdAllocator::value ||
 225       A::propagate_on_container_move_assignment::value> moveIsSwap;
 226
 227   //===========================================================================
 228   //---------------------------------------------------------------------------
 229   // allocator helpers
 230 private:
 231
 232   //---------------------------------------------------------------------------
 233   // allocate
 234
 235   T* M_allocate(size_type n) {
 236     return impl_.D_allocate(n);
 237   }
 238
 239   //---------------------------------------------------------------------------
 240   // deallocate
 241
 242   void M_deallocate(T* p, size_type n) noexcept {
 243     impl_.D_deallocate(p, n);
 244   }
 245
 246   //---------------------------------------------------------------------------
 247   // construct
 248
 249   // GCC is very sensitive to the exact way that construct is called. For
 250   //  that reason there are several different specializations of construct.
 251
 252   template <typename U, typename... Args>
 253   void M_construct(U* p, Args&&... args) {
 254     if (usingStdAllocator::value) {
 255       new (p) U(std::forward<Args>(args)...);
 256     } else {
 257       std::allocator_traits<Allocator>::construct(
 258         impl_, p, std::forward<Args>(args)...);
 259     }
 260   }
 261
 262   template <typename U, typename... Args>
 263   static void S_construct(U* p, Args&&... args) {
 264     new (p) U(std::forward<Args>(args)...);
 265   }
 266
 267   template <typename U, typename... Args>
 268   static void S_construct_a(Allocator& a, U* p, Args&&... args) {
 269     std::allocator_traits<Allocator>::construct(
 270       a, p, std::forward<Args>(args)...);
 271   }
 272
 273   // scalar optimization
 274   // TODO we can expand this optimization to: default copyable and assignable
 275   template <typename U, typename Enable = typename
 276     std::enable_if<std::is_scalar<U>::value>::type>
 277   void M_construct(U* p, U arg) {
 278     if (usingStdAllocator::value) {
 279       *p = arg;
 280     } else {
 281       std::allocator_traits<Allocator>::construct(impl_, p, arg);
 282     }
 283   }
 284
 285   template <typename U, typename Enable = typename
 286     std::enable_if<std::is_scalar<U>::value>::type>
 287   static void S_construct(U* p, U arg) {
 288     *p = arg;
 289   }
 290
 291   template <typename U, typename Enable = typename
 292     std::enable_if<std::is_scalar<U>::value>::type>
 293   static void S_construct_a(Allocator& a, U* p, U arg) {
 294     std::allocator_traits<Allocator>::construct(a, p, arg);
 295   }
 296
 297   // const& optimization
 298   template <typename U, typename Enable = typename
 299     std::enable_if<!std::is_scalar<U>::value>::type>
 300   void M_construct(U* p, const U& value) {
 301     if (usingStdAllocator::value) {
 302       new (p) U(value);
 303     } else {
 304       std::allocator_traits<Allocator>::construct(impl_, p, value);
 305     }
 306   }
 307
 308   template <typename U, typename Enable = typename
 309     std::enable_if<!std::is_scalar<U>::value>::type>
 310   static void S_construct(U* p, const U& value) {
 311     new (p) U(value);
 312   }
 313
 314   template <typename U, typename Enable = typename
 315     std::enable_if<!std::is_scalar<U>::value>::type>
 316   static void S_construct_a(Allocator& a, U* p, const U& value) {
 317     std::allocator_traits<Allocator>::construct(a, p, value);
 318   }
 319
 320   //---------------------------------------------------------------------------
 321   // destroy
 322
 323   void M_destroy(T* p) noexcept {
 324     if (usingStdAllocator::value) {
 325       if (!boost::has_trivial_destructor<T>::value) p->~T();
 326     } else {
 327       std::allocator_traits<Allocator>::destroy(impl_, p);
 328     }
 329   }
 330
 331   //===========================================================================
 332   //---------------------------------------------------------------------------
 333   // algorithmic helpers
 334 private:
 335
 336   //---------------------------------------------------------------------------
 337   // destroy_range
 338
 339   // wrappers
 340   void M_destroy_range_e(T* pos) noexcept {
 341     D_destroy_range_a(pos, impl_.e_);
 342     impl_.e_ = pos;
 343   }
 344
 345   // dispatch
 346   // THIS DISPATCH CODE IS DUPLICATED IN IMPL. SEE IMPL FOR DETAILS.
 347   void D_destroy_range_a(T* first, T* last) noexcept {
 348     if (usingStdAllocator::value) {
 349       S_destroy_range(first, last);
 350     } else {
 351       S_destroy_range_a(impl_, first, last);
 352     }
 353   }
 354
 355   // allocator
 356   static void S_destroy_range_a(Allocator& a, T* first, T* last) noexcept {
 357     for (; first != last; ++first)
 358       std::allocator_traits<Allocator>::destroy(a, first);
 359   }
 360
 361   // optimized
 362   static void S_destroy_range(T* first, T* last) noexcept {
 363     if (!boost::has_trivial_destructor<T>::value) {
 364       // EXPERIMENTAL DATA on fbvector<vector<int>> (where each vector<int> has
 365       //  size 0).
 366       // The unrolled version seems to work faster for small to medium sized
 367       //  fbvectors. It gets a 10% speedup on fbvectors of size 1024, 64, and
 368       //  16.
 369       // The simple loop version seems to work faster for large fbvectors. The
 370       //  unrolled version is about 6% slower on fbvectors on size 16384.
 371       // The two methods seem tied for very large fbvectors. The unrolled
 372       //  version is about 0.5% slower on size 262144.
 373
 374       // for (; first != last; ++first) first->~T();
 375       #define FOLLY_FBV_OP(p) (p)->~T()
 376       FOLLY_FBV_UNROLL_PTR(first, last, FOLLY_FBV_OP)
 377       #undef FOLLY_FBV_OP
 378     }
 379   }
 380
 381   //---------------------------------------------------------------------------
 382   // uninitialized_fill_n
 383
 384   // wrappers
 385   void M_uninitialized_fill_n_e(size_type sz) {
 386     D_uninitialized_fill_n_a(impl_.e_, sz);
 387     impl_.e_ += sz;
 388   }
 389
 390   void M_uninitialized_fill_n_e(size_type sz, VT value) {
 391     D_uninitialized_fill_n_a(impl_.e_, sz, value);
 392     impl_.e_ += sz;
 393   }
 394
 395   // dispatch
 396   void D_uninitialized_fill_n_a(T* dest, size_type sz) {
 397     if (usingStdAllocator::value) {
 398       S_uninitialized_fill_n(dest, sz);
 399     } else {
 400       S_uninitialized_fill_n_a(impl_, dest, sz);
 401     }
 402   }
 403
 404   void D_uninitialized_fill_n_a(T* dest, size_type sz, VT value) {
 405     if (usingStdAllocator::value) {
 406       S_uninitialized_fill_n(dest, sz, value);
 407     } else {
 408       S_uninitialized_fill_n_a(impl_, dest, sz, value);
 409     }
 410   }
 411
 412   // allocator
 413   template <typename... Args>
 414   static void S_uninitialized_fill_n_a(Allocator& a, T* dest,
 415                                        size_type sz, Args&&... args) {
 416     auto b = dest;
 417     auto e = dest + sz;
 418     try {
 419       for (; b != e; ++b)
 420         std::allocator_traits<Allocator>::construct(a, b,
 421           std::forward<Args>(args)...);
 422     } catch (...) {
 423       S_destroy_range_a(a, dest, b);
 424       throw;
 425     }
 426   }
 427
 428   // optimized
 429   static void S_uninitialized_fill_n(T* dest, size_type n) {
 430     if (folly::IsZeroInitializable<T>::value) {
 431       if (LIKELY(n != 0)) {
 432         std::memset(dest, 0, sizeof(T) * n);
 433       }
 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 size_type(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 size_type(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_, size_type(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
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 !(*this == other);
1512   }
1513
1514   bool operator<(const fbvector& other) const {
1515     return std::lexicographical_compare(
1516       begin(), end(), other.begin(), other.end());
1517   }
1518
1519   bool operator>(const fbvector& other) const {
1520     return other < *this;
1521   }
1522
1523   bool operator<=(const fbvector& other) const {
1524     return !(*this > other);
1525   }
1526
1527   bool operator>=(const fbvector& other) const {
1528     return !(*this < other);
1529   }
1530
1531   //===========================================================================
1532   //---------------------------------------------------------------------------
1533   // friends
1534 private:
1535
1536   template <class _T, class _A>
1537   friend _T* relinquish(fbvector<_T, _A>&);
1538
1539   template <class _T, class _A>
1540   friend void attach(fbvector<_T, _A>&, _T* data, size_t sz, size_t cap);
1541
1542 }; // class fbvector
1543
1544
1545 //=============================================================================
1546 //-----------------------------------------------------------------------------
1547 // outlined functions (gcc, you finicky compiler you)
1548
1549 template <typename T, typename Allocator>
1550 template <class... Args>
1551 void fbvector<T, Allocator>::emplace_back_aux(Args&&... args) {
1552   size_type byte_sz = folly::goodMallocSize(
1553     computePushBackCapacity() * sizeof(T));
1554   if (usingStdAllocator::value
1555       && usingJEMalloc()
1556       && ((impl_.z_ - impl_.b_) * sizeof(T) >=
1557           folly::jemallocMinInPlaceExpandable)) {
1558     // Try to reserve in place.
1559     // Ask xallocx to allocate in place at least size()+1 and at most sz space.
1560     // xallocx will allocate as much as possible within that range, which
1561     //  is the best possible outcome: if sz space is available, take it all,
1562     //  otherwise take as much as possible. If nothing is available, then fail.
1563     // In this fashion, we never relocate if there is a possibility of
1564     //  expanding in place, and we never reallocate by less than the desired
1565     //  amount unless we cannot expand further. Hence we will not reallocate
1566     //  sub-optimally twice in a row (modulo the blocking memory being freed).
1567     size_type lower = folly::goodMallocSize(sizeof(T) + size() * sizeof(T));
1568     size_type upper = byte_sz;
1569     size_type extra = upper - lower;
1570
1571     void* p = impl_.b_;
1572     size_t actual;
1573
1574     if ((actual = xallocx(p, lower, extra, 0)) >= lower) {
1575       impl_.z_ = impl_.b_ + actual / sizeof(T);
1576       M_construct(impl_.e_, std::forward<Args>(args)...);
1577       ++impl_.e_;
1578       return;
1579     }
1580   }
1581
1582   // Reallocation failed. Perform a manual relocation.
1583   size_type sz = byte_sz / sizeof(T);
1584   auto newB = M_allocate(sz);
1585   auto newE = newB + size();
1586   try {
1587     if (folly::IsRelocatable<T>::value && usingStdAllocator::value) {
1588       // For linear memory access, relocate before construction.
1589       // By the test condition, relocate is noexcept.
1590       // Note that there is no cleanup to do if M_construct throws - that's
1591       //  one of the beauties of relocation.
1592       // Benchmarks for this code have high variance, and seem to be close.
1593       relocate_move(newB, impl_.b_, impl_.e_);
1594       M_construct(newE, std::forward<Args>(args)...);
1595       ++newE;
1596     } else {
1597       M_construct(newE, std::forward<Args>(args)...);
1598       ++newE;
1599       try {
1600         M_relocate(newB);
1601       } catch (...) {
1602         M_destroy(newE - 1);
1603         throw;
1604       }
1605     }
1606   } catch (...) {
1607     M_deallocate(newB, sz);
1608     throw;
1609   }
1610   if (impl_.b_) M_deallocate(impl_.b_, size());
1611   impl_.b_ = newB;
1612   impl_.e_ = newE;
1613   impl_.z_ = newB + sz;
1614 }
1615
1616 //=============================================================================
1617 //-----------------------------------------------------------------------------
1618 // specialized functions
1619
1620 template <class T, class A>
1621 void swap(fbvector<T, A>& lhs, fbvector<T, A>& rhs) noexcept {
1622   lhs.swap(rhs);
1623 }
1624
1625 //=============================================================================
1626 //-----------------------------------------------------------------------------
1627 // other
1628
1629 namespace detail {
1630
1631 // Format support.
1632 template <class T, class A>
1633 struct IndexableTraits<fbvector<T, A>>
1634   : public IndexableTraitsSeq<fbvector<T, A>> {
1635 };
1636
1637 }  // namespace detail
1638
1639 template <class T, class A>
1640 void compactResize(fbvector<T, A>* v, size_t sz) {
1641   v->resize(sz);
1642   v->shrink_to_fit();
1643 }
1644
1645 // DANGER
1646 //
1647 // relinquish and attach are not a members function specifically so that it is
1648 //  awkward to call them. It is very easy to shoot yourself in the foot with
1649 //  these functions.
1650 //
1651 // If you call relinquish, then it is your responsibility to free the data
1652 //  and the storage, both of which may have been generated in a non-standard
1653 //  way through the fbvector's allocator.
1654 //
1655 // If you call attach, it is your responsibility to ensure that the fbvector
1656 //  is fresh (size and capacity both zero), and that the supplied data is
1657 //  capable of being manipulated by the allocator.
1658 // It is acceptable to supply a stack pointer IF:
1659 //  (1) The vector's data does not outlive the stack pointer. This includes
1660 //      extension of the data's life through a move operation.
1661 //  (2) The pointer has enough capacity that the vector will never be
1662 //      relocated.
1663 //  (3) Insert is not called on the vector; these functions have leeway to
1664 //      relocate the vector even if there is enough capacity.
1665 //  (4) A stack pointer is compatible with the fbvector's allocator.
1666 //
1667
1668 template <class T, class A>
1669 T* relinquish(fbvector<T, A>& v) {
1670   T* ret = v.data();
1671   v.impl_.b_ = v.impl_.e_ = v.impl_.z_ = nullptr;
1672   return ret;
1673 }
1674
1675 template <class T, class A>
1676 void attach(fbvector<T, A>& v, T* data, size_t sz, size_t cap) {
1677   assert(v.data() == nullptr);
1678   v.impl_.b_ = data;
1679   v.impl_.e_ = data + sz;
1680   v.impl_.z_ = data + cap;
1681 }
1682
1683 } // namespace folly