folly/FBVector.h

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