folly/FBVector.h

   1 /*
   2  * Copyright 2012 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 (boost::has_trivial_copy<T>::value) {
 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*>(malloc(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*>(malloc(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       if (b_ <= &*first && &*first < e_) {
 380         // Aliased assign, work on the side
 381         fbvector result(first, last);
 382         result.swap(*this);
 383         return;
 384       }
 385
 386       auto const oldSize = size();
 387       auto const newSize = std::distance(first, last);
 388
 389       if (static_cast<difference_type>(oldSize) >= newSize) {
 390         // No reallocation, nice
 391         auto const newEnd = std::copy(first, last, b_);
 392         fbvector_detail::destroyRange(newEnd, e_);
 393         e_ = newEnd;
 394         return;
 395       }
 396
 397       // Must reallocate - just do it on the side
 398       auto const nBytes = goodMallocSize(newSize * sizeof(T));
 399       auto const b = static_cast<T*>(malloc(nBytes));
 400       std::uninitialized_copy(first, last, b);
 401       this->fbvector::~fbvector();
 402       b_ = b;
 403       e_ = b + newSize;
 404       z_ = b_ + nBytes / sizeof(T);
 405     } else {
 406       // Input iterator sucks
 407       FOR_EACH (i, *this) {
 408         if (first == last) {
 409           fbvector_detail::destroyRange(i, e_);
 410           e_ = i;
 411           return;
 412         }
 413         *i = *first;
 414         ++first;
 415       }
 416       FOR_EACH_RANGE (i, first, last) {
 417         push_back(*i);
 418       }
 419     }
 420   }
 421
 422   void assignImpl(const size_type newSize, const T value, boost::true_type) {
 423     // Arithmetic type, forward back to unambiguous definition
 424     assign(newSize, value);
 425   }
 426
 427 public:
 428   // Classic ambiguity (and a lot of unnecessary complexity) in
 429   // std::vector: assign(10, 20) for vector<int> means "assign 10
 430   // elements all having the value 20" but is intercepted by the
 431   // two-iterators overload assign(first, last). So we need to
 432   // disambiguate here. There is no pretty solution. We use here
 433   // overloading based on is_arithmetic. Method insert has the same
 434   // issue (and the same solution in this implementation).
 435   template <class InputIteratorOrNum>
 436   void assign(InputIteratorOrNum first, InputIteratorOrNum last) {
 437     assignImpl(first, last, boost::is_arithmetic<InputIteratorOrNum>());
 438   }
 439
 440   void assign(const size_type newSize, const T& value) {
 441     if (b_ <= &value && &value < e_) {
 442       // Need to check for aliased assign, sigh
 443       return assign(newSize, T(value));
 444     }
 445
 446     auto const oldSize = size();
 447     if (oldSize >= newSize) {
 448       // No reallocation, nice
 449       auto const newEnd = b_ + newSize;
 450       fbvector_detail::destroyRange(newEnd, e_);
 451       e_ = newEnd;
 452       return;
 453     }
 454
 455     // Need to reallocate
 456     if (reserve_in_place(newSize)) {
 457       // Careful here, fill and uninitialized_fill may throw. The
 458       // latter is transactional, so no need to worry about a
 459       // buffer partially filled in case of exception.
 460       std::fill(b_, e_, value);
 461       auto const newEnd = b_ + newSize;
 462       std::uninitialized_fill(e_, newEnd, value);
 463       e_ = newEnd;
 464       return;
 465     }
 466
 467     // Cannot expand or jemalloc not present at all; must just
 468     // allocate a new chunk and discard the old one. This is
 469     // tantamount with creating a new fbvector altogether. This won't
 470     // recurse infinitely; the constructor implements its own.
 471     fbvector temp(newSize, value);
 472     temp.swap(*this);
 473   }
 474
 475   void assign(std::initializer_list<T> il) {
 476     assign(il.begin(), il.end());
 477   }
 478
 479   allocator_type get_allocator() const {
 480     // whatevs
 481     return allocator_type();
 482   }
 483
 484 // iterators:
 485   iterator begin() {
 486     return b_;
 487   }
 488   const_iterator begin() const {
 489     return b_;
 490   }
 491   iterator end() {
 492     return e_;
 493   }
 494   const_iterator end() const {
 495     return e_;
 496   }
 497   reverse_iterator rbegin() {
 498     return reverse_iterator(end());
 499   }
 500   const_reverse_iterator rbegin() const {
 501     return const_reverse_iterator(end());
 502   }
 503   reverse_iterator rend() {
 504     return reverse_iterator(begin());
 505   }
 506   const_reverse_iterator rend() const {
 507     return const_reverse_iterator(begin());
 508   }
 509   const_iterator cbegin() const {
 510     return b_;
 511   }
 512   const_iterator cend() const {
 513     return e_;
 514   }
 515
 516 // 23.3.6.2 capacity:
 517   size_type size() const {
 518     return e_ - b_;
 519   }
 520
 521   size_type max_size() {
 522     // good luck gettin' there
 523     return ~size_type(0);
 524   }
 525
 526   void resize(const size_type sz) {
 527     auto const oldSize = size();
 528     if (sz <= oldSize) {
 529       auto const newEnd = b_ + sz;
 530       fbvector_detail::destroyRange(newEnd, e_);
 531       e_ = newEnd;
 532     } else {
 533       // Must expand
 534       reserve(sz);
 535       auto newEnd = b_ + sz;
 536       std::uninitialized_fill(e_, newEnd, T());
 537       e_ = newEnd;
 538     }
 539   }
 540
 541   void resize(const size_type sz, const T& c) {
 542     auto const oldSize = size();
 543     if (sz <= oldSize) {
 544       auto const newEnd = b_ + sz;
 545       fbvector_detail::destroyRange(newEnd, e_);
 546       e_ = newEnd;
 547     } else {
 548       // Must expand
 549       reserve(sz);
 550       auto newEnd = b_ + sz;
 551       std::uninitialized_fill(e_, newEnd, c);
 552       e_ = newEnd;
 553     }
 554   }
 555
 556   size_type capacity() const {
 557     return z_ - b_;
 558   }
 559   bool empty() const {
 560     return b_ == e_;
 561   }
 562
 563 private:
 564   bool reserve_in_place(const size_type n) {
 565     auto const crtCapacity = capacity();
 566     if (n <= crtCapacity) return true;
 567     if (!rallocm) return false;
 568
 569     // using jemalloc's API. Don't forget that jemalloc can never grow
 570     // in place blocks smaller than 4096 bytes.
 571     auto const crtCapacityBytes = crtCapacity * sizeof(T);
 572     if (crtCapacityBytes < jemallocMinInPlaceExpandable) return false;
 573
 574     auto const newCapacityBytes = goodMallocSize(n * sizeof(T));
 575     void* p = b_;
 576     if (rallocm(&p, NULL, newCapacityBytes, 0, ALLOCM_NO_MOVE)
 577         != ALLOCM_SUCCESS) {
 578       return false;
 579     }
 580
 581     // Managed to expand in place, reflect that in z_
 582     assert(b_ == p);
 583     z_ = b_ + newCapacityBytes / sizeof(T);
 584     return true;
 585   }
 586
 587   void reserve_with_move(const size_type n) {
 588     // Here we can be sure we'll need to do a full reallocation
 589     auto const crtCapacity = capacity();
 590     assert(crtCapacity < n); // reserve_in_place should have taken
 591                              // care of this
 592     auto const newCapacityBytes = goodMallocSize(n * sizeof(T));
 593     auto b = static_cast<T*>(malloc(newCapacityBytes));
 594     auto const oldSize = size();
 595     memcpy(b, b_, oldSize * sizeof(T));
 596     // Done with the old chunk. Free but don't call destructors!
 597     free(b_);
 598     b_ = b;
 599     e_ = b_ + oldSize;
 600     z_ = b_ + newCapacityBytes / sizeof(T);
 601     // done with the old chunk
 602   }
 603
 604 public:
 605   void reserve(const size_type n) {
 606     if (reserve_in_place(n)) return;
 607     reserve_with_move(n);
 608   }
 609
 610   void shrink_to_fit() {
 611     if (!rallocm) return;
 612
 613     // using jemalloc's API. Don't forget that jemalloc can never
 614     // shrink in place blocks smaller than 4096 bytes.
 615     void* p = b_;
 616     auto const crtCapacityBytes = capacity() * sizeof(T);
 617     auto const newCapacityBytes = goodMallocSize(size() * sizeof(T));
 618     if (crtCapacityBytes >= jemallocMinInPlaceExpandable &&
 619         rallocm(&p, NULL, newCapacityBytes, 0, ALLOCM_NO_MOVE)
 620         == ALLOCM_SUCCESS) {
 621       // Celebrate
 622       z_ = b_ + newCapacityBytes / sizeof(T);
 623     }
 624   }
 625
 626 // element access
 627   reference operator[](size_type n) {
 628     assert(n < size());
 629     return b_[n];
 630   }
 631   const_reference operator[](size_type n) const {
 632     assert(n < size());
 633     return b_[n];
 634   }
 635   const_reference at(size_type n) const {
 636     if (n > size()) {
 637       throw std::out_of_range("fbvector: index is greater than size.");
 638     }
 639     return (*this)[n];
 640   }
 641   reference at(size_type n) {
 642     auto const& cThis = *this;
 643     return const_cast<reference>(cThis.at(n));
 644   }
 645   reference front() {
 646     assert(!empty());
 647     return *b_;
 648   }
 649   const_reference front() const {
 650     assert(!empty());
 651     return *b_;
 652   }
 653   reference back()  {
 654     assert(!empty());
 655     return e_[-1];
 656   }
 657   const_reference back() const {
 658     assert(!empty());
 659     return e_[-1];
 660   }
 661
 662 // 23.3.6.3 data access
 663   T* data() {
 664     return b_;
 665   }
 666   const T* data() const {
 667     return b_;
 668   }
 669
 670 private:
 671   size_t computePushBackCapacity() const {
 672     return empty() ? std::max(64 / sizeof(T), size_t(1))
 673       : capacity() < jemallocMinInPlaceExpandable ? capacity() * 2
 674       : (capacity() * 3) / 2;
 675   }
 676
 677 public:
 678 // 23.3.6.4 modifiers:
 679   template <class... Args>
 680   void emplace_back(Args&&... args) {
 681     if (e_ == z_) {
 682       if (!reserve_in_place(size() + 1)) {
 683         reserve_with_move(computePushBackCapacity());
 684       }
 685     }
 686     new (e_) T(std::forward<Args>(args)...);
 687     ++e_;
 688   }
 689
 690   void push_back(T x) {
 691     if (e_ == z_) {
 692       if (!reserve_in_place(size() + 1)) {
 693         reserve_with_move(computePushBackCapacity());
 694       }
 695     }
 696     fbvector_detail::uninitialized_destructive_move(x, e_);
 697     ++e_;
 698   }
 699
 700 private:
 701   bool expand() {
 702     if (!rallocm) return false;
 703     auto const capBytes = capacity() * sizeof(T);
 704     if (capBytes < jemallocMinInPlaceExpandable) return false;
 705     auto const newCapBytes = goodMallocSize(capBytes + sizeof(T));
 706     void * bv = b_;
 707     if (rallocm(&bv, NULL, newCapBytes, 0, ALLOCM_NO_MOVE) != ALLOCM_SUCCESS) {
 708       return false;
 709     }
 710     // Managed to expand in place
 711     assert(bv == b_); // nothing moved
 712     z_ = b_ + newCapBytes / sizeof(T);
 713     assert(capacity() > capBytes / sizeof(T));
 714     return true;
 715   }
 716
 717 public:
 718   void pop_back() {
 719     assert(!empty());
 720     --e_;
 721     if (!boost::has_trivial_destructor<T>::value) {
 722       e_->T::~T();
 723     }
 724   }
 725   // template <class... Args>
 726   // iterator emplace(const_iterator position, Args&&... args);
 727
 728   iterator insert(const_iterator position, T x) {
 729     size_t newSize; // intentionally uninitialized
 730     if (e_ == z_ && !reserve_in_place(newSize = size() + 1)) {
 731       // Can't reserve in place, make a copy
 732       auto const offset = position - cbegin();
 733       fbvector tmp;
 734       tmp.reserve(newSize);
 735       memcpy(tmp.b_, b_, offset * sizeof(T));
 736       fbvector_detail::uninitialized_destructive_move(
 737         x,
 738         tmp.b_ + offset);
 739       memcpy(tmp.b_ + offset + 1, b_ + offset, (size() - offset) * sizeof(T));
 740       // Brutally reassign this to refer to tmp's guts
 741       free(b_);
 742       b_ = tmp.b_;
 743       e_ = b_ + newSize;
 744       z_ = tmp.z_;
 745       // get rid of tmp's guts
 746       new(&tmp) fbvector;
 747       return begin() + offset;
 748     }
 749     // Here we have enough room
 750     memmove(const_cast<T*>(&*position) + 1,
 751             const_cast<T*>(&*position),
 752             sizeof(T) * (e_ - position));
 753     fbvector_detail::uninitialized_destructive_move(
 754       x,
 755       const_cast<T*>(&*position));
 756     ++e_;
 757     return const_cast<iterator>(position);
 758   }
 759
 760   iterator insert(const_iterator position, const size_type n, const T& x) {
 761     if (e_ + n >= z_) {
 762       if (b_ <= &x && &x < e_) {
 763         // Ew, aliased insert
 764         auto copy = x;
 765         return insert(position, n, copy);
 766       }
 767       auto const m = position - b_;
 768       reserve(size() + n);
 769       position = b_ + m;
 770     }
 771     memmove(const_cast<T*>(position) + n,
 772             position,
 773             sizeof(T) * (e_ - position));
 774     if (boost::has_trivial_copy<T>::value) {
 775       std::uninitialized_fill(const_cast<T*>(position),
 776                               const_cast<T*>(position) + n,
 777                               x);
 778     } else {
 779       try {
 780         std::uninitialized_fill(const_cast<T*>(position),
 781                                 const_cast<T*>(position) + n,
 782                                 x);
 783       } catch (...) {
 784         // Oops, put things back where they were
 785         memmove(const_cast<T*>(position),
 786                 position + n,
 787                 sizeof(T) * (e_ - position));
 788         throw;
 789       }
 790     }
 791     e_ += n;
 792     return const_cast<iterator>(position);
 793   }
 794
 795 private:
 796   template <class InputIterator>
 797   iterator insertImpl(const_iterator position,
 798                       InputIterator first, InputIterator last,
 799                       boost::false_type) {
 800     // Pair of iterators
 801     if (fbvector_detail::isForwardIterator<InputIterator>::value) {
 802       // Can compute distance
 803       auto const n = std::distance(first, last);
 804       if (e_ + n >= z_) {
 805         if (b_ <= &*first && &*first < e_) {
 806           // Ew, aliased insert
 807           goto conservative;
 808         }
 809         auto const m = position - b_;
 810         reserve(size() + n);
 811         position = b_ + m;
 812       }
 813       memmove(const_cast<T*>(position) + n,
 814               position,
 815               sizeof(T) * (e_ - position));
 816       try {
 817         std::uninitialized_copy(first, last,
 818                            const_cast<T*>(position));
 819       } catch (...) {
 820         // Oops, put things back where they were
 821         memmove(const_cast<T*>(position),
 822                 position + n,
 823                 sizeof(T) * (e_ - position));
 824         throw;
 825       }
 826       e_ += n;
 827       return const_cast<iterator>(position);
 828     } else {
 829       // Cannot compute distance, crappy approach
 830       // TODO: OPTIMIZE
 831       conservative:
 832       fbvector result(cbegin(), position);
 833       auto const offset = result.size();
 834       FOR_EACH_RANGE (i, first, last) {
 835         result.push_back(*i);
 836       }
 837       result.insert(result.end(), position, cend());
 838       result.swap(*this);
 839       return begin() + offset;
 840     }
 841   }
 842
 843   iterator insertImpl(const_iterator position,
 844                       const size_type count, const T value, boost::true_type) {
 845     // Forward back to unambiguous function
 846     return insert(position, count, value);
 847   }
 848
 849 public:
 850   template <class InputIteratorOrNum>
 851   iterator insert(const_iterator position, InputIteratorOrNum first,
 852                   InputIteratorOrNum last) {
 853     return insertImpl(position, first, last,
 854                       boost::is_arithmetic<InputIteratorOrNum>());
 855   }
 856
 857   iterator insert(const_iterator position, std::initializer_list<T> il) {
 858     return insert(position, il.begin(), il.end());
 859   }
 860
 861   iterator erase(const_iterator position) {
 862     if (position == e_) return e_;
 863     auto p = const_cast<T*>(position);
 864     (*p).T::~T();
 865     memmove(p, p + 1, sizeof(T) * (e_ - p - 1));
 866     --e_;
 867     return p;
 868   }
 869
 870   iterator erase(const_iterator first, const_iterator last) {
 871     assert(first <= last);
 872     auto p1 = const_cast<T*>(first);
 873     auto p2 = const_cast<T*>(last);
 874     fbvector_detail::destroyRange(p1, p2);
 875     memmove(p1, last, sizeof(T) * (e_ - last));
 876     e_ -= last - first;
 877     return p1;
 878   }
 879
 880   void swap(fbvector& rhs) {
 881     std::swap(b_, rhs.b_);
 882     std::swap(e_, rhs.e_);
 883     std::swap(z_, rhs.z_);
 884   }
 885
 886   void clear() {
 887     fbvector_detail::destroyRange(b_, e_);
 888     e_ = b_;
 889   }
 890
 891 private:
 892   // Data
 893   T *b_, *e_, *z_;
 894 };
 895
 896 template <class T, class A>
 897 bool operator!=(const fbvector<T, A>& lhs,
 898                 const fbvector<T, A>& rhs) {
 899   return !(lhs == rhs);
 900 }
 901
 902 template <class T, class A>
 903 void swap(fbvector<T, A>& lhs, fbvector<T, A>& rhs) {
 904   lhs.swap(rhs);
 905 }
 906
 907 /**
 908  * Resizes *v to exactly n elements.  May reallocate the vector to a
 909  * smaller buffer if too much space will be left unused.
 910  */
 911 template <class T>
 912 static void compactResize(folly::fbvector<T> * v, size_t size) {
 913   auto const oldCap = v->capacity();
 914   if (oldCap > size + 1024 && size < oldCap * 0.3) {
 915     // Too much slack memory, reallocate a smaller buffer
 916     auto const oldSize = v->size();
 917     if (size <= oldSize) {
 918       // Shrink
 919       folly::fbvector<T>(v->begin(), v->begin() + size).swap(*v);
 920     } else {
 921       // Expand
 922       folly::fbvector<T> temp;
 923       temp.reserve(size);
 924       copy(v->begin(), v->end(), back_inserter(temp));
 925       temp.resize(size);
 926       temp.swap(*v);
 927     }
 928   } else {
 929     // Nolo contendere
 930     v->resize(size);
 931   }
 932 }
 933
 934 } // namespace folly
 935
 936 #endif // FOLLY_FBVECTOR_H_