*/
/*
- * For high-level documentation and usage examples see folly/doc/small_vector.md
+ * For high-level documentation and usage examples see
+ * folly/docs/small_vector.md
*
* @author Jordan DeLong <delong.j@fb.com>
*/
#ifndef FOLLY_SMALL_VECTOR_H_
#define FOLLY_SMALL_VECTOR_H_
-#include "Portability.h"
+#include <folly/Portability.h>
#include <stdexcept>
#include <cstdlib>
#include <boost/mpl/count.hpp>
#include <boost/mpl/max.hpp>
-#include "folly/Malloc.h"
+#include <folly/Malloc.h>
-#if defined(__GNUC__) && defined(__x86_64__)
-# include "folly/SmallLocks.h"
-# define FB_PACKED __attribute__((packed))
+#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_PACKED
+# define FB_PACK_ATTR
+# define FB_PACK_PUSH
+# define FB_PACK_POP
#endif
#if FOLLY_HAVE_MALLOC_SIZE
*/
struct NoHeap;
-/*
- * Passing this policy will cause small_vector to provide lock() and
- * unlock() functions using a 1-bit spin lock in the size value.
- *
- * Note that this is intended for a fairly specialized (although
- * strangely common at facebook) use case, where you have billions of
- * vectors in memory where none of them are "hot" and most of them are
- * small. This allows you to get fine-grained locks without spending
- * a lot of memory on mutexes (the alternative of a large hashtable of
- * locks leads to extra cache misses in the lookup path).
- *
- * __x86_64__ only.
- */
-struct OneBitMutex;
-
//////////////////////////////////////////////////////////////////////
} // small_vector_policy
IntegralSizePolicy() : size_(0) {}
protected:
- std::size_t policyMaxSize() const {
+ static constexpr std::size_t policyMaxSize() {
return SizeType(~kExternMask);
}
SizeType size_;
};
-#ifdef __x86_64__
- template<class SizeType, bool ShouldUseHeap>
- struct OneBitMutexImpl {
- typedef SizeType InternalSizeType;
-
- OneBitMutexImpl() { psl_.init(); }
-
- void lock() const { psl_.lock(); }
- void unlock() const { psl_.unlock(); }
- bool try_lock() const { return psl_.try_lock(); }
-
- protected:
- static bool const kShouldUseHeap = ShouldUseHeap;
-
- std::size_t policyMaxSize() const {
- return SizeType(~(SizeType(1) << kLockBit | kExternMask));
- }
-
- std::size_t doSize() const {
- return psl_.getData() & ~kExternMask;
- }
-
- std::size_t isExtern() const {
- return psl_.getData() & kExternMask;
- }
-
- void setExtern(bool b) {
- if (b) {
- setSize(SizeType(doSize()) | kExternMask);
- } else {
- setSize(SizeType(doSize()) & ~kExternMask);
- }
- }
-
- void setSize(std::size_t sz) {
- assert(sz < (std::size_t(1) << kLockBit));
- psl_.setData((kExternMask & psl_.getData()) | SizeType(sz));
- }
-
- void swapSizePolicy(OneBitMutexImpl& o) {
- std::swap(psl_, o.psl_);
- }
-
- private:
- static SizeType const kLockBit = sizeof(SizeType) * 8 - 1;
- static SizeType const kExternMask =
- kShouldUseHeap ? SizeType(1) << (sizeof(SizeType) * 8 - 2)
- : 0;
-
- PicoSpinLock<SizeType,kLockBit> psl_;
- };
-#else
- template<class SizeType, bool ShouldUseHeap>
- struct OneBitMutexImpl {
- static_assert(std::is_same<SizeType,void>::value,
- "OneBitMutex only works on x86-64");
- };
-#endif
-
/*
* If you're just trying to use this class, ignore everything about
* this next small_vector_base class thing.
mpl::size<Integrals>::value == 1,
"Multiple size types specified in small_vector<>");
- /*
- * Figure out if we're supposed to supply a one-bit mutex. :)
- */
- typedef typename mpl::count<
- PolicyList,small_vector_policy::OneBitMutex
- >::type HasMutex;
-
- static_assert(HasMutex::value == 0 || HasMutex::value == 1,
- "Multiple copies of small_vector_policy::OneBitMutex "
- "supplied; this is probably a mistake");
-
/*
* Determine whether we should allow spilling to the heap or not.
*/
/*
* Make the real policy base classes.
*/
- typedef typename mpl::if_<
- HasMutex,
- OneBitMutexImpl<SizeType,!HasNoHeap::value>,
- IntegralSizePolicy<SizeType,!HasNoHeap::value>
- >::type ActualSizePolicy;
+ typedef IntegralSizePolicy<SizeType,!HasNoHeap::value>
+ ActualSizePolicy;
/*
* Now inherit from them all. This is done in such a convoluted
}
//////////////////////////////////////////////////////////////////////
-
+FB_PACK_PUSH
template<class Value,
std::size_t RequestedMaxInline = 1,
class PolicyA = void,
};
public:
- typedef std::size_t size_type;
+ typedef std::size_t size_type;
typedef Value value_type;
typedef value_type& reference;
typedef value_type const& const_reference;
explicit small_vector() {}
small_vector(small_vector const& o) {
- assign(o.begin(), o.end());
+ auto n = o.size();
+ makeSize(n);
+ try {
+ std::uninitialized_copy(o.begin(), o.end(), begin());
+ } catch (...) {
+ if (this->isExtern()) {
+ u.freeHeap();
+ }
+ throw;
+ }
+ this->setSize(n);
}
- small_vector(small_vector&& o) {
- *this = std::move(o);
+ small_vector(small_vector&& o)
+ noexcept(std::is_nothrow_move_constructible<Value>::value) {
+ if (o.isExtern()) {
+ swap(o);
+ } else {
+ std::uninitialized_copy(std::make_move_iterator(o.begin()),
+ std::make_move_iterator(o.end()),
+ begin());
+ this->setSize(o.size());
+ }
}
small_vector(std::initializer_list<value_type> il) {
}
small_vector& operator=(small_vector&& o) {
+ // TODO: optimization:
+ // if both are internal, use move assignment where possible
+ if (this == &o) return *this;
clear();
- if (!o.isExtern()) {
- makeSize(o.size());
- for (std::size_t i = 0; i < o.size(); ++i) {
- new (data() + i) value_type(std::move(o[i]));
- }
- this->setSize(o.size());
- } else {
- swap(o);
- }
+ swap(o);
return *this;
}
return std::lexicographical_compare(begin(), end(), o.begin(), o.end());
}
- size_type max_size() const {
+ static constexpr size_type max_size() {
return !BaseType::kShouldUseHeap ? MaxInline
- : this->policyMaxSize();
+ : BaseType::policyMaxSize();
}
size_type size() const { return this->doSize(); }
}
size_type i = oldSmall.size();
+ const size_type ci = i;
try {
for (; i < oldLarge.size(); ++i) {
- new (&oldSmall[i]) value_type(std::move(oldLarge[i]));
+ auto addr = oldSmall.begin() + i;
+ new (addr) value_type(std::move(oldLarge[i]));
oldLarge[i].~value_type();
}
} catch (...) {
+ oldSmall.setSize(i);
for (; i < oldLarge.size(); ++i) {
oldLarge[i].~value_type();
}
- oldLarge.setSize(oldSmall.size());
+ oldLarge.setSize(ci);
throw;
}
- this->swapSizePolicy(o);
+ oldSmall.setSize(i);
+ oldLarge.setSize(ci);
return;
}
}
iterator erase(const_iterator q1, const_iterator q2) {
+ if (q1 == q2) return unconst(q1);
std::move(unconst(q2), end(), unconst(q1));
- for (auto it = q1; it != end(); ++it) {
+ for (auto it = (end() - std::distance(q1, q2)); it != end(); ++it) {
it->~value_type();
}
this->setSize(size() - (q2 - q1));
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) {
makeSize(n);
this->setSize(n);
- detail::populateMemForward(data(), n,
- [&] (void* p) { new (p) value_type(val); }
- );
+ try {
+ detail::populateMemForward(data(), n,
+ [&] (void* p) { new (p) value_type(val); }
+ );
+ } catch (...) {
+ if (this->isExtern()) {
+ u.freeHeap();
+ }
+ throw;
+ }
}
// The true_type means we should forward to the size_t,value_type
doConstruct(n, val);
}
- void makeSize(size_type size, value_type* v = NULL) {
+ void makeSize(size_type size, value_type* v = nullptr) {
makeSize(size, v, size - 1);
}
detail::shiftPointer(newh, kHeapifyCapacitySize) :
newh);
- if (v != NULL) {
+ if (v != nullptr) {
// move new element
try {
new (&newp[pos]) value_type(std::move(*v));
InternalSizeType* getCapacity() {
return &capacity_;
}
- } FB_PACKED;
+ } FB_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_PACKED;
+ } FB_PACK_ATTR;
-#if defined(__x86_64_)
+#if FOLLY_X64
typedef unsigned char InlineStorageType[sizeof(value_type) * MaxInline];
#else
typedef typename std::aligned_storage<
auto vp = detail::pointerFlagClear(pdata_.heap_);
free(vp);
}
- } FB_PACKED u;
-} FB_PACKED;
+ } FB_PACK_ATTR u;
+} FB_PACK_ATTR;
+FB_PACK_POP
//////////////////////////////////////////////////////////////////////
#pragma GCC diagnostic pop
-#ifdef FB_PACKED
-# undef FB_PACKED
+#ifdef FB_PACK_ATTR
+# undef FB_PACK_ATTR
+# undef FB_PACK_PUSH
+# undef FB_PACK_POP
#endif
#endif
projects / folly.git / blobdiff