X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2FFBVector.h;h=428eba628d10b1629887c3fb09b94c181d1c3ff9;hp=6c6de44e2d7768e1ae6fff642bb781ba82ffc0f0;hb=54b16a23784d48f1a3b56ff0c33bdf7fdfe46355;hpb=eb6bd53fde2fd971d891c06fa81f8d0e385a79a1 diff --git a/folly/FBVector.h b/folly/FBVector.h index 6c6de44e..428eba62 100644 --- a/folly/FBVector.h +++ b/folly/FBVector.h @@ -1,5 +1,5 @@ /* - * Copyright 2016 Facebook, Inc. + * Copyright 2017 Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -37,19 +37,17 @@ #include #include -#include #include +#include #include -#include - //============================================================================= // forward declaration namespace folly { - template > - class fbvector; -} +template > +class fbvector; +} // namespace folly //============================================================================= // unrolling @@ -74,13 +72,12 @@ namespace folly { namespace folly { template -class fbvector : private boost::totally_ordered> { +class fbvector { //=========================================================================== //--------------------------------------------------------------------------- // implementation -private: - + private: typedef std::allocator_traits A; struct Impl : public Allocator { @@ -149,7 +146,7 @@ private: S_destroy_range_a(*this, b_, e_); } - D_deallocate(b_, z_ - b_); + D_deallocate(b_, size_type(z_ - b_)); } } @@ -187,15 +184,16 @@ private: static void swap(Impl& a, Impl& b) { using std::swap; - if (!usingStdAllocator::value) swap(a, b); + if (!usingStdAllocator::value) { + swap(a, b); + } a.swapData(b); } //=========================================================================== //--------------------------------------------------------------------------- // types and constants -public: - + public: typedef T value_type; typedef value_type& reference; typedef const value_type& const_reference; @@ -209,10 +207,9 @@ public: typedef std::reverse_iterator reverse_iterator; typedef std::reverse_iterator const_reverse_iterator; -private: - + private: typedef std::integral_constant::value && + IsTriviallyCopyable::value && sizeof(T) <= 16 // don't force large structures to be passed by value > should_pass_by_value; typedef typename std::conditional< @@ -229,8 +226,7 @@ private: //=========================================================================== //--------------------------------------------------------------------------- // allocator helpers -private: - + private: //--------------------------------------------------------------------------- // allocate @@ -324,7 +320,9 @@ private: void M_destroy(T* p) noexcept { if (usingStdAllocator::value) { - if (!boost::has_trivial_destructor::value) p->~T(); + if (!std::is_trivially_destructible::value) { + p->~T(); + } } else { std::allocator_traits::destroy(impl_, p); } @@ -333,8 +331,7 @@ private: //=========================================================================== //--------------------------------------------------------------------------- // algorithmic helpers -private: - + private: //--------------------------------------------------------------------------- // destroy_range @@ -356,13 +353,14 @@ private: // allocator static void S_destroy_range_a(Allocator& a, T* first, T* last) noexcept { - for (; first != last; ++first) + for (; first != last; ++first) { std::allocator_traits::destroy(a, first); + } } // optimized static void S_destroy_range(T* first, T* last) noexcept { - if (!boost::has_trivial_destructor::value) { + if (!std::is_trivially_destructible::value) { // EXPERIMENTAL DATA on fbvector> (where each vector has // size 0). // The unrolled version seems to work faster for small to medium sized @@ -418,9 +416,10 @@ private: auto b = dest; auto e = dest + sz; try { - for (; b != e; ++b) + for (; b != e; ++b) { std::allocator_traits::construct(a, b, std::forward(args)...); + } } catch (...) { S_destroy_range_a(a, dest, b); throw; @@ -430,15 +429,21 @@ private: // optimized static void S_uninitialized_fill_n(T* dest, size_type n) { if (folly::IsZeroInitializable::value) { - std::memset(dest, 0, sizeof(T) * n); + if (LIKELY(n != 0)) { + std::memset(dest, 0, sizeof(T) * n); + } } else { auto b = dest; auto e = dest + n; try { - for (; b != e; ++b) S_construct(b); + for (; b != e; ++b) { + S_construct(b); + } } catch (...) { --b; - for (; b >= dest; --b) b->~T(); + for (; b >= dest; --b) { + b->~T(); + } throw; } } @@ -448,7 +453,9 @@ private: auto b = dest; auto e = dest + n; try { - for (; b != e; ++b) S_construct(b, value); + for (; b != e; ++b) { + S_construct(b, value); + } } catch (...) { S_destroy_range(dest, b); throw; @@ -500,8 +507,9 @@ private: S_uninitialized_copy_a(Allocator& a, T* dest, It first, It last) { auto b = dest; try { - for (; first != last; ++first, ++b) + for (; first != last; ++first, ++b) { std::allocator_traits::construct(a, b, *first); + } } catch (...) { S_destroy_range_a(a, dest, b); throw; @@ -513,8 +521,9 @@ private: static void S_uninitialized_copy(T* dest, It first, It last) { auto b = dest; try { - for (; first != last; ++first, ++b) + for (; first != last; ++first, ++b) { S_construct(b, *first); + } } catch (...) { S_destroy_range(dest, b); throw; @@ -554,7 +563,9 @@ private: template static It S_copy_n(T* dest, It first, size_type n) { auto e = dest + n; - for (; dest != e; ++dest, ++first) *dest = *first; + for (; dest != e; ++dest, ++first) { + *dest = *first; + } return first; } @@ -581,8 +592,7 @@ private: //=========================================================================== //--------------------------------------------------------------------------- // relocation helpers -private: - + private: // Relocation is divided into three parts: // // 1: relocate_move @@ -688,8 +698,7 @@ private: //=========================================================================== //--------------------------------------------------------------------------- // construct/copy/destroy -public: - + public: fbvector() = default; explicit fbvector(const Allocator& a) : impl_(a) {} @@ -731,7 +740,9 @@ public: ~fbvector() = default; // the cleanup occurs in impl_ fbvector& operator=(const fbvector& other) { - if (UNLIKELY(this == &other)) return *this; + if (UNLIKELY(this == &other)) { + return *this; + } if (!usingStdAllocator::value && A::propagate_on_container_copy_assignment::value) { @@ -747,7 +758,9 @@ public: } fbvector& operator=(fbvector&& other) { - if (UNLIKELY(this == &other)) return *this; + if (UNLIKELY(this == &other)) { + return *this; + } moveFrom(std::move(other), moveIsSwap()); return *this; } @@ -793,20 +806,25 @@ public: return impl_; } -private: - + private: // contract dispatch for iterator types fbvector(It first, It last) template fbvector(ForwardIterator first, ForwardIterator last, const Allocator& a, std::forward_iterator_tag) - : impl_(std::distance(first, last), a) + : impl_(size_type(std::distance(first, last)), a) { M_uninitialized_copy_e(first, last); } template - fbvector(InputIterator first, InputIterator last, - const Allocator& a, std::input_iterator_tag) - : impl_(a) - { for (; first != last; ++first) emplace_back(*first); } + fbvector( + InputIterator first, + InputIterator last, + const Allocator& a, + std::input_iterator_tag) + : impl_(a) { + for (; first != last; ++first) { + emplace_back(*first); + } + } // contract dispatch for allocator movement in operator=(fbvector&&) void @@ -826,7 +844,7 @@ private: template void assign(ForwardIterator first, ForwardIterator last, std::forward_iterator_tag) { - const size_t newSize = std::distance(first, last); + const auto newSize = size_type(std::distance(first, last)); if (newSize > capacity()) { impl_.reset(newSize); M_uninitialized_copy_e(first, last); @@ -849,13 +867,17 @@ private: if (p != impl_.e_) { M_destroy_range_e(p); } else { - for (; first != last; ++first) emplace_back(*first); + for (; first != last; ++first) { + emplace_back(*first); + } } } // contract dispatch for aliasing under VT optimization bool dataIsInternalAndNotVT(const T& t) { - if (should_pass_by_value::value) return false; + if (should_pass_by_value::value) { + return false; + } return dataIsInternal(t); } bool dataIsInternal(const T& t) { @@ -867,8 +889,7 @@ private: //=========================================================================== //--------------------------------------------------------------------------- // iterators -public: - + public: iterator begin() noexcept { return impl_.b_; } @@ -910,10 +931,9 @@ public: //=========================================================================== //--------------------------------------------------------------------------- // capacity -public: - + public: size_type size() const noexcept { - return impl_.e_ - impl_.b_; + return size_type(impl_.e_ - impl_.b_); } size_type max_size() const noexcept { @@ -944,7 +964,7 @@ public: } size_type capacity() const noexcept { - return impl_.z_ - impl_.b_; + return size_type(impl_.z_ - impl_.b_); } bool empty() const noexcept { @@ -952,8 +972,12 @@ public: } void reserve(size_type n) { - if (n <= capacity()) return; - if (impl_.b_ && reserve_in_place(n)) return; + if (n <= capacity()) { + return; + } + if (impl_.b_ && reserve_in_place(n)) { + return; + } auto newCap = folly::goodMallocSize(n * sizeof(T)) / sizeof(T); auto newB = M_allocate(newCap); @@ -963,8 +987,9 @@ public: M_deallocate(newB, newCap); throw; } - if (impl_.b_) - M_deallocate(impl_.b_, impl_.z_ - impl_.b_); + if (impl_.b_) { + M_deallocate(impl_.b_, size_type(impl_.z_ - impl_.b_)); + } impl_.z_ = newB + newCap; impl_.e_ = newB + (impl_.e_ - impl_.b_); impl_.b_ = newB; @@ -980,7 +1005,9 @@ public: auto const newCap = newCapacityBytes / sizeof(T); auto const oldCap = capacity(); - if (newCap >= oldCap) return; + if (newCap >= oldCap) { + return; + } void* p = impl_.b_; // xallocx() will shrink to precisely newCapacityBytes (which was generated @@ -1002,22 +1029,26 @@ public: } catch (...) { return; } - if (impl_.b_) - M_deallocate(impl_.b_, impl_.z_ - impl_.b_); + if (impl_.b_) { + M_deallocate(impl_.b_, size_type(impl_.z_ - impl_.b_)); + } impl_.z_ = newB + newCap; impl_.e_ = newB + (impl_.e_ - impl_.b_); impl_.b_ = newB; } } -private: - + private: bool reserve_in_place(size_type n) { - if (!usingStdAllocator::value || !usingJEMalloc()) return false; + if (!usingStdAllocator::value || !usingJEMalloc()) { + return false; + } // jemalloc can never grow in place blocks smaller than 4096 bytes. if ((impl_.z_ - impl_.b_) * sizeof(T) < - folly::jemallocMinInPlaceExpandable) return false; + folly::jemallocMinInPlaceExpandable) { + return false; + } auto const newCapacityBytes = folly::goodMallocSize(n * sizeof(T)); void* p = impl_.b_; @@ -1031,8 +1062,7 @@ private: //=========================================================================== //--------------------------------------------------------------------------- // element access -public: - + public: reference operator[](size_type n) { assert(n < size()); return impl_.b_[n]; @@ -1071,8 +1101,7 @@ public: //=========================================================================== //--------------------------------------------------------------------------- // data access -public: - + public: T* data() noexcept { return impl_.b_; } @@ -1083,8 +1112,7 @@ public: //=========================================================================== //--------------------------------------------------------------------------- // modifiers (common) -public: - + public: template void emplace_back(Args&&... args) { if (impl_.e_ != impl_.z_) { @@ -1122,18 +1150,18 @@ public: } void swap(fbvector& other) noexcept { - if (!usingStdAllocator::value && - A::propagate_on_container_swap::value) + if (!usingStdAllocator::value && A::propagate_on_container_swap::value) { swap(impl_, other.impl_); - else impl_.swapData(other.impl_); + } else { + impl_.swapData(other.impl_); + } } void clear() noexcept { M_destroy_range_e(impl_.b_); } -private: - + private: // std::vector implements a similar function with a different growth // strategy: empty() ? 1 : capacity() * 2. // @@ -1171,8 +1199,7 @@ private: //=========================================================================== //--------------------------------------------------------------------------- // modifiers (erase) -public: - + public: iterator erase(const_iterator position) { return erase(position, position + 1); } @@ -1206,8 +1233,7 @@ public: //=========================================================================== //--------------------------------------------------------------------------- // modifiers (insert) -private: // we have the private section first because it defines some macros - + private: // we have the private section first because it defines some macros bool isValid(const_iterator it) { return cbegin() <= it && it <= cend(); } @@ -1275,7 +1301,7 @@ private: // we have the private section first because it defines some macros void make_window(iterator position, size_type n) { // The result is guaranteed to be non-negative, so use an unsigned type: - size_type tail = std::distance(position, impl_.e_); + size_type tail = size_type(std::distance(position, impl_.e_)); if (tail <= n) { relocate_move(position + n, position, impl_.e_); @@ -1329,12 +1355,18 @@ private: // we have the private section first because it defines some macros bool insert_use_fresh(bool at_end, size_type n) { if (at_end) { - if (size() + n <= capacity()) return false; - if (reserve_in_place(size() + n)) return false; + if (size() + n <= capacity()) { + return false; + } + if (reserve_in_place(size() + n)) { + return false; + } return true; } - if (size() + n > capacity()) return true; + if (size() + n > capacity()) { + return true; + } return false; } @@ -1342,117 +1374,125 @@ private: // we have the private section first because it defines some macros //--------------------------------------------------------------------------- // interface - #define FOLLY_FBVECTOR_INSERT_PRE(cpos, n) \ - if (n == 0) return (iterator)cpos; \ - bool at_end = cpos == cend(); \ - bool fresh = insert_use_fresh(at_end, n); \ - if (!at_end) { \ - if (!fresh) { - - // check for internal data (technically not required by the standard) - - #define FOLLY_FBVECTOR_INSERT_START(cpos, n) \ - } \ - assert(isValid(cpos)); \ - } \ - T* position = const_cast(cpos); \ - size_type idx = std::distance(impl_.b_, position); \ - T* b; \ - size_type newCap; /* intentionally uninitialized */ \ - \ - if (fresh) { \ - newCap = computeInsertCapacity(n); \ - b = M_allocate(newCap); \ - } else { \ - if (!at_end) { \ - make_window(position, n); \ - } else { \ - impl_.e_ += n; \ - } \ - b = impl_.b_; \ - } \ - \ - T* start = b + idx; \ - \ - try { \ - - // construct the inserted elements - - #define FOLLY_FBVECTOR_INSERT_TRY(cpos, n) \ - } catch (...) { \ - if (fresh) { \ - M_deallocate(b, newCap); \ - } else { \ - if (!at_end) { \ - undo_window(position, n); \ - } else { \ - impl_.e_ -= n; \ - } \ - } \ - throw; \ - } \ - \ - if (fresh) { \ - try { \ - wrap_frame(b, idx, n); \ - } catch (...) { \ - - - // delete the inserted elements (exception has been thrown) - - #define FOLLY_FBVECTOR_INSERT_END(cpos, n) \ - M_deallocate(b, newCap); \ - throw; \ - } \ - if (impl_.b_) M_deallocate(impl_.b_, capacity()); \ - impl_.set(b, size() + n, newCap); \ - return impl_.b_ + idx; \ - } else { \ - return position; \ - } \ + template < + typename IsInternalFunc, + typename InsertInternalFunc, + typename ConstructFunc, + typename DestroyFunc> + iterator do_real_insert( + const_iterator cpos, + size_type n, + IsInternalFunc&& isInternalFunc, + InsertInternalFunc&& insertInternalFunc, + ConstructFunc&& constructFunc, + DestroyFunc&& destroyFunc) { + if (n == 0) { + return iterator(cpos); + } + bool at_end = cpos == cend(); + bool fresh = insert_use_fresh(at_end, n); + if (!at_end) { + if (!fresh && isInternalFunc()) { + // check for internal data (technically not required by the standard) + return insertInternalFunc(); + } + assert(isValid(cpos)); + } + T* position = const_cast(cpos); + size_type idx = size_type(std::distance(impl_.b_, position)); + T* b; + size_type newCap; /* intentionally uninitialized */ - //--------------------------------------------------------------------------- - // insert functions -public: + if (fresh) { + newCap = computeInsertCapacity(n); + b = M_allocate(newCap); + } else { + if (!at_end) { + make_window(position, n); + } else { + impl_.e_ += n; + } + b = impl_.b_; + } + + T* start = b + idx; + try { + // construct the inserted elements + constructFunc(start); + } catch (...) { + if (fresh) { + M_deallocate(b, newCap); + } else { + if (!at_end) { + undo_window(position, n); + } else { + impl_.e_ -= n; + } + } + throw; + } + + if (fresh) { + try { + wrap_frame(b, idx, n); + } catch (...) { + // delete the inserted elements (exception has been thrown) + destroyFunc(start); + M_deallocate(b, newCap); + throw; + } + if (impl_.b_) { + M_deallocate(impl_.b_, capacity()); + } + impl_.set(b, size() + n, newCap); + return impl_.b_ + idx; + } else { + return position; + } + } + public: template iterator emplace(const_iterator cpos, Args&&... args) { - FOLLY_FBVECTOR_INSERT_PRE(cpos, 1) - FOLLY_FBVECTOR_INSERT_START(cpos, 1) - M_construct(start, std::forward(args)...); - FOLLY_FBVECTOR_INSERT_TRY(cpos, 1) - M_destroy(start); - FOLLY_FBVECTOR_INSERT_END(cpos, 1) + return do_real_insert( + cpos, + 1, + [&] { return false; }, + [&] { return iterator{}; }, + [&](iterator start) { + M_construct(start, std::forward(args)...); + }, + [&](iterator start) { M_destroy(start); }); } iterator insert(const_iterator cpos, const T& value) { - FOLLY_FBVECTOR_INSERT_PRE(cpos, 1) - if (dataIsInternal(value)) return insert(cpos, T(value)); - FOLLY_FBVECTOR_INSERT_START(cpos, 1) - M_construct(start, value); - FOLLY_FBVECTOR_INSERT_TRY(cpos, 1) - M_destroy(start); - FOLLY_FBVECTOR_INSERT_END(cpos, 1) + return do_real_insert( + cpos, + 1, + [&] { return dataIsInternal(value); }, + [&] { return insert(cpos, T(value)); }, + [&](iterator start) { M_construct(start, value); }, + [&](iterator start) { M_destroy(start); }); } iterator insert(const_iterator cpos, T&& value) { - FOLLY_FBVECTOR_INSERT_PRE(cpos, 1) - if (dataIsInternal(value)) return insert(cpos, T(std::move(value))); - FOLLY_FBVECTOR_INSERT_START(cpos, 1) - M_construct(start, std::move(value)); - FOLLY_FBVECTOR_INSERT_TRY(cpos, 1) - M_destroy(start); - FOLLY_FBVECTOR_INSERT_END(cpos, 1) + return do_real_insert( + cpos, + 1, + [&] { return dataIsInternal(value); }, + [&] { return insert(cpos, T(std::move(value))); }, + [&](iterator start) { M_construct(start, std::move(value)); }, + [&](iterator start) { M_destroy(start); }); } iterator insert(const_iterator cpos, size_type n, VT value) { - FOLLY_FBVECTOR_INSERT_PRE(cpos, n) - if (dataIsInternalAndNotVT(value)) return insert(cpos, n, T(value)); - FOLLY_FBVECTOR_INSERT_START(cpos, n) - D_uninitialized_fill_n_a(start, n, value); - FOLLY_FBVECTOR_INSERT_TRY(cpos, n) - D_destroy_range_a(start, start + n); - FOLLY_FBVECTOR_INSERT_END(cpos, n) + return do_real_insert( + cpos, + n, + [&] { return dataIsInternalAndNotVT(value); }, + [&] { return insert(cpos, n, T(value)); }, + [&](iterator start) { D_uninitialized_fill_n_a(start, n, value); }, + [&](iterator start) { D_destroy_range_a(start, start + n); }); } template iterator insert(const_iterator cpos, FIt first, FIt last, std::forward_iterator_tag) { - size_type n = std::distance(first, last); - FOLLY_FBVECTOR_INSERT_PRE(cpos, n) - FOLLY_FBVECTOR_INSERT_START(cpos, n) - D_uninitialized_copy_a(start, first, last); - FOLLY_FBVECTOR_INSERT_TRY(cpos, n) - D_destroy_range_a(start, start + n); - FOLLY_FBVECTOR_INSERT_END(cpos, n) + size_type n = size_type(std::distance(first, last)); + return do_real_insert( + cpos, + n, + [&] { return false; }, + [&] { return iterator{}; }, + [&](iterator start) { D_uninitialized_copy_a(start, first, last); }, + [&](iterator start) { D_destroy_range_a(start, start + n); }); } template @@ -1492,7 +1532,9 @@ private: std::make_move_iterator(end()), A::select_on_container_copy_construction(impl_)); M_destroy_range_e(position); - for (; first != last; ++first) emplace_back(*first); + for (; first != last; ++first) { + emplace_back(*first); + } insert(cend(), std::make_move_iterator(storage.begin()), std::make_move_iterator(storage.end())); return impl_.b_ + idx; @@ -1500,23 +1542,37 @@ private: //=========================================================================== //--------------------------------------------------------------------------- - // lexicographical functions (others from boost::totally_ordered superclass) -public: - + // lexicographical functions + public: bool operator==(const fbvector& other) const { return size() == other.size() && std::equal(begin(), end(), other.begin()); } + bool operator!=(const fbvector& other) const { + return !(*this == other); + } + bool operator<(const fbvector& other) const { return std::lexicographical_compare( begin(), end(), other.begin(), other.end()); } + bool operator>(const fbvector& other) const { + return other < *this; + } + + bool operator<=(const fbvector& other) const { + return !(*this > other); + } + + bool operator>=(const fbvector& other) const { + return !(*this < other); + } + //=========================================================================== //--------------------------------------------------------------------------- // friends -private: - + private: template friend _T* relinquish(fbvector<_T, _A>&); @@ -1591,7 +1647,9 @@ void fbvector::emplace_back_aux(Args&&... args) { M_deallocate(newB, sz); throw; } - if (impl_.b_) M_deallocate(impl_.b_, size()); + if (impl_.b_) { + M_deallocate(impl_.b_, size()); + } impl_.b_ = newB; impl_.e_ = newE; impl_.z_ = newB + sz; @@ -1618,7 +1676,7 @@ struct IndexableTraits> : public IndexableTraitsSeq> { }; -} // namespace detail +} // namespace detail template void compactResize(fbvector* v, size_t sz) {