folly/FBVector.h

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