aboutsummaryrefslogtreecommitdiff
path: root/libcxx/include
diff options
context:
space:
mode:
Diffstat (limited to 'libcxx/include')
-rw-r--r--libcxx/include/__algorithm/for_each.h6
-rw-r--r--libcxx/include/__algorithm/generate_n.h13
-rw-r--r--libcxx/include/__compare/strong_order.h42
-rw-r--r--libcxx/include/__cxx03/__algorithm/count.h10
-rw-r--r--libcxx/include/__cxx03/__algorithm/for_each.h6
-rw-r--r--libcxx/include/__cxx03/__bit/popcount.h12
-rw-r--r--libcxx/include/__hash_table100
7 files changed, 102 insertions, 87 deletions
diff --git a/libcxx/include/__algorithm/for_each.h b/libcxx/include/__algorithm/for_each.h
index e31fcae..6fb66d2 100644
--- a/libcxx/include/__algorithm/for_each.h
+++ b/libcxx/include/__algorithm/for_each.h
@@ -16,15 +16,11 @@
#include <__iterator/segmented_iterator.h>
#include <__type_traits/enable_if.h>
#include <__type_traits/invoke.h>
-#include <__utility/move.h>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header
#endif
-_LIBCPP_PUSH_MACROS
-#include <__undef_macros>
-
_LIBCPP_BEGIN_NAMESPACE_STD
template <class _InputIterator, class _Sent, class _Func, class _Proj>
@@ -60,6 +56,4 @@ for_each(_InputIterator __first, _InputIterator __last, _Func __f) {
_LIBCPP_END_NAMESPACE_STD
-_LIBCPP_POP_MACROS
-
#endif // _LIBCPP___ALGORITHM_FOR_EACH_H
diff --git a/libcxx/include/__algorithm/generate_n.h b/libcxx/include/__algorithm/generate_n.h
index f36403f..e9da133 100644
--- a/libcxx/include/__algorithm/generate_n.h
+++ b/libcxx/include/__algorithm/generate_n.h
@@ -9,8 +9,10 @@
#ifndef _LIBCPP___ALGORITHM_GENERATE_N_H
#define _LIBCPP___ALGORITHM_GENERATE_N_H
+#include <__algorithm/for_each_n.h>
#include <__config>
-#include <__utility/convert_to_integral.h>
+#include <__functional/identity.h>
+#include <__utility/forward.h>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header
@@ -21,11 +23,10 @@ _LIBCPP_BEGIN_NAMESPACE_STD
template <class _OutputIterator, class _Size, class _Generator>
inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen) {
- typedef decltype(std::__convert_to_integral(__orig_n)) _IntegralSize;
- _IntegralSize __n = __orig_n;
- for (; __n > 0; ++__first, (void)--__n)
- *__first = __gen();
- return __first;
+ using __iter_ref = decltype(*__first);
+ __identity __proj;
+ auto __f = [&](__iter_ref __element) { std::forward<__iter_ref>(__element) = __gen(); };
+ return std::__for_each_n(__first, __orig_n, __f, __proj);
}
_LIBCPP_END_NAMESPACE_STD
diff --git a/libcxx/include/__compare/strong_order.h b/libcxx/include/__compare/strong_order.h
index 8c363b5..ba6de44 100644
--- a/libcxx/include/__compare/strong_order.h
+++ b/libcxx/include/__compare/strong_order.h
@@ -13,7 +13,6 @@
#include <__compare/compare_three_way.h>
#include <__compare/ordering.h>
#include <__config>
-#include <__math/exponential_functions.h>
#include <__math/traits.h>
#include <__type_traits/conditional.h>
#include <__type_traits/decay.h>
@@ -53,38 +52,21 @@ struct __fn {
template <class _Tp, class _Up, class _Dp = decay_t<_Tp>>
requires is_same_v<_Dp, decay_t<_Up>> && is_floating_point_v<_Dp>
_LIBCPP_HIDE_FROM_ABI static constexpr strong_ordering __go(_Tp&& __t, _Up&& __u, __priority_tag<1>) noexcept {
- if constexpr (numeric_limits<_Dp>::is_iec559 && sizeof(_Dp) == sizeof(int32_t)) {
- int32_t __rx = std::bit_cast<int32_t>(__t);
- int32_t __ry = std::bit_cast<int32_t>(__u);
- __rx = (__rx < 0) ? (numeric_limits<int32_t>::min() - __rx - 1) : __rx;
- __ry = (__ry < 0) ? (numeric_limits<int32_t>::min() - __ry - 1) : __ry;
- return (__rx <=> __ry);
- } else if constexpr (numeric_limits<_Dp>::is_iec559 && sizeof(_Dp) == sizeof(int64_t)) {
- int64_t __rx = std::bit_cast<int64_t>(__t);
- int64_t __ry = std::bit_cast<int64_t>(__u);
- __rx = (__rx < 0) ? (numeric_limits<int64_t>::min() - __rx - 1) : __rx;
- __ry = (__ry < 0) ? (numeric_limits<int64_t>::min() - __ry - 1) : __ry;
+ if constexpr (numeric_limits<_Dp>::is_iec559 &&
+ (sizeof(_Dp) == sizeof(int32_t) || sizeof(_Dp) == sizeof(int64_t))) {
+ using _IntT = conditional_t<sizeof(_Dp) == sizeof(int32_t), int32_t, int64_t>;
+ _IntT __rx = std::bit_cast<_IntT>(__t);
+ _IntT __ry = std::bit_cast<_IntT>(__u);
+ __rx = (__rx < 0) ? (numeric_limits<_IntT>::min() - __rx - 1) : __rx;
+ __ry = (__ry < 0) ? (numeric_limits<_IntT>::min() - __ry - 1) : __ry;
return (__rx <=> __ry);
} else if (__t < __u) {
return strong_ordering::less;
} else if (__t > __u) {
return strong_ordering::greater;
} else if (__t == __u) {
- if constexpr (numeric_limits<_Dp>::radix == 2) {
- return __math::signbit(__u) <=> __math::signbit(__t);
- } else {
- // This is bullet 3 of the IEEE754 algorithm, relevant
- // only for decimal floating-point;
- // see https://stackoverflow.com/questions/69068075/
- if (__t == 0 || __math::isinf(__t)) {
- return __math::signbit(__u) <=> __math::signbit(__t);
- } else {
- int __texp, __uexp;
- (void)__math::frexp(__t, &__texp);
- (void)__math::frexp(__u, &__uexp);
- return (__t < 0) ? (__texp <=> __uexp) : (__uexp <=> __texp);
- }
- }
+ static_assert(numeric_limits<_Dp>::radix == 2, "floating point type with a radix other than 2?");
+ return __math::signbit(__u) <=> __math::signbit(__t);
} else {
// They're unordered, so one of them must be a NAN.
// The order is -QNAN, -SNAN, numbers, +SNAN, +QNAN.
@@ -93,9 +75,9 @@ struct __fn {
bool __t_is_negative = __math::signbit(__t);
bool __u_is_negative = __math::signbit(__u);
using _IntType =
- conditional_t< sizeof(__t) == sizeof(int32_t),
- int32_t,
- conditional_t< sizeof(__t) == sizeof(int64_t), int64_t, void> >;
+ conditional_t<sizeof(__t) == sizeof(int32_t),
+ int32_t,
+ conditional_t<sizeof(__t) == sizeof(int64_t), int64_t, void>>;
if constexpr (is_same_v<_IntType, void>) {
static_assert(sizeof(_Dp) == 0, "std::strong_order is unimplemented for this floating-point type");
} else if (__t_is_nan && __u_is_nan) {
diff --git a/libcxx/include/__cxx03/__algorithm/count.h b/libcxx/include/__cxx03/__algorithm/count.h
index 5440fd0..5b05b4b 100644
--- a/libcxx/include/__cxx03/__algorithm/count.h
+++ b/libcxx/include/__cxx03/__algorithm/count.h
@@ -54,18 +54,18 @@ __count_bool(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
if (__first.__ctz_ != 0) {
__storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
__storage_type __dn = std::min(__clz_f, __n);
- __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
- __r = std::__libcpp_popcount(std::__invert_if<!_ToCount>(*__first.__seg_) & __m);
+ __storage_type __m = (__storage_type(~0) << __first.__ctz_) & (__storage_type(~0) >> (__clz_f - __dn));
+ __r = std::__libcpp_popcount<__storage_type>(std::__invert_if<!_ToCount>(*__first.__seg_) & __m);
__n -= __dn;
++__first.__seg_;
}
// do middle whole words
for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
- __r += std::__libcpp_popcount(std::__invert_if<!_ToCount>(*__first.__seg_));
+ __r += std::__libcpp_popcount<__storage_type>(std::__invert_if<!_ToCount>(*__first.__seg_));
// do last partial word
if (__n > 0) {
- __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
- __r += std::__libcpp_popcount(std::__invert_if<!_ToCount>(*__first.__seg_) & __m);
+ __storage_type __m = __storage_type(~0) >> (__bits_per_word - __n);
+ __r += std::__libcpp_popcount<__storage_type>(std::__invert_if<!_ToCount>(*__first.__seg_) & __m);
}
return __r;
}
diff --git a/libcxx/include/__cxx03/__algorithm/for_each.h b/libcxx/include/__cxx03/__algorithm/for_each.h
index d160a9e..1ffb013 100644
--- a/libcxx/include/__cxx03/__algorithm/for_each.h
+++ b/libcxx/include/__cxx03/__algorithm/for_each.h
@@ -14,15 +14,11 @@
#include <__cxx03/__config>
#include <__cxx03/__iterator/segmented_iterator.h>
#include <__cxx03/__type_traits/enable_if.h>
-#include <__cxx03/__utility/move.h>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header
#endif
-_LIBCPP_PUSH_MACROS
-#include <__cxx03/__undef_macros>
-
_LIBCPP_BEGIN_NAMESPACE_STD
template <class _InputIterator, class _Function>
@@ -34,6 +30,4 @@ _LIBCPP_HIDE_FROM_ABI _Function for_each(_InputIterator __first, _InputIterator
_LIBCPP_END_NAMESPACE_STD
-_LIBCPP_POP_MACROS
-
#endif // _LIBCPP___CXX03___ALGORITHM_FOR_EACH_H
diff --git a/libcxx/include/__cxx03/__bit/popcount.h b/libcxx/include/__cxx03/__bit/popcount.h
index 64404d2..a61a921 100644
--- a/libcxx/include/__cxx03/__bit/popcount.h
+++ b/libcxx/include/__cxx03/__bit/popcount.h
@@ -6,9 +6,6 @@
//
//===----------------------------------------------------------------------===//
-// TODO: __builtin_popcountg is available since Clang 19 and GCC 14. When support for older versions is dropped, we can
-// refactor this code to exclusively use __builtin_popcountg.
-
#ifndef _LIBCPP___CXX03___BIT_POPCOUNT_H
#define _LIBCPP___CXX03___BIT_POPCOUNT_H
@@ -25,12 +22,9 @@ _LIBCPP_PUSH_MACROS
_LIBCPP_BEGIN_NAMESPACE_STD
-inline _LIBCPP_HIDE_FROM_ABI int __libcpp_popcount(unsigned __x) _NOEXCEPT { return __builtin_popcount(__x); }
-
-inline _LIBCPP_HIDE_FROM_ABI int __libcpp_popcount(unsigned long __x) _NOEXCEPT { return __builtin_popcountl(__x); }
-
-inline _LIBCPP_HIDE_FROM_ABI int __libcpp_popcount(unsigned long long __x) _NOEXCEPT {
- return __builtin_popcountll(__x);
+template <class _Tp>
+_LIBCPP_HIDE_FROM_ABI int __libcpp_popcount(_Tp __v) {
+ return __builtin_popcountg(__v);
}
_LIBCPP_END_NAMESPACE_STD
diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table
index 6b65e73..5432abb 100644
--- a/libcxx/include/__hash_table
+++ b/libcxx/include/__hash_table
@@ -1037,7 +1037,21 @@ private:
}
_LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
- _LIBCPP_HIDE_FROM_ABI void __deallocate_node(__next_pointer __np) _NOEXCEPT;
+ _LIBCPP_HIDE_FROM_ABI void __deallocate_node(__node_pointer __nd) _NOEXCEPT {
+ auto& __alloc = __node_alloc();
+ __node_traits::destroy(__alloc, std::addressof(__nd->__get_value()));
+ std::__destroy_at(std::__to_address(__nd));
+ __node_traits::deallocate(__alloc, __nd, 1);
+ }
+
+ _LIBCPP_HIDE_FROM_ABI void __deallocate_node_list(__next_pointer __np) _NOEXCEPT {
+ while (__np != nullptr) {
+ __next_pointer __next = __np->__next_;
+ __deallocate_node(__np->__upcast());
+ __np = __next;
+ }
+ }
+
_LIBCPP_HIDE_FROM_ABI __next_pointer __detach() _NOEXCEPT;
template <class _From, class _ValueT = _Tp, __enable_if_t<__is_hash_value_type<_ValueT>::value, int> = 0>
@@ -1175,7 +1189,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() {
static_assert(is_copy_constructible<hasher>::value, "Hasher must be copy-constructible.");
#endif
- __deallocate_node(__first_node_.__next_);
+ __deallocate_node_list(__first_node_.__next_);
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
@@ -1251,7 +1265,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __other)
// At this point we either have consumed the whole incoming hash table, or we don't have any more nodes to reuse in
// the destination. Either continue with constructing new nodes, or deallocate the left over nodes.
if (__own_iter->__next_) {
- __deallocate_node(__own_iter->__next_);
+ __deallocate_node_list(__own_iter->__next_);
__own_iter->__next_ = nullptr;
} else {
__copy_construct(__other_iter, __own_iter, __current_chash);
@@ -1263,19 +1277,6 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __other)
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
-void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np) _NOEXCEPT {
- __node_allocator& __na = __node_alloc();
- while (__np != nullptr) {
- __next_pointer __next = __np->__next_;
- __node_pointer __real_np = __np->__upcast();
- __node_traits::destroy(__na, std::addressof(__real_np->__get_value()));
- std::__destroy_at(std::addressof(*__real_np));
- __node_traits::deallocate(__na, __real_np, 1);
- __np = __next;
- }
-}
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT {
size_type __bc = bucket_count();
@@ -1318,7 +1319,7 @@ void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(__hash_table& __u,
max_load_factor() = __u.max_load_factor();
if (bucket_count() != 0) {
__next_pointer __cache = __detach();
- auto __guard = std::__make_scope_guard([&] { __deallocate_node(__cache); });
+ auto __guard = std::__make_scope_guard([&] { __deallocate_node_list(__cache); });
const_iterator __i = __u.begin();
while (__cache != nullptr && __u.size() != 0) {
__assign_value(__cache->__upcast()->__get_value(), std::move(__u.remove(__i++)->__get_value()));
@@ -1353,7 +1354,7 @@ void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __
if (bucket_count() != 0) {
__next_pointer __cache = __detach();
- auto __guard = std::__make_scope_guard([&] { __deallocate_node(__cache); });
+ auto __guard = std::__make_scope_guard([&] { __deallocate_node_list(__cache); });
for (; __cache != nullptr && __first != __last; ++__first) {
__assign_value(__cache->__upcast()->__get_value(), *__first);
__next_pointer __next = __cache->__next_;
@@ -1374,7 +1375,7 @@ void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __f
"__assign_multi may only be called with the containers value type or the nodes value type");
if (bucket_count() != 0) {
__next_pointer __cache = __detach();
- auto __guard = std::__make_scope_guard([&] { __deallocate_node(__cache); });
+ auto __guard = std::__make_scope_guard([&] { __deallocate_node_list(__cache); });
for (; __cache != nullptr && __first != __last; ++__first) {
__assign_value(__cache->__upcast()->__get_value(), *__first);
__next_pointer __next = __cache->__next_;
@@ -1413,7 +1414,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT {
template <class _Tp, class _Hash, class _Equal, class _Alloc>
void __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT {
if (size() > 0) {
- __deallocate_node(__first_node_.__next_);
+ __deallocate_node_list(__first_node_.__next_);
__first_node_.__next_ = nullptr;
size_type __bc = bucket_count();
for (size_type __i = 0; __i < __bc; ++__i)
@@ -1873,12 +1874,61 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) {
template <class _Tp, class _Hash, class _Equal, class _Alloc>
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, const_iterator __last) {
- for (const_iterator __p = __first; __first != __last; __p = __first) {
- ++__first;
- erase(__p);
+ if (__first == __last)
+ return iterator(__last.__node_);
+
+ // current node
+ __next_pointer __current = __first.__node_;
+ size_type __bucket_count = bucket_count();
+ size_t __chash = std::__constrain_hash(__current->__hash(), __bucket_count);
+ // find previous node
+ __next_pointer __before_first = __bucket_list_[__chash];
+ for (; __before_first->__next_ != __current; __before_first = __before_first->__next_)
+ ;
+
+ __next_pointer __last_node = __last.__node_;
+
+ // If __before_first is in the same bucket (i.e. the first element we erase is not the first in the bucket), clear
+ // this bucket first without re-linking it
+ if (__before_first != __first_node_.__ptr() &&
+ std::__constrain_hash(__before_first->__hash(), __bucket_count) == __chash) {
+ while (__current != __last_node) {
+ auto __next = __current->__next_;
+ __deallocate_node(__current->__upcast());
+ __current = __next;
+ --__size_;
+
+ if (__next) {
+ if (auto __next_chash = std::__constrain_hash(__next->__hash(), __bucket_count); __next_chash != __chash) {
+ __bucket_list_[__next_chash] = __before_first;
+ __chash = __next_chash;
+ break;
+ }
+ }
+ }
+ }
+
+ while (__current != __last_node) {
+ auto __next = __current->__next_;
+ __deallocate_node(__current->__upcast());
+ __current = __next;
+ --__size_;
+
+ // When switching buckets, set the old bucket to be empty and update the next bucket to have __before_first as its
+ // before-first element
+ if (__next) {
+ if (auto __next_chash = std::__constrain_hash(__next->__hash(), __bucket_count); __next_chash != __chash) {
+ __bucket_list_[__chash] = nullptr;
+ __bucket_list_[__next_chash] = __before_first;
+ __chash = __next_chash;
+ }
+ }
}
- __next_pointer __np = __last.__node_;
- return iterator(__np);
+
+ // re-link __before_first with __last
+ __before_first->__next_ = __current;
+
+ return iterator(__last.__node_);
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
generated by cgit v1.1 at 2025-10-23 14:14:44 +0000