2 * Copyright 2012 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 // Andrei Alexandrescu (aalexandre)
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.
24 * In order for a type to be used with fbvector, it must be
25 * relocatable, see Traits.h.
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*.
31 * For more information and documentation see folly/docs/FBVector.md
34 #ifndef FOLLY_FBVECTOR_H_
35 #define FOLLY_FBVECTOR_H_
37 #include "folly/Foreach.h"
38 #include "folly/Malloc.h"
39 #include "folly/Traits.h"
45 #include <boost/type_traits.hpp>
46 #include <boost/operators.hpp>
47 #include <boost/utility/enable_if.hpp>
48 #include <type_traits>
52 * Forward declaration for use by FOLLY_ASSUME_FBVECTOR_COMPATIBLE_2,
55 template <typename T, class Allocator = std::allocator<T> >
59 // You can define an fbvector of fbvectors.
60 FOLLY_ASSUME_FBVECTOR_COMPATIBLE_2(folly::fbvector);
63 namespace fbvector_detail {
66 * isForwardIterator<T>::value yields true if T is a forward iterator
67 * or better, and false otherwise.
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
77 * Destroys all elements in the range [b, e). If the type referred to
78 * by the iterators has a trivial destructor, does nothing.
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;
90 * Moves the "interesting" part of value to the uninitialized memory
91 * at address addr, and leaves value in a destroyable state.
95 typename boost::enable_if_c<
96 boost::has_trivial_assign<T>::value
98 uninitialized_destructive_move(T& value, T* addr) {
99 // Just assign the thing; this is most efficient
104 typename boost::enable_if_c<
105 !boost::has_trivial_assign<T>::value &&
106 boost::has_nothrow_constructor<T>::value
108 uninitialized_destructive_move(T& value, T* addr) {
109 // Cheap default constructor - move and reinitialize
110 memcpy(addr, &value, sizeof(T));
115 typename std::enable_if<
116 !boost::has_trivial_assign<T>::value &&
117 !boost::has_nothrow_constructor<T>::value
119 uninitialized_destructive_move(T& value, T* addr) {
120 // User defined move construction.
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));
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).
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));
142 } else if (boost::has_nothrow_constructor<T>::value) {
145 auto const e1 = b + (n & ~size_t(7));
146 for (; i != e1; i += 8) {
156 for (auto const e = b + n; i != e; ++i) {
160 // Conservative approach
163 for (auto const e = b + n; i != e; ++i) {
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
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) {
184 auto const e1 = b + (n & ~size_t(7));
185 for (; i != e1; i += 8) {
195 for (; i != e; ++i) {
199 // Conservative approach
202 for (; i != e; ++i) {
212 } // namespace fbvector_detail
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
220 template <class T, class Allocator>
221 class fbvector : private boost::totally_ordered<fbvector<T,Allocator> > {
222 bool isSane() const {
225 empty() == (size() == 0) &&
226 empty() == (begin() == end()) &&
227 size() <= max_size() &&
228 capacity() <= max_size() &&
229 size() <= capacity() &&
231 // Either we have no capacity or our pointers should make sense:
232 ((!b_ && !e_ && !z_) || (b_ != z_ && e_ <= z_));
237 explicit Invariant(const fbvector& s) : s_(s) {
246 explicit Invariant(const fbvector&) {}
248 Invariant& operator=(const Invariant&);
254 typedef T value_type;
255 typedef value_type& reference;
256 typedef const value_type& const_reference;
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;
269 // 23.3.6.1 construct/copy/destroy:
270 fbvector() : b_(NULL), e_(NULL), z_(NULL) {}
272 explicit fbvector(const Allocator&) {
276 explicit fbvector(const size_type n) {
282 auto const nBytes = goodMallocSize(n * sizeof(T));
283 b_ = static_cast<T*>(malloc(nBytes));
284 fbvector_detail::uninitializedFillDefaultOrFree(b_, n);
286 z_ = b_ + nBytes / sizeof(T);
289 fbvector(const size_type n, const T& value) {
295 auto const nBytes = goodMallocSize(n * sizeof(T));
296 b_ = static_cast<T*>(malloc(nBytes));
297 fbvector_detail::uninitializedFillOrFree(b_, n, value);
299 z_ = b_ + nBytes / sizeof(T);
302 fbvector(const size_type n, const T& value, const Allocator&) {
303 new(this) fbvector(n, value);
306 template <class InputIteratorOrNum>
307 fbvector(InputIteratorOrNum first, InputIteratorOrNum last) {
312 template <class InputIterator>
313 fbvector(InputIterator first, InputIterator last,
315 new(this) fbvector(first, last);
318 fbvector(const fbvector& rhs) {
319 new(this) fbvector(rhs.begin(), rhs.end());
321 fbvector(const fbvector& rhs, const Allocator&) {
322 new(this) fbvector(rhs);
325 fbvector(fbvector&& o, const Allocator& = Allocator())
330 o.b_ = o.e_ = o.z_ = 0;
333 fbvector(std::initializer_list<T> il, const Allocator& = Allocator()) {
334 new(this) fbvector(il.begin(), il.end());
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);
346 fbvector_detail::destroyRange(b_, e_);
349 fbvector& operator=(const fbvector& rhs) {
350 assign(rhs.begin(), rhs.end());
354 fbvector& operator=(fbvector&& v) {
360 fbvector& operator=(std::initializer_list<T> il) {
361 assign(il.begin(), il.end());
365 bool operator==(const fbvector& rhs) const {
366 return size() == rhs.size() && std::equal(begin(), end(), rhs.begin());
369 bool operator<(const fbvector& rhs) const {
370 return std::lexicographical_compare(begin(), end(),
371 rhs.begin(), rhs.end());
375 template <class InputIterator>
376 void assignImpl(InputIterator first, InputIterator last, boost::false_type) {
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);
386 auto const oldSize = size();
387 auto const newSize = std::distance(first, last);
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_);
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();
404 z_ = b_ + nBytes / sizeof(T);
406 // Input iterator sucks
407 FOR_EACH (i, *this) {
409 fbvector_detail::destroyRange(i, e_);
416 FOR_EACH_RANGE (i, first, last) {
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);
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>());
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));
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_);
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);
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);
475 void assign(std::initializer_list<T> il) {
476 assign(il.begin(), il.end());
479 allocator_type get_allocator() const {
481 return allocator_type();
488 const_iterator begin() const {
494 const_iterator end() const {
497 reverse_iterator rbegin() {
498 return reverse_iterator(end());
500 const_reverse_iterator rbegin() const {
501 return const_reverse_iterator(end());
503 reverse_iterator rend() {
504 return reverse_iterator(begin());
506 const_reverse_iterator rend() const {
507 return const_reverse_iterator(begin());
509 const_iterator cbegin() const {
512 const_iterator cend() const {
516 // 23.3.6.2 capacity:
517 size_type size() const {
521 size_type max_size() {
522 // good luck gettin' there
523 return ~size_type(0);
526 void resize(const size_type sz) {
527 auto const oldSize = size();
529 auto const newEnd = b_ + sz;
530 fbvector_detail::destroyRange(newEnd, e_);
535 auto newEnd = b_ + sz;
536 std::uninitialized_fill(e_, newEnd, T());
541 void resize(const size_type sz, const T& c) {
542 auto const oldSize = size();
544 auto const newEnd = b_ + sz;
545 fbvector_detail::destroyRange(newEnd, e_);
550 auto newEnd = b_ + sz;
551 std::uninitialized_fill(e_, newEnd, c);
556 size_type capacity() const {
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;
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;
574 auto const newCapacityBytes = goodMallocSize(n * sizeof(T));
576 if (rallocm(&p, NULL, newCapacityBytes, 0, ALLOCM_NO_MOVE)
581 // Managed to expand in place, reflect that in z_
583 z_ = b_ + newCapacityBytes / sizeof(T);
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
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!
600 z_ = b_ + newCapacityBytes / sizeof(T);
601 // done with the old chunk
605 void reserve(const size_type n) {
606 if (reserve_in_place(n)) return;
607 reserve_with_move(n);
610 void shrink_to_fit() {
611 if (!rallocm) return;
613 // using jemalloc's API. Don't forget that jemalloc can never
614 // shrink in place blocks smaller than 4096 bytes.
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)
622 z_ = b_ + newCapacityBytes / sizeof(T);
627 reference operator[](size_type n) {
631 const_reference operator[](size_type n) const {
635 const_reference at(size_type n) const {
637 throw std::out_of_range("fbvector: index is greater than size.");
641 reference at(size_type n) {
642 auto const& cThis = *this;
643 return const_cast<reference>(cThis.at(n));
649 const_reference front() const {
657 const_reference back() const {
662 // 23.3.6.3 data access
666 const T* data() const {
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;
678 // 23.3.6.4 modifiers:
679 template <class... Args>
680 void emplace_back(Args&&... args) {
682 if (!reserve_in_place(size() + 1)) {
683 reserve_with_move(computePushBackCapacity());
686 new (e_) T(std::forward<Args>(args)...);
690 void push_back(T x) {
692 if (!reserve_in_place(size() + 1)) {
693 reserve_with_move(computePushBackCapacity());
696 fbvector_detail::uninitialized_destructive_move(x, e_);
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));
707 if (rallocm(&bv, NULL, newCapBytes, 0, ALLOCM_NO_MOVE) != ALLOCM_SUCCESS) {
710 // Managed to expand in place
711 assert(bv == b_); // nothing moved
712 z_ = b_ + newCapBytes / sizeof(T);
713 assert(capacity() > capBytes / sizeof(T));
721 if (!boost::has_trivial_destructor<T>::value) {
725 // template <class... Args>
726 // iterator emplace(const_iterator position, Args&&... args);
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();
734 tmp.reserve(newSize);
735 memcpy(tmp.b_, b_, offset * sizeof(T));
736 fbvector_detail::uninitialized_destructive_move(
739 memcpy(tmp.b_ + offset + 1, b_ + offset, (size() - offset) * sizeof(T));
740 // Brutally reassign this to refer to tmp's guts
745 // get rid of tmp's guts
747 return begin() + offset;
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(
755 const_cast<T*>(&*position));
757 return const_cast<iterator>(position);
760 iterator insert(const_iterator position, const size_type n, const T& x) {
762 if (b_ <= &x && &x < e_) {
763 // Ew, aliased insert
765 return insert(position, n, copy);
767 auto const m = position - b_;
771 memmove(const_cast<T*>(position) + n,
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,
780 std::uninitialized_fill(const_cast<T*>(position),
781 const_cast<T*>(position) + n,
784 // Oops, put things back where they were
785 memmove(const_cast<T*>(position),
787 sizeof(T) * (e_ - position));
792 return const_cast<iterator>(position);
796 template <class InputIterator>
797 iterator insertImpl(const_iterator position,
798 InputIterator first, InputIterator last,
801 if (fbvector_detail::isForwardIterator<InputIterator>::value) {
802 // Can compute distance
803 auto const n = std::distance(first, last);
805 if (b_ <= &*first && &*first < e_) {
806 // Ew, aliased insert
809 auto const m = position - b_;
813 memmove(const_cast<T*>(position) + n,
815 sizeof(T) * (e_ - position));
817 std::uninitialized_copy(first, last,
818 const_cast<T*>(position));
820 // Oops, put things back where they were
821 memmove(const_cast<T*>(position),
823 sizeof(T) * (e_ - position));
827 return const_cast<iterator>(position);
829 // Cannot compute distance, crappy approach
832 fbvector result(cbegin(), position);
833 auto const offset = result.size();
834 FOR_EACH_RANGE (i, first, last) {
835 result.push_back(*i);
837 result.insert(result.end(), position, cend());
839 return begin() + offset;
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);
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>());
857 iterator insert(const_iterator position, std::initializer_list<T> il) {
858 return insert(position, il.begin(), il.end());
861 iterator erase(const_iterator position) {
862 if (position == e_) return e_;
863 auto p = const_cast<T*>(position);
865 memmove(p, p + 1, sizeof(T) * (e_ - p - 1));
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));
880 void swap(fbvector& rhs) {
881 std::swap(b_, rhs.b_);
882 std::swap(e_, rhs.e_);
883 std::swap(z_, rhs.z_);
887 fbvector_detail::destroyRange(b_, e_);
896 template <class T, class A>
897 bool operator!=(const fbvector<T, A>& lhs,
898 const fbvector<T, A>& rhs) {
899 return !(lhs == rhs);
902 template <class T, class A>
903 void swap(fbvector<T, A>& lhs, fbvector<T, A>& rhs) {
908 * Resizes *v to exactly n elements. May reallocate the vector to a
909 * smaller buffer if too much space will be left unused.
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) {
919 folly::fbvector<T>(v->begin(), v->begin() + size).swap(*v);
922 folly::fbvector<T> temp;
924 copy(v->begin(), v->end(), back_inserter(temp));
936 #endif // FOLLY_FBVECTOR_H_