#pragma once
-#include <stdexcept>
-#include <cstdlib>
-#include <type_traits>
#include <algorithm>
-#include <iterator>
#include <cassert>
+#include <cstdlib>
+#include <iterator>
+#include <stdexcept>
+#include <type_traits>
-#include <boost/operators.hpp>
-#include <boost/type_traits.hpp>
-#include <boost/mpl/if.hpp>
+#include <boost/mpl/count.hpp>
+#include <boost/mpl/empty.hpp>
#include <boost/mpl/eval_if.hpp>
-#include <boost/mpl/vector.hpp>
-#include <boost/mpl/front.hpp>
#include <boost/mpl/filter_view.hpp>
+#include <boost/mpl/front.hpp>
#include <boost/mpl/identity.hpp>
+#include <boost/mpl/if.hpp>
#include <boost/mpl/placeholders.hpp>
-#include <boost/mpl/empty.hpp>
#include <boost/mpl/size.hpp>
-#include <boost/mpl/count.hpp>
+#include <boost/mpl/vector.hpp>
+#include <boost/operators.hpp>
+#include <boost/type_traits.hpp>
+#include <folly/Assume.h>
#include <folly/FormatTraits.h>
#include <folly/Malloc.h>
#include <folly/Portability.h>
#include <folly/SmallLocks.h>
+#include <folly/Traits.h>
#include <folly/portability/BitsFunctexcept.h>
#include <folly/portability/Constexpr.h>
#include <folly/portability/Malloc.h>
#include <folly/portability/TypeTraits.h>
// 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 {
//////////////////////////////////////////////////////////////////////
-} // small_vector_policy
+} // namespace small_vector_policy
//////////////////////////////////////////////////////////////////////
-template<class T, std::size_t M, class A, class B, class C>
+template <class T, std::size_t M, class A, class B, class C>
class small_vector;
//////////////////////////////////////////////////////////////////////
* Move a range to a range of uninitialized memory. Assumes the
* ranges don't overlap.
*/
- template<class T>
+ template <class T>
typename std::enable_if<
!FOLLY_IS_TRIVIALLY_COPYABLE(T)
>::type
}
// Specialization for trivially copyable types.
- template<class T>
+ template <class T>
typename std::enable_if<
FOLLY_IS_TRIVIALLY_COPYABLE(T)
>::type
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 <class T, class Size, class EmplaceFunc>
+ 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<class T>
+ template <class T>
typename std::enable_if<
!FOLLY_IS_TRIVIALLY_COPYABLE(T)
>::type
// 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<class T>
+ template <class T>
typename std::enable_if<
FOLLY_IS_TRIVIALLY_COPYABLE(T)
>::type
* Populate a region of memory using `op' to construct elements. If
* anything throws, undo what we did.
*/
- template<class T, class Function>
+ template <class T, class Function>
void populateMemForward(T* mem, std::size_t n, Function const& op) {
std::size_t idx = 0;
try {
}
}
- template<class SizeType, bool ShouldUseHeap>
+ template <class SizeType, bool ShouldUseHeap>
struct IntegralSizePolicy {
typedef SizeType InternalSizeType;
IntegralSizePolicy() : size_(0) {}
- protected:
+ protected:
static constexpr std::size_t policyMaxSize() {
return SizeType(~kExternMask);
}
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;
* Apologies for all the black magic.
*/
namespace mpl = boost::mpl;
- template<class Value,
- std::size_t RequestedMaxInline,
- class InPolicyA,
- class InPolicyB,
- class InPolicyC>
+ template <
+ class Value,
+ std::size_t RequestedMaxInline,
+ class InPolicyA,
+ class InPolicyB,
+ class InPolicyC>
struct small_vector_base {
typedef mpl::vector<InPolicyA,InPolicyB,InPolicyC> PolicyList;
//////////////////////////////////////////////////////////////////////
FOLLY_PACK_PUSH
-template<class Value,
- std::size_t RequestedMaxInline = 1,
- class PolicyA = void,
- class PolicyB = void,
- class PolicyC = void>
+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
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<class Arg>
+ small_vector(size_type n, value_type const& t) {
+ doConstruct(n, [&](void* p) { new (p) value_type(t); });
+ }
+
+ template <class Arg>
explicit small_vector(Arg arg1, Arg arg2) {
// Forward using std::is_arithmetic to get to the proper
// implementation; this disambiguates between the iterators and
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);
return this->isExtern() ? u.heap() : u.buffer();
}
- template<class ...Args>
+ template <class... Args>
iterator emplace(const_iterator p, Args&&... args) {
if (p == cend()) {
emplace_back(std::forward<Args>(args)...);
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);
}
tmp.swap(*this);
}
- template<class ...Args>
+ template <class... Args>
void emplace_back(Args&&... args) {
- // call helper function for static dispatch of special cases
- emplaceBack(std::forward<Args>(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>(args)...); },
+ size());
} else {
- new (end()) value_type(std::move(t));
+ new (end()) value_type(std::forward<Args>(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() {
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);
return begin() + offset;
}
- template<class Arg>
+ template <class Arg>
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
erase(begin(), end());
}
- template<class Arg>
+ template <class Arg>
void assign(Arg first, Arg last) {
clear();
insert(end(), first, last);
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<class ...Args>
- void emplaceBack(Args&&... args) {
- makeSize(size() + 1);
- new (end()) value_type(std::forward<Args>(args)...);
- this->setSize(size() + 1);
- }
-
+ private:
static iterator unconst(const_iterator it) {
return const_cast<iterator>(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<class T> 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<class It>
+ template <class It>
iterator insertImpl(iterator pos, It first, It last, std::false_type) {
typedef typename std::iterator_traits<It>::iterator_category categ;
if (std::is_same<categ,std::input_iterator_tag>::value) {
// The std::false_type argument came from std::is_arithmetic as part
// of disambiguating an overload (see the comment in the
// constructor).
- template<class It>
+ template <class It>
void constructImpl(It first, It last, std::false_type) {
typedef typename std::iterator_traits<It>::iterator_category categ;
if (std::is_same<categ,std::input_iterator_tag>::value) {
}
}
- void doConstruct(size_type n, value_type const& val) {
+ template <typename InitFunc>
+ 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<InitFunc>(func));
} catch (...) {
if (this->isExtern()) {
u.freeHeap();
// 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 <typename EmplaceFunc>
+ void makeSize(size_type newSize, EmplaceFunc&& emplaceFunc, size_type pos) {
+ assert(size() == capacity());
+ makeSizeInternal(
+ newSize, true, std::forward<EmplaceFunc>(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 <typename EmplaceFunc>
+ 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.
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>(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();
assert(this->isExtern());
if (u.hasCapacity()) {
assert(newCapacity < std::numeric_limits<InternalSizeType>::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;
// stored at the front of the heap allocation.
void* heap_;
- InternalSizeType* getCapacity() {
+ InternalSizeType getCapacity() const {
assert(detail::pointerFlagGet(heap_));
- return static_cast<InternalSizeType*>(
- detail::pointerFlagClear(heap_));
+ return *static_cast<InternalSizeType*>(detail::pointerFlagClear(heap_));
+ }
+ void setCapacity(InternalSizeType c) {
+ *static_cast<InternalSizeType*>(detail::pointerFlagClear(heap_)) = c;
}
} FOLLY_PACK_ATTR;
value_type* heap() noexcept {
if (kHasInlineCapacity || !detail::pointerFlagGet(pdata_.heap_)) {
return static_cast<value_type*>(pdata_.heap_);
+ } else {
+ return static_cast<value_type*>(detail::shiftPointer(
+ detail::pointerFlagClear(pdata_.heap_), kHeapifyCapacitySize));
}
- return static_cast<value_type*>(
- detail::shiftPointer(
- detail::pointerFlagClear(pdata_.heap_), kHeapifyCapacitySize));
}
value_type const* heap() const noexcept {
return const_cast<Data*>(this)->heap();
bool hasCapacity() const {
return kHasInlineCapacity || detail::pointerFlagGet(pdata_.heap_);
}
- InternalSizeType* getCapacity() {
+ InternalSizeType getCapacity() const {
return pdata_.getCapacity();
}
- InternalSizeType* getCapacity() const {
- return const_cast<Data*>(this)->getCapacity();
+ void setCapacity(InternalSizeType c) {
+ pdata_.setCapacity(c);
}
void freeHeap() {
// Basic guarantee only, or provides the nothrow guarantee iff T has a
// nothrow move or copy constructor.
-template<class T, std::size_t MaxInline, class A, class B, class C>
+template <class T, std::size_t MaxInline, class A, class B, class C>
void swap(small_vector<T,MaxInline,A,B,C>& a,
small_vector<T,MaxInline,A,B,C>& b) {
a.swap(b);
: public IndexableTraitsSeq<small_vector<T, M, A, B, C>> {
};
-} // namespace detail
+} // namespace detail
-} // namespace folly
+} // namespace folly
-#pragma GCC diagnostic pop
+FOLLY_POP_WARNING