X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FFBVector.h;h=1bcc76513a793e42534756a176e9fe1784cfe16f;hb=eac2f407712046f9a3b91c244301467d31ec3819;hp=22d76034bf084d5ce249fe50665e286c13f7777a;hpb=58ddb58be76d43be88709cd45afabe0c785ea9e2;p=folly.git diff --git a/folly/FBVector.h b/folly/FBVector.h index 22d76034..1bcc7651 100644 --- a/folly/FBVector.h +++ b/folly/FBVector.h @@ -1,5 +1,5 @@ /* - * Copyright 2015 Facebook, Inc. + * Copyright 2016 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 @@ -40,6 +39,7 @@ #include #include #include +#include #include @@ -149,7 +149,7 @@ private: S_destroy_range_a(*this, b_, e_); } - D_deallocate(b_, z_ - b_); + D_deallocate(b_, size_type(z_ - b_)); } } @@ -164,8 +164,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; @@ -431,7 +430,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; @@ -524,7 +525,9 @@ private: static void S_uninitialized_copy_bits(T* dest, const T* first, const T* last) { - std::memcpy((void*)dest, (void*)first, (last - first) * sizeof(T)); + if (last != first) { + std::memcpy((void*)dest, (void*)first, (last - first) * sizeof(T)); + } } static void @@ -532,7 +535,9 @@ private: std::move_iterator last) { T* bFirst = first.base(); T* bLast = last.base(); - std::memcpy((void*)dest, (void*)bFirst, (bLast - bFirst) * sizeof(T)); + if (bLast != bFirst) { + std::memcpy((void*)dest, (void*)bFirst, (bLast - bFirst) * sizeof(T)); + } } template @@ -638,7 +643,9 @@ private: } void relocate_move_or_memcpy(T* dest, T* first, T* last, std::true_type) { - std::memcpy((void*)dest, (void*)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) { @@ -908,7 +915,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 { @@ -939,7 +946,7 @@ public: } size_type capacity() const noexcept { - return impl_.z_ - impl_.b_; + return size_type(impl_.z_ - impl_.b_); } bool empty() const noexcept { @@ -959,13 +966,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(); @@ -1033,7 +1045,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]; } @@ -1130,9 +1142,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. @@ -1255,7 +1267,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. // @@ -1264,10 +1276,6 @@ 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_); @@ -1321,8 +1329,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; @@ -1336,19 +1344,33 @@ 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)); \ + } \ + 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; \ + size_type newCap; /* intentionally uninitialized */ \ \ if (fresh) { \ newCap = computeInsertCapacity(n); \ b = M_allocate(newCap); \ } else { \ - make_window(position, n); \ + if (!at_end) { \ + make_window(position, n); \ + } else { \ + impl_.e_ += n; \ + } \ b = impl_.b_; \ } \ \ @@ -1363,7 +1385,11 @@ private: // we have the private section first because it defines some macros if (fresh) { \ M_deallocate(b, newCap); \ } else { \ - undo_window(position, n); \ + if (!at_end) { \ + undo_window(position, n); \ + } else { \ + impl_.e_ -= n; \ + } \ } \ throw; \ } \ @@ -1393,6 +1419,7 @@ 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) @@ -1401,8 +1428,8 @@ public: } iterator insert(const_iterator cpos, const T& value) { - if (dataIsInternal(value)) return insert(cpos, 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) @@ -1411,8 +1438,8 @@ public: } iterator insert(const_iterator cpos, T&& value) { - if (dataIsInternal(value)) return insert(cpos, T(std::move(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) @@ -1421,9 +1448,8 @@ public: } 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_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) @@ -1449,8 +1475,7 @@ private: 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_PRE(cpos, n) FOLLY_FBVECTOR_INSERT_START(cpos, n) D_uninitialized_copy_a(start, first, last); FOLLY_FBVECTOR_INSERT_TRY(cpos, n) @@ -1642,5 +1667,3 @@ void attach(fbvector& v, T* data, size_t sz, size_t cap) { } } // namespace folly - -#endif // FOLLY_FBVECTOR_H