folly/FBVector.h

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