35 #include <type_traits> 48 template <
class T,
class Allocator = std::allocator<T>>
55 #define FOLLY_FBV_UNROLL_PTR(first, last, OP) \ 57 for (; (last) - (first) >= 4; (first) += 4) { \ 63 for (; (first) != (last); ++(first)) \ 76 template <
class T,
class Allocator>
82 typedef std::allocator_traits<Allocator>
A;
84 struct Impl :
public Allocator {
94 Impl(
const Allocator& alloc)
99 Impl(size_type n,
const Allocator& alloc = Allocator())
109 other.b_ = other.e_ = other.z_ =
nullptr;
123 return std::allocator_traits<Allocator>::allocate(*
this, n);
131 std::allocator_traits<Allocator>::deallocate(*
this, p, n);
160 b_ = e_ = z_ =
nullptr;
169 void set(pointer newB, size_type newSize, size_type newCap) {
186 b_ = e_ = z_ =
nullptr;
193 swap(static_cast<Allocator&>(a), static_cast<Allocator&>(b));
220 should_pass_by_value;
241 T* M_allocate(size_type n) {
248 void M_deallocate(
T* p, size_type n)
noexcept {
258 template <
typename U,
typename...
Args>
259 void M_construct(U* p,
Args&&... args) {
261 new (p) U(std::forward<Args>(args)...);
263 std::allocator_traits<Allocator>::construct(
264 impl_, p, std::forward<Args>(args)...);
268 template <
typename U,
typename...
Args>
269 static void S_construct(U* p,
Args&&... args) {
270 new (p) U(std::forward<Args>(args)...);
273 template <
typename U,
typename...
Args>
274 static void S_construct_a(Allocator&
a, U* p,
Args&&... args) {
275 std::allocator_traits<Allocator>::construct(
276 a, p, std::forward<Args>(args)...);
284 void M_construct(U* p, U arg) {
288 std::allocator_traits<Allocator>::construct(
impl_, p, arg);
295 static void S_construct(U* p, U arg) {
302 static void S_construct_a(Allocator& a, U* p, U arg) {
303 std::allocator_traits<Allocator>::construct(a, p, arg);
311 void M_construct(U* p,
const U&
value) {
315 std::allocator_traits<Allocator>::construct(
impl_, p, value);
323 static void S_construct(U* p,
const U& value) {
331 static void S_construct_a(Allocator& a, U* p,
const U& value) {
332 std::allocator_traits<Allocator>::construct(a, p, value);
381 #define FOLLY_FBV_OP(p) (p)->~T() 439 for (;
b != e; ++
b) {
440 std::allocator_traits<Allocator>::construct(
441 a,
b, std::forward<Args>(args)...);
453 std::memset(dest, 0,
sizeof(
T) * n);
459 for (;
b != e; ++
b) {
476 for (;
b != e; ++
b) {
477 S_construct(
b, value);
492 template <
typename It>
495 impl_.
e_ += std::distance(first, last);
498 template <
typename It>
501 impl_.
e_ += std::distance(first, last);
505 template <
typename It>
518 template <
typename It>
521 dest, std::make_move_iterator(first), std::make_move_iterator(last));
525 template <
typename It>
529 for (; first != last; ++
first, ++
b) {
530 std::allocator_traits<Allocator>::construct(a,
b, *first);
539 template <
typename It>
543 for (; first != last; ++
first, ++
b) {
544 S_construct(
b, *first);
555 std::memcpy((
void*)dest, (
void*)first, (last - first) *
sizeof(
T));
561 std::move_iterator<T*>
first,
562 std::move_iterator<T*> last) {
563 T* bFirst = first.base();
564 T* bLast = last.base();
565 if (bLast != bFirst) {
566 std::memcpy((
void*)dest, (
void*)bFirst, (bLast - bFirst) *
sizeof(
T));
570 template <
typename It>
582 template <
typename It>
593 std::memcpy((
void*)dest, (
void*)first, n *
sizeof(
T));
596 return S_copy_n<const T*>(
dest,
first, n);
600 static std::move_iterator<T*>
604 std::memcpy((
void*)dest, (
void*)first, n *
sizeof(
T));
605 return std::make_move_iterator(first + n);
607 return S_copy_n<std::move_iterator<T*>>(
dest, mIt, n);
673 if (first !=
nullptr) {
674 std::memcpy((
void*)dest, (
void*)first, (last - first) *
sizeof(
T));
725 explicit fbvector(size_type n,
const Allocator& a = Allocator())
730 fbvector(size_type n, VT value,
const Allocator& a = Allocator())
737 class Category =
typename std::iterator_traits<It>::iterator_category>
738 fbvector(It
first, It last,
const Allocator& a = Allocator())
739 : fbvector(first, last, a, Category()) {}
744 A::select_on_container_copy_construction(other.
impl_)) {
754 if (
impl_ == other.impl_) {
762 fbvector(std::initializer_list<T> il,
const Allocator& a = Allocator())
774 if (
impl_ != other.impl_) {
778 (Allocator&)
impl_ = (Allocator&)other.impl_;
781 assign(other.begin(), other.end());
794 assign(il.begin(), il.end());
800 class Category =
typename std::iterator_traits<It>::iterator_category>
801 void assign(It first, It last) {
802 assign(first, last, Category());
805 void assign(size_type n, VT value) {
817 }
else if (n <=
size()) {
819 std::fill(
impl_.
b_, newE, value);
827 void assign(std::initializer_list<T> il) {
828 assign(il.begin(), il.end());
837 template <
class ForwardIterator>
839 ForwardIterator first,
840 ForwardIterator last,
842 std::forward_iterator_tag)
843 :
impl_(size_type(
std::distance(first, last)), a) {
847 template <
class InputIterator>
852 std::input_iterator_tag)
854 for (; first != last; ++
first) {
864 if (
impl_ == other.impl_) {
873 template <
class ForwardIterator>
875 ForwardIterator first,
876 ForwardIterator last,
877 std::forward_iterator_tag) {
878 const auto newSize =
size_type(std::distance(first, last));
882 }
else if (newSize <=
size()) {
887 M_uninitialized_copy_e<decltype(last)>(mid, last);
891 template <
class InputIterator>
893 assign(InputIterator first, InputIterator last, std::input_iterator_tag) {
901 for (; first != last; ++
first) {
971 return ~size_type(0);
974 void resize(size_type n) {
983 void resize(size_type n, VT
t) {
1013 auto newB = M_allocate(newCap);
1017 M_deallocate(newB, newCap);
1035 auto const newCap = newCapacityBytes /
sizeof(
T);
1038 if (newCap >= oldCap) {
1047 xallocx(p, newCapacityBytes, 0, 0) == newCapacityBytes) {
1052 newB = M_allocate(newCap);
1056 M_deallocate(newB, newCap);
1085 if (
xallocx(p, newCapacityBytes, 0, 0) == newCapacityBytes) {
1100 const_reference
operator[](size_type n)
const {
1104 const_reference
at(size_type n)
const {
1106 throw_exception<std::out_of_range>(
1107 "fbvector: index is greater than size.");
1111 reference
at(size_type n) {
1112 auto const& cThis = *
this;
1113 return const_cast<reference
>(cThis.at(n));
1119 const_reference
front()
const {
1127 const_reference
back()
const {
1150 M_construct(
impl_.
e_, std::forward<Args>(args)...);
1219 if (
capacity() > 4096 * 32 /
sizeof(
T)) {
1225 template <
class...
Args>
1232 iterator
erase(const_iterator position) {
1233 return erase(position, position + 1);
1236 iterator
erase(const_iterator first, const_iterator last) {
1238 assert(first <= last);
1239 if (first != last) {
1240 if (last ==
end()) {
1245 if (last - first >=
cend() - last) {
1246 std::memcpy((
void*)first, (
void*)last, (
cend() - last) *
sizeof(
T));
1248 std::memmove((iterator)first, last, (
cend() - last) *
sizeof(
T));
1253 std::make_move_iterator((iterator)last),
1254 std::make_move_iterator(
end()),
1256 auto newEnd =
impl_.
e_ - std::distance(first, last);
1261 return (iterator)
first;
1268 bool isValid(const_iterator it) {
1333 void make_window(iterator position, size_type n) {
1343 std::memmove(position + n, position, tail *
sizeof(
T));
1349 std::make_move_iterator(position),
1350 std::make_move_iterator(
impl_.
e_ - n),
1371 void wrap_frame(
T* ledge, size_type idx, size_type n) {
1372 assert(
size() >= idx);
1411 typename IsInternalFunc,
1412 typename InsertInternalFunc,
1413 typename ConstructFunc,
1414 typename DestroyFunc>
1416 const_iterator cpos,
1418 IsInternalFunc&& isInternalFunc,
1419 InsertInternalFunc&& insertInternalFunc,
1420 ConstructFunc&& constructFunc,
1421 DestroyFunc&& destroyFunc) {
1425 bool at_end = cpos ==
cend();
1428 if (!fresh && isInternalFunc()) {
1430 return insertInternalFunc();
1434 T* position =
const_cast<T*
>(cpos);
1441 b = M_allocate(newCap);
1454 constructFunc(start);
1457 M_deallocate(b, newCap);
1474 M_deallocate(b, newCap);
1489 iterator
emplace(const_iterator cpos,
Args&&... args) {
1493 [&] {
return false; },
1494 [&] {
return iterator{}; },
1495 [&](iterator
start) {
1496 M_construct(
start, std::forward<Args>(args)...);
1501 iterator
insert(const_iterator cpos,
const T& value) {
1506 [&] {
return insert(cpos,
T(value)); },
1507 [&](iterator
start) { M_construct(
start, value); },
1511 iterator
insert(const_iterator cpos,
T&& value) {
1521 iterator
insert(const_iterator cpos, size_type n, VT value) {
1526 [&] {
return insert(cpos, n,
T(value)); },
1533 class Category =
typename std::iterator_traits<It>::iterator_category>
1534 iterator
insert(const_iterator cpos, It first, It last) {
1535 return insert(cpos, first, last, Category());
1538 iterator
insert(const_iterator cpos, std::initializer_list<T> il) {
1539 return insert(cpos, il.begin(), il.end());
1545 template <
class FIt>
1547 insert(const_iterator cpos, FIt first, FIt last, std::forward_iterator_tag) {
1548 size_type n =
size_type(std::distance(first, last));
1552 [&] {
return false; },
1553 [&] {
return iterator{}; },
1558 template <
class IIt>
1560 insert(const_iterator cpos, IIt first, IIt last, std::input_iterator_tag) {
1561 T* position =
const_cast<T*
>(cpos);
1563 size_type idx = std::distance(
begin(), position);
1566 std::make_move_iterator(position),
1567 std::make_move_iterator(
end()),
1568 A::select_on_container_copy_construction(
impl_));
1570 for (; first != last; ++
first) {
1575 std::make_move_iterator(storage.begin()),
1576 std::make_move_iterator(storage.end()));
1585 return size() == other.size() && std::equal(
begin(),
end(), other.begin());
1589 return !(*
this == other);
1593 return std::lexicographical_compare(
1594 begin(),
end(), other.begin(), other.end());
1598 return other < *
this;
1602 return !(*
this > other);
1606 return !(*
this < other);
1613 template <
class _T,
class _A>
1616 template <
class _T,
class _A>
1625 template <
typename T,
typename Allocator>
1643 size_type upper = byte_sz;
1644 size_type extra = upper - lower;
1649 if ((actual =
xallocx(p, lower, extra, 0)) >= lower) {
1651 M_construct(
impl_.
e_, std::forward<Args>(args)...);
1658 size_type sz = byte_sz /
sizeof(
T);
1659 auto newB = M_allocate(sz);
1660 auto newE = newB +
size();
1669 M_construct(newE, std::forward<Args>(args)...);
1672 M_construct(newE, std::forward<Args>(args)...);
1677 M_destroy(newE - 1);
1682 M_deallocate(newB, sz);
1686 M_deallocate(
impl_.
b_, size());
1697 template <
class T,
class A>
1709 template <
class T,
class A>
1715 template <
class T,
class A>
1744 template <
class T,
class A>
1747 v.impl_.b_ = v.impl_.e_ = v.impl_.z_ =
nullptr;
1751 template <
class T,
class A>
1753 assert(v.data() ==
nullptr);
1755 v.impl_.e_ = data + sz;
1756 v.impl_.z_ = data + cap;
static void S_uninitialized_fill_n_a(Allocator &a, T *dest, size_type sz, Args &&...args)
static void S_destroy_range_a(Allocator &a, T *first, T *last) noexcept
size_type computeInsertCapacity(size_type n)
static void S_destroy_range(T *first, T *last) noexcept
iterator erase(const_iterator position)
void set(pointer newB, size_type newSize, size_type newCap)
void * checkedMalloc(size_t size)
folly::fbvector::Impl impl_
void undo_window(iterator position, size_type n) noexcept
reverse_iterator rbegin() noexcept
friend void attach(fbvector< _T, _A > &, _T *data, size_t sz, size_t cap)
void relocate_done(T *, T *first, T *last) noexcept
iterator do_real_insert(const_iterator cpos, size_type n, IsInternalFunc &&isInternalFunc, InsertInternalFunc &&insertInternalFunc, ConstructFunc &&constructFunc, DestroyFunc &&destroyFunc)
T * D_allocate(size_type n)
bool usingJEMalloc() noexcept
bool dataIsInternal(const T &t)
bool operator<=(const fbvector &other) const
#define FOLLY_FBV_UNROLL_PTR(first, last, OP)
constexpr detail::Map< Move > move
void assign(It first, It last)
static void swap(Impl &a, Impl &b)
bool isValid(const_iterator it)
void reserve(size_type n)
allocator_type get_allocator() const noexcept
bool insert_use_fresh(bool at_end, size_type n)
void M_destroy_range_e(T *pos) noexcept
internal::ArgsMatcher< InnerMatcher > Args(const InnerMatcher &matcher)
—— Concurrent Priority Queue Implementation ——
bool_constant< (std::is_nothrow_move_constructible< HTTPHeaderCode >::value &&usingStdAllocator::value)||!std::is_copy_constructible< HTTPHeaderCode >::value > relocate_use_move
void M_uninitialized_fill_n_e(size_type sz)
requires E e noexcept(noexcept(s.error(std::move(e))))
const_reverse_iterator crend() const noexcept
iterator begin() noexcept
bool operator>=(const fbvector &other) const
void D_uninitialized_fill_n_a(T *dest, size_type sz)
static const size_t jemallocMinInPlaceExpandable
void D_uninitialized_copy_a(T *dest, It first, It last)
bool_constant< true > true_type
FOLLY_PUSH_WARNING RHS rhs
void relocate_undo(T *dest, T *first, T *last) noexcept
Impl(const Allocator &alloc)
void push_back(const T &value)
fbvector & operator=(const fbvector &other)
size_t(* xallocx)(void *, size_t, size_t, int)
constexpr std::decay< T >::type copy(T &&value) noexcept(noexcept(typename std::decay< T >::type(std::forward< T >(value))))
void emplace_back_aux(Args &&...args)
bool dataIsInternalAndNotVT(const T &t)
std::integral_constant< bool, B > bool_constant
void relocate_move_or_memcpy(T *dest, T *first, T *last, std::true_type)
bool operator==(const fbvector &other) const
static void S_uninitialized_fill_n(T *dest, size_type n)
static void S_uninitialized_copy_a(Allocator &a, T *dest, It first, It last)
void M_uninitialized_copy_e(It first, It last)
static void S_uninitialized_copy(T *dest, It first, It last)
void swapData(Impl &other)
bool operator!=(const fbvector &other) const
Impl(size_type n, const Allocator &alloc=Allocator())
void relocate_move_or_copy(T *dest, T *first, T *last, std::true_type)
size_type max_size() const noexcept
std::is_trivially_copyable< T > is_trivially_copyable
void moveFrom(fbvector &&other, std::true_type)
void wrap_frame(T *ledge, size_type idx, size_type n)
void shrink_to_fit() noexcept
const_iterator cbegin() const noexcept
void D_deallocate(T *p, size_type n) noexcept
static const char *const value
void emplace_back(Args &&...args)
bool_constant< folly::IsRelocatable< T >::value &&usingStdAllocator::value > relocate_use_memcpy
iterator emplace(const_iterator cpos, Args &&...args)
std::allocator_traits< Allocator > A
void compactResize(fbvector< T, A > *v, size_t sz)
std::reverse_iterator< const_iterator > const_reverse_iterator
size_type computePushBackCapacity() const
bool reserve_in_place(size_type n)
void M_uninitialized_move_e(It first, It last)
bool empty() const noexcept
size_type capacity() const noexcept
const value_type & const_reference
A::const_pointer const_pointer
const_iterator cend() const noexcept
static void S_uninitialized_copy_bits(T *dest, const T *first, const T *last)
uint64_t value(const typename LockFreeRingBuffer< T, Atom >::Cursor &rbcursor)
bool_constant< false > false_type
bool operator>(const fbvector &other) const
void D_uninitialized_move_a(T *dest, It first, It last)
void reset(size_type newCap)
friend _T * relinquish(fbvector< _T, _A > &)
reverse_iterator rend() noexcept
const_reference at(size_type n) const
reference operator[](size_type n)
void D_destroy_range_a(T *first, T *last) noexcept
void make_window(iterator position, size_type n)
std::reverse_iterator< iterator > reverse_iterator
size_type size() const noexcept
std::make_signed< size_type >::type difference_type
iterator insert(const_iterator cpos, const T &value)
void relocate_move(T *dest, T *first, T *last)
Impl(Impl &&other) noexcept
bool operator<(const fbvector &other) const
static It S_copy_n(T *dest, It first, size_type n)
constexpr detail::First first
void swap(fbvector< T, A > &lhs, fbvector< T, A > &rhs) noexcept
size_t goodMallocSize(size_t minSize) noexcept
const_reverse_iterator crbegin() const noexcept