/*
- * Copyright 2014 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.
*
* @author Jordan DeLong <delong.j@fb.com>
*/
-#ifndef FOLLY_SMALL_VECTOR_H_
-#define FOLLY_SMALL_VECTOR_H_
-#include <folly/Portability.h>
+#pragma once
#include <stdexcept>
#include <cstdlib>
#include <boost/mpl/empty.hpp>
#include <boost/mpl/size.hpp>
#include <boost/mpl/count.hpp>
-#include <boost/mpl/max.hpp>
+#include <folly/FormatTraits.h>
#include <folly/Malloc.h>
-
-#if defined(__GNUC__) && FOLLY_X64
-# include <folly/SmallLocks.h>
-# define FB_PACK_ATTR FOLLY_PACK_ATTR
-# define FB_PACK_PUSH FOLLY_PACK_PUSH
-# define FB_PACK_POP FOLLY_PACK_POP
-#else
-# define FB_PACK_ATTR
-# define FB_PACK_PUSH
-# define FB_PACK_POP
-#endif
-
-#if FOLLY_HAVE_MALLOC_SIZE
- extern "C" std::size_t malloc_size(const void*);
-# if !FOLLY_HAVE_MALLOC_USABLE_SIZE
-# define malloc_usable_size malloc_size
-# endif
-# ifndef malloc_usable_size
-# define malloc_usable_size malloc_size
-# endif
-#endif
+#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
!FOLLY_IS_TRIVIALLY_COPYABLE(T)
>::type
moveToUninitialized(T* first, T* last, T* out) {
- auto const count = last - first;
std::size_t idx = 0;
try {
- for (; idx < count; ++first, ++idx) {
+ for (; first != last; ++first, ++idx) {
new (&out[idx]) T(std::move(*first));
}
} catch (...) {
}
//////////////////////////////////////////////////////////////////////
-FB_PACK_PUSH
+FOLLY_PACK_PUSH
template<class Value,
std::size_t RequestedMaxInline = 1,
class PolicyA = void,
* the user asks for less inlined elements than we can fit unioned
* into our value_type*, we will inline more than they asked.)
*/
- enum {
- MaxInline = boost::mpl::max<
- boost::mpl::int_<sizeof(Value*) / sizeof(Value)>,
- boost::mpl::int_<RequestedMaxInline>
- >::type::value
- };
+ static constexpr std::size_t MaxInline{
+ constexpr_max(sizeof(Value*) / sizeof(Value), RequestedMaxInline)};
-public:
+ public:
typedef std::size_t size_type;
typedef Value value_type;
typedef value_type& reference;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
- explicit small_vector() {}
+ explicit small_vector() = default;
small_vector(small_vector const& o) {
auto n = o.size();
try {
std::uninitialized_copy(o.begin(), o.end(), begin());
} catch (...) {
- if (this->isExtern()) u.freeHeap();
+ if (this->isExtern()) {
+ u.freeHeap();
+ }
throw;
}
this->setSize(n);
}
- small_vector(small_vector&& o) {
+ small_vector(small_vector&& o)
+ noexcept(std::is_nothrow_move_constructible<Value>::value) {
if (o.isExtern()) {
swap(o);
} else {
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(); });
+ }
+
+ small_vector(size_type n, value_type const& t) {
+ doConstruct(n, [&](void* p) { new (p) value_type(t); });
}
template<class Arg>
}
static constexpr size_type max_size() {
- return !BaseType::kShouldUseHeap ? MaxInline
+ return !BaseType::kShouldUseHeap ? static_cast<size_type>(MaxInline)
: BaseType::policyMaxSize();
}
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());
}
void push_back(value_type const& t) {
- // Make a copy and forward to the rvalue value_type&& overload
- // above.
- push_back(value_type(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);
+ }
}
void pop_back() {
reference at(size_type i) {
if (i >= size()) {
- throw std::out_of_range("index out of range");
+ std::__throw_out_of_range("index out of range");
}
return (*this)[i];
}
const_reference at(size_type i) const {
if (i >= size()) {
- throw std::out_of_range("index out of range");
+ std::__throw_out_of_range("index out of range");
}
return (*this)[i];
}
this->setSize(size() + 1);
}
- /*
- * Special case of emplaceBack for rvalue
- */
- void emplaceBack(value_type&& t) {
- push_back(std::move(t));
- }
-
static iterator unconst(const_iterator it) {
return const_cast<iterator>(it);
}
// With iterators that only allow a single pass, we can't really
// do anything sane here.
while (first != last) {
- push_back(*first++);
+ emplace_back(*first++);
}
return;
}
auto distance = std::distance(first, last);
makeSize(distance);
this->setSize(distance);
-
- detail::populateMemForward(data(), distance,
- [&] (void* p) { new (p) value_type(*first++); }
- );
+ try {
+ detail::populateMemForward(data(), distance,
+ [&] (void* p) { new (p) value_type(*first++); }
+ );
+ } catch (...) {
+ if (this->isExtern()) {
+ u.freeHeap();
+ }
+ throw;
+ }
}
- void doConstruct(size_type n, value_type const& val) {
+ template <typename InitFunc>
+ void doConstruct(size_type n, InitFunc&& func) {
makeSize(n);
this->setSize(n);
- detail::populateMemForward(data(), n,
- [&] (void* p) { new (p) value_type(val); }
- );
+ try {
+ detail::populateMemForward(data(), n, std::forward<InitFunc>(func));
+ } catch (...) {
+ if (this->isExtern()) {
+ u.freeHeap();
+ }
+ throw;
+ }
}
// 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); });
}
void makeSize(size_type size, value_type* v = nullptr) {
InternalSizeType* getCapacity() {
return &capacity_;
}
- } FB_PACK_ATTR;
+ } FOLLY_PACK_ATTR;
struct HeapPtr {
// Lower order bit of heap_ is used as flag to indicate whether capacity is
return static_cast<InternalSizeType*>(
detail::pointerFlagClear(heap_));
}
- } FB_PACK_ATTR;
+ } FOLLY_PACK_ATTR;
-#if FOLLY_X64
- typedef unsigned char InlineStorageType[sizeof(value_type) * MaxInline];
+#if (FOLLY_X64 || FOLLY_PPC64)
+ typedef unsigned char InlineStorageDataType[sizeof(value_type) * MaxInline];
#else
typedef typename std::aligned_storage<
sizeof(value_type) * MaxInline,
alignof(value_type)
- >::type InlineStorageType;
+ >::type InlineStorageDataType;
#endif
+ typedef typename std::conditional<
+ sizeof(value_type) * MaxInline != 0,
+ InlineStorageDataType,
+ void*
+ >::type InlineStorageType;
+
static bool const kHasInlineCapacity =
sizeof(HeapPtrWithCapacity) < sizeof(InlineStorageType);
auto vp = detail::pointerFlagClear(pdata_.heap_);
free(vp);
}
- } FB_PACK_ATTR u;
-} FB_PACK_ATTR;
-FB_PACK_POP
+ } FOLLY_PACK_ATTR u;
+} FOLLY_PACK_ATTR;
+FOLLY_PACK_POP
//////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////
-}
+namespace detail {
-#pragma GCC diagnostic pop
+// Format support.
+template <class T, size_t M, class A, class B, class C>
+struct IndexableTraits<small_vector<T, M, A, B, C>>
+ : public IndexableTraitsSeq<small_vector<T, M, A, B, C>> {
+};
-#ifdef FB_PACK_ATTR
-# undef FB_PACK_ATTR
-# undef FB_PACK_PUSH
-# undef FB_PACK_POP
-#endif
+} // namespace detail
-#endif
+} // namespace folly
+
+#pragma GCC diagnostic pop