X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2FFBVector.h;h=4a792af025d2e6dfbb1f7442218c3bb9537422d2;hp=ca96ff033d337721724f8fc3e1d4f76170399ac2;hb=d3e8b83f6a8388d97443b9e5bdd4dc375b092fa1;hpb=275ca94d04e44f28cfa411668eb1c1dd8db90b80 diff --git a/folly/FBVector.h b/folly/FBVector.h index ca96ff03..4a792af0 100644 --- a/folly/FBVector.h +++ b/folly/FBVector.h @@ -1,5 +1,5 @@ /* - * Copyright 2015 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. @@ -22,8 +22,7 @@ * optimizations for use with relocatable types and jemalloc. */ -#ifndef FOLLY_FBVECTOR_H -#define FOLLY_FBVECTOR_H +#pragma once //============================================================================= // headers @@ -36,17 +35,11 @@ #include #include +#include #include #include #include - -#include - -// some files expected these from FBVector -#include -#include -#include -#include +#include //============================================================================= // forward declaration @@ -79,7 +72,7 @@ namespace folly { namespace folly { template -class fbvector : private boost::totally_ordered> { +class fbvector { //=========================================================================== //--------------------------------------------------------------------------- @@ -154,7 +147,7 @@ private: S_destroy_range_a(*this, b_, e_); } - D_deallocate(b_, z_ - b_); + D_deallocate(b_, size_type(z_ - b_)); } } @@ -169,8 +162,7 @@ private: } } - void - set(pointer newB, size_type newSize, size_type newCap) { + void set(pointer newB, size_type newSize, size_type newCap) { z_ = newB + newCap; e_ = newB + newSize; b_ = newB; @@ -218,7 +210,7 @@ public: 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< @@ -330,7 +322,8 @@ 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); } @@ -368,7 +361,7 @@ private: // 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 @@ -436,7 +429,9 @@ 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; @@ -529,7 +524,9 @@ private: static void S_uninitialized_copy_bits(T* dest, const T* first, const T* last) { - std::memcpy(dest, first, (last - first) * sizeof(T)); + if (last != first) { + std::memcpy((void*)dest, (void*)first, (last - first) * sizeof(T)); + } } static void @@ -537,7 +534,9 @@ private: std::move_iterator last) { T* bFirst = first.base(); T* bLast = last.base(); - std::memcpy(dest, bFirst, (bLast - bFirst) * sizeof(T)); + if (bLast != bFirst) { + std::memcpy((void*)dest, (void*)bFirst, (bLast - bFirst) * sizeof(T)); + } } template @@ -562,7 +561,7 @@ private: static const T* S_copy_n(T* dest, const T* first, size_type n) { if (folly::IsTriviallyCopyable::value) { - std::memcpy(dest, first, n * sizeof(T)); + std::memcpy((void*)dest, (void*)first, n * sizeof(T)); return first + n; } else { return S_copy_n(dest, first, n); @@ -573,7 +572,7 @@ private: S_copy_n(T* dest, std::move_iterator mIt, size_type n) { if (folly::IsTriviallyCopyable::value) { T* first = mIt.base(); - std::memcpy(dest, first, n * sizeof(T)); + std::memcpy((void*)dest, (void*)first, n * sizeof(T)); return std::make_move_iterator(first + n); } else { return S_copy_n>(dest, mIt, n); @@ -643,7 +642,9 @@ private: } void relocate_move_or_memcpy(T* dest, T* first, T* last, std::true_type) { - std::memcpy(dest, first, (last - first) * sizeof(T)); + if (first != nullptr) { + std::memcpy((void*)dest, (void*)first, (last - first) * sizeof(T)); + } } void relocate_move_or_memcpy(T* dest, T* first, T* last, std::false_type) { @@ -659,7 +660,7 @@ private: } // done - void relocate_done(T* dest, T* first, T* last) noexcept { + void relocate_done(T* /*dest*/, T* first, T* last) noexcept { if (folly::IsRelocatable::value && usingStdAllocator::value) { // used memcpy; data has been relocated, do not call destructor } else { @@ -799,7 +800,7 @@ private: 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 @@ -826,7 +827,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); @@ -913,7 +914,7 @@ 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 +945,7 @@ public: } size_type capacity() const noexcept { - return impl_.z_ - impl_.b_; + return size_type(impl_.z_ - impl_.b_); } bool empty() const noexcept { @@ -964,13 +965,18 @@ public: throw; } if (impl_.b_) - M_deallocate(impl_.b_, impl_.z_ - 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; } void shrink_to_fit() noexcept { + if (empty()) { + impl_.reset(); + return; + } + auto const newCapacityBytes = folly::goodMallocSize(size() * sizeof(T)); auto const newCap = newCapacityBytes / sizeof(T); auto const oldCap = capacity(); @@ -998,7 +1004,7 @@ public: return; } if (impl_.b_) - M_deallocate(impl_.b_, impl_.z_ - 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; @@ -1038,7 +1044,7 @@ public: } const_reference at(size_type n) const { if (UNLIKELY(n >= size())) { - throw std::out_of_range("fbvector: index is greater than size."); + std::__throw_out_of_range("fbvector: index is greater than size."); } return (*this)[n]; } @@ -1135,9 +1141,9 @@ private: // fbvector grows differently on two counts: // // (1) initial size - // Instead of grwoing to size 1 from empty, and fbvector allocates at - // least 64 bytes. You may still use reserve to reserve a lesser amount - // of memory. + // Instead of growing to size 1 from empty, fbvector allocates at least + // 64 bytes. You may still use reserve to reserve a lesser amount of + // memory. // (2) 1.5x // For medium-sized vectors, the growth strategy is 1.5x. See the docs // for details. @@ -1182,7 +1188,7 @@ public: if (folly::IsRelocatable::value && usingStdAllocator::value) { D_destroy_range_a((iterator)first, (iterator)last); if (last - first >= cend() - last) { - std::memcpy((iterator)first, last, (cend() - last) * sizeof(T)); + std::memcpy((void*)first, (void*)last, (cend() - last) * sizeof(T)); } else { std::memmove((iterator)first, last, (cend() - last) * sizeof(T)); } @@ -1260,7 +1266,7 @@ private: // we have the private section first because it defines some macros // These three functions, make_window, wrap_frame, and // insert_use_fresh_memory, can be combined into a uniform interface. // Since that interface involves a lot of case-work, it is built into - // some macros: FOLLY_FBVECTOR_INSERT_(START|TRY|END) + // some macros: FOLLY_FBVECTOR_INSERT_(PRE|START|TRY|END) // Macros are used in an attempt to let GCC perform better optimizations, // especially control flow optimization. // @@ -1269,12 +1275,8 @@ private: // we have the private section first because it defines some macros // window void make_window(iterator position, size_type n) { - assert(isValid(position)); - assert(size() + n <= capacity()); - assert(n != 0); - // 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_); @@ -1326,8 +1328,8 @@ private: // we have the private section first because it defines some macros //--------------------------------------------------------------------------- // use fresh? - bool insert_use_fresh(const_iterator cposition, size_type n) { - if (cposition == cend()) { + 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; return true; @@ -1341,99 +1343,125 @@ private: // we have the private section first because it defines some macros //--------------------------------------------------------------------------- // interface - #define FOLLY_FBVECTOR_INSERT_START(cpos, n) \ - assert(isValid(cpos)); \ - T* position = const_cast(cpos); \ - size_type idx = std::distance(impl_.b_, position); \ - bool fresh = insert_use_fresh(position, n); \ - T* b; \ - size_type newCap = 0; \ - \ - if (fresh) { \ - newCap = computeInsertCapacity(n); \ - b = M_allocate(newCap); \ - } else { \ - make_window(position, 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 { \ - undo_window(position, 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_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) { - 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) { - 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) { - if (n == 0) return (iterator)cpos; - 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); - if (n == 0) return (iterator)cpos; - - 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 @@ -1482,18 +1510,34 @@ private: //=========================================================================== //--------------------------------------------------------------------------- - // lexicographical functions (others from boost::totally_ordered superclass) + // 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 @@ -1592,6 +1636,16 @@ void swap(fbvector& lhs, fbvector& rhs) noexcept { //----------------------------------------------------------------------------- // other +namespace detail { + +// Format support. +template +struct IndexableTraits> + : public IndexableTraitsSeq> { +}; + +} // namespace detail + template void compactResize(fbvector* v, size_t sz) { v->resize(sz); @@ -1637,5 +1691,3 @@ void attach(fbvector& v, T* data, size_t sz, size_t cap) { } } // namespace folly - -#endif // FOLLY_FBVECTOR_H