folly/test/stl_tests/OFBVector.h

   1 /*
   2  * Copyright 2013 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 // Andrei Alexandrescu (aalexandre)
  18
  19 /**
  20  * Vector type. Drop-in replacement for std::vector featuring
  21  * significantly faster primitives, see e.g. benchmark results at
  22  * https:*phabricator.fb.com/D235852.
  23  *
  24  * In order for a type to be used with fbvector, it must be
  25  * relocatable, see Traits.h.
  26  *
  27  * For user-defined types you must specialize templates
  28  * appropriately. Consult Traits.h for ways to do so and for a handy
  29  * family of macros FOLLY_ASSUME_FBVECTOR_COMPATIBLE*.
  30  *
  31  * For more information and documentation see folly/docs/FBVector.md
  32  */
  33
  34 #ifndef FOLLY_FBVECTOR_H_
  35 #define FOLLY_FBVECTOR_H_
  36
  37 #include "folly/Foreach.h"
  38 #include "folly/Malloc.h"
  39 #include "folly/Traits.h"
  40 #include <iterator>
  41 #include <algorithm>
  42 #include <stdexcept>
  43 #include <limits>
  44 #include <cassert>
  45 #include <boost/type_traits.hpp>
  46 #include <boost/operators.hpp>
  47 #include <boost/utility/enable_if.hpp>
  48 #include <type_traits>
  49
  50 namespace folly {
  51 /**
  52  * Forward declaration for use by FOLLY_ASSUME_FBVECTOR_COMPATIBLE_2,
  53  * see folly/Traits.h.
  54  */
  55 template <typename T, class Allocator = std::allocator<T> >
  56 class fbvector;
  57 }
  58
  59 // You can define an fbvector of fbvectors.
  60 FOLLY_ASSUME_FBVECTOR_COMPATIBLE_2(folly::fbvector);
  61
  62 namespace folly {
  63 namespace fbvector_detail {
  64
  65 /**
  66  * isForwardIterator<T>::value yields true if T is a forward iterator
  67  * or better, and false otherwise.
  68  */
  69 template <class It> struct isForwardIterator {
  70   enum { value = boost::is_convertible<
  71          typename std::iterator_traits<It>::iterator_category,
  72          std::forward_iterator_tag>::value
  73   };
  74 };
  75
  76 /**
  77  * Destroys all elements in the range [b, e). If the type referred to
  78  * by the iterators has a trivial destructor, does nothing.
  79  */
  80 template <class It>
  81 void destroyRange(It b, It e) {
  82   typedef typename boost::remove_reference<decltype(*b)>::type T;
  83   if (boost::has_trivial_destructor<T>::value) return;
  84   for (; b != e; ++b) {
  85     (*b).~T();
  86   }
  87 }
  88
  89 /**
  90  * Moves the "interesting" part of value to the uninitialized memory
  91  * at address addr, and leaves value in a destroyable state.
  92  */
  93
  94 template <class T>
  95 typename boost::enable_if_c<
  96   boost::has_trivial_assign<T>::value
  97 >::type
  98 uninitialized_destructive_move(T& value, T* addr) {
  99   // Just assign the thing; this is most efficient
 100   *addr = value;
 101 }
 102
 103 template <class T>
 104 typename boost::enable_if_c<
 105   !boost::has_trivial_assign<T>::value &&
 106   boost::has_nothrow_constructor<T>::value
 107 >::type
 108 uninitialized_destructive_move(T& value, T* addr) {
 109   // Cheap default constructor - move and reinitialize
 110   memcpy(addr, &value, sizeof(T));
 111   new(&value) T;
 112 }
 113
 114 template <class T>
 115 typename std::enable_if<
 116   !boost::has_trivial_assign<T>::value &&
 117   !boost::has_nothrow_constructor<T>::value
 118 >::type
 119 uninitialized_destructive_move(T& value, T* addr) {
 120   // User defined move construction.
 121
 122   // TODO: we should probably prefer this over the above memcpy()
 123   // version when the type has a user-defined move constructor.  We
 124   // don't right now because 4.6 doesn't implement
 125   // std::is_move_constructible<> yet.
 126   new (addr) T(std::move(value));
 127 }
 128
 129 /**
 130  * Fills n objects of type T starting at address b with T's default
 131  * value. If the operation throws, destroys all objects constructed so
 132  * far and calls free(b).
 133  */
 134 template <class T>
 135 void uninitializedFillDefaultOrFree(T * b, size_t n) {
 136   if (boost::is_arithmetic<T>::value || boost::is_pointer<T>::value) {
 137     if (n <= 16384 / sizeof(T)) {
 138       memset(b, 0, n * sizeof(T));
 139     } else {
 140       goto duff_fill;
 141     }
 142   } else if (boost::has_nothrow_constructor<T>::value) {
 143     duff_fill:
 144     auto i = b;
 145     auto const e1 = b + (n & ~size_t(7));
 146     for (; i != e1; i += 8) {
 147       new(i) T();
 148       new(i + 1) T();
 149       new(i + 2) T();
 150       new(i + 3) T();
 151       new(i + 4) T();
 152       new(i + 5) T();
 153       new(i + 6) T();
 154       new(i + 7) T();
 155     }
 156     for (auto const e = b + n; i != e; ++i) {
 157       new(i) T();
 158     }
 159   } else {
 160     // Conservative approach
 161     auto i = b;
 162     try {
 163       for (auto const e = b + n; i != e; ++i) {
 164         new(i) T;
 165       }
 166     } catch (...) {
 167       destroyRange(b, i);
 168       free(b);
 169       throw;
 170     }
 171   }
 172 }
 173
 174 /**
 175  * Fills n objects of type T starting at address b with value. If the
 176  * operation throws, destroys all objects constructed so far and calls
 177  * free(b).
 178  */
 179 template <class T>
 180 void uninitializedFillOrFree(T * b, size_t n, const T& value) {
 181   auto const e = b + n;
 182   if (FOLLY_IS_TRIVIALLY_COPYABLE(T)) {
 183     auto i = b;
 184     auto const e1 = b + (n & ~size_t(7));
 185     for (; i != e1; i += 8) {
 186       new(i) T(value);
 187       new(i + 1) T(value);
 188       new(i + 2) T(value);
 189       new(i + 3) T(value);
 190       new(i + 4) T(value);
 191       new(i + 5) T(value);
 192       new(i + 6) T(value);
 193       new(i + 7) T(value);
 194     }
 195     for (; i != e; ++i) {
 196       new(i) T(value);
 197     }
 198   } else {
 199     // Conservative approach
 200     auto i = b;
 201     try {
 202       for (; i != e; ++i) {
 203         new(i) T(value);
 204       }
 205     } catch (...) {
 206       destroyRange(b, i);
 207       free(b);
 208       throw;
 209     }
 210   }
 211 }
 212 } // namespace fbvector_detail
 213
 214 /**
 215  * This is the std::vector replacement. For conformity, fbvector takes
 216  * the same template parameters, but it doesn't use the
 217  * allocator. Instead, it uses malloc, and when present, jemalloc's
 218  * extensions.
 219  */
 220 template <class T, class Allocator>
 221 class fbvector : private boost::totally_ordered<fbvector<T,Allocator> > {
 222   bool isSane() const {
 223     return
 224       begin() <= end() &&
 225       empty() == (size() == 0) &&
 226       empty() == (begin() == end()) &&
 227       size() <= max_size() &&
 228       capacity() <= max_size() &&
 229       size() <= capacity() &&
 230
 231       // Either we have no capacity or our pointers should make sense:
 232       ((!b_ && !e_ && !z_) || (b_ != z_ && e_ <= z_));
 233   }
 234
 235   struct Invariant {
 236 #ifndef NDEBUG
 237     explicit Invariant(const fbvector& s) : s_(s) {
 238       assert(s_.isSane());
 239     }
 240     ~Invariant() {
 241       assert(s_.isSane());
 242     }
 243   private:
 244     const fbvector& s_;
 245 #else
 246     explicit Invariant(const fbvector&) {}
 247 #endif
 248     Invariant& operator=(const Invariant&);
 249   };
 250
 251 public:
 252
 253 // types:
 254   typedef T value_type;
 255   typedef value_type& reference;
 256   typedef const value_type& const_reference;
 257   typedef T* iterator;
 258   typedef const T* const_iterator;
 259   typedef size_t size_type;
 260   typedef ssize_t difference_type;
 261   // typedef typename allocator_traits<Allocator>::pointer pointer;
 262   // typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
 263   typedef Allocator allocator_type;
 264   typedef typename Allocator::pointer pointer;
 265   typedef typename Allocator::const_pointer const_pointer;
 266   typedef std::reverse_iterator<iterator> reverse_iterator;
 267   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 268
 269 // 23.3.6.1 construct/copy/destroy:
 270   fbvector() : b_(NULL), e_(NULL), z_(NULL) {}
 271
 272   explicit fbvector(const Allocator&) {
 273     new(this) fbvector;
 274   }
 275
 276   explicit fbvector(const size_type n) {
 277     if (n == 0) {
 278       b_ = e_ = z_ = 0;
 279       return;
 280     }
 281
 282     auto const nBytes = goodMallocSize(n * sizeof(T));
 283     b_ = static_cast<T*>(checkedMalloc(nBytes));
 284     fbvector_detail::uninitializedFillDefaultOrFree(b_, n);
 285     e_ = b_ + n;
 286     z_ = b_ + nBytes / sizeof(T);
 287   }
 288
 289   fbvector(const size_type n, const T& value) {
 290     if (!n) {
 291       b_ = e_ = z_ = 0;
 292       return;
 293     }
 294
 295     auto const nBytes = goodMallocSize(n * sizeof(T));
 296     b_ = static_cast<T*>(checkedMalloc(nBytes));
 297     fbvector_detail::uninitializedFillOrFree(b_, n, value);
 298     e_ = b_ + n;
 299     z_ = b_ + nBytes / sizeof(T);
 300   }
 301
 302   fbvector(const size_type n, const T& value, const Allocator&) {
 303     new(this) fbvector(n, value);
 304   }
 305
 306   template <class InputIteratorOrNum>
 307   fbvector(InputIteratorOrNum first, InputIteratorOrNum last) {
 308     new(this) fbvector;
 309     assign(first, last);
 310   }
 311
 312   template <class InputIterator>
 313   fbvector(InputIterator first, InputIterator last,
 314            const Allocator&) {
 315     new(this) fbvector(first, last);
 316   }
 317
 318   fbvector(const fbvector& rhs) {
 319     new(this) fbvector(rhs.begin(), rhs.end());
 320   }
 321   fbvector(const fbvector& rhs, const Allocator&) {
 322     new(this) fbvector(rhs);
 323   }
 324
 325   fbvector(fbvector&& o, const Allocator& = Allocator())
 326     : b_(o.b_)
 327     , e_(o.e_)
 328     , z_(o.z_)
 329   {
 330     o.b_ = o.e_ = o.z_ = 0;
 331   }
 332
 333   fbvector(std::initializer_list<T> il, const Allocator& = Allocator()) {
 334     new(this) fbvector(il.begin(), il.end());
 335   }
 336
 337   ~fbvector() {
 338     // fbvector only works with relocatable objects. We insert this
 339     // static check inside the destructor because pretty much any
 340     // instantiation of fbvector<T> will generate the destructor (and
 341     // therefore refuse compilation if the assertion fails). To see
 342     // how you can enable IsRelocatable for your type, refer to the
 343     // definition of IsRelocatable in Traits.h.
 344     BOOST_STATIC_ASSERT(IsRelocatable<T>::value);
 345     if (!b_) return;
 346     fbvector_detail::destroyRange(b_, e_);
 347     free(b_);
 348   }
 349   fbvector& operator=(const fbvector& rhs) {
 350     assign(rhs.begin(), rhs.end());
 351     return *this;
 352   }
 353
 354   fbvector& operator=(fbvector&& v) {
 355     clear();
 356     swap(v);
 357     return *this;
 358   }
 359
 360   fbvector& operator=(std::initializer_list<T> il) {
 361     assign(il.begin(), il.end());
 362     return *this;
 363   }
 364
 365   bool operator==(const fbvector& rhs) const {
 366     return size() == rhs.size() && std::equal(begin(), end(), rhs.begin());
 367   }
 368
 369   bool operator<(const fbvector& rhs) const {
 370     return std::lexicographical_compare(begin(), end(),
 371                                         rhs.begin(), rhs.end());
 372   }
 373
 374 private:
 375   template <class InputIterator>
 376   void assignImpl(InputIterator first, InputIterator last, boost::false_type) {
 377     // Pair of iterators
 378     if (fbvector_detail::isForwardIterator<InputIterator>::value) {
 379       auto const oldSize = size();
 380       auto const newSize = std::distance(first, last);
 381
 382       if (static_cast<difference_type>(oldSize) >= newSize) {
 383         // No reallocation, nice
 384         auto const newEnd = std::copy(first, last, b_);
 385         fbvector_detail::destroyRange(newEnd, e_);
 386         e_ = newEnd;
 387         return;
 388       }
 389
 390       // Must reallocate - just do it on the side
 391       auto const nBytes = goodMallocSize(newSize * sizeof(T));
 392       auto const b = static_cast<T*>(checkedMalloc(nBytes));
 393       std::uninitialized_copy(first, last, b);
 394       this->fbvector::~fbvector();
 395       b_ = b;
 396       e_ = b + newSize;
 397       z_ = b_ + nBytes / sizeof(T);
 398     } else {
 399       // Input iterator sucks
 400       FOR_EACH (i, *this) {
 401         if (first == last) {
 402           fbvector_detail::destroyRange(i, e_);
 403           e_ = i;
 404           return;
 405         }
 406         *i = *first;
 407         ++first;
 408       }
 409       FOR_EACH_RANGE (i, first, last) {
 410         push_back(*i);
 411       }
 412     }
 413   }
 414
 415   void assignImpl(const size_type newSize, const T value, boost::true_type) {
 416     // Arithmetic type, forward back to unambiguous definition
 417     assign(newSize, value);
 418   }
 419
 420 public:
 421   // Classic ambiguity (and a lot of unnecessary complexity) in
 422   // std::vector: assign(10, 20) for vector<int> means "assign 10
 423   // elements all having the value 20" but is intercepted by the
 424   // two-iterators overload assign(first, last). So we need to
 425   // disambiguate here. There is no pretty solution. We use here
 426   // overloading based on is_arithmetic. Method insert has the same
 427   // issue (and the same solution in this implementation).
 428   template <class InputIteratorOrNum>
 429   void assign(InputIteratorOrNum first, InputIteratorOrNum last) {
 430     assignImpl(first, last, boost::is_arithmetic<InputIteratorOrNum>());
 431   }
 432
 433   void assign(const size_type newSize, const T& value) {
 434     if (b_ <= &value && &value < e_) {
 435       // Need to check for aliased assign, sigh
 436       return assign(newSize, T(value));
 437     }
 438
 439     auto const oldSize = size();
 440     if (oldSize >= newSize) {
 441       // No reallocation, nice
 442       auto const newEnd = b_ + newSize;
 443       fbvector_detail::destroyRange(newEnd, e_);
 444       e_ = newEnd;
 445       return;
 446     }
 447
 448     // Need to reallocate
 449     if (reserve_in_place(newSize)) {
 450       // Careful here, fill and uninitialized_fill may throw. The
 451       // latter is transactional, so no need to worry about a
 452       // buffer partially filled in case of exception.
 453       std::fill(b_, e_, value);
 454       auto const newEnd = b_ + newSize;
 455       std::uninitialized_fill(e_, newEnd, value);
 456       e_ = newEnd;
 457       return;
 458     }
 459
 460     // Cannot expand or jemalloc not present at all; must just
 461     // allocate a new chunk and discard the old one. This is
 462     // tantamount with creating a new fbvector altogether. This won't
 463     // recurse infinitely; the constructor implements its own.
 464     fbvector temp(newSize, value);
 465     temp.swap(*this);
 466   }
 467
 468   void assign(std::initializer_list<T> il) {
 469     assign(il.begin(), il.end());
 470   }
 471
 472   allocator_type get_allocator() const {
 473     // whatevs
 474     return allocator_type();
 475   }
 476
 477 // iterators:
 478   iterator begin() {
 479     return b_;
 480   }
 481   const_iterator begin() const {
 482     return b_;
 483   }
 484   iterator end() {
 485     return e_;
 486   }
 487   const_iterator end() const {
 488     return e_;
 489   }
 490   reverse_iterator rbegin() {
 491     return reverse_iterator(end());
 492   }
 493   const_reverse_iterator rbegin() const {
 494     return const_reverse_iterator(end());
 495   }
 496   reverse_iterator rend() {
 497     return reverse_iterator(begin());
 498   }
 499   const_reverse_iterator rend() const {
 500     return const_reverse_iterator(begin());
 501   }
 502   const_iterator cbegin() const {
 503     return b_;
 504   }
 505   const_iterator cend() const {
 506     return e_;
 507   }
 508
 509 // 23.3.6.2 capacity:
 510   size_type size() const {
 511     return e_ - b_;
 512   }
 513
 514   size_type max_size() {
 515     // good luck gettin' there
 516     return ~size_type(0);
 517   }
 518
 519   void resize(const size_type sz) {
 520     auto const oldSize = size();
 521     if (sz <= oldSize) {
 522       auto const newEnd = b_ + sz;
 523       fbvector_detail::destroyRange(newEnd, e_);
 524       e_ = newEnd;
 525     } else {
 526       // Must expand
 527       reserve(sz);
 528       auto newEnd = b_ + sz;
 529       std::uninitialized_fill(e_, newEnd, T());
 530       e_ = newEnd;
 531     }
 532   }
 533
 534   void resize(const size_type sz, const T& c) {
 535     auto const oldSize = size();
 536     if (sz <= oldSize) {
 537       auto const newEnd = b_ + sz;
 538       fbvector_detail::destroyRange(newEnd, e_);
 539       e_ = newEnd;
 540     } else {
 541       // Must expand
 542       reserve(sz);
 543       auto newEnd = b_ + sz;
 544       std::uninitialized_fill(e_, newEnd, c);
 545       e_ = newEnd;
 546     }
 547   }
 548
 549   size_type capacity() const {
 550     return z_ - b_;
 551   }
 552   bool empty() const {
 553     return b_ == e_;
 554   }
 555
 556 private:
 557   bool reserve_in_place(const size_type n) {
 558     auto const crtCapacity = capacity();
 559     if (n <= crtCapacity) return true;
 560     if (!rallocm) return false;
 561
 562     // using jemalloc's API. Don't forget that jemalloc can never grow
 563     // in place blocks smaller than 4096 bytes.
 564     auto const crtCapacityBytes = crtCapacity * sizeof(T);
 565     if (crtCapacityBytes < jemallocMinInPlaceExpandable) return false;
 566
 567     auto const newCapacityBytes = goodMallocSize(n * sizeof(T));
 568     void* p = b_;
 569     if (rallocm(&p, NULL, newCapacityBytes, 0, ALLOCM_NO_MOVE)
 570         != ALLOCM_SUCCESS) {
 571       return false;
 572     }
 573
 574     // Managed to expand in place, reflect that in z_
 575     assert(b_ == p);
 576     z_ = b_ + newCapacityBytes / sizeof(T);
 577     return true;
 578   }
 579
 580   void reserve_with_move(const size_type n) {
 581     // Here we can be sure we'll need to do a full reallocation
 582     auto const crtCapacity = capacity();
 583     assert(crtCapacity < n); // reserve_in_place should have taken
 584                              // care of this
 585     auto const newCapacityBytes = goodMallocSize(n * sizeof(T));
 586     auto b = static_cast<T*>(checkedMalloc(newCapacityBytes));
 587     auto const oldSize = size();
 588     memcpy(b, b_, oldSize * sizeof(T));
 589     // Done with the old chunk. Free but don't call destructors!
 590     free(b_);
 591     b_ = b;
 592     e_ = b_ + oldSize;
 593     z_ = b_ + newCapacityBytes / sizeof(T);
 594     // done with the old chunk
 595   }
 596
 597 public:
 598   void reserve(const size_type n) {
 599     if (reserve_in_place(n)) return;
 600     reserve_with_move(n);
 601   }
 602
 603   void shrink_to_fit() {
 604     if (!rallocm) return;
 605
 606     // using jemalloc's API. Don't forget that jemalloc can never
 607     // shrink in place blocks smaller than 4096 bytes.
 608     void* p = b_;
 609     auto const crtCapacityBytes = capacity() * sizeof(T);
 610     auto const newCapacityBytes = goodMallocSize(size() * sizeof(T));
 611     if (crtCapacityBytes >= jemallocMinInPlaceExpandable &&
 612         rallocm(&p, NULL, newCapacityBytes, 0, ALLOCM_NO_MOVE)
 613         == ALLOCM_SUCCESS) {
 614       // Celebrate
 615       z_ = b_ + newCapacityBytes / sizeof(T);
 616     }
 617   }
 618
 619 // element access
 620   reference operator[](size_type n) {
 621     assert(n < size());
 622     return b_[n];
 623   }
 624   const_reference operator[](size_type n) const {
 625     assert(n < size());
 626     return b_[n];
 627   }
 628   const_reference at(size_type n) const {
 629     if (n > size()) {
 630       throw std::out_of_range("fbvector: index is greater than size.");
 631     }
 632     return (*this)[n];
 633   }
 634   reference at(size_type n) {
 635     auto const& cThis = *this;
 636     return const_cast<reference>(cThis.at(n));
 637   }
 638   reference front() {
 639     assert(!empty());
 640     return *b_;
 641   }
 642   const_reference front() const {
 643     assert(!empty());
 644     return *b_;
 645   }
 646   reference back()  {
 647     assert(!empty());
 648     return e_[-1];
 649   }
 650   const_reference back() const {
 651     assert(!empty());
 652     return e_[-1];
 653   }
 654
 655 // 23.3.6.3 data access
 656   T* data() {
 657     return b_;
 658   }
 659   const T* data() const {
 660     return b_;
 661   }
 662
 663 private:
 664   size_t computePushBackCapacity() const {
 665     return empty() ? std::max(64 / sizeof(T), size_t(1))
 666       : capacity() < jemallocMinInPlaceExpandable ? capacity() * 2
 667       : (capacity() * 3) / 2;
 668   }
 669
 670 public:
 671 // 23.3.6.4 modifiers:
 672   template <class... Args>
 673   void emplace_back(Args&&... args) {
 674     if (e_ == z_) {
 675       if (!reserve_in_place(size() + 1)) {
 676         reserve_with_move(computePushBackCapacity());
 677       }
 678     }
 679     new (e_) T(std::forward<Args>(args)...);
 680     ++e_;
 681   }
 682
 683   void push_back(T x) {
 684     if (e_ == z_) {
 685       if (!reserve_in_place(size() + 1)) {
 686         reserve_with_move(computePushBackCapacity());
 687       }
 688     }
 689     fbvector_detail::uninitialized_destructive_move(x, e_);
 690     ++e_;
 691   }
 692
 693 private:
 694   bool expand() {
 695     if (!rallocm) return false;
 696     auto const capBytes = capacity() * sizeof(T);
 697     if (capBytes < jemallocMinInPlaceExpandable) return false;
 698     auto const newCapBytes = goodMallocSize(capBytes + sizeof(T));
 699     void * bv = b_;
 700     if (rallocm(&bv, NULL, newCapBytes, 0, ALLOCM_NO_MOVE) != ALLOCM_SUCCESS) {
 701       return false;
 702     }
 703     // Managed to expand in place
 704     assert(bv == b_); // nothing moved
 705     z_ = b_ + newCapBytes / sizeof(T);
 706     assert(capacity() > capBytes / sizeof(T));
 707     return true;
 708   }
 709
 710 public:
 711   void pop_back() {
 712     assert(!empty());
 713     --e_;
 714     if (!boost::has_trivial_destructor<T>::value) {
 715       e_->T::~T();
 716     }
 717   }
 718   // template <class... Args>
 719   // iterator emplace(const_iterator position, Args&&... args);
 720
 721   iterator insert(const_iterator position, T x) {
 722     size_t newSize; // intentionally uninitialized
 723     if (e_ == z_ && !reserve_in_place(newSize = size() + 1)) {
 724       // Can't reserve in place, make a copy
 725       auto const offset = position - cbegin();
 726       fbvector tmp;
 727       tmp.reserve(newSize);
 728       memcpy(tmp.b_, b_, offset * sizeof(T));
 729       fbvector_detail::uninitialized_destructive_move(
 730         x,
 731         tmp.b_ + offset);
 732       memcpy(tmp.b_ + offset + 1, b_ + offset, (size() - offset) * sizeof(T));
 733       // Brutally reassign this to refer to tmp's guts
 734       free(b_);
 735       b_ = tmp.b_;
 736       e_ = b_ + newSize;
 737       z_ = tmp.z_;
 738       // get rid of tmp's guts
 739       new(&tmp) fbvector;
 740       return begin() + offset;
 741     }
 742     // Here we have enough room
 743     memmove(const_cast<T*>(&*position) + 1,
 744             const_cast<T*>(&*position),
 745             sizeof(T) * (e_ - position));
 746     fbvector_detail::uninitialized_destructive_move(
 747       x,
 748       const_cast<T*>(&*position));
 749     ++e_;
 750     return const_cast<iterator>(position);
 751   }
 752
 753   iterator insert(const_iterator position, const size_type n, const T& x) {
 754     if (e_ + n >= z_) {
 755       if (b_ <= &x && &x < e_) {
 756         // Ew, aliased insert
 757         auto copy = x;
 758         return insert(position, n, copy);
 759       }
 760       auto const m = position - b_;
 761       reserve(size() + n);
 762       position = b_ + m;
 763     }
 764     memmove(const_cast<T*>(position) + n,
 765             position,
 766             sizeof(T) * (e_ - position));
 767     if (FOLLY_IS_TRIVIALLY_COPYABLE(T)) {
 768       std::uninitialized_fill(const_cast<T*>(position),
 769                               const_cast<T*>(position) + n,
 770                               x);
 771     } else {
 772       try {
 773         std::uninitialized_fill(const_cast<T*>(position),
 774                                 const_cast<T*>(position) + n,
 775                                 x);
 776       } catch (...) {
 777         // Oops, put things back where they were
 778         memmove(const_cast<T*>(position),
 779                 position + n,
 780                 sizeof(T) * (e_ - position));
 781         throw;
 782       }
 783     }
 784     e_ += n;
 785     return const_cast<iterator>(position);
 786   }
 787
 788 private:
 789   template <class InputIterator>
 790   iterator insertImpl(const_iterator position,
 791                       InputIterator first, InputIterator last,
 792                       boost::false_type) {
 793     // Pair of iterators
 794     if (fbvector_detail::isForwardIterator<InputIterator>::value) {
 795       // Can compute distance
 796       auto const n = std::distance(first, last);
 797       if (e_ + n >= z_) {
 798         auto const m = position - b_;
 799         reserve(size() + n);
 800         position = b_ + m;
 801       }
 802       memmove(const_cast<T*>(position) + n,
 803               position,
 804               sizeof(T) * (e_ - position));
 805       try {
 806         std::uninitialized_copy(first, last,
 807                            const_cast<T*>(position));
 808       } catch (...) {
 809         // Oops, put things back where they were
 810         memmove(const_cast<T*>(position),
 811                 position + n,
 812                 sizeof(T) * (e_ - position));
 813         throw;
 814       }
 815       e_ += n;
 816       return const_cast<iterator>(position);
 817     } else {
 818       // Cannot compute distance, crappy approach
 819       // TODO: OPTIMIZE
 820       fbvector result(cbegin(), position);
 821       auto const offset = result.size();
 822       FOR_EACH_RANGE (i, first, last) {
 823         result.push_back(*i);
 824       }
 825       result.insert(result.end(), position, cend());
 826       result.swap(*this);
 827       return begin() + offset;
 828     }
 829   }
 830
 831   iterator insertImpl(const_iterator position,
 832                       const size_type count, const T value, boost::true_type) {
 833     // Forward back to unambiguous function
 834     return insert(position, count, value);
 835   }
 836
 837 public:
 838   template <class InputIteratorOrNum>
 839   iterator insert(const_iterator position, InputIteratorOrNum first,
 840                   InputIteratorOrNum last) {
 841     return insertImpl(position, first, last,
 842                       boost::is_arithmetic<InputIteratorOrNum>());
 843   }
 844
 845   iterator insert(const_iterator position, std::initializer_list<T> il) {
 846     return insert(position, il.begin(), il.end());
 847   }
 848
 849   iterator erase(const_iterator position) {
 850     if (position == e_) return e_;
 851     auto p = const_cast<T*>(position);
 852     (*p).T::~T();
 853     memmove(p, p + 1, sizeof(T) * (e_ - p - 1));
 854     --e_;
 855     return p;
 856   }
 857
 858   iterator erase(const_iterator first, const_iterator last) {
 859     assert(first <= last);
 860     auto p1 = const_cast<T*>(first);
 861     auto p2 = const_cast<T*>(last);
 862     fbvector_detail::destroyRange(p1, p2);
 863     memmove(p1, last, sizeof(T) * (e_ - last));
 864     e_ -= last - first;
 865     return p1;
 866   }
 867
 868   void swap(fbvector& rhs) {
 869     std::swap(b_, rhs.b_);
 870     std::swap(e_, rhs.e_);
 871     std::swap(z_, rhs.z_);
 872   }
 873
 874   void clear() {
 875     fbvector_detail::destroyRange(b_, e_);
 876     e_ = b_;
 877   }
 878
 879 private:
 880   // Data
 881   T *b_, *e_, *z_;
 882 };
 883
 884 template <class T, class A>
 885 bool operator!=(const fbvector<T, A>& lhs,
 886                 const fbvector<T, A>& rhs) {
 887   return !(lhs == rhs);
 888 }
 889
 890 template <class T, class A>
 891 void swap(fbvector<T, A>& lhs, fbvector<T, A>& rhs) {
 892   lhs.swap(rhs);
 893 }
 894
 895 /**
 896  * Resizes *v to exactly n elements.  May reallocate the vector to a
 897  * smaller buffer if too much space will be left unused.
 898  */
 899 template <class T>
 900 static void compactResize(folly::fbvector<T> * v, size_t size) {
 901   auto const oldCap = v->capacity();
 902   if (oldCap > size + 1024 && size < oldCap * 0.3) {
 903     // Too much slack memory, reallocate a smaller buffer
 904     auto const oldSize = v->size();
 905     if (size <= oldSize) {
 906       // Shrink
 907       folly::fbvector<T>(v->begin(), v->begin() + size).swap(*v);
 908     } else {
 909       // Expand
 910       folly::fbvector<T> temp;
 911       temp.reserve(size);
 912       copy(v->begin(), v->end(), back_inserter(temp));
 913       temp.resize(size);
 914       temp.swap(*v);
 915     }
 916   } else {
 917     // Nolo contendere
 918     v->resize(size);
 919   }
 920 }
 921
 922 } // namespace folly
 923
 924 #endif // FOLLY_FBVECTOR_H_