X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2Fsmall_vector.h;h=f28f4dfbb1e5e0cdc289392b0bdf70815ab6c27e;hp=b3db04eaf39e99e5d32990d939c4db9d71fb418f;hb=d4aacd244f21e76dce685365acc281a9015897c1;hpb=eb6bd53fde2fd971d891c06fa81f8d0e385a79a1 diff --git a/folly/small_vector.h b/folly/small_vector.h index b3db04ea..f28f4dfb 100644 --- a/folly/small_vector.h +++ b/folly/small_vector.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. @@ -23,38 +23,40 @@ #pragma once -#include -#include -#include #include -#include #include +#include +#include +#include +#include -#include -#include -#include +#include +#include #include -#include -#include #include +#include #include +#include #include -#include #include -#include +#include +#include +#include +#include #include #include #include #include +#include #include #include #include #include // Ignore shadowing warnings within this file, so includers can use -Wshadow. -#pragma GCC diagnostic push -#pragma GCC diagnostic ignored "-Wshadow" +FOLLY_PUSH_WARNING +FOLLY_GCC_DISABLE_WARNING("-Wshadow") namespace folly { @@ -72,11 +74,11 @@ struct NoHeap; ////////////////////////////////////////////////////////////////////// -} // small_vector_policy +} // namespace small_vector_policy ////////////////////////////////////////////////////////////////////// -template +template class small_vector; ////////////////////////////////////////////////////////////////////// @@ -87,7 +89,7 @@ namespace detail { * Move a range to a range of uninitialized memory. Assumes the * ranges don't overlap. */ - template + template typename std::enable_if< !FOLLY_IS_TRIVIALLY_COPYABLE(T) >::type @@ -111,7 +113,7 @@ namespace detail { } // Specialization for trivially copyable types. - template + template typename std::enable_if< FOLLY_IS_TRIVIALLY_COPYABLE(T) >::type @@ -119,13 +121,49 @@ namespace detail { std::memmove(out, first, (last - first) * sizeof *first); } + /* + * Move a range to a range of uninitialized memory. Assumes the + * ranges don't overlap. Inserts an element at out + pos using emplaceFunc(). + * out will contain (end - begin) + 1 elements on success and none on failure. + * If emplaceFunc() throws [begin, end) is unmodified. + */ + template + void moveToUninitializedEmplace( + T* begin, + T* end, + T* out, + Size pos, + EmplaceFunc&& emplaceFunc) { + // Must be called first so that if it throws [begin, end) is unmodified. + // We have to support the strong exception guarantee for emplace_back(). + emplaceFunc(out + pos); + // move old elements to the left of the new one + try { + detail::moveToUninitialized(begin, begin + pos, out); + } catch (...) { + out[pos].~T(); + throw; + } + // move old elements to the right of the new one + try { + if (begin + pos < end) { + detail::moveToUninitialized(begin + pos, end, out + pos + 1); + } + } catch (...) { + for (Size i = 0; i <= pos; ++i) { + out[i].~T(); + } + throw; + } + } + /* * Move objects in memory to the right into some uninitialized * memory, where the region overlaps. This doesn't just use * std::move_backward because move_backward only works if all the * memory is initialized to type T already. */ - template + template typename std::enable_if< !FOLLY_IS_TRIVIALLY_COPYABLE(T) >::type @@ -164,7 +202,7 @@ namespace detail { // Specialization for trivially copyable types. The call to // std::move_backward here will just turn into a memmove. (TODO: // change to std::is_trivially_copyable when that works.) - template + template typename std::enable_if< FOLLY_IS_TRIVIALLY_COPYABLE(T) >::type @@ -176,7 +214,7 @@ namespace detail { * Populate a region of memory using `op' to construct elements. If * anything throws, undo what we did. */ - template + template void populateMemForward(T* mem, std::size_t n, Function const& op) { std::size_t idx = 0; try { @@ -192,13 +230,13 @@ namespace detail { } } - template + template struct IntegralSizePolicy { typedef SizeType InternalSizeType; IntegralSizePolicy() : size_(0) {} - protected: + protected: static constexpr std::size_t policyMaxSize() { return SizeType(~kExternMask); } @@ -228,10 +266,10 @@ namespace detail { std::swap(size_, o.size_); } - protected: + protected: static bool const kShouldUseHeap = ShouldUseHeap; - private: + private: static SizeType const kExternMask = kShouldUseHeap ? SizeType(1) << (sizeof(SizeType) * 8 - 1) : 0; @@ -251,11 +289,12 @@ namespace detail { * Apologies for all the black magic. */ namespace mpl = boost::mpl; - template + template < + class Value, + std::size_t RequestedMaxInline, + class InPolicyA, + class InPolicyB, + class InPolicyC> struct small_vector_base { typedef mpl::vector PolicyList; @@ -326,11 +365,12 @@ namespace detail { ////////////////////////////////////////////////////////////////////// FOLLY_PACK_PUSH -template +template < + class Value, + std::size_t RequestedMaxInline = 1, + class PolicyA = void, + class PolicyB = void, + class PolicyC = void> class small_vector : public detail::small_vector_base< Value,RequestedMaxInline,PolicyA,PolicyB,PolicyC @@ -393,11 +433,15 @@ class small_vector constructImpl(il.begin(), il.end(), std::false_type()); } - explicit small_vector(size_type n, value_type const& t = value_type()) { - doConstruct(n, t); + explicit small_vector(size_type n) { + doConstruct(n, [&](void* p) { new (p) value_type(); }); } - template + small_vector(size_type n, value_type const& t) { + doConstruct(n, [&](void* p) { new (p) value_type(t); }); + } + + template explicit small_vector(Arg arg1, Arg arg2) { // Forward using std::is_arithmetic to get to the proper // implementation; this disambiguates between the iterators and @@ -482,7 +526,9 @@ class small_vector auto thisCapacity = this->capacity(); auto oCapacity = o.capacity(); - std::swap(unpackHack(&u.pdata_.heap_), unpackHack(&o.u.pdata_.heap_)); + auto* tmp = u.pdata_.heap_; + u.pdata_.heap_ = o.u.pdata_.heap_; + o.u.pdata_.heap_ = tmp; this->setCapacity(oCapacity); o.setCapacity(thisCapacity); @@ -582,7 +628,7 @@ class small_vector return this->isExtern() ? u.heap() : u.buffer(); } - template + template iterator emplace(const_iterator p, Args&&... args) { if (p == cend()) { emplace_back(std::forward(args)...); @@ -615,7 +661,7 @@ class small_vector size_type capacity() const { if (this->isExtern()) { if (u.hasCapacity()) { - return *u.getCapacity(); + return u.getCapacity(); } return malloc_usable_size(u.pdata_.heap_) / sizeof(value_type); } @@ -631,44 +677,28 @@ class small_vector tmp.swap(*this); } - template + template void emplace_back(Args&&... args) { - // call helper function for static dispatch of special cases - emplaceBack(std::forward(args)...); - } - - void emplace_back(const value_type& t) { - push_back(t); - } - void emplace_back(value_type& t) { - push_back(t); - } - - void emplace_back(value_type&& t) { - push_back(std::move(t)); - } - - void push_back(value_type&& t) { if (capacity() == size()) { - makeSize(std::max(size_type(2), 3 * size() / 2), &t, size()); + // Any of args may be references into the vector. + // When we are reallocating, we have to be careful to construct the new + // element before modifying the data in the old buffer. + makeSize( + size() + 1, + [&](void* p) { new (p) value_type(std::forward(args)...); }, + size()); } else { - new (end()) value_type(std::move(t)); + new (end()) value_type(std::forward(args)...); } this->setSize(size() + 1); } + void push_back(value_type&& t) { + return emplace_back(std::move(t)); + } + void push_back(value_type const& t) { - // TODO: we'd like to make use of makeSize (it can be optimized better, - // because it manipulates the internals) - // unfortunately the current implementation only supports moving from - // a supplied rvalue, and doing an extra move just to reuse it is a perf - // net loss - if (size() == capacity()) {// && isInside(&t)) { - value_type tmp(t); - emplaceBack(std::move(tmp)); - } else { - emplaceBack(t); - } + emplace_back(t); } void pop_back() { @@ -686,10 +716,12 @@ class small_vector auto offset = p - begin(); if (capacity() == size()) { - makeSize(size() + 1, &t, offset); + makeSize( + size() + 1, + [&t](void* ptr) { new (ptr) value_type(std::move(t)); }, + offset); this->setSize(this->size() + 1); } else { - makeSize(size() + 1); detail::moveObjectsRight(data() + offset, data() + size(), data() + size() + 1); @@ -717,7 +749,7 @@ class small_vector return begin() + offset; } - template + template iterator insert(const_iterator p, Arg arg1, Arg arg2) { // Forward using std::is_arithmetic to get to the proper // implementation; this disambiguates between the iterators and @@ -750,7 +782,7 @@ class small_vector erase(begin(), end()); } - template + template void assign(Arg first, Arg last) { clear(); insert(end(), first, last); @@ -794,35 +826,14 @@ class small_vector return (*this)[i]; } -private: - - /* - * This is doing the same like emplace_back, but we need this helper - * to catch the special case - see the next overload function.. - */ - template - void emplaceBack(Args&&... args) { - makeSize(size() + 1); - new (end()) value_type(std::forward(args)...); - this->setSize(size() + 1); - } - + private: static iterator unconst(const_iterator it) { return const_cast(it); } - /* - * g++ doesn't allow you to bind a non-const reference to a member - * of a packed structure, presumably because it would make it too - * easy to accidentally make an unaligned memory access? - */ - template static T& unpackHack(T* p) { - return *p; - } - // The std::false_type argument is part of disambiguating the // iterator insert functions from integral types (see insert().) - template + template iterator insertImpl(iterator pos, It first, It last, std::false_type) { typedef typename std::iterator_traits::iterator_category categ; if (std::is_same::value) { @@ -855,7 +866,7 @@ private: // The std::false_type argument came from std::is_arithmetic as part // of disambiguating an overload (see the comment in the // constructor). - template + template void constructImpl(It first, It last, std::false_type) { typedef typename std::iterator_traits::iterator_category categ; if (std::is_same::value) { @@ -882,13 +893,12 @@ private: } } - void doConstruct(size_type n, value_type const& val) { + template + void doConstruct(size_type n, InitFunc&& func) { makeSize(n); this->setSize(n); try { - detail::populateMemForward(data(), n, - [&] (void* p) { new (p) value_type(val); } - ); + detail::populateMemForward(data(), n, std::forward(func)); } catch (...) { if (this->isExtern()) { u.freeHeap(); @@ -900,33 +910,53 @@ private: // The true_type means we should forward to the size_t,value_type // overload. void constructImpl(size_type n, value_type const& val, std::true_type) { - doConstruct(n, val); + doConstruct(n, [&](void* p) { new (p) value_type(val); }); + } + + /* + * Compute the size after growth. + */ + size_type computeNewSize() const { + return std::min((3 * capacity()) / 2 + 1, max_size()); + } + + void makeSize(size_type newSize) { + makeSizeInternal(newSize, false, [](void*) { assume_unreachable(); }, 0); } - void makeSize(size_type size, value_type* v = nullptr) { - makeSize(size, v, size - 1); + template + void makeSize(size_type newSize, EmplaceFunc&& emplaceFunc, size_type pos) { + assert(size() == capacity()); + makeSizeInternal( + newSize, true, std::forward(emplaceFunc), pos); } /* - * Ensure we have a large enough memory region to be size `size'. + * Ensure we have a large enough memory region to be size `newSize'. * Will move/copy elements if we are spilling to heap_ or needed to * allocate a new region, but if resized in place doesn't initialize * anything in the new region. In any case doesn't change size(). * Supports insertion of new element during reallocation by given * pointer to new element and position of new element. - * NOTE: If reallocation is not needed, and new element should be - * inserted in the middle of vector (not at the end), do the move - * objects and insertion outside the function, otherwise exception is thrown. + * NOTE: If reallocation is not needed, insert must be false, + * because we only know how to emplace elements into new memory. */ - void makeSize(size_type size, value_type* v, size_type pos) { - if (size > this->max_size()) { + template + void makeSizeInternal( + size_type newSize, + bool insert, + EmplaceFunc&& emplaceFunc, + size_type pos) { + if (newSize > max_size()) { throw std::length_error("max_size exceeded in small_vector"); } - if (size <= this->capacity()) { + if (newSize <= capacity()) { + assert(!insert); return; } + newSize = std::max(newSize, computeNewSize()); - auto needBytes = size * sizeof(value_type); + auto needBytes = newSize * sizeof(value_type); // If the capacity isn't explicitly stored inline, but the heap // allocation is grown to over some threshold, we should store // a capacity at the front of the heap allocation. @@ -946,44 +976,18 @@ private: detail::shiftPointer(newh, kHeapifyCapacitySize) : newh); - if (v != nullptr) { - // move new element - try { - new (&newp[pos]) value_type(std::move(*v)); - } catch (...) { - free(newh); - throw; - } - - // move old elements to the left of the new one - try { - detail::moveToUninitialized(begin(), begin() + pos, newp); - } catch (...) { - newp[pos].~value_type(); - free(newh); - throw; - } - - // move old elements to the right of the new one - try { - if (pos < size-1) { - detail::moveToUninitialized(begin() + pos, end(), newp + pos + 1); - } - } catch (...) { - for (size_type i = 0; i <= pos; ++i) { - newp[i].~value_type(); - } - free(newh); - throw; - } - } else { - // move without inserting new element - try { + try { + if (insert) { + // move and insert the new element + detail::moveToUninitializedEmplace( + begin(), end(), newp, pos, std::forward(emplaceFunc)); + } else { + // move without inserting new element detail::moveToUninitialized(begin(), end(), newp); - } catch (...) { - free(newh); - throw; } + } catch (...) { + free(newh); + throw; } for (auto& val : *this) { val.~value_type(); @@ -1011,17 +1015,20 @@ private: assert(this->isExtern()); if (u.hasCapacity()) { assert(newCapacity < std::numeric_limits::max()); - *u.getCapacity() = InternalSizeType(newCapacity); + u.setCapacity(newCapacity); } } -private: + private: struct HeapPtrWithCapacity { void* heap_; InternalSizeType capacity_; - InternalSizeType* getCapacity() { - return &capacity_; + InternalSizeType getCapacity() const { + return capacity_; + } + void setCapacity(InternalSizeType c) { + capacity_ = c; } } FOLLY_PACK_ATTR; @@ -1030,10 +1037,12 @@ private: // stored at the front of the heap allocation. void* heap_; - InternalSizeType* getCapacity() { + InternalSizeType getCapacity() const { assert(detail::pointerFlagGet(heap_)); - return static_cast( - detail::pointerFlagClear(heap_)); + return *static_cast(detail::pointerFlagClear(heap_)); + } + void setCapacity(InternalSizeType c) { + *static_cast(detail::pointerFlagClear(heap_)) = c; } } FOLLY_PACK_ATTR; @@ -1087,10 +1096,10 @@ private: value_type* heap() noexcept { if (kHasInlineCapacity || !detail::pointerFlagGet(pdata_.heap_)) { return static_cast(pdata_.heap_); + } else { + return static_cast(detail::shiftPointer( + detail::pointerFlagClear(pdata_.heap_), kHeapifyCapacitySize)); } - return static_cast( - detail::shiftPointer( - detail::pointerFlagClear(pdata_.heap_), kHeapifyCapacitySize)); } value_type const* heap() const noexcept { return const_cast(this)->heap(); @@ -1099,11 +1108,11 @@ private: bool hasCapacity() const { return kHasInlineCapacity || detail::pointerFlagGet(pdata_.heap_); } - InternalSizeType* getCapacity() { + InternalSizeType getCapacity() const { return pdata_.getCapacity(); } - InternalSizeType* getCapacity() const { - return const_cast(this)->getCapacity(); + void setCapacity(InternalSizeType c) { + pdata_.setCapacity(c); } void freeHeap() { @@ -1118,7 +1127,7 @@ FOLLY_PACK_POP // Basic guarantee only, or provides the nothrow guarantee iff T has a // nothrow move or copy constructor. -template +template void swap(small_vector& a, small_vector& b) { a.swap(b); @@ -1134,8 +1143,8 @@ struct IndexableTraits> : public IndexableTraitsSeq> { }; -} // namespace detail +} // namespace detail -} // namespace folly +} // namespace folly -#pragma GCC diagnostic pop +FOLLY_POP_WARNING