/*
- * 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.
//===========================================================================
//---------------------------------------------------------------------------
// implementation
-private:
-
+ private:
typedef std::allocator_traits<Allocator> A;
struct Impl : public Allocator {
//===========================================================================
//---------------------------------------------------------------------------
// types and constants
-public:
-
+ public:
typedef T value_type;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
-private:
-
+ private:
typedef std::integral_constant<bool,
- boost::has_trivial_copy_constructor<T>::value &&
+ IsTriviallyCopyable<T>::value &&
sizeof(T) <= 16 // don't force large structures to be passed by value
> should_pass_by_value;
typedef typename std::conditional<
//===========================================================================
//---------------------------------------------------------------------------
// allocator helpers
-private:
-
+ private:
//---------------------------------------------------------------------------
// allocate
void M_destroy(T* p) noexcept {
if (usingStdAllocator::value) {
- if (!boost::has_trivial_destructor<T>::value) p->~T();
+ if (!std::is_trivially_destructible<T>::value)
+ p->~T();
} else {
std::allocator_traits<Allocator>::destroy(impl_, p);
}
//===========================================================================
//---------------------------------------------------------------------------
// algorithmic helpers
-private:
-
+ private:
//---------------------------------------------------------------------------
// destroy_range
// optimized
static void S_destroy_range(T* first, T* last) noexcept {
- if (!boost::has_trivial_destructor<T>::value) {
+ if (!std::is_trivially_destructible<T>::value) {
// EXPERIMENTAL DATA on fbvector<vector<int>> (where each vector<int> has
// size 0).
// The unrolled version seems to work faster for small to medium sized
//===========================================================================
//---------------------------------------------------------------------------
// relocation helpers
-private:
-
+ private:
// Relocation is divided into three parts:
//
// 1: relocate_move
//===========================================================================
//---------------------------------------------------------------------------
// construct/copy/destroy
-public:
-
+ public:
fbvector() = default;
explicit fbvector(const Allocator& a) : impl_(a) {}
return impl_;
}
-private:
-
+ private:
// contract dispatch for iterator types fbvector(It first, It last)
template <class ForwardIterator>
fbvector(ForwardIterator first, ForwardIterator last,
const Allocator& a, std::forward_iterator_tag)
- : impl_(std::distance(first, last), a)
+ : impl_(size_type(std::distance(first, last)), a)
{ M_uninitialized_copy_e(first, last); }
template <class InputIterator>
template <class ForwardIterator>
void assign(ForwardIterator first, ForwardIterator last,
std::forward_iterator_tag) {
- const size_t newSize = std::distance(first, last);
+ const auto newSize = size_type(std::distance(first, last));
if (newSize > capacity()) {
impl_.reset(newSize);
M_uninitialized_copy_e(first, last);
//===========================================================================
//---------------------------------------------------------------------------
// iterators
-public:
-
+ public:
iterator begin() noexcept {
return impl_.b_;
}
//===========================================================================
//---------------------------------------------------------------------------
// capacity
-public:
-
+ public:
size_type size() const noexcept {
return size_type(impl_.e_ - impl_.b_);
}
return;
}
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;
}
}
-private:
-
+ private:
bool reserve_in_place(size_type n) {
if (!usingStdAllocator::value || !usingJEMalloc()) return false;
//===========================================================================
//---------------------------------------------------------------------------
// element access
-public:
-
+ public:
reference operator[](size_type n) {
assert(n < size());
return impl_.b_[n];
//===========================================================================
//---------------------------------------------------------------------------
// data access
-public:
-
+ public:
T* data() noexcept {
return impl_.b_;
}
//===========================================================================
//---------------------------------------------------------------------------
// modifiers (common)
-public:
-
+ public:
template <class... Args>
void emplace_back(Args&&... args) {
if (impl_.e_ != impl_.z_) {
M_destroy_range_e(impl_.b_);
}
-private:
-
+ private:
// std::vector implements a similar function with a different growth
// strategy: empty() ? 1 : capacity() * 2.
//
//===========================================================================
//---------------------------------------------------------------------------
// modifiers (erase)
-public:
-
+ public:
iterator erase(const_iterator position) {
return erase(position, position + 1);
}
//===========================================================================
//---------------------------------------------------------------------------
// modifiers (insert)
-private: // we have the private section first because it defines some macros
-
+ private: // we have the private section first because it defines some macros
bool isValid(const_iterator it) {
return cbegin() <= it && it <= cend();
}
void make_window(iterator position, size_type n) {
// The result is guaranteed to be non-negative, so use an unsigned type:
- size_type tail = std::distance(position, impl_.e_);
+ size_type tail = size_type(std::distance(position, impl_.e_));
if (tail <= n) {
relocate_move(position + n, position, impl_.e_);
//---------------------------------------------------------------------------
// 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)); \
- } \
- T* position = const_cast<T*>(cpos); \
- size_type idx = std::distance(impl_.b_, position); \
- T* b; \
- size_type newCap; /* intentionally uninitialized */ \
- \
- if (fresh) { \
- newCap = computeInsertCapacity(n); \
- b = M_allocate(newCap); \
- } else { \
- if (!at_end) { \
- make_window(position, n); \
- } else { \
- impl_.e_ += n; \
- } \
- b = impl_.b_; \
- } \
- \
- T* start = b + idx; \
- \
- try { \
-
- // construct the inserted elements
-
- #define FOLLY_FBVECTOR_INSERT_TRY(cpos, n) \
- } catch (...) { \
- if (fresh) { \
- M_deallocate(b, newCap); \
- } else { \
- if (!at_end) { \
- undo_window(position, n); \
- } else { \
- impl_.e_ -= n; \
- } \
- } \
- throw; \
- } \
- \
- if (fresh) { \
- try { \
- wrap_frame(b, idx, n); \
- } catch (...) { \
-
-
- // delete the inserted elements (exception has been thrown)
-
- #define FOLLY_FBVECTOR_INSERT_END(cpos, n) \
- M_deallocate(b, newCap); \
- throw; \
- } \
- if (impl_.b_) M_deallocate(impl_.b_, capacity()); \
- impl_.set(b, size() + n, newCap); \
- return impl_.b_ + idx; \
- } else { \
- return position; \
- } \
+ template <
+ typename IsInternalFunc,
+ typename InsertInternalFunc,
+ typename ConstructFunc,
+ typename DestroyFunc>
+ iterator do_real_insert(
+ const_iterator cpos,
+ size_type n,
+ IsInternalFunc&& isInternalFunc,
+ InsertInternalFunc&& insertInternalFunc,
+ ConstructFunc&& constructFunc,
+ DestroyFunc&& destroyFunc) {
+ if (n == 0) {
+ return iterator(cpos);
+ }
+ bool at_end = cpos == cend();
+ bool fresh = insert_use_fresh(at_end, n);
+ if (!at_end) {
+ if (!fresh && isInternalFunc()) {
+ // check for internal data (technically not required by the standard)
+ return insertInternalFunc();
+ }
+ assert(isValid(cpos));
+ }
+ T* position = const_cast<T*>(cpos);
+ size_type idx = size_type(std::distance(impl_.b_, position));
+ T* b;
+ size_type newCap; /* intentionally uninitialized */
- //---------------------------------------------------------------------------
- // insert functions
-public:
+ if (fresh) {
+ newCap = computeInsertCapacity(n);
+ b = M_allocate(newCap);
+ } else {
+ if (!at_end) {
+ make_window(position, n);
+ } else {
+ impl_.e_ += n;
+ }
+ b = impl_.b_;
+ }
+
+ T* start = b + idx;
+ try {
+ // construct the inserted elements
+ constructFunc(start);
+ } catch (...) {
+ if (fresh) {
+ M_deallocate(b, newCap);
+ } else {
+ if (!at_end) {
+ undo_window(position, n);
+ } else {
+ impl_.e_ -= n;
+ }
+ }
+ throw;
+ }
+ if (fresh) {
+ try {
+ wrap_frame(b, idx, n);
+ } catch (...) {
+ // delete the inserted elements (exception has been thrown)
+ destroyFunc(start);
+ M_deallocate(b, newCap);
+ throw;
+ }
+ if (impl_.b_) {
+ M_deallocate(impl_.b_, capacity());
+ }
+ impl_.set(b, size() + n, newCap);
+ return impl_.b_ + idx;
+ } else {
+ return position;
+ }
+ }
+
+ public:
template <class... Args>
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>(args)...);
- FOLLY_FBVECTOR_INSERT_TRY(cpos, 1)
- M_destroy(start);
- FOLLY_FBVECTOR_INSERT_END(cpos, 1)
+ return do_real_insert(
+ cpos,
+ 1,
+ [&] { return false; },
+ [&] { return iterator{}; },
+ [&](iterator start) {
+ M_construct(start, std::forward<Args>(args)...);
+ },
+ [&](iterator start) { M_destroy(start); });
}
iterator insert(const_iterator cpos, const 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)
- M_destroy(start);
- FOLLY_FBVECTOR_INSERT_END(cpos, 1)
+ return do_real_insert(
+ cpos,
+ 1,
+ [&] { return dataIsInternal(value); },
+ [&] { return insert(cpos, T(value)); },
+ [&](iterator start) { M_construct(start, value); },
+ [&](iterator start) { M_destroy(start); });
}
iterator insert(const_iterator cpos, T&& 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)
- M_destroy(start);
- FOLLY_FBVECTOR_INSERT_END(cpos, 1)
+ return do_real_insert(
+ cpos,
+ 1,
+ [&] { return dataIsInternal(value); },
+ [&] { return insert(cpos, T(std::move(value))); },
+ [&](iterator start) { M_construct(start, std::move(value)); },
+ [&](iterator start) { M_destroy(start); });
}
iterator insert(const_iterator cpos, size_type n, VT 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)
- D_destroy_range_a(start, start + n);
- FOLLY_FBVECTOR_INSERT_END(cpos, n)
+ return do_real_insert(
+ cpos,
+ n,
+ [&] { return dataIsInternalAndNotVT(value); },
+ [&] { return insert(cpos, n, T(value)); },
+ [&](iterator start) { D_uninitialized_fill_n_a(start, n, value); },
+ [&](iterator start) { D_destroy_range_a(start, start + n); });
}
template <class It, class Category = typename
//---------------------------------------------------------------------------
// insert dispatch for iterator types
-private:
-
+ private:
template <class FIt>
iterator insert(const_iterator cpos, FIt first, FIt last,
std::forward_iterator_tag) {
- size_type n = std::distance(first, last);
- 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)
- D_destroy_range_a(start, start + n);
- FOLLY_FBVECTOR_INSERT_END(cpos, n)
+ size_type n = size_type(std::distance(first, last));
+ return do_real_insert(
+ cpos,
+ n,
+ [&] { return false; },
+ [&] { return iterator{}; },
+ [&](iterator start) { D_uninitialized_copy_a(start, first, last); },
+ [&](iterator start) { D_destroy_range_a(start, start + n); });
}
template <class IIt>
//===========================================================================
//---------------------------------------------------------------------------
// lexicographical functions
-public:
-
+ public:
bool operator==(const fbvector& other) const {
return size() == other.size() && std::equal(begin(), end(), other.begin());
}
//===========================================================================
//---------------------------------------------------------------------------
// friends
-private:
-
+ private:
template <class _T, class _A>
friend _T* relinquish(fbvector<_T, _A>&);
: public IndexableTraitsSeq<fbvector<T, A>> {
};
-} // namespace detail
+} // namespace detail
template <class T, class A>
void compactResize(fbvector<T, A>* v, size_t sz) {
projects / folly.git / blobdiff