diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 66a1747..b603864 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake
@@ -13,6 +13,8 @@ "base/dynamic_annotations.h" "base/fast_type_id.h" "base/internal/atomic_hook.h" + "base/internal/cpu_detect.cc" + "base/internal/cpu_detect.h" "base/internal/cycleclock.cc" "base/internal/cycleclock.h" "base/internal/cycleclock_config.h" @@ -105,8 +107,6 @@ "container/node_hash_set.h" "crc/crc32c.cc" "crc/crc32c.h" - "crc/internal/cpu_detect.cc" - "crc/internal/cpu_detect.h" "crc/internal/crc.cc" "crc/internal/crc.h" "crc/internal/crc32_x86_arm_combined_simd.h"
diff --git a/absl/algorithm/algorithm.h b/absl/algorithm/algorithm.h index 4e2ebf4..0b75908 100644 --- a/absl/algorithm/algorithm.h +++ b/absl/algorithm/algorithm.h
@@ -85,8 +85,8 @@ // n = (`last` - `first`) comparisons. A linear search over short containers // may be faster than a binary search, even when the container is sorted. template <typename InputIterator, typename EqualityComparable> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool linear_search( - InputIterator first, InputIterator last, const EqualityComparable& value) { +constexpr bool linear_search(InputIterator first, InputIterator last, + const EqualityComparable& value) { return std::find(first, last, value) != last; }
diff --git a/absl/algorithm/container.h b/absl/algorithm/container.h index c0934f7..3361e71 100644 --- a/absl/algorithm/container.h +++ b/absl/algorithm/container.h
@@ -99,21 +99,20 @@ // These are meant for internal use only. template <typename C> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX17 ContainerIter<C> c_begin(C& c) { +constexpr ContainerIter<C> c_begin(C& c) { return begin(c); } template <typename C> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX17 ContainerIter<C> c_end(C& c) { +constexpr ContainerIter<C> c_end(C& c) { return end(c); } // Helper to check that the `OutputRange` has enough space. // Only performs the check if the iterators are ForwardIterators or better. template <typename InputSequence, typename Size, typename OutputRange> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX17 void AssertCopyNSize(InputSequence& input, - Size n, - OutputRange& output) { +constexpr void AssertCopyNSize(InputSequence& input, Size n, + OutputRange& output) { using InputIter = ContainerIter<InputSequence>; using OutputIter = ContainerIter<OutputRange>; @@ -130,8 +129,7 @@ } template <typename InputSequence, typename OutputRange> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX17 void AssertCopySize(InputSequence& input, - OutputRange& output) { +constexpr void AssertCopySize(InputSequence& input, OutputRange& output) { using InputIter = ContainerIter<InputSequence>; using OutputIter = ContainerIter<OutputRange>; if constexpr (base_internal::IsAtLeastForwardIterator<InputIter>::value && @@ -176,6 +174,25 @@ struct IsIterator< Iter, std::void_t<typename std::iterator_traits<Iter>::iterator_category>> : std::true_type {}; + +template <typename C, typename OutputIterator> +using ResultOfRangeToIteratorTransfer = + std::enable_if_t<container_algorithm_internal::IsIterator< + absl::remove_cvref_t<OutputIterator>>::value && + !container_algorithm_internal::IsMultidimensionalArray< + std::remove_reference_t<C>>::value, + std::decay_t<OutputIterator>>; + +template <typename C, typename OutputRange> +using ResultOfRangeToRangeTransfer = + std::enable_if_t<container_algorithm_internal::HasBeginEnd< + std::add_lvalue_reference_t<OutputRange>>::value && + !container_algorithm_internal::IsMultidimensionalArray< + std::remove_reference_t<OutputRange>>::value && + !container_algorithm_internal::IsMultidimensionalArray< + std::remove_reference_t<C>>::value, + void>; + } // namespace container_algorithm_internal // PUBLIC API @@ -191,8 +208,7 @@ // // For a generalization that uses a predicate, see absl::c_any_of(). template <typename C, typename EqualityComparable> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_linear_search( - const C& c, EqualityComparable&& value) { +constexpr bool c_linear_search(const C& c, EqualityComparable&& value) { return absl::linear_search(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<EqualityComparable>(value)); @@ -207,9 +223,8 @@ // Container-based version of the <iterator> `std::distance()` function to // return the number of elements within a container. template <typename C> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX17 - container_algorithm_internal::ContainerDifferenceType<const C> - c_distance(const C& c) { +constexpr container_algorithm_internal::ContainerDifferenceType<const C> +c_distance(const C& c) { return std::distance(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c)); } @@ -223,7 +238,7 @@ // Container-based version of the <algorithm> `std::all_of()` function to // test if all elements within a container satisfy a condition. template <typename C, typename Pred> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_all_of(const C& c, Pred&& pred) { +constexpr bool c_all_of(const C& c, Pred&& pred) { return std::all_of(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<Pred>(pred)); @@ -234,7 +249,7 @@ // Container-based version of the <algorithm> `std::any_of()` function to // test if any element in a container fulfills a condition. template <typename C, typename Pred> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_any_of(const C& c, Pred&& pred) { +constexpr bool c_any_of(const C& c, Pred&& pred) { return std::any_of(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<Pred>(pred)); @@ -245,7 +260,7 @@ // Container-based version of the <algorithm> `std::none_of()` function to // test if no elements in a container fulfill a condition. template <typename C, typename Pred> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_none_of(const C& c, Pred&& pred) { +constexpr bool c_none_of(const C& c, Pred&& pred) { return std::none_of(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<Pred>(pred)); @@ -256,8 +271,7 @@ // Container-based version of the <algorithm> `std::for_each()` function to // apply a function to a container's elements. template <typename C, typename Function> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 std::decay_t<Function> c_for_each( - C&& c, Function&& f) { +constexpr std::decay_t<Function> c_for_each(C&& c, Function&& f) { return std::for_each(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<Function>(f)); @@ -268,9 +282,8 @@ // Container-based version of the <algorithm> `std::find()` function to find // the first element containing the passed value within a container value. template <typename C, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<C> - c_find(C& c, T&& value) { +constexpr container_algorithm_internal::ContainerIter<C> c_find(C& c, + T&& value) { return std::find(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<T>(value)); @@ -281,8 +294,7 @@ // Container-based version of the <algorithm> `std::ranges::contains()` C++23 // function to search a container for a value. template <typename Sequence, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_contains(const Sequence& sequence, - T&& value) { +constexpr bool c_contains(const Sequence& sequence, T&& value) { return absl::c_find(sequence, std::forward<T>(value)) != container_algorithm_internal::c_end(sequence); } @@ -292,9 +304,8 @@ // Container-based version of the <algorithm> `std::find_if()` function to find // the first element in a container matching the given condition. template <typename C, typename Pred> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<C> - c_find_if(C& c, Pred&& pred) { +constexpr container_algorithm_internal::ContainerIter<C> c_find_if( + C& c, Pred&& pred) { return std::find_if(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<Pred>(pred)); @@ -305,9 +316,8 @@ // Container-based version of the <algorithm> `std::find_if_not()` function to // find the first element in a container not matching the given condition. template <typename C, typename Pred> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<C> - c_find_if_not(C& c, Pred&& pred) { +constexpr container_algorithm_internal::ContainerIter<C> c_find_if_not( + C& c, Pred&& pred) { return std::find_if_not(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<Pred>(pred)); @@ -318,9 +328,8 @@ // Container-based version of the <algorithm> `std::find_end()` function to // find the last subsequence within a container. template <typename Sequence1, typename Sequence2> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<Sequence1> - c_find_end(Sequence1& sequence, Sequence2& subsequence) { +constexpr container_algorithm_internal::ContainerIter<Sequence1> c_find_end( + Sequence1& sequence, Sequence2& subsequence) { return std::find_end(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), container_algorithm_internal::c_begin(subsequence), @@ -330,10 +339,8 @@ // Overload of c_find_end() for using a predicate evaluation other than `==` as // the function's test condition. template <typename Sequence1, typename Sequence2, typename BinaryPredicate> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<Sequence1> - c_find_end(Sequence1& sequence, Sequence2& subsequence, - BinaryPredicate&& pred) { +constexpr container_algorithm_internal::ContainerIter<Sequence1> c_find_end( + Sequence1& sequence, Sequence2& subsequence, BinaryPredicate&& pred) { return std::find_end(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), container_algorithm_internal::c_begin(subsequence), @@ -347,9 +354,8 @@ // find the first element within the container that is also within the options // container. template <typename C1, typename C2> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<C1> - c_find_first_of(C1& container, const C2& options) { +constexpr container_algorithm_internal::ContainerIter<C1> c_find_first_of( + C1& container, const C2& options) { return std::find_first_of(container_algorithm_internal::c_begin(container), container_algorithm_internal::c_end(container), container_algorithm_internal::c_begin(options), @@ -359,9 +365,8 @@ // Overload of c_find_first_of() for using a predicate evaluation other than // `==` as the function's test condition. template <typename C1, typename C2, typename BinaryPredicate> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<C1> - c_find_first_of(C1& container, const C2& options, BinaryPredicate&& pred) { +constexpr container_algorithm_internal::ContainerIter<C1> c_find_first_of( + C1& container, const C2& options, BinaryPredicate&& pred) { return std::find_first_of(container_algorithm_internal::c_begin(container), container_algorithm_internal::c_end(container), container_algorithm_internal::c_begin(options), @@ -374,9 +379,8 @@ // Container-based version of the <algorithm> `std::adjacent_find()` function to // find equal adjacent elements within a container. template <typename Sequence> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<Sequence> - c_adjacent_find(Sequence& sequence) { +constexpr container_algorithm_internal::ContainerIter<Sequence> c_adjacent_find( + Sequence& sequence) { return std::adjacent_find(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence)); } @@ -384,9 +388,8 @@ // Overload of c_adjacent_find() for using a predicate evaluation other than // `==` as the function's test condition. template <typename Sequence, typename BinaryPredicate> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<Sequence> - c_adjacent_find(Sequence& sequence, BinaryPredicate&& pred) { +constexpr container_algorithm_internal::ContainerIter<Sequence> c_adjacent_find( + Sequence& sequence, BinaryPredicate&& pred) { return std::adjacent_find(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), std::forward<BinaryPredicate>(pred)); @@ -397,9 +400,8 @@ // Container-based version of the <algorithm> `std::count()` function to count // values that match within a container. template <typename C, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerDifferenceType<const C> - c_count(const C& c, T&& value) { +constexpr container_algorithm_internal::ContainerDifferenceType<const C> +c_count(const C& c, T&& value) { return std::count(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<T>(value)); @@ -410,9 +412,8 @@ // Container-based version of the <algorithm> `std::count_if()` function to // count values matching a condition within a container. template <typename C, typename Pred> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerDifferenceType<const C> - c_count_if(const C& c, Pred&& pred) { +constexpr container_algorithm_internal::ContainerDifferenceType<const C> +c_count_if(const C& c, Pred&& pred) { return std::count_if(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<Pred>(pred)); @@ -424,9 +425,8 @@ // return the first element where two ordered containers differ. Applies `==` to // the first N elements of `c1` and `c2`, where N = min(size(c1), size(c2)). template <typename C1, typename C2> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIterPairType<C1, C2> - c_mismatch(C1& c1, C2& c2) { +constexpr container_algorithm_internal::ContainerIterPairType<C1, C2> +c_mismatch(C1& c1, C2& c2) { return std::mismatch(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -437,9 +437,8 @@ // the function's test condition. Applies `pred`to the first N elements of `c1` // and `c2`, where N = min(size(c1), size(c2)). template <typename C1, typename C2, typename BinaryPredicate> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIterPairType<C1, C2> - c_mismatch(C1& c1, C2& c2, BinaryPredicate pred) { +constexpr container_algorithm_internal::ContainerIterPairType<C1, C2> +c_mismatch(C1& c1, C2& c2, BinaryPredicate pred) { return std::mismatch(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -451,7 +450,7 @@ // Container-based version of the <algorithm> `std::equal()` function to // test whether two containers are equal. template <typename C1, typename C2> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_equal(const C1& c1, const C2& c2) { +constexpr bool c_equal(const C1& c1, const C2& c2) { return std::equal(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -461,8 +460,7 @@ // Overload of c_equal() for using a predicate evaluation other than `==` as // the function's test condition. template <typename C1, typename C2, typename BinaryPredicate> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_equal(const C1& c1, const C2& c2, - BinaryPredicate&& pred) { +constexpr bool c_equal(const C1& c1, const C2& c2, BinaryPredicate&& pred) { return std::equal(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -475,8 +473,7 @@ // Container-based version of the <algorithm> `std::is_permutation()` function // to test whether a container is a permutation of another. template <typename C1, typename C2> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_is_permutation(const C1& c1, - const C2& c2) { +constexpr bool c_is_permutation(const C1& c1, const C2& c2) { return std::is_permutation(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -486,8 +483,8 @@ // Overload of c_is_permutation() for using a predicate evaluation other than // `==` as the function's test condition. template <typename C1, typename C2, typename BinaryPredicate> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_is_permutation( - const C1& c1, const C2& c2, BinaryPredicate&& pred) { +constexpr bool c_is_permutation(const C1& c1, const C2& c2, + BinaryPredicate&& pred) { return std::is_permutation(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -500,9 +497,8 @@ // Container-based version of the <algorithm> `std::search()` function to search // a container for a subsequence. template <typename Sequence1, typename Sequence2> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<Sequence1> - c_search(Sequence1& sequence, Sequence2& subsequence) { +constexpr container_algorithm_internal::ContainerIter<Sequence1> c_search( + Sequence1& sequence, Sequence2& subsequence) { return std::search(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), container_algorithm_internal::c_begin(subsequence), @@ -512,10 +508,8 @@ // Overload of c_search() for using a predicate evaluation other than // `==` as the function's test condition. template <typename Sequence1, typename Sequence2, typename BinaryPredicate> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<Sequence1> - c_search(Sequence1& sequence, Sequence2& subsequence, - BinaryPredicate&& pred) { +constexpr container_algorithm_internal::ContainerIter<Sequence1> c_search( + Sequence1& sequence, Sequence2& subsequence, BinaryPredicate&& pred) { return std::search(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), container_algorithm_internal::c_begin(subsequence), @@ -528,8 +522,8 @@ // Container-based version of the <algorithm> `std::ranges::contains_subrange()` // C++23 function to search a container for a subsequence. template <typename Sequence1, typename Sequence2> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_contains_subrange( - Sequence1& sequence, Sequence2& subsequence) { +constexpr bool c_contains_subrange(Sequence1& sequence, + Sequence2& subsequence) { return absl::c_search(sequence, subsequence) != container_algorithm_internal::c_end(sequence); } @@ -537,8 +531,8 @@ // Overload of c_contains_subrange() for using a predicate evaluation other than // `==` as the function's test condition. template <typename Sequence1, typename Sequence2, typename BinaryPredicate> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_contains_subrange( - Sequence1& sequence, Sequence2& subsequence, BinaryPredicate&& pred) { +constexpr bool c_contains_subrange(Sequence1& sequence, Sequence2& subsequence, + BinaryPredicate&& pred) { return absl::c_search(sequence, subsequence, std::forward<BinaryPredicate>(pred)) != container_algorithm_internal::c_end(sequence); @@ -549,9 +543,8 @@ // Container-based version of the <algorithm> `std::search_n()` function to // search a container for the first sequence of N elements. template <typename Sequence, typename Size, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<Sequence> - c_search_n(Sequence& sequence, Size count, T&& value) { +constexpr container_algorithm_internal::ContainerIter<Sequence> c_search_n( + Sequence& sequence, Size count, T&& value) { return std::search_n(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), count, std::forward<T>(value)); @@ -561,10 +554,8 @@ // `==` as the function's test condition. template <typename Sequence, typename Size, typename T, typename BinaryPredicate> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<Sequence> - c_search_n(Sequence& sequence, Size count, T&& value, - BinaryPredicate&& pred) { +constexpr container_algorithm_internal::ContainerIter<Sequence> c_search_n( + Sequence& sequence, Size count, T&& value, BinaryPredicate&& pred) { return std::search_n(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), count, std::forward<T>(value), @@ -580,13 +571,9 @@ // Container-based version of the <algorithm> `std::copy()` function to copy a // container's elements into an iterator. template <typename InputSequence, typename OutputIterator> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - std::enable_if_t<container_algorithm_internal::IsIterator< - absl::remove_cvref_t<OutputIterator>>::value && - !container_algorithm_internal::IsMultidimensionalArray< - InputSequence>::value, - std::decay_t<OutputIterator>> - c_copy(const InputSequence& input, OutputIterator&& output) { +constexpr container_algorithm_internal::ResultOfRangeToIteratorTransfer< + InputSequence, OutputIterator> +c_copy(const InputSequence& input, OutputIterator&& output) { return std::copy(container_algorithm_internal::c_begin(input), container_algorithm_internal::c_end(input), std::forward<OutputIterator>(output)); @@ -603,15 +590,9 @@ // If `std::size(output) > std::size(input)`, only `std::size(input)` elements // are copied, and `output` is not truncated. template <typename InputSequence, typename OutputRange> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - std::enable_if_t<container_algorithm_internal::HasBeginEnd< - std::add_lvalue_reference_t<OutputRange>>::value && - !container_algorithm_internal::IsMultidimensionalArray< - std::remove_reference_t<OutputRange>>::value && - !container_algorithm_internal::IsMultidimensionalArray< - InputSequence>::value, - void> - c_copy(const InputSequence& input, OutputRange&& output) { +constexpr container_algorithm_internal::ResultOfRangeToRangeTransfer< + InputSequence, OutputRange> +c_copy(const InputSequence& input, OutputRange&& output) { container_algorithm_internal::AssertCopySize(input, output); absl::c_copy(input, container_algorithm_internal::c_begin( std::forward<OutputRange>(output))); @@ -622,11 +603,8 @@ // Container-based version of the <algorithm> `std::copy_n()` function to copy a // container's first N elements into an iterator. template <typename C, typename Size, typename OutputIterator> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 std::enable_if_t< - container_algorithm_internal::IsIterator< - absl::remove_cvref_t<OutputIterator>>::value && - !container_algorithm_internal::IsMultidimensionalArray<C>::value, - std::decay_t<OutputIterator>> +constexpr container_algorithm_internal::ResultOfRangeToIteratorTransfer< + C, OutputIterator> c_copy_n(const C& input, Size n, OutputIterator&& output) { return std::copy_n(container_algorithm_internal::c_begin(input), n, std::forward<OutputIterator>(output)); @@ -644,13 +622,8 @@ // If `std::size(output) > n`, only `n` elements are copied, and `output` is not // truncated. template <typename C, typename Size, typename OutputRange> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 std::enable_if_t< - container_algorithm_internal::HasBeginEnd< - std::add_lvalue_reference_t<OutputRange>>::value && - !container_algorithm_internal::IsMultidimensionalArray< - std::remove_reference_t<OutputRange>>::value && - !container_algorithm_internal::IsMultidimensionalArray<C>::value, - void> +constexpr container_algorithm_internal::ResultOfRangeToRangeTransfer< + C, OutputRange> c_copy_n(const C& input, Size n, OutputRange&& output) { container_algorithm_internal::AssertCopyNSize(input, n, output); absl::c_copy_n( @@ -663,8 +636,8 @@ // Container-based version of the <algorithm> `std::copy_if()` function to copy // a container's elements satisfying some condition into an iterator. template <typename InputSequence, typename OutputIterator, typename Pred> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator -c_copy_if(const InputSequence& input, OutputIterator output, Pred&& pred) { +constexpr OutputIterator c_copy_if(const InputSequence& input, + OutputIterator output, Pred&& pred) { return std::copy_if(container_algorithm_internal::c_begin(input), container_algorithm_internal::c_end(input), output, std::forward<Pred>(pred)); @@ -675,8 +648,8 @@ // Container-based version of the <algorithm> `std::copy_backward()` function to // copy a container's elements in reverse order into an iterator. template <typename C, typename BidirectionalIterator> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 BidirectionalIterator -c_copy_backward(const C& src, BidirectionalIterator dest) { +constexpr BidirectionalIterator c_copy_backward(const C& src, + BidirectionalIterator dest) { return std::copy_backward(container_algorithm_internal::c_begin(src), container_algorithm_internal::c_end(src), dest); } @@ -686,13 +659,9 @@ // Container-based version of the <algorithm> `std::move()` function to move // a container's elements into an iterator. template <typename C, typename OutputIterator> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - std::enable_if_t<container_algorithm_internal::IsIterator< - absl::remove_cvref_t<OutputIterator>>::value && - !container_algorithm_internal::IsMultidimensionalArray< - std::remove_reference_t<C>>::value, - std::decay_t<OutputIterator>> - c_move(C&& src, OutputIterator&& dest) { +constexpr container_algorithm_internal::ResultOfRangeToIteratorTransfer< + C, OutputIterator> +c_move(C&& src, OutputIterator&& dest) { return std::move(container_algorithm_internal::c_begin(src), container_algorithm_internal::c_end(src), std::forward<OutputIterator>(dest)); @@ -704,15 +673,9 @@ // The `dest` container must be large enough to hold all elements of `src`; // this function does not resize `dest`. template <typename C, typename OutputRange> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - std::enable_if_t<container_algorithm_internal::HasBeginEnd< - std::add_lvalue_reference_t<OutputRange>>::value && - !container_algorithm_internal::IsMultidimensionalArray< - std::remove_reference_t<OutputRange>>::value && - !container_algorithm_internal::IsMultidimensionalArray< - std::remove_reference_t<C>>::value, - void> - c_move(C&& src, OutputRange&& dest) { +constexpr container_algorithm_internal::ResultOfRangeToRangeTransfer< + C, OutputRange> +c_move(C&& src, OutputRange&& dest) { container_algorithm_internal::AssertCopySize(src, dest); absl::c_move(std::forward<C>(src), container_algorithm_internal::c_begin( std::forward<OutputRange>(dest))); @@ -723,8 +686,8 @@ // Container-based version of the <algorithm> `std::move_backward()` function to // move a container's elements into an iterator in reverse order. template <typename C, typename BidirectionalIterator> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 BidirectionalIterator -c_move_backward(C&& src, BidirectionalIterator dest) { +constexpr BidirectionalIterator c_move_backward(C&& src, + BidirectionalIterator dest) { return std::move_backward(container_algorithm_internal::c_begin(src), container_algorithm_internal::c_end(src), dest); } @@ -735,9 +698,8 @@ // swap a container's elements with another container's elements. Swaps the // first N elements of `c1` and `c2`, where N = min(size(c1), size(c2)). template <typename C1, typename C2> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<C2> - c_swap_ranges(C1& c1, C2& c2) { +constexpr container_algorithm_internal::ContainerIter<C2> c_swap_ranges( + C1& c1, C2& c2) { auto first1 = container_algorithm_internal::c_begin(c1); auto last1 = container_algorithm_internal::c_end(c1); auto first2 = container_algorithm_internal::c_begin(c2); @@ -757,8 +719,9 @@ // result in an iterator pointing to the last transformed element in the output // range. template <typename InputSequence, typename OutputIterator, typename UnaryOp> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator c_transform( - const InputSequence& input, OutputIterator output, UnaryOp&& unary_op) { +constexpr OutputIterator c_transform(const InputSequence& input, + OutputIterator output, + UnaryOp&& unary_op) { return std::transform(container_algorithm_internal::c_begin(input), container_algorithm_internal::c_end(input), output, std::forward<UnaryOp>(unary_op)); @@ -769,9 +732,10 @@ // where N = min(size(c1), size(c2)). template <typename InputSequence1, typename InputSequence2, typename OutputIterator, typename BinaryOp> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator -c_transform(const InputSequence1& input1, const InputSequence2& input2, - OutputIterator output, BinaryOp&& binary_op) { +constexpr OutputIterator c_transform(const InputSequence1& input1, + const InputSequence2& input2, + OutputIterator output, + BinaryOp&& binary_op) { auto first1 = container_algorithm_internal::c_begin(input1); auto last1 = container_algorithm_internal::c_end(input1); auto first2 = container_algorithm_internal::c_begin(input2); @@ -790,9 +754,8 @@ // replace a container's elements of some value with a new value. The container // is modified in place. template <typename Sequence, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_replace(Sequence& sequence, - const T& old_value, - const T& new_value) { +constexpr void c_replace(Sequence& sequence, const T& old_value, + const T& new_value) { std::replace(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), old_value, new_value); @@ -804,8 +767,7 @@ // replace a container's elements of some value with a new value based on some // condition. The container is modified in place. template <typename C, typename Pred, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_replace_if(C& c, Pred&& pred, - T&& new_value) { +constexpr void c_replace_if(C& c, Pred&& pred, T&& new_value) { std::replace_if(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<Pred>(pred), std::forward<T>(new_value)); @@ -817,8 +779,8 @@ // replace a container's elements of some value with a new value and return the // results within an iterator. template <typename C, typename OutputIterator, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator c_replace_copy( - const C& c, OutputIterator result, T&& old_value, T&& new_value) { +constexpr OutputIterator c_replace_copy(const C& c, OutputIterator result, + T&& old_value, T&& new_value) { return std::replace_copy(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), result, std::forward<T>(old_value), @@ -831,8 +793,8 @@ // to replace a container's elements of some value with a new value based on // some condition, and return the results within an iterator. template <typename C, typename OutputIterator, typename Pred, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator c_replace_copy_if( - const C& c, OutputIterator result, Pred&& pred, const T& new_value) { +constexpr OutputIterator c_replace_copy_if(const C& c, OutputIterator result, + Pred&& pred, const T& new_value) { return std::replace_copy_if(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), result, std::forward<Pred>(pred), new_value); @@ -843,7 +805,7 @@ // Container-based version of the <algorithm> `std::fill()` function to fill a // container with some value. template <typename C, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_fill(C& c, const T& value) { +constexpr void c_fill(C& c, const T& value) { std::fill(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), value); } @@ -853,8 +815,7 @@ // Container-based version of the <algorithm> `std::fill_n()` function to fill // the first N elements in a container with some value. template <typename C, typename Size, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_fill_n(C& c, Size n, - const T& value) { +constexpr void c_fill_n(C& c, Size n, const T& value) { std::fill_n(container_algorithm_internal::c_begin(c), n, value); } @@ -863,7 +824,7 @@ // Container-based version of the <algorithm> `std::generate()` function to // assign a container's elements to the values provided by the given generator. template <typename C, typename Generator> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_generate(C& c, Generator&& gen) { +constexpr void c_generate(C& c, Generator&& gen) { std::generate(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<Generator>(gen)); @@ -875,9 +836,8 @@ // assign a container's first N elements to the values provided by the given // generator. template <typename C, typename Size, typename Generator> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<C> - c_generate_n(C& c, Size n, Generator&& gen) { +constexpr container_algorithm_internal::ContainerIter<C> c_generate_n( + C& c, Size n, Generator&& gen) { return std::generate_n(container_algorithm_internal::c_begin(c), n, std::forward<Generator>(gen)); } @@ -893,8 +853,8 @@ // copy a container's elements while removing any elements matching the given // `value`. template <typename C, typename OutputIterator, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator -c_remove_copy(const C& c, OutputIterator result, const T& value) { +constexpr OutputIterator c_remove_copy(const C& c, OutputIterator result, + const T& value) { return std::remove_copy(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), result, value); @@ -906,8 +866,8 @@ // to copy a container's elements while removing any elements matching the given // condition. template <typename C, typename OutputIterator, typename Pred> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator -c_remove_copy_if(const C& c, OutputIterator result, Pred&& pred) { +constexpr OutputIterator c_remove_copy_if(const C& c, OutputIterator result, + Pred&& pred) { return std::remove_copy_if(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), result, std::forward<Pred>(pred)); @@ -919,8 +879,7 @@ // copy a container's elements while removing any elements containing duplicate // values. template <typename C, typename OutputIterator> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator -c_unique_copy(const C& c, OutputIterator result) { +constexpr OutputIterator c_unique_copy(const C& c, OutputIterator result) { return std::unique_copy(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), result); } @@ -928,8 +887,8 @@ // Overload of c_unique_copy() for using a predicate evaluation other than // `==` for comparing uniqueness of the element values. template <typename C, typename OutputIterator, typename BinaryPredicate> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator -c_unique_copy(const C& c, OutputIterator result, BinaryPredicate&& pred) { +constexpr OutputIterator c_unique_copy(const C& c, OutputIterator result, + BinaryPredicate&& pred) { return std::unique_copy(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), result, std::forward<BinaryPredicate>(pred)); @@ -940,7 +899,7 @@ // Container-based version of the <algorithm> `std::reverse()` function to // reverse a container's elements. template <typename Sequence> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_reverse(Sequence& sequence) { +constexpr void c_reverse(Sequence& sequence) { std::reverse(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence)); } @@ -950,8 +909,8 @@ // Container-based version of the <algorithm> `std::reverse()` function to // reverse a container's elements and write them to an iterator range. template <typename C, typename OutputIterator> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator -c_reverse_copy(const C& sequence, OutputIterator result) { +constexpr OutputIterator c_reverse_copy(const C& sequence, + OutputIterator result) { return std::reverse_copy(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), result); @@ -964,10 +923,9 @@ // the first element in the container. template <typename C, typename Iterator = container_algorithm_internal::ContainerIter<C>> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 Iterator c_rotate(C& sequence, - Iterator middle) { - return absl::rotate(container_algorithm_internal::c_begin(sequence), middle, - container_algorithm_internal::c_end(sequence)); +constexpr Iterator c_rotate(C& sequence, Iterator middle) { + return std::rotate(container_algorithm_internal::c_begin(sequence), middle, + container_algorithm_internal::c_end(sequence)); } // c_rotate_copy() @@ -976,10 +934,10 @@ // shift a container's elements leftward such that the `middle` element becomes // the first element in a new iterator range. template <typename C, typename OutputIterator> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator -c_rotate_copy(const C& sequence, - container_algorithm_internal::ContainerIter<const C> middle, - OutputIterator result) { +constexpr OutputIterator c_rotate_copy( + const C& sequence, + container_algorithm_internal::ContainerIter<const C> middle, + OutputIterator result) { return std::rotate_copy(container_algorithm_internal::c_begin(sequence), middle, container_algorithm_internal::c_end(sequence), result); @@ -1021,8 +979,7 @@ // to test whether all elements in the container for which `pred` returns `true` // precede those for which `pred` is `false`. template <typename C, typename Pred> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_is_partitioned(const C& c, - Pred&& pred) { +constexpr bool c_is_partitioned(const C& c, Pred&& pred) { return std::is_partitioned(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<Pred>(pred)); @@ -1035,9 +992,8 @@ // which `pred` returns `true` precede all those for which it returns `false`, // returning an iterator to the first element of the second group. template <typename C, typename Pred> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<C> - c_partition(C& c, Pred&& pred) { +constexpr container_algorithm_internal::ContainerIter<C> c_partition( + C& c, Pred&& pred) { return std::partition(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<Pred>(pred)); @@ -1066,9 +1022,9 @@ template <typename C, typename OutputIterator1, typename OutputIterator2, typename Pred> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 std::pair<OutputIterator1, OutputIterator2> -c_partition_copy(const C& c, OutputIterator1 out_true, - OutputIterator2 out_false, Pred&& pred) { +constexpr std::pair<OutputIterator1, OutputIterator2> c_partition_copy( + const C& c, OutputIterator1 out_true, OutputIterator2 out_false, + Pred&& pred) { return std::partition_copy(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), out_true, out_false, std::forward<Pred>(pred)); @@ -1080,9 +1036,8 @@ // to return the first element of an already partitioned container for which // the given `pred` is not `true`. template <typename C, typename Pred> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<C> - c_partition_point(C& c, Pred&& pred) { +constexpr container_algorithm_internal::ContainerIter<C> c_partition_point( + C& c, Pred&& pred) { return std::partition_point(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<Pred>(pred)); @@ -1097,7 +1052,7 @@ // Container-based version of the <algorithm> `std::sort()` function // to sort elements in ascending order of their values. template <typename C> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_sort(C& c) { +constexpr void c_sort(C& c) { std::sort(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c)); } @@ -1105,7 +1060,7 @@ // Overload of c_sort() for performing a `comp` comparison other than the // default `operator<`. template <typename C, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_sort(C& c, LessThan&& comp) { +constexpr void c_sort(C& c, LessThan&& comp) { std::sort(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<LessThan>(comp)); @@ -1136,7 +1091,7 @@ // Container-based version of the <algorithm> `std::is_sorted()` function // to evaluate whether the given container is sorted in ascending order. template <typename C> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_is_sorted(const C& c) { +constexpr bool c_is_sorted(const C& c) { return std::is_sorted(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c)); } @@ -1144,8 +1099,7 @@ // c_is_sorted() overload for performing a `comp` comparison other than the // default `operator<`. template <typename C, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_is_sorted(const C& c, - LessThan&& comp) { +constexpr bool c_is_sorted(const C& c, LessThan&& comp) { return std::is_sorted(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<LessThan>(comp)); @@ -1157,7 +1111,7 @@ // to rearrange elements within a container such that elements before `middle` // are sorted in ascending order. template <typename RandomAccessContainer> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_partial_sort( +constexpr void c_partial_sort( RandomAccessContainer& sequence, container_algorithm_internal::ContainerIter<RandomAccessContainer> middle) { std::partial_sort(container_algorithm_internal::c_begin(sequence), middle, @@ -1167,7 +1121,7 @@ // Overload of c_partial_sort() for performing a `comp` comparison other than // the default `operator<`. template <typename RandomAccessContainer, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_partial_sort( +constexpr void c_partial_sort( RandomAccessContainer& sequence, container_algorithm_internal::ContainerIter<RandomAccessContainer> middle, LessThan&& comp) { @@ -1184,9 +1138,8 @@ // At most min(result.last - result.first, sequence.last - sequence.first) // elements from the sequence will be stored in the result. template <typename C, typename RandomAccessContainer> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<RandomAccessContainer> - c_partial_sort_copy(const C& sequence, RandomAccessContainer& result) { +constexpr container_algorithm_internal::ContainerIter<RandomAccessContainer> +c_partial_sort_copy(const C& sequence, RandomAccessContainer& result) { return std::partial_sort_copy(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), container_algorithm_internal::c_begin(result), @@ -1196,10 +1149,9 @@ // Overload of c_partial_sort_copy() for performing a `comp` comparison other // than the default `operator<`. template <typename C, typename RandomAccessContainer, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<RandomAccessContainer> - c_partial_sort_copy(const C& sequence, RandomAccessContainer& result, - LessThan&& comp) { +constexpr container_algorithm_internal::ContainerIter<RandomAccessContainer> +c_partial_sort_copy(const C& sequence, RandomAccessContainer& result, + LessThan&& comp) { return std::partial_sort_copy(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), container_algorithm_internal::c_begin(result), @@ -1213,9 +1165,8 @@ // to return the first element within a container that is not sorted in // ascending order as an iterator. template <typename C> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<C> - c_is_sorted_until(C& c) { +constexpr container_algorithm_internal::ContainerIter<C> c_is_sorted_until( + C& c) { return std::is_sorted_until(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c)); } @@ -1223,9 +1174,8 @@ // Overload of c_is_sorted_until() for performing a `comp` comparison other than // the default `operator<`. template <typename C, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<C> - c_is_sorted_until(C& c, LessThan&& comp) { +constexpr container_algorithm_internal::ContainerIter<C> c_is_sorted_until( + C& c, LessThan&& comp) { return std::is_sorted_until(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<LessThan>(comp)); @@ -1239,7 +1189,7 @@ // any order, except that all preceding `nth` will be less than that element, // and all following `nth` will be greater than that element. template <typename RandomAccessContainer> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_nth_element( +constexpr void c_nth_element( RandomAccessContainer& sequence, container_algorithm_internal::ContainerIter<RandomAccessContainer> nth) { std::nth_element(container_algorithm_internal::c_begin(sequence), nth, @@ -1249,7 +1199,7 @@ // Overload of c_nth_element() for performing a `comp` comparison other than // the default `operator<`. template <typename RandomAccessContainer, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_nth_element( +constexpr void c_nth_element( RandomAccessContainer& sequence, container_algorithm_internal::ContainerIter<RandomAccessContainer> nth, LessThan&& comp) { @@ -1268,9 +1218,8 @@ // to return an iterator pointing to the first element in a sorted container // which does not compare less than `value`. template <typename Sequence, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<Sequence> - c_lower_bound(Sequence& sequence, const T& value) { +constexpr container_algorithm_internal::ContainerIter<Sequence> c_lower_bound( + Sequence& sequence, const T& value) { return std::lower_bound(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), value); } @@ -1278,9 +1227,8 @@ // Overload of c_lower_bound() for performing a `comp` comparison other than // the default `operator<`. template <typename Sequence, typename T, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<Sequence> - c_lower_bound(Sequence& sequence, const T& value, LessThan&& comp) { +constexpr container_algorithm_internal::ContainerIter<Sequence> c_lower_bound( + Sequence& sequence, const T& value, LessThan&& comp) { return std::lower_bound(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), value, std::forward<LessThan>(comp)); @@ -1292,9 +1240,8 @@ // to return an iterator pointing to the first element in a sorted container // which is greater than `value`. template <typename Sequence, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<Sequence> - c_upper_bound(Sequence& sequence, const T& value) { +constexpr container_algorithm_internal::ContainerIter<Sequence> c_upper_bound( + Sequence& sequence, const T& value) { return std::upper_bound(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), value); } @@ -1302,9 +1249,8 @@ // Overload of c_upper_bound() for performing a `comp` comparison other than // the default `operator<`. template <typename Sequence, typename T, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<Sequence> - c_upper_bound(Sequence& sequence, const T& value, LessThan&& comp) { +constexpr container_algorithm_internal::ContainerIter<Sequence> c_upper_bound( + Sequence& sequence, const T& value, LessThan&& comp) { return std::upper_bound(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), value, std::forward<LessThan>(comp)); @@ -1316,9 +1262,9 @@ // to return an iterator pair pointing to the first and last elements in a // sorted container which compare equal to `value`. template <typename Sequence, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIterPairType<Sequence, Sequence> - c_equal_range(Sequence& sequence, const T& value) { +constexpr container_algorithm_internal::ContainerIterPairType<Sequence, + Sequence> +c_equal_range(Sequence& sequence, const T& value) { return std::equal_range(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), value); } @@ -1326,9 +1272,9 @@ // Overload of c_equal_range() for performing a `comp` comparison other than // the default `operator<`. template <typename Sequence, typename T, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIterPairType<Sequence, Sequence> - c_equal_range(Sequence& sequence, const T& value, LessThan&& comp) { +constexpr container_algorithm_internal::ContainerIterPairType<Sequence, + Sequence> +c_equal_range(Sequence& sequence, const T& value, LessThan&& comp) { return std::equal_range(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), value, std::forward<LessThan>(comp)); @@ -1340,8 +1286,7 @@ // to test if any element in the sorted container contains a value equivalent to // 'value'. template <typename Sequence, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_binary_search( - const Sequence& sequence, const T& value) { +constexpr bool c_binary_search(const Sequence& sequence, const T& value) { return std::binary_search(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), value); @@ -1350,8 +1295,8 @@ // Overload of c_binary_search() for performing a `comp` comparison other than // the default `operator<`. template <typename Sequence, typename T, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_binary_search( - const Sequence& sequence, const T& value, LessThan&& comp) { +constexpr bool c_binary_search(const Sequence& sequence, const T& value, + LessThan&& comp) { return std::binary_search(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), value, std::forward<LessThan>(comp)); @@ -1366,8 +1311,8 @@ // Container-based version of the <algorithm> `std::merge()` function // to merge two sorted containers into a single sorted iterator. template <typename C1, typename C2, typename OutputIterator> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator -c_merge(const C1& c1, const C2& c2, OutputIterator result) { +constexpr OutputIterator c_merge(const C1& c1, const C2& c2, + OutputIterator result) { return std::merge(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -1377,8 +1322,8 @@ // Overload of c_merge() for performing a `comp` comparison other than // the default `operator<`. template <typename C1, typename C2, typename OutputIterator, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator -c_merge(const C1& c1, const C2& c2, OutputIterator result, LessThan&& comp) { +constexpr OutputIterator c_merge(const C1& c1, const C2& c2, + OutputIterator result, LessThan&& comp) { return std::merge(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -1414,8 +1359,7 @@ // to test whether a sorted container `c1` entirely contains another sorted // container `c2`. template <typename C1, typename C2> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_includes(const C1& c1, - const C2& c2) { +constexpr bool c_includes(const C1& c1, const C2& c2) { return std::includes(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -1425,8 +1369,7 @@ // Overload of c_includes() for performing a merge using a `comp` other than // `operator<`. template <typename C1, typename C2, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_includes(const C1& c1, const C2& c2, - LessThan&& comp) { +constexpr bool c_includes(const C1& c1, const C2& c2, LessThan&& comp) { return std::includes(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -1446,8 +1389,8 @@ typename = typename std::enable_if< !container_algorithm_internal::IsUnorderedContainer<C2>::value, void>::type> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator -c_set_union(const C1& c1, const C2& c2, OutputIterator output) { +constexpr OutputIterator c_set_union(const C1& c1, const C2& c2, + OutputIterator output) { return std::set_union(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -1463,8 +1406,8 @@ typename = typename std::enable_if< !container_algorithm_internal::IsUnorderedContainer<C2>::value, void>::type> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator c_set_union( - const C1& c1, const C2& c2, OutputIterator output, LessThan&& comp) { +constexpr OutputIterator c_set_union(const C1& c1, const C2& c2, + OutputIterator output, LessThan&& comp) { return std::set_union(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -1483,8 +1426,8 @@ typename = typename std::enable_if< !container_algorithm_internal::IsUnorderedContainer<C2>::value, void>::type> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator -c_set_intersection(const C1& c1, const C2& c2, OutputIterator output) { +constexpr OutputIterator c_set_intersection(const C1& c1, const C2& c2, + OutputIterator output) { // In debug builds, ensure that both containers are sorted with respect to the // default comparator. std::set_intersection requires the containers be sorted // using operator<. @@ -1505,8 +1448,9 @@ typename = typename std::enable_if< !container_algorithm_internal::IsUnorderedContainer<C2>::value, void>::type> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator c_set_intersection( - const C1& c1, const C2& c2, OutputIterator output, LessThan&& comp) { +constexpr OutputIterator c_set_intersection(const C1& c1, const C2& c2, + OutputIterator output, + LessThan&& comp) { // In debug builds, ensure that both containers are sorted with respect to the // default comparator. std::set_intersection requires the containers be sorted // using the same comparator. @@ -1531,8 +1475,8 @@ typename = typename std::enable_if< !container_algorithm_internal::IsUnorderedContainer<C2>::value, void>::type> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator -c_set_difference(const C1& c1, const C2& c2, OutputIterator output) { +constexpr OutputIterator c_set_difference(const C1& c1, const C2& c2, + OutputIterator output) { return std::set_difference(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -1548,8 +1492,9 @@ typename = typename std::enable_if< !container_algorithm_internal::IsUnorderedContainer<C2>::value, void>::type> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator c_set_difference( - const C1& c1, const C2& c2, OutputIterator output, LessThan&& comp) { +constexpr OutputIterator c_set_difference(const C1& c1, const C2& c2, + OutputIterator output, + LessThan&& comp) { return std::set_difference(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -1569,8 +1514,8 @@ typename = typename std::enable_if< !container_algorithm_internal::IsUnorderedContainer<C2>::value, void>::type> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator -c_set_symmetric_difference(const C1& c1, const C2& c2, OutputIterator output) { +constexpr OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2, + OutputIterator output) { return std::set_symmetric_difference( container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), @@ -1587,8 +1532,9 @@ typename = typename std::enable_if< !container_algorithm_internal::IsUnorderedContainer<C2>::value, void>::type> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIterator c_set_symmetric_difference( - const C1& c1, const C2& c2, OutputIterator output, LessThan&& comp) { +constexpr OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2, + OutputIterator output, + LessThan&& comp) { return std::set_symmetric_difference( container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), @@ -1606,8 +1552,7 @@ // Container-based version of the <algorithm> `std::push_heap()` function // to push a value onto a container heap. template <typename RandomAccessContainer> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_push_heap( - RandomAccessContainer& sequence) { +constexpr void c_push_heap(RandomAccessContainer& sequence) { std::push_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence)); } @@ -1615,8 +1560,7 @@ // Overload of c_push_heap() for performing a push operation on a heap using a // `comp` other than `operator<`. template <typename RandomAccessContainer, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_push_heap( - RandomAccessContainer& sequence, LessThan&& comp) { +constexpr void c_push_heap(RandomAccessContainer& sequence, LessThan&& comp) { std::push_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), std::forward<LessThan>(comp)); @@ -1627,8 +1571,7 @@ // Container-based version of the <algorithm> `std::pop_heap()` function // to pop a value from a heap container. template <typename RandomAccessContainer> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_pop_heap( - RandomAccessContainer& sequence) { +constexpr void c_pop_heap(RandomAccessContainer& sequence) { std::pop_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence)); } @@ -1636,8 +1579,7 @@ // Overload of c_pop_heap() for performing a pop operation on a heap using a // `comp` other than `operator<`. template <typename RandomAccessContainer, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_pop_heap( - RandomAccessContainer& sequence, LessThan&& comp) { +constexpr void c_pop_heap(RandomAccessContainer& sequence, LessThan&& comp) { std::pop_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), std::forward<LessThan>(comp)); @@ -1648,8 +1590,7 @@ // Container-based version of the <algorithm> `std::make_heap()` function // to make a container a heap. template <typename RandomAccessContainer> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_make_heap( - RandomAccessContainer& sequence) { +constexpr void c_make_heap(RandomAccessContainer& sequence) { std::make_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence)); } @@ -1657,8 +1598,7 @@ // Overload of c_make_heap() for performing heap comparisons using a // `comp` other than `operator<` template <typename RandomAccessContainer, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_make_heap( - RandomAccessContainer& sequence, LessThan&& comp) { +constexpr void c_make_heap(RandomAccessContainer& sequence, LessThan&& comp) { std::make_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), std::forward<LessThan>(comp)); @@ -1669,8 +1609,7 @@ // Container-based version of the <algorithm> `std::sort_heap()` function // to sort a heap into ascending order (after which it is no longer a heap). template <typename RandomAccessContainer> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_sort_heap( - RandomAccessContainer& sequence) { +constexpr void c_sort_heap(RandomAccessContainer& sequence) { std::sort_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence)); } @@ -1678,8 +1617,7 @@ // Overload of c_sort_heap() for performing heap comparisons using a // `comp` other than `operator<` template <typename RandomAccessContainer, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_sort_heap( - RandomAccessContainer& sequence, LessThan&& comp) { +constexpr void c_sort_heap(RandomAccessContainer& sequence, LessThan&& comp) { std::sort_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), std::forward<LessThan>(comp)); @@ -1690,8 +1628,7 @@ // Container-based version of the <algorithm> `std::is_heap()` function // to check whether the given container is a heap. template <typename RandomAccessContainer> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_is_heap( - const RandomAccessContainer& sequence) { +constexpr bool c_is_heap(const RandomAccessContainer& sequence) { return std::is_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence)); } @@ -1699,8 +1636,8 @@ // Overload of c_is_heap() for performing heap comparisons using a // `comp` other than `operator<` template <typename RandomAccessContainer, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_is_heap( - const RandomAccessContainer& sequence, LessThan&& comp) { +constexpr bool c_is_heap(const RandomAccessContainer& sequence, + LessThan&& comp) { return std::is_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), std::forward<LessThan>(comp)); @@ -1711,9 +1648,8 @@ // Container-based version of the <algorithm> `std::is_heap_until()` function // to find the first element in a given container which is not in heap order. template <typename RandomAccessContainer> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<RandomAccessContainer> - c_is_heap_until(RandomAccessContainer& sequence) { +constexpr container_algorithm_internal::ContainerIter<RandomAccessContainer> +c_is_heap_until(RandomAccessContainer& sequence) { return std::is_heap_until(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence)); } @@ -1721,9 +1657,8 @@ // Overload of c_is_heap_until() for performing heap comparisons using a // `comp` other than `operator<` template <typename RandomAccessContainer, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 - container_algorithm_internal::ContainerIter<RandomAccessContainer> - c_is_heap_until(RandomAccessContainer& sequence, LessThan&& comp) { +constexpr container_algorithm_internal::ContainerIter<RandomAccessContainer> +c_is_heap_until(RandomAccessContainer& sequence, LessThan&& comp) { return std::is_heap_until(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), std::forward<LessThan>(comp)); @@ -1739,9 +1674,8 @@ // to return an iterator pointing to the element with the smallest value, using // `operator<` to make the comparisons. template <typename Sequence> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX17 - container_algorithm_internal::ContainerIter<Sequence> - c_min_element(Sequence& sequence) { +constexpr container_algorithm_internal::ContainerIter<Sequence> c_min_element( + Sequence& sequence) { return std::min_element(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence)); } @@ -1749,9 +1683,8 @@ // Overload of c_min_element() for performing a `comp` comparison other than // `operator<`. template <typename Sequence, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX17 - container_algorithm_internal::ContainerIter<Sequence> - c_min_element(Sequence& sequence, LessThan&& comp) { +constexpr container_algorithm_internal::ContainerIter<Sequence> c_min_element( + Sequence& sequence, LessThan&& comp) { return std::min_element(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), std::forward<LessThan>(comp)); @@ -1763,9 +1696,8 @@ // to return an iterator pointing to the element with the largest value, using // `operator<` to make the comparisons. template <typename Sequence> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX17 - container_algorithm_internal::ContainerIter<Sequence> - c_max_element(Sequence& sequence) { +constexpr container_algorithm_internal::ContainerIter<Sequence> c_max_element( + Sequence& sequence) { return std::max_element(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence)); } @@ -1773,9 +1705,8 @@ // Overload of c_max_element() for performing a `comp` comparison other than // `operator<`. template <typename Sequence, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX17 - container_algorithm_internal::ContainerIter<Sequence> - c_max_element(Sequence& sequence, LessThan&& comp) { +constexpr container_algorithm_internal::ContainerIter<Sequence> c_max_element( + Sequence& sequence, LessThan&& comp) { return std::max_element(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), std::forward<LessThan>(comp)); @@ -1788,9 +1719,8 @@ // smallest and largest values, respectively, using `operator<` to make the // comparisons. template <typename C> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX17 - container_algorithm_internal::ContainerIterPairType<C, C> - c_minmax_element(C& c) { +constexpr container_algorithm_internal::ContainerIterPairType<C, C> +c_minmax_element(C& c) { return std::minmax_element(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c)); } @@ -1798,9 +1728,8 @@ // Overload of c_minmax_element() for performing `comp` comparisons other than // `operator<`. template <typename C, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX17 - container_algorithm_internal::ContainerIterPairType<C, C> - c_minmax_element(C& c, LessThan&& comp) { +constexpr container_algorithm_internal::ContainerIterPairType<C, C> +c_minmax_element(C& c, LessThan&& comp) { return std::minmax_element(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<LessThan>(comp)); @@ -1818,8 +1747,8 @@ // that capital letters ("A-Z") have ASCII values less than lowercase letters // ("a-z"). template <typename Sequence1, typename Sequence2> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_lexicographical_compare( - const Sequence1& sequence1, const Sequence2& sequence2) { +constexpr bool c_lexicographical_compare(const Sequence1& sequence1, + const Sequence2& sequence2) { return std::lexicographical_compare( container_algorithm_internal::c_begin(sequence1), container_algorithm_internal::c_end(sequence1), @@ -1830,8 +1759,9 @@ // Overload of c_lexicographical_compare() for performing a lexicographical // comparison using a `comp` operator instead of `operator<`. template <typename Sequence1, typename Sequence2, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_lexicographical_compare( - const Sequence1& sequence1, const Sequence2& sequence2, LessThan&& comp) { +constexpr bool c_lexicographical_compare(const Sequence1& sequence1, + const Sequence2& sequence2, + LessThan&& comp) { return std::lexicographical_compare( container_algorithm_internal::c_begin(sequence1), container_algorithm_internal::c_end(sequence1), @@ -1846,7 +1776,7 @@ // to rearrange a container's elements into the next lexicographically greater // permutation. template <typename C> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_next_permutation(C& c) { +constexpr bool c_next_permutation(C& c) { return std::next_permutation(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c)); } @@ -1854,8 +1784,7 @@ // Overload of c_next_permutation() for performing a lexicographical // comparison using a `comp` operator instead of `operator<`. template <typename C, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_next_permutation(C& c, - LessThan&& comp) { +constexpr bool c_next_permutation(C& c, LessThan&& comp) { return std::next_permutation(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<LessThan>(comp)); @@ -1867,7 +1796,7 @@ // to rearrange a container's elements into the next lexicographically lesser // permutation. template <typename C> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_prev_permutation(C& c) { +constexpr bool c_prev_permutation(C& c) { return std::prev_permutation(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c)); } @@ -1875,8 +1804,7 @@ // Overload of c_prev_permutation() for performing a lexicographical // comparison using a `comp` operator instead of `operator<`. template <typename C, typename LessThan> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool c_prev_permutation(C& c, - LessThan&& comp) { +constexpr bool c_prev_permutation(C& c, LessThan&& comp) { return std::prev_permutation(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), std::forward<LessThan>(comp)); @@ -1892,8 +1820,7 @@ // to compute successive values of `value`, as if incremented with `++value` // after each element is written, and write them to the container. template <typename Sequence, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 void c_iota(Sequence& sequence, - const T& value) { +constexpr void c_iota(Sequence& sequence, const T& value) { std::iota(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), value); } @@ -1908,8 +1835,7 @@ // std::decay_t<T>. As a user of this function you can casually read // this as "returns T by value" and assume it does the right thing. template <typename Sequence, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 std::decay_t<T> c_accumulate( - const Sequence& sequence, T&& init) { +constexpr std::decay_t<T> c_accumulate(const Sequence& sequence, T&& init) { return std::accumulate(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), std::forward<T>(init)); @@ -1918,8 +1844,8 @@ // Overload of c_accumulate() for using a binary operations other than // addition for computing the accumulation. template <typename Sequence, typename T, typename BinaryOp> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 std::decay_t<T> c_accumulate( - const Sequence& sequence, T&& init, BinaryOp&& binary_op) { +constexpr std::decay_t<T> c_accumulate(const Sequence& sequence, T&& init, + BinaryOp&& binary_op) { return std::accumulate(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), std::forward<T>(init), @@ -1935,8 +1861,8 @@ // std::decay_t<T>. As a user of this function you can casually read // this as "returns T by value" and assume it does the right thing. template <typename Sequence1, typename Sequence2, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 std::decay_t<T> c_inner_product( - const Sequence1& factors1, const Sequence2& factors2, T&& sum) { +constexpr std::decay_t<T> c_inner_product(const Sequence1& factors1, + const Sequence2& factors2, T&& sum) { return std::inner_product(container_algorithm_internal::c_begin(factors1), container_algorithm_internal::c_end(factors1), container_algorithm_internal::c_begin(factors2), @@ -1948,9 +1874,9 @@ // the product between the two container's element pair). template <typename Sequence1, typename Sequence2, typename T, typename BinaryOp1, typename BinaryOp2> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 std::decay_t<T> c_inner_product( - const Sequence1& factors1, const Sequence2& factors2, T&& sum, - BinaryOp1&& op1, BinaryOp2&& op2) { +constexpr std::decay_t<T> c_inner_product(const Sequence1& factors1, + const Sequence2& factors2, T&& sum, + BinaryOp1&& op1, BinaryOp2&& op2) { return std::inner_product(container_algorithm_internal::c_begin(factors1), container_algorithm_internal::c_end(factors1), container_algorithm_internal::c_begin(factors2), @@ -1964,8 +1890,8 @@ // function to compute the difference between each element and the one preceding // it and write it to an iterator. template <typename InputSequence, typename OutputIt> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIt -c_adjacent_difference(const InputSequence& input, OutputIt output_first) { +constexpr OutputIt c_adjacent_difference(const InputSequence& input, + OutputIt output_first) { return std::adjacent_difference(container_algorithm_internal::c_begin(input), container_algorithm_internal::c_end(input), output_first); @@ -1974,8 +1900,8 @@ // Overload of c_adjacent_difference() for using a binary operation other than // subtraction to compute the adjacent difference. template <typename InputSequence, typename OutputIt, typename BinaryOp> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIt c_adjacent_difference( - const InputSequence& input, OutputIt output_first, BinaryOp&& op) { +constexpr OutputIt c_adjacent_difference(const InputSequence& input, + OutputIt output_first, BinaryOp&& op) { return std::adjacent_difference(container_algorithm_internal::c_begin(input), container_algorithm_internal::c_end(input), output_first, std::forward<BinaryOp>(op)); @@ -1988,8 +1914,8 @@ // to an iterator. The partial sum is the sum of all element values so far in // the sequence. template <typename InputSequence, typename OutputIt> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIt -c_partial_sum(const InputSequence& input, OutputIt output_first) { +constexpr OutputIt c_partial_sum(const InputSequence& input, + OutputIt output_first) { return std::partial_sum(container_algorithm_internal::c_begin(input), container_algorithm_internal::c_end(input), output_first); @@ -1998,8 +1924,8 @@ // Overload of c_partial_sum() for using a binary operation other than addition // to compute the "partial sum". template <typename InputSequence, typename OutputIt, typename BinaryOp> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 OutputIt c_partial_sum( - const InputSequence& input, OutputIt output_first, BinaryOp&& op) { +constexpr OutputIt c_partial_sum(const InputSequence& input, + OutputIt output_first, BinaryOp&& op) { return std::partial_sum(container_algorithm_internal::c_begin(input), container_algorithm_internal::c_end(input), output_first, std::forward<BinaryOp>(op));
diff --git a/absl/algorithm/container_test.cc b/absl/algorithm/container_test.cc index 6bacb1e..887c5ce 100644 --- a/absl/algorithm/container_test.cc +++ b/absl/algorithm/container_test.cc
@@ -2536,15 +2536,15 @@ struct CanCopy : std::false_type {}; template <typename Container, typename Output> struct CanCopy<Container, Output, - absl::void_t<decltype(absl::c_copy(std::declval<Container>(), - std::declval<Output>()))>> + std::void_t<decltype(absl::c_copy(std::declval<Container>(), + std::declval<Output>()))>> : std::true_type {}; template <typename Container, typename Output, typename = void> struct CanCopyN : std::false_type {}; template <typename Container, typename Output> struct CanCopyN<Container, Output, - absl::void_t<decltype(absl::c_copy_n( + std::void_t<decltype(absl::c_copy_n( std::declval<Container>(), std::declval<ptrdiff_t>(), std::declval<Output>()))>> : std::true_type {}; @@ -2552,8 +2552,8 @@ struct CanMove : std::false_type {}; template <typename Container, typename Output> struct CanMove<Container, Output, - absl::void_t<decltype(absl::c_move(std::declval<Container>(), - std::declval<Output>()))>> + std::void_t<decltype(absl::c_move(std::declval<Container>(), + std::declval<Output>()))>> : std::true_type {}; TEST(CanCopyTest, CopyToMultiDimArray) {
diff --git a/absl/base/BUILD.bazel b/absl/base/BUILD.bazel index 867f27d..abbf099 100644 --- a/absl/base/BUILD.bazel +++ b/absl/base/BUILD.bazel
@@ -62,6 +62,23 @@ ) cc_library( + name = "cpu_detect", + srcs = [ + "internal/cpu_detect.cc", + ], + hdrs = ["internal/cpu_detect.h"], + copts = ABSL_DEFAULT_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + visibility = [ + "//absl:__subpackages__", + "//absl:friends", + ], + deps = [ + ":config", + ], +) + +cc_library( name = "hardening", hdrs = [ "internal/hardening.h",
diff --git a/absl/base/CMakeLists.txt b/absl/base/CMakeLists.txt index 9608061..f3875b0 100644 --- a/absl/base/CMakeLists.txt +++ b/absl/base/CMakeLists.txt
@@ -32,6 +32,21 @@ # Internal-only target, do not depend on directly. absl_cc_library( NAME + base_cpu_detect + HDRS + "internal/cpu_detect.h" + SRCS + "internal/cpu_detect.cc" + DEPS + absl::base + absl::config + COPTS + ${ABSL_DEFAULT_COPTS} +) + +# Internal-only target, do not depend on directly. +absl_cc_library( + NAME errno_saver HDRS "internal/errno_saver.h"
diff --git a/absl/base/config.h b/absl/base/config.h index d4a7bfb..4a35ff1 100644 --- a/absl/base/config.h +++ b/absl/base/config.h
@@ -493,34 +493,6 @@ #error "absl endian detection needs to be set up for your compiler" #endif -// macOS < 10.13 and iOS < 12 don't support <any>, <optional>, or <variant> -// because the libc++ shared library shipped on the system doesn't have the -// requisite exported symbols. See -// https://github.com/abseil/abseil-cpp/issues/207 and -// https://developer.apple.com/documentation/xcode_release_notes/xcode_10_release_notes -// -// libc++ spells out the availability requirements in the file -// llvm-project/libcxx/include/__config via the #define -// _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS. The set of versions has been -// modified a few times, via -// https://github.com/llvm/llvm-project/commit/7fb40e1569dd66292b647f4501b85517e9247953 -// and -// https://github.com/llvm/llvm-project/commit/0bc451e7e137c4ccadcd3377250874f641ca514a -// The second has the actually correct versions, thus, is what we copy here. -#if defined(__APPLE__) && \ - ((defined(__ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__) && \ - __ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__ < 101300) || \ - (defined(__ENVIRONMENT_IPHONE_OS_VERSION_MIN_REQUIRED__) && \ - __ENVIRONMENT_IPHONE_OS_VERSION_MIN_REQUIRED__ < 120000) || \ - (defined(__ENVIRONMENT_WATCH_OS_VERSION_MIN_REQUIRED__) && \ - __ENVIRONMENT_WATCH_OS_VERSION_MIN_REQUIRED__ < 50000) || \ - (defined(__ENVIRONMENT_TV_OS_VERSION_MIN_REQUIRED__) && \ - __ENVIRONMENT_TV_OS_VERSION_MIN_REQUIRED__ < 120000)) -#define ABSL_INTERNAL_APPLE_CXX17_TYPES_UNAVAILABLE 1 -#else -#define ABSL_INTERNAL_APPLE_CXX17_TYPES_UNAVAILABLE 0 -#endif - // Deprecated macros for polyfill detection. #define ABSL_HAVE_STD_ANY 1 #define ABSL_USES_STD_ANY 1 @@ -854,27 +826,6 @@ #define ABSL_HAVE_CONSTANT_EVALUATED 1 #endif -// ABSL_INTERNAL_CONSTEXPR_SINCE_CXXYY is used to conditionally define constexpr -// for different C++ versions. -// -// These macros are an implementation detail and will be unconditionally removed -// once the minimum supported C++ version catches up to a given version. -// -// For this reason, this symbol is considered INTERNAL and code outside of -// Abseil must not use it. -#if defined(ABSL_INTERNAL_CPLUSPLUS_LANG) && \ - ABSL_INTERNAL_CPLUSPLUS_LANG >= 201703L -#define ABSL_INTERNAL_CONSTEXPR_SINCE_CXX17 constexpr -#else -#define ABSL_INTERNAL_CONSTEXPR_SINCE_CXX17 -#endif -#if defined(ABSL_INTERNAL_CPLUSPLUS_LANG) && \ - ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L -#define ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 constexpr -#else -#define ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 -#endif - // ABSL_INTERNAL_EMSCRIPTEN_VERSION combines Emscripten's three version macros // into an integer that can be compared against. #ifdef ABSL_INTERNAL_EMSCRIPTEN_VERSION
diff --git a/absl/crc/internal/cpu_detect.cc b/absl/base/internal/cpu_detect.cc similarity index 82% rename from absl/crc/internal/cpu_detect.cc rename to absl/base/internal/cpu_detect.cc index 86f55d0..c08637c 100644 --- a/absl/crc/internal/cpu_detect.cc +++ b/absl/base/internal/cpu_detect.cc
@@ -12,7 +12,7 @@ // See the License for the specific language governing permissions and // limitations under the License. -#include "absl/crc/internal/cpu_detect.h" +#include "absl/base/internal/cpu_detect.h" #include <cstdint> #include <optional> // IWYU pragma: keep @@ -42,6 +42,7 @@ // MSVC-equivalent __cpuid intrinsic declaration for clang-like compilers // for non-Windows build environments. extern void __cpuid(int[4], int); +extern void __cpuidex(int[4], int, int); #elif !defined(_WIN32) && !defined(_WIN64) // MSVC defines this function for us. // https://learn.microsoft.com/en-us/cpp/intrinsics/cpuid-cpuidex @@ -51,12 +52,18 @@ "=d"(cpu_info[3]) : "a"(info_type), "c"(0)); } +static void __cpuidex(int cpu_info[4], int info_type, int ecx) { + __asm__ volatile("cpuid \n\t" + : "=a"(cpu_info[0]), "=b"(cpu_info[1]), "=c"(cpu_info[2]), + "=d"(cpu_info[3]) + : "a"(info_type), "c"(ecx)); +} #endif // !defined(_WIN32) && !defined(_WIN64) #endif // defined(__x86_64__) || defined(_M_X64) namespace absl { ABSL_NAMESPACE_BEGIN -namespace crc_internal { +namespace base_internal { #if defined(__x86_64__) || defined(_M_X64) @@ -137,7 +144,7 @@ case 0x4f: // Broadwell case 0x56: // BroadwellDE return CpuType::kIntelBroadwell; - case 0x55: // Skylake Xeon + case 0x55: // Skylake Xeon if ((cpu_info[0] & 0x0f) < 5) { // stepping < 5 is skylake return CpuType::kIntelSkylakeXeon; } else { // stepping >= 5 is cascadelake @@ -152,7 +159,7 @@ case 0xcf: // Emerald Rapids return CpuType::kIntelEmeraldrapids; case 0xad: // Granite Rapids - return CpuType::kIntelGraniterapidsap; + return CpuType::kIntelGraniterapids; default: return CpuType::kUnknown; } @@ -271,18 +278,30 @@ switch (implementer) { case 0x41: switch (part_number) { - case 0xd0c: return CpuType::kArmNeoverseN1; - case 0xd40: return CpuType::kArmNeoverseV1; - case 0xd49: return CpuType::kArmNeoverseN2; - case 0xd4f: return CpuType::kArmNeoverseV2; - case 0xd8e: return CpuType::kArmNeoverseN3; + case 0xd0c: + return CpuType::kArmNeoverseN1; + case 0xd40: + return CpuType::kArmNeoverseV1; + case 0xd49: + return CpuType::kArmNeoverseN2; + case 0xd4f: { + uint64_t isar0 = 0; + ABSL_INTERNAL_AARCH64_ID_REG_READ(ID_AA64ISAR0_EL1, isar0); + if (((isar0 >> 60) & 0xf) == 0x0) { + return CpuType::kNvidiaGrace; + } + return CpuType::kArmNeoverseV2; + } + case 0xd8e: + return CpuType::kArmNeoverseN3; default: return CpuType::kUnknown; } break; case 0xc0: switch (part_number) { - case 0xac3: return CpuType::kAmpereSiryn; + case 0xac3: + return CpuType::kAmpereSiryn; default: return CpuType::kUnknown; } @@ -354,6 +373,47 @@ #endif -} // namespace crc_internal +// Returns how many hardware contexts per CPU exist. Note: AMD CPUs prior to Zen +// 2 (Rome, 2019) do not support CPUID leaf 0xb. We intentionally avoid falling +// back to leaf 1 ebx[23:16] because it reports total logical processors per +// package (not threads per core), which risks false positives on older +// multi-core non-SMT chips. Pre-Zen 2 AMD safely defaults to 1. +int NumContextsPerCPU() { +#if defined(__x86_64__) || defined(_M_X64) + int info[4]; + __cpuid(info, 0); + if (info[0] < 0xb) { + return 1; + } + + __cpuid(info, 1); + bool has_ht = (info[3] & (1 << 28)) != 0; + if (!has_ht) { + return 1; + } + + for (int sub_leaf = 0; sub_leaf < 4; ++sub_leaf) { + __cpuidex(info, 0xb, sub_leaf); + int level_type = (info[2] >> 8) & 0xff; + if (level_type == 0) { + break; + } + if (level_type == 1) { + int num_threads = info[1] & 0x0ffff; + if (num_threads >= 1) { + return num_threads; + } + } + } + + return 1; +#else + return 1; +#endif +} + +bool IsSMTEnabled() { return NumContextsPerCPU() > 1; } + +} // namespace base_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/crc/internal/cpu_detect.h b/absl/base/internal/cpu_detect.h similarity index 80% rename from absl/crc/internal/cpu_detect.h rename to absl/base/internal/cpu_detect.h index e76a802..5ea76ec 100644 --- a/absl/crc/internal/cpu_detect.h +++ b/absl/base/internal/cpu_detect.h
@@ -12,14 +12,14 @@ // See the License for the specific language governing permissions and // limitations under the License. -#ifndef ABSL_CRC_INTERNAL_CPU_DETECT_H_ -#define ABSL_CRC_INTERNAL_CPU_DETECT_H_ +#ifndef ABSL_BASE_INTERNAL_CPU_DETECT_H_ +#define ABSL_BASE_INTERNAL_CPU_DETECT_H_ #include "absl/base/config.h" namespace absl { ABSL_NAMESPACE_BEGIN -namespace crc_internal { +namespace base_internal { // Enumeration of architectures that we have special-case tuning parameters for. // This set may change over time. @@ -38,7 +38,7 @@ kIntelIcelake, kIntelSapphirerapids, kIntelEmeraldrapids, - kIntelGraniterapidsap, + kIntelGraniterapids, kIntelSkylake, kIntelIvybridge, kIntelSandybridge, @@ -49,6 +49,7 @@ kArmNeoverseN2, kArmNeoverseV2, kArmNeoverseN3, + kNvidiaGrace, }; // Returns the type of host CPU this code is running on. Returns kUnknown if @@ -62,8 +63,15 @@ // tuning. bool SupportsArmCRC32PMULL(); -} // namespace crc_internal +// Returns whether the host CPU supports simultaneous multithreading (SMT) and +// if it is enabled. +bool IsSMTEnabled(); + +// Returns how many hardware contexts per CPU exist. +int NumContextsPerCPU(); + +} // namespace base_internal ABSL_NAMESPACE_END } // namespace absl -#endif // ABSL_CRC_INTERNAL_CPU_DETECT_H_ +#endif // ABSL_BASE_INTERNAL_CPU_DETECT_H_
diff --git a/absl/base/internal/hardening.h b/absl/base/internal/hardening.h index 31b25d9..188c8f3 100644 --- a/absl/base/internal/hardening.h +++ b/absl/base/internal/hardening.h
@@ -45,7 +45,7 @@ ABSL_ASSERT(cond); #if (ABSL_OPTION_HARDENED == 1 || ABSL_OPTION_HARDENED == 2) && defined(NDEBUG) if (ABSL_PREDICT_FALSE(!cond)) { - base_internal::HardeningAbort(); + ABSL_INTERNAL_HARDENING_ABORT(); } #endif } @@ -59,7 +59,7 @@ ABSL_ASSERT(cond); #if (ABSL_OPTION_HARDENED == 1) && defined(NDEBUG) if (ABSL_PREDICT_FALSE(!cond)) { - base_internal::HardeningAbort(); + ABSL_INTERNAL_HARDENING_ABORT(); } #endif } @@ -69,7 +69,7 @@ ABSL_ASSERT(val1 > val2); #if (ABSL_OPTION_HARDENED == 1 || ABSL_OPTION_HARDENED == 2) && defined(NDEBUG) if (!ABSL_PREDICT_TRUE(val1 > val2)) { - base_internal::HardeningAbort(); + ABSL_INTERNAL_HARDENING_ABORT(); } #endif } @@ -79,7 +79,7 @@ ABSL_ASSERT(val1 >= val2); #if (ABSL_OPTION_HARDENED == 1 || ABSL_OPTION_HARDENED == 2) && defined(NDEBUG) if (!ABSL_PREDICT_TRUE(val1 >= val2)) { - base_internal::HardeningAbort(); + ABSL_INTERNAL_HARDENING_ABORT(); } #endif } @@ -89,7 +89,7 @@ ABSL_ASSERT(val1 < val2); #if (ABSL_OPTION_HARDENED == 1 || ABSL_OPTION_HARDENED == 2) && defined(NDEBUG) if (!ABSL_PREDICT_TRUE(val1 < val2)) { - base_internal::HardeningAbort(); + ABSL_INTERNAL_HARDENING_ABORT(); } #endif } @@ -99,7 +99,7 @@ ABSL_ASSERT(val1 <= val2); #if (ABSL_OPTION_HARDENED == 1 || ABSL_OPTION_HARDENED == 2) && defined(NDEBUG) if (!ABSL_PREDICT_TRUE(val1 <= val2)) { - base_internal::HardeningAbort(); + ABSL_INTERNAL_HARDENING_ABORT(); } #endif } @@ -113,7 +113,7 @@ ABSL_ASSERT(!container.empty()); #if (ABSL_OPTION_HARDENED == 1 || ABSL_OPTION_HARDENED == 2) && defined(NDEBUG) if (ABSL_PREDICT_FALSE(container.empty())) { - base_internal::HardeningAbort(); + ABSL_INTERNAL_HARDENING_ABORT(); } #endif } @@ -123,7 +123,7 @@ ABSL_ASSERT(ptr != nullptr); #if (ABSL_OPTION_HARDENED == 1 || ABSL_OPTION_HARDENED == 2) && defined(NDEBUG) if (ABSL_PREDICT_FALSE(ptr == nullptr)) { - base_internal::HardeningAbort(); + ABSL_INTERNAL_HARDENING_ABORT(); } #endif }
diff --git a/absl/base/macros.h b/absl/base/macros.h index 8c4a34d..f57643a 100644 --- a/absl/base/macros.h +++ b/absl/base/macros.h
@@ -135,7 +135,15 @@ // aborts the program in release mode (when NDEBUG is defined). The // implementation should abort the program as quickly as possible and ideally it // should not be possible to ignore the abort request. +#if defined(__CUDACC__) || defined(__CUDA_ARCH__) || defined(__CUDA__) +#define ABSL_INTERNAL_HARDENING_ABORT() \ + do { \ + ABSL_INTERNAL_IMMEDIATE_ABORT_IMPL(); \ + ABSL_INTERNAL_UNREACHABLE_IMPL(); \ + } while (false) +#else #define ABSL_INTERNAL_HARDENING_ABORT() ::absl::base_internal::HardeningAbort() +#endif // ABSL_HARDENING_ASSERT() // @@ -149,9 +157,12 @@ // See `ABSL_OPTION_HARDENED` in `absl/base/options.h` for more information on // hardened mode. #if (ABSL_OPTION_HARDENED == 1 || ABSL_OPTION_HARDENED == 2) && defined(NDEBUG) -#define ABSL_HARDENING_ASSERT(expr) \ - (ABSL_PREDICT_TRUE((expr)) ? static_cast<void>(0) \ - : ABSL_INTERNAL_HARDENING_ABORT()) +#define ABSL_HARDENING_ASSERT(expr) \ + do { \ + if (!ABSL_PREDICT_TRUE((expr))) { \ + ABSL_INTERNAL_HARDENING_ABORT(); \ + } \ + } while (false) #else #define ABSL_HARDENING_ASSERT(expr) ABSL_ASSERT(expr) #endif @@ -168,9 +179,7 @@ // See `ABSL_OPTION_HARDENED` in `absl/base/options.h` for more information on // hardened mode. #if ABSL_OPTION_HARDENED == 1 && defined(NDEBUG) -#define ABSL_HARDENING_ASSERT_SLOW(expr) \ - (ABSL_PREDICT_TRUE((expr)) ? static_cast<void>(0) \ - : ABSL_INTERNAL_HARDENING_ABORT()) +#define ABSL_HARDENING_ASSERT_SLOW(expr) ABSL_HARDENING_ASSERT(expr) #else #define ABSL_HARDENING_ASSERT_SLOW(expr) ABSL_ASSERT(expr) #endif
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h index d4ce523..5261b6f 100644 --- a/absl/container/internal/btree_container.h +++ b/absl/container/internal/btree_container.h
@@ -501,7 +501,7 @@ IfRRef<int KQual>::AddPtr<K>, \ IfRRef<int MQual>::AddPtr<M>>>()), \ ABSL_INTERNAL_SINGLE_ARG( \ - int &..., \ + int&..., \ decltype(EnableIf<LifetimeBoundKV<K, KValue, M, MValue>>()) = \ 0))> \ decltype(auto) Func( \ @@ -515,7 +515,7 @@ __VA_ARGS__ std::forward<decltype(k)>(k), \ std::forward<decltype(obj)>(obj)); \ } \ - friend struct std::enable_if<false> /* just to force a semicolon */ + static_assert(true, "this assertion forces a semicolon") // Insertion routines. // Note: the nullptr template arguments and extra `const M&` overloads allow // for supporting bitfield arguments. @@ -609,12 +609,12 @@ decltype(auto) Func( \ __VA_ARGS__ key_arg<K> KQual k ABSL_INTERNAL_IF_##KValue( \ ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this)), \ - Args &&...args) ABSL_ATTRIBUTE_LIFETIME_BOUND { \ + Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND { \ return ABSL_INTERNAL_IF_##KValue((this->template Func<K, 0>), Callee)( \ __VA_ARGS__ std::forward<decltype(k)>(k), \ std::forward<decltype(args)>(args)...); \ } \ - friend struct std::enable_if<false> /* just to force a semicolon */ + static_assert(true, "this assertion forces a semicolon") ABSL_INTERNAL_X(try_emplace, try_emplace_impl, const &, false); ABSL_INTERNAL_X(try_emplace, try_emplace_impl, const &, true); ABSL_INTERNAL_X(try_emplace, try_emplace_impl, &&, false);
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index 6ab06e4..5a2c08a 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -367,6 +367,23 @@ SetCtrl(c, i, static_cast<ctrl_t>(h), slot_size); } +inline void SetCtrlInSingleGroupTableNoSanitizeImpl(const CommonFields& c, + size_t i, ctrl_t h) { + ABSL_SWISSTABLE_ASSERT(!c.is_small()); + ABSL_SWISSTABLE_ASSERT(is_single_group(c.capacity())); + ctrl_t* ctrl = c.control(); + ctrl[i] = h; + ctrl[i + c.capacity() + 1] = h; +} + +// Sets `ctrl[i]` to `ctrl_t::kSentinel` in single group table. +// +// Unlike setting it directly, this function will perform bounds checks and +// mirror the value to the cloned tail if necessary. +inline void BlockCtrlInSingleGroupTable(const CommonFields& c, size_t i) { + SetCtrlInSingleGroupTableNoSanitizeImpl(c, i, ctrl_t::kSentinel); +} + // Like SetCtrl, but in a single group table, we can save some operations when // setting the cloned control byte. inline void SetCtrlInSingleGroupTable(const CommonFields& c, size_t i, ctrl_t h, @@ -374,9 +391,7 @@ ABSL_SWISSTABLE_ASSERT(!c.is_small()); ABSL_SWISSTABLE_ASSERT(is_single_group(c.capacity())); DoSanitizeOnSetCtrl(c, i, h, slot_size); - ctrl_t* ctrl = c.control(); - ctrl[i] = h; - ctrl[i + c.capacity() + 1] = h; + SetCtrlInSingleGroupTableNoSanitizeImpl(c, i, h); } // Overload for setting to an occupied `h2_t` rather than a special `ctrl_t`. inline void SetCtrlInSingleGroupTable(const CommonFields& c, size_t i, h2_t h, @@ -528,8 +543,13 @@ } // Updates the control bytes to indicate a completely empty table such that all -// control bytes are kEmpty except for the kSentinel byte. -void ResetCtrl(CommonFields& common, size_t slot_size) { +// control bytes are kEmpty except for the kSentinel bytes. +// If the table has blocked elements, last `blocked_element_count` are set to +// kSentinel. +void ResetCtrl(CommonFields& common, size_t slot_size, + size_t blocked_element_count) { + ABSL_SWISSTABLE_ASSERT(IsCapacityValidForBlockedElements(common.capacity()) || + blocked_element_count == 0); const size_t capacity = common.capacity(); ctrl_t* ctrl = common.control(); static constexpr size_t kTwoGroupCapacity = 2 * Group::kWidth - 1; @@ -547,7 +567,12 @@ capacity + 1 + NumClonedBytes()); } ctrl[capacity] = ctrl_t::kSentinel; - SanitizerPoisonMemoryRegion(common.slot_array(), slot_size * capacity); + SanitizerPoisonMemoryRegion(common.slot_array(), + slot_size * (capacity - blocked_element_count)); + while (blocked_element_count > 0) { + BlockCtrlInSingleGroupTable(common, capacity - blocked_element_count); + --blocked_element_count; + } } // Initializes control bytes for growing from capacity 1 to 3. @@ -629,7 +654,8 @@ c.infoz().RecordStorageChanged(0, policy.soo_capacity()); c.infoz().Unregister(); (*policy.dealloc)(alloc, c.capacity(), c.control(), policy.slot_size, - policy.slot_align, c.has_infoz()); + policy.slot_align, c.has_infoz(), + c.blocked_element_count()); c = policy.soo_enabled ? CommonFields{soo_tag_t{}} : CommonFields{non_soo_tag_t{}}; } @@ -670,21 +696,76 @@ bool reuse) { ABSL_SWISSTABLE_ASSERT(c.capacity() > MaxSmallCapacity()); if (reuse) { + size_t blocked_element_count = c.blocked_element_count(); c.set_size_to_zero(); - ResetCtrl(c, policy.slot_size); + ABSL_SWISSTABLE_ASSERT(c.capacity() > policy.soo_capacity()); + ResetCtrl(c, policy.slot_size, blocked_element_count); ResetGrowthLeft(c); + c.growth_info().OverwriteManyEmptyAsFull(blocked_element_count); + ABSL_SWISSTABLE_ASSERT(c.blocked_element_count() == blocked_element_count); c.infoz().RecordStorageChanged(0, c.capacity()); } else { ClearBackingArrayNoReuse(c, policy, alloc); } } -namespace { +void DestroySlots(CommonFields& c, size_t slot_size, + DestroySlotFn destroy_slot) { + ABSL_SWISSTABLE_ASSERT(!c.is_small()); + ABSL_SWISSTABLE_ASSERT(destroy_slot != nullptr); + auto destroy_slot_wrapper = [&](const ctrl_t*, void* slot) { + destroy_slot(&c, slot); + }; + if constexpr (SwisstableAssertAccessToDestroyedTable()) { + CommonFields common_copy(non_soo_tag_t{}, c); + c.set_capacity(HashtableCapacity::CreateDestroyed()); + IterateOverFullSlotsImpl(common_copy, slot_size, destroy_slot_wrapper); + c.set_capacity(common_copy.capacity()); + } else { + IterateOverFullSlotsImpl(c, slot_size, destroy_slot_wrapper); + } +} -enum class ResizeNonSooMode { - kGuaranteedEmpty, - kGuaranteedAllocated, -}; +void DeallocBackingArray(CommonFields& c, size_t slot_size, size_t slot_align, + DeallocBackingArrayFn dealloc, void* alloc) { + const size_t cap = c.capacity(); + c.infoz().Unregister(); + dealloc(alloc, cap, c.control(), slot_size, slot_align, c.has_infoz(), + c.blocked_element_count()); +} + +void DestructSoo(CommonFields& c, size_t slot_size, size_t slot_align, + DestroySlotFn destroy_slot, DeallocBackingArrayFn dealloc, + void* alloc) { + ABSL_SWISSTABLE_ASSERT(!c.is_small() || !c.empty()); + if (c.is_small()) { + ABSL_SWISSTABLE_ASSERT(destroy_slot != nullptr); + destroy_slot(&c, c.soo_data()); + return; + } + if (destroy_slot != nullptr) { + DestroySlots(c, slot_size, destroy_slot); + } + DeallocBackingArray(c, slot_size, slot_align, dealloc, alloc); +} + +void DestructNonSoo(CommonFields& c, size_t slot_size, size_t slot_align, + DestroySlotFn destroy_slot, DeallocBackingArrayFn dealloc, + void* alloc) { + ABSL_SWISSTABLE_ASSERT(c.capacity() > 0); + if (destroy_slot != nullptr) { + if (c.is_small()) { + if (!c.empty()) { + destroy_slot(&c, c.slot_array()); + } + } else { + DestroySlots(c, slot_size, destroy_slot); + } + } + DeallocBackingArray(c, slot_size, slot_align, dealloc, alloc); +} + +namespace { // Iterates over full slots in old table, finds new positions for them and // transfers the slots. @@ -773,9 +854,9 @@ BackingArrayPtrs AllocBackingArray(CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_capacity, bool has_infoz, - void* alloc) { + void* alloc, size_t blocked_element_count) { RawHashSetLayout layout(new_capacity, policy.slot_size, policy.slot_align, - has_infoz); + has_infoz, blocked_element_count); // Perform a direct call in the common case to allow for profile-guided // heap optimization (PGHO) to understand which allocation function is used. constexpr size_t kDefaultAlignment = BackingArrayAlignment(alignof(size_t)); @@ -795,67 +876,15 @@ mem + layout.slot_offset()}; } -template <ResizeNonSooMode kMode> -void ResizeNonSooImpl(CommonFields& common, - const PolicyFunctions& __restrict policy, - size_t new_capacity, HashtablezInfoHandle infoz) { - ABSL_SWISSTABLE_ASSERT(IsValidCapacity(new_capacity)); - ABSL_SWISSTABLE_ASSERT(new_capacity > policy.soo_capacity()); - - [[maybe_unused]] const size_t old_capacity = common.capacity(); - [[maybe_unused]] ctrl_t* old_ctrl; - [[maybe_unused]] void* old_slots; - if constexpr (kMode == ResizeNonSooMode::kGuaranteedAllocated) { - old_ctrl = common.control(); - old_slots = common.slot_array(); - } - - const size_t slot_size = policy.slot_size; - [[maybe_unused]] const size_t slot_align = policy.slot_align; - const bool has_infoz = infoz.IsSampled(); - void* alloc = policy.get_char_alloc(common); - - common.set_capacity(new_capacity); - const auto [new_ctrl, new_slots] = - AllocBackingArray(common, policy, new_capacity, has_infoz, alloc); - common.set_control(new_ctrl); - common.set_slots(new_slots); - common.generate_new_seed(has_infoz); - - size_t total_probe_length = 0; - ResetCtrl(common, slot_size); - ABSL_SWISSTABLE_ASSERT(kMode != ResizeNonSooMode::kGuaranteedEmpty || - old_capacity == policy.soo_capacity()); - ABSL_SWISSTABLE_ASSERT(kMode != ResizeNonSooMode::kGuaranteedAllocated || - old_capacity > 0); - if constexpr (kMode == ResizeNonSooMode::kGuaranteedAllocated) { - total_probe_length = FindNewPositionsAndTransferSlots( - common, policy, old_ctrl, old_slots, old_capacity); - (*policy.dealloc)(alloc, old_capacity, old_ctrl, slot_size, slot_align, - has_infoz); - if (HasGrowthInfoForCapacity(new_capacity)) { - ResetGrowthLeft(GetGrowthInfoFromControl(new_ctrl), new_capacity, - common.size()); - } - } else { - if (HasGrowthInfoForCapacity(new_capacity)) { - GetGrowthInfoFromControl(new_ctrl).InitGrowthLeftNoDeleted( - CapacityToGrowth(new_capacity)); - } - } - - if (ABSL_PREDICT_FALSE(has_infoz)) { - ReportResizeToInfoz(common, infoz, total_probe_length); - } -} - void ResizeEmptyNonAllocatedTableImpl(CommonFields& common, const PolicyFunctions& __restrict policy, - size_t new_capacity, bool force_infoz) { + size_t new_capacity, + size_t blocked_element_count, + bool force_infoz) { ABSL_SWISSTABLE_ASSERT(IsValidCapacity(new_capacity)); ABSL_SWISSTABLE_ASSERT(new_capacity > policy.soo_capacity()); ABSL_SWISSTABLE_ASSERT(!force_infoz || policy.soo_enabled); - ABSL_SWISSTABLE_ASSERT(common.capacity() <= policy.soo_capacity()); + ABSL_SWISSTABLE_ASSERT(common.capacity() == policy.soo_capacity()); ABSL_SWISSTABLE_ASSERT(common.empty()); const size_t slot_size = policy.slot_size; HashtablezInfoHandle infoz; @@ -865,8 +894,25 @@ infoz = ForcedTrySample(slot_size, policy.key_size, policy.value_size, policy.soo_capacity()); } - ResizeNonSooImpl<ResizeNonSooMode::kGuaranteedEmpty>(common, policy, - new_capacity, infoz); + const bool has_infoz = infoz.IsSampled(); + void* alloc = policy.get_char_alloc(common); + + common.set_capacity(new_capacity); + const auto [new_ctrl, new_slots] = AllocBackingArray( + common, policy, new_capacity, has_infoz, alloc, blocked_element_count); + common.set_control(new_ctrl); + common.set_slots(new_slots); + common.generate_new_seed(has_infoz); + + ResetCtrl(common, slot_size, blocked_element_count); + if (HasGrowthInfoForCapacity(new_capacity)) { + GetGrowthInfoFromControl(new_ctrl).InitGrowthLeftNoDeleted( + CapacityToGrowth(new_capacity) - blocked_element_count); + } + + if (ABSL_PREDICT_FALSE(has_infoz)) { + ReportResizeToInfoz(common, infoz, 0); + } } // If the table was SOO, initializes new control bytes and transfers slot. @@ -892,7 +938,7 @@ policy.transfer_n(&c, target_slot, c.soo_data(), 1); c.set_control(new_ctrl); c.set_slots(new_slots); - ResetCtrl(c, policy.slot_size); + ResetCtrl(c, policy.slot_size, /*blocked_element_count=*/0); SetCtrl(c, offset, H2(soo_slot_hash), policy.slot_size); } @@ -939,7 +985,8 @@ // We do not set control and slots in CommonFields yet to avoid overriding // SOO data. const auto [new_ctrl, new_slots] = - AllocBackingArray(common, policy, new_capacity, has_infoz, alloc); + AllocBackingArray(common, policy, new_capacity, has_infoz, alloc, + /*blocked_element_count=*/0); InsertOldSooSlotAndInitializeControlBytes(common, policy, new_ctrl, new_slots, has_infoz); @@ -953,6 +1000,7 @@ void GrowIntoSingleGroupShuffleControlBytes(ctrl_t* __restrict old_ctrl, size_t old_capacity, + size_t old_blocked_element_count, ctrl_t* __restrict new_ctrl, size_t new_capacity) { ABSL_SWISSTABLE_ASSERT(is_single_group(new_capacity)); @@ -972,6 +1020,9 @@ // Example: // old_ctrl = 012S012EEEEEEEEE... // copied_bytes = S012EEEE + // Example with blocked elements: + // old_ctrl = 01SS01SEEEEEEEEE... + // copied_bytes = S01SEEEE uint64_t copied_bytes = absl::little_endian::Load64(old_ctrl + old_capacity); // We change the sentinel byte to kEmpty before storing to both the start of @@ -991,6 +1042,22 @@ // after = E012EEEE copied_bytes ^= kEmptyXorSentinel; + if (ABSL_PREDICT_FALSE(old_blocked_element_count > 0)) { + // Replacing blocked sentinel elements with kEmpty. + static constexpr uint64_t kAllBytesEmptyXorSentinel = + kEmptyXorSentinel * uint64_t{0x0101010101010101}; + uint64_t blocked_mask = kAllBytesEmptyXorSentinel; + // Keep old_blocked_element_count bytes in the mask. + blocked_mask >>= 64 - old_blocked_element_count * 8; + // Shift the mask to the start of the blocked elements bytes. + blocked_mask <<= (old_capacity - old_blocked_element_count + 1) * 8; + // Example with blocked elements: + // old_ctrl = 0SSS0SSEEEEEEEEE... + // before = E0SSEEEE + // after = E0EEEEEE + copied_bytes ^= blocked_mask; + } + if (Group::kWidth == 8) { // With group size 8, we can grow with two write operations. ABSL_SWISSTABLE_ASSERT(old_capacity < 8 && @@ -1418,6 +1485,8 @@ ABSL_SWISSTABLE_ASSERT(common.capacity() == 1); ABSL_SWISSTABLE_ASSERT(!common.empty()); ABSL_SWISSTABLE_ASSERT(!policy.soo_enabled); + // 1-element tables can't have any blocked elements. + ABSL_SWISSTABLE_ASSERT(common.blocked_element_count() == 0); constexpr size_t kOldCapacity = 1; constexpr size_t kNewCapacity = NextCapacity(kOldCapacity); ctrl_t* old_ctrl = common.control(); @@ -1431,7 +1500,8 @@ common.set_capacity(kNewCapacity); const auto [new_ctrl, new_slots] = - AllocBackingArray(common, policy, kNewCapacity, has_infoz, alloc); + AllocBackingArray(common, policy, kNewCapacity, has_infoz, alloc, + /*blocked_element_count=*/0); common.set_control(new_ctrl); common.set_slots(new_slots); SanitizerPoisonMemoryRegion(new_slots, kNewCapacity * slot_size); @@ -1455,7 +1525,8 @@ SanitizerUnpoisonMemoryRegion(new_element_target_slot, slot_size); policy.dealloc(alloc, kOldCapacity, old_ctrl, slot_size, slot_align, - has_infoz); + has_infoz, + /*blocked_element_count=*/0); PrepareInsertCommon(common); ABSL_SWISSTABLE_ASSERT(common.size() == 2); GetGrowthInfoFromControl(new_ctrl).InitGrowthLeftNoDeleted(kNewCapacity - 2); @@ -1479,6 +1550,7 @@ const size_t new_capacity = NextCapacity(old_capacity); ctrl_t* old_ctrl = common.control(); void* old_slots = common.slot_array(); + size_t old_blocked_element_count = common.blocked_element_count(); common.set_capacity(new_capacity); const size_t slot_size = policy.slot_size; @@ -1488,7 +1560,8 @@ const bool has_infoz = infoz.IsSampled(); const auto [new_ctrl, new_slots] = - AllocBackingArray(common, policy, new_capacity, has_infoz, alloc); + AllocBackingArray(common, policy, new_capacity, has_infoz, alloc, + /*blocked_element_count=*/0); common.set_control(new_ctrl); common.set_slots(new_slots); SanitizerPoisonMemoryRegion(new_slots, new_capacity * slot_size); @@ -1498,7 +1571,9 @@ FindInfo find_info; if (ABSL_PREDICT_TRUE(is_single_group(new_capacity))) { size_t offset; - GrowIntoSingleGroupShuffleControlBytes(old_ctrl, old_capacity, new_ctrl, + const size_t old_size = common.size(); + GrowIntoSingleGroupShuffleControlBytes(old_ctrl, old_capacity, + old_blocked_element_count, new_ctrl, new_capacity); // We put the new element either at the beginning or at the end of the // table with approximately equal probability. @@ -1510,10 +1585,11 @@ find_info = FindInfo{offset, 0}; // Single group tables have all slots full on resize. So we can transfer // all slots without checking the control bytes. - ABSL_SWISSTABLE_ASSERT(common.size() == old_capacity); + ABSL_SWISSTABLE_ASSERT(common.size() + old_blocked_element_count == + old_capacity); void* target = NextSlot(new_slots, slot_size); - SanitizerUnpoisonMemoryRegion(target, old_capacity * slot_size); - policy.transfer_n(&common, target, old_slots, old_capacity); + SanitizerUnpoisonMemoryRegion(target, old_size * slot_size); + policy.transfer_n(&common, target, old_slots, old_size); } else { total_probe_length = GrowToNextCapacityDispatch(common, policy, old_ctrl, old_slots); @@ -1522,7 +1598,7 @@ } ABSL_SWISSTABLE_ASSERT(old_capacity > policy.soo_capacity()); (*policy.dealloc)(alloc, old_capacity, old_ctrl, slot_size, slot_align, - has_infoz); + has_infoz, old_blocked_element_count); PrepareInsertCommon(common); ResetGrowthLeft(GetGrowthInfoFromControl(new_ctrl), new_capacity, common.size()); @@ -1570,7 +1646,8 @@ void* alloc = policy.get_char_alloc(common); const auto [new_ctrl, new_slots] = - AllocBackingArray(common, policy, kNewCapacity, has_infoz, alloc); + AllocBackingArray(common, policy, kNewCapacity, has_infoz, alloc, + /*blocked_element_count=*/0); common.set_control(new_ctrl); common.set_slots(new_slots); @@ -1648,6 +1725,7 @@ // Slow path for PrepareInsertLarge that is called when the table has deleted // slots or need to be resized or rehashed. +ABSL_ATTRIBUTE_NOINLINE size_t PrepareInsertLargeSlow(CommonFields& common, const PolicyFunctions& __restrict policy, size_t hash) { @@ -1683,6 +1761,7 @@ CommonFields& common, const PolicyFunctions& __restrict policy, absl::FunctionRef<size_t(size_t)> get_hash) { ResizeEmptyNonAllocatedTableImpl(common, policy, NextCapacity(SooCapacity()), + /*blocked_element_count=*/0, /*force_infoz=*/true); PrepareInsertCommon(common); common.growth_info().OverwriteEmptyAsFull(); @@ -1693,6 +1772,16 @@ return SooSlotIndex(); } +// Returns the number of elements to block for the given capacity and reserved +// size. +size_t BlockedElementCount(size_t capacity, size_t reserved_size) { + if (!IsCapacityValidForBlockedElements(capacity)) { + return 0; + } + ABSL_SWISSTABLE_ASSERT(is_single_group(capacity)); + return CapacityToGrowth(capacity) - reserved_size; +} + // Resizes empty non-allocated table to the capacity to fit new_size elements. // Requires: // 1. `c.capacity() == policy.soo_capacity()`. @@ -1704,7 +1793,9 @@ size_t new_size) { ValidateMaxSize(new_size, policy.key_size, policy.slot_size); ABSL_ASSUME(new_size > 0); - ResizeEmptyNonAllocatedTableImpl(common, policy, SizeToCapacity(new_size), + const size_t new_capacity = SizeToCapacity(new_size); + ResizeEmptyNonAllocatedTableImpl(common, policy, new_capacity, + BlockedElementCount(new_capacity, new_size), /*force_infoz=*/false); // This is after resize, to ensure that we have completed the allocation // and have potentially sampled the hashtable. @@ -1760,8 +1851,43 @@ void ResizeAllocatedTableWithSeedChange( CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_capacity) { - ResizeNonSooImpl<ResizeNonSooMode::kGuaranteedAllocated>( - common, policy, new_capacity, common.infoz()); + ABSL_SWISSTABLE_ASSERT(IsValidCapacity(new_capacity)); + ABSL_SWISSTABLE_ASSERT(new_capacity > policy.soo_capacity()); + + const size_t old_capacity = common.capacity(); + ctrl_t* const old_ctrl = common.control(); + void* const old_slots = common.slot_array(); + const size_t old_blocked_element_count = common.blocked_element_count(); + + const size_t slot_size = policy.slot_size; + const size_t slot_align = policy.slot_align; + HashtablezInfoHandle infoz = common.infoz(); + const bool has_infoz = infoz.IsSampled(); + void* alloc = policy.get_char_alloc(common); + + common.set_capacity(new_capacity); + const auto [new_ctrl, new_slots] = + AllocBackingArray(common, policy, new_capacity, has_infoz, alloc, + /*blocked_element_count=*/0); + common.set_control(new_ctrl); + common.set_slots(new_slots); + common.generate_new_seed(has_infoz); + + size_t total_probe_length = 0; + ResetCtrl(common, slot_size, /*blocked_element_count=*/0); + ABSL_SWISSTABLE_ASSERT(old_capacity > 0); + total_probe_length = FindNewPositionsAndTransferSlots( + common, policy, old_ctrl, old_slots, old_capacity); + (*policy.dealloc)(alloc, old_capacity, old_ctrl, slot_size, slot_align, + has_infoz, old_blocked_element_count); + if (HasGrowthInfoForCapacity(new_capacity)) { + ResetGrowthLeft(GetGrowthInfoFromControl(new_ctrl), new_capacity, + common.size()); + } + + if (ABSL_PREDICT_FALSE(has_infoz)) { + ReportResizeToInfoz(common, infoz, total_probe_length); + } } void ReserveEmptyNonAllocatedTableToFitBucketCount( @@ -1770,6 +1896,7 @@ size_t new_capacity = NormalizeCapacity(bucket_count); ValidateMaxCapacity(new_capacity, policy.key_size, policy.slot_size); ResizeEmptyNonAllocatedTableImpl(common, policy, new_capacity, + /*blocked_element_count=*/0, /*force_infoz=*/false); } @@ -1796,7 +1923,8 @@ // We do not set control and slots in CommonFields yet to avoid overriding // SOO data. const auto [new_ctrl, new_slots] = AllocBackingArray( - common, policy, kNewCapacity, /*has_infoz=*/false, alloc); + common, policy, kNewCapacity, /*has_infoz=*/false, alloc, + /*blocked_element_count=*/0); PrepareInsertCommon(common); ABSL_SWISSTABLE_ASSERT(common.size() == 2); @@ -1894,6 +2022,7 @@ if (cap == policy.soo_capacity()) { if (common.empty()) { ResizeEmptyNonAllocatedTableImpl(common, policy, new_capacity, + /*blocked_element_count=*/0, /*force_infoz=*/false); } else { ResizeFullSooTable(common, policy, new_capacity, @@ -2103,7 +2232,7 @@ template void DeallocateBackingArray<BackingArrayAlignment(alignof(size_t)), std::allocator<char>>( void* alloc, size_t capacity, ctrl_t* ctrl, size_t slot_size, - size_t slot_align, bool had_infoz); + size_t slot_align, bool had_infoz, size_t blocked_element_count); } // namespace container_internal ABSL_NAMESPACE_END
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index a50a488..affe395 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -13,6 +13,7 @@ // limitations under the License. // // An open-addressing +// [https://en.wikipedia.org/wiki/Open_addressing] // hashtable with quadratic probing. // // This is a low level hashtable on top of which different interfaces can be @@ -364,6 +365,10 @@ constexpr size_t SooCapacity() { return 1; } // Maximum capacity of a table where we don't need to hash any keys. constexpr size_t MaxSmallCapacity() { return 1; } +// Maximum capacity of a table where we can use blocked elements. +constexpr size_t MaxCapacityWithBlockedElements() { + return Group::kWidth - 1; +} // Sentinel type to indicate SOO CommonFields construction. struct soo_tag_t {}; // Sentinel type to indicate SOO CommonFields construction with full size. @@ -385,6 +390,18 @@ return capacity <= MaxSmallCapacity(); } +// Whether a table fits entirely into a probing group. +// Arbitrary order of elements in such tables is correct. +constexpr bool is_single_group(size_t capacity) { + return capacity <= Group::kWidth; +} + +// Whether `cap` is a valid capacity for a table that can store blocked +// elements. +constexpr bool IsCapacityValidForBlockedElements(size_t cap) { + return !IsSmallCapacity(cap) && cap <= MaxCapacityWithBlockedElements(); +} + // Converts `n` into the next valid capacity, per `IsValidCapacity`. constexpr size_t NormalizeCapacity(size_t n) { return n ? ~size_t{} >> countl_zero(n) : 1; @@ -1015,13 +1032,15 @@ class RawHashSetLayout { public: explicit RawHashSetLayout(size_t capacity, size_t slot_size, - size_t slot_align, bool has_infoz) + size_t slot_align, bool has_infoz, + size_t blocked_element_count) : control_offset_( ControlOffset(has_infoz, HasGrowthInfoForCapacity(capacity))), generation_offset_(control_offset_ + NumControlBytes(capacity)), slot_offset_( AlignUpTo(generation_offset_ + NumGenerationBytes(), slot_align)), - alloc_size_(slot_offset_ + capacity * slot_size) { + alloc_size_(slot_offset_ + + (capacity - blocked_element_count) * slot_size) { ABSL_SWISSTABLE_ASSERT(IsValidCapacity(capacity)); ABSL_SWISSTABLE_ASSERT( slot_size <= @@ -1297,9 +1316,26 @@ CommonFieldsGenerationInfo::reset_reserved_growth(reservation, size()); } + // Returns the number of blocked elements in the table. + // Blocked elements are located at the end of the table and do not have + // corresponding slots. + // Control bytes are set to kSentinel for blocked elements. + size_t blocked_element_count() const { + size_t cap = capacity(); + if (!IsCapacityValidForBlockedElements(cap)) { + return 0; + } + ABSL_SWISSTABLE_ASSERT(is_single_group(cap)); + // Formula is valid because MaxCapacityWithBlockedElements is less than + // group width. On erase for single group tables, we always increment the + // growth left. + return CapacityToGrowth(cap) - size() - growth_left(); + } + // The size of the backing array allocation. size_t alloc_size(size_t slot_size, size_t slot_align) const { - return RawHashSetLayout(capacity(), slot_size, slot_align, has_infoz()) + return RawHashSetLayout(capacity(), slot_size, slot_align, has_infoz(), + blocked_element_count()) .alloc_size(); } @@ -1566,12 +1602,6 @@ size_t probe_length; }; -// Whether a table fits entirely into a probing group. -// Arbitrary order of elements in such tables is correct. -constexpr bool is_single_group(size_t capacity) { - return capacity <= Group::kWidth; -} - // The state for a probe sequence. // // Currently, the sequence is a triangular progression of the form @@ -1723,13 +1753,12 @@ return Allocate<AlignOfBackingArray>(static_cast<Alloc*>(alloc), n); } -// Note: we mark this function as ABSL_ATTRIBUTE_NOINLINE because we don't want -// it to be inlined into e.g. the destructor to save code size. template <size_t AlignOfBackingArray, typename Alloc> -ABSL_ATTRIBUTE_NOINLINE void DeallocateBackingArray( - void* alloc, size_t capacity, ctrl_t* ctrl, size_t slot_size, - size_t slot_align, bool had_infoz) { - RawHashSetLayout layout(capacity, slot_size, slot_align, had_infoz); +void DeallocateBackingArray(void* alloc, size_t capacity, ctrl_t* ctrl, + size_t slot_size, size_t slot_align, bool had_infoz, + size_t blocked_element_count) { + RawHashSetLayout layout(capacity, slot_size, slot_align, had_infoz, + blocked_element_count); void* backing_array = ctrl - layout.control_offset(); // Unpoison before returning the memory to the allocator. SanitizerUnpoisonMemoryRegion(backing_array, layout.alloc_size()); @@ -1737,6 +1766,9 @@ layout.alloc_size()); } +using DeallocBackingArrayFn = + decltype(&DeallocateBackingArray<8, std::allocator<char>>); + // PolicyFunctions bundles together some information for a particular // raw_hash_set<T, ...> instantiation. This information is passed to // type-erased functions that want to do small amounts of type-specific @@ -1766,8 +1798,7 @@ void* (*alloc)(void* alloc, size_t n); // Deallocates the backing store from common. - void (*dealloc)(void* alloc, size_t capacity, ctrl_t* ctrl, size_t slot_size, - size_t slot_align, bool had_infoz); + DeallocBackingArrayFn dealloc; // Implementation detail of GrowToNextCapacity. // Iterates over all full slots and transfers unprobed elements. @@ -1942,6 +1973,37 @@ void ClearBackingArray(CommonFields& c, const PolicyFunctions& policy, void* alloc, bool reuse); +using DestroySlotFn = void (*)(void* set, void* slot); + +// Destroys all full slots in the backing array. +// REQUIRES: !is_small(c.capacity()). +// REQUIRES: destroy_slot != nullptr. +void DestroySlots(CommonFields& c, size_t slot_size, + DestroySlotFn destroy_slot); + +// Deallocates the backing array and unregister infoz if necessary. +// REQUIRES: c.capacity > raw_hash_set::DefaultCapacity(). +void DeallocBackingArray(CommonFields& c, size_t slot_size, size_t slot_align, + DeallocBackingArrayFn dealloc, void* alloc); + +// NOTE: Destruct* functions couldn't use PolicyFunctions in order to support +// incomplete types. +// TODO(b/515666499): try to use PolicyFunctions since it makes code simpler and +// binary size smaller. + +// Destructs all elements and deallocates the backing array for SOO tables. +// REQUIRES: !c.is_small || !c.empty() +// REQUIRES: !c.is_small || destroy_slot != nullptr +void DestructSoo(CommonFields& c, size_t slot_size, size_t slot_align, + DestroySlotFn destroy_slot, DeallocBackingArrayFn dealloc, + void* alloc); + +// Destructs all elements and deallocates the backing array for non-SOO tables. +// REQUIRES: c.capacity > 0. +void DestructNonSoo(CommonFields& c, size_t slot_size, size_t slot_align, + DestroySlotFn destroy_slot, DeallocBackingArrayFn dealloc, + void* alloc); + // Type-erased versions of raw_hash_set::erase_meta_only_{small,large}. void EraseMetaOnlySmall(CommonFields& c, bool soo_enabled, size_t slot_size); void EraseMetaOnlyLarge(CommonFields& c, const ctrl_t* ctrl, size_t slot_size); @@ -2611,6 +2673,7 @@ } size_t max_size() const { return MaxValidSize(); } + // TODO(b/515666499): Type erase clear(). ABSL_ATTRIBUTE_REINITIALIZES void clear() { if (SwisstableGenerationsEnabled() && maybe_invalid_capacity().IsMovedFrom()) { @@ -2914,6 +2977,7 @@ erase_meta_only(it); } + // TODO(b/515666499): Type erase entire function or begin/end case. iterator erase(const_iterator first, const_iterator last) ABSL_ATTRIBUTE_LIFETIME_BOUND { AssertNotDebugCapacity(); @@ -3202,19 +3266,19 @@ }; template <typename... Args> - inline void construct(slot_type* slot, Args&&... args) { + void construct(slot_type* slot, Args&&... args) { common().RunWithReentrancyGuard([&] { allocator_type alloc(char_alloc_ref()); PolicyTraits::construct(&alloc, slot, std::forward<Args>(args)...); }); } - inline void destroy(slot_type* slot) { + void destroy(slot_type* slot) { common().RunWithReentrancyGuard([&] { allocator_type alloc(char_alloc_ref()); PolicyTraits::destroy(&alloc, slot); }); } - inline void transfer(slot_type* to, slot_type* from) { + void transfer(slot_type* to, slot_type* from) { common().RunWithReentrancyGuard([&] { allocator_type alloc(char_alloc_ref()); PolicyTraits::transfer(&alloc, to, from); @@ -3280,28 +3344,13 @@ void destroy_slots() { ABSL_SWISSTABLE_ASSERT(!is_small()); if (PolicyTraits::template destroy_is_trivial<Alloc>()) return; - auto destroy_slot = [&](const ctrl_t*, void* slot) { - this->destroy(static_cast<slot_type*>(slot)); - }; - if constexpr (SwisstableAssertAccessToDestroyedTable()) { - CommonFields common_copy(non_soo_tag_t{}, this->common()); - common().set_capacity(HashtableCapacity::CreateDestroyed()); - IterateOverFullSlots(common_copy, sizeof(slot_type), destroy_slot); - common().set_capacity(common_copy.capacity()); - } else { - IterateOverFullSlots(common(), sizeof(slot_type), destroy_slot); - } + DestroySlots(common(), sizeof(slot_type), get_destroy_slot_fn()); } void dealloc() { ABSL_SWISSTABLE_ASSERT(capacity() > DefaultCapacity()); - // Unpoison before returning the memory to the allocator. - SanitizerUnpoisonMemoryRegion(slot_array(), sizeof(slot_type) * capacity()); - infoz().Unregister(); - DeallocateBackingArray<BackingArrayAlignment(alignof(slot_type)), - CharAlloc>(&char_alloc_ref(), capacity(), control(), - sizeof(slot_type), alignof(slot_type), - common().has_infoz()); + DeallocBackingArray(common(), sizeof(slot_type), alignof(slot_type), + get_dealloc_backing_array_fn(), &char_alloc_ref()); } void destructor_impl() { @@ -3309,16 +3358,20 @@ maybe_invalid_capacity().IsMovedFrom()) { return; } - if (capacity() == 0) return; - if (is_small()) { - if (!empty()) { - ABSL_SWISSTABLE_IGNORE_UNINITIALIZED(destroy(single_slot())); + if constexpr (SooEnabled()) { + if (is_small() && + (PolicyTraits::template destroy_is_trivial<Alloc>() || empty())) { + return; } - if constexpr (SooEnabled()) return; + DestructSoo(common(), sizeof(slot_type), alignof(slot_type), + get_destroy_slot_fn(), get_dealloc_backing_array_fn(), + &char_alloc_ref()); } else { - destroy_slots(); + if (capacity() == 0) return; + DestructNonSoo(common(), sizeof(slot_type), alignof(slot_type), + get_destroy_slot_fn(), get_dealloc_backing_array_fn(), + &char_alloc_ref()); } - dealloc(); } // Erases, but does not destroy, the value pointed to by `it`. @@ -3794,6 +3847,16 @@ } } + static void destroy_slot_fn_impl(void* set, void* slot) { + auto* h = static_cast<raw_hash_set*>(set); + h->destroy(to_slot(slot)); + } + static constexpr DestroySlotFn get_destroy_slot_fn() { + return PolicyTraits::template destroy_is_trivial<Alloc>() + ? nullptr + : &raw_hash_set::destroy_slot_fn_impl; + } + // TODO(b/382423690): Try to type erase entire function or at least type erase // by GetKey + Hash for memcpyable types. // TODO(b/382423690): Try to type erase for big slots: sizeof(slot_type) > 16. @@ -3848,6 +3911,11 @@ } } + static constexpr DeallocBackingArrayFn get_dealloc_backing_array_fn() { + return &DeallocateBackingArray<BackingArrayAlignment(alignof(slot_type)), + CharAlloc>; + } + static const PolicyFunctions& GetPolicyFunctions() { static_assert(sizeof(slot_type) <= (std::numeric_limits<uint32_t>::max)(), "Slot size is too large. Use std::unique_ptr for value type " @@ -3877,7 +3945,7 @@ std::is_empty_v<Alloc> ? &GetRefForEmptyClass : &raw_hash_set::get_char_alloc_ref_fn, &AllocateBackingArray<kBackingArrayAlignment, CharAlloc>, - &DeallocateBackingArray<kBackingArrayAlignment, CharAlloc>, + get_dealloc_backing_array_fn(), &raw_hash_set::transfer_unprobed_elements_to_next_capacity_fn}; return value; } @@ -4042,15 +4110,13 @@ extern template void DeallocateBackingArray< BackingArrayAlignment(alignof(size_t)), std::allocator<char>>( void* alloc, size_t capacity, ctrl_t* ctrl, size_t slot_size, - size_t slot_align, bool had_infoz); + size_t slot_align, bool had_infoz, size_t blocked_element_count); } // namespace container_internal ABSL_NAMESPACE_END } // namespace absl #undef ABSL_SWISSTABLE_ENABLE_GENERATIONS -#undef ABSL_SWISSTABLE_IGNORE_UNINITIALIZED -#undef ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN #undef ABSL_SWISSTABLE_ASSERT #endif // ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 332f99d..59492ab 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -1117,6 +1117,116 @@ EXPECT_TRUE(t.empty()); } +TEST(Table, ReservedTableWithTombstonesDestructWell) { + constexpr int64_t kCoef = 17; + for (size_t capacity = Group::kWidth * 2 - 1; capacity < 256; + capacity = NextCapacity(capacity)) { + int64_t reserve_size = + static_cast<int64_t>(CapacityToGrowth(capacity) - capacity / 16); + IntTable t; + t.reserve(static_cast<size_t>(reserve_size)); + for (int64_t i = 0; i < reserve_size; ++i) { + ASSERT_TRUE(t.insert(i * kCoef).second); + } + ASSERT_EQ(t.size(), reserve_size); + ASSERT_EQ(t.capacity(), capacity); + // Erase and insert values until we get a tombstone. + for (int64_t i = reserve_size; i < static_cast<int64_t>(capacity) * 1000; + ++i) { + ASSERT_EQ(t.erase((i - reserve_size) * kCoef), 1); + if (RawHashSetTestOnlyAccess::CountTombstones(t) > 0) { + break; + } + ASSERT_TRUE(t.insert(i * kCoef).second); + } + ASSERT_GT(RawHashSetTestOnlyAccess::CountTombstones(t), 0); + } +} + +struct BadTwoValuesHash { + explicit BadTwoValuesHash(size_t other_value) : other_value(other_value) {} + size_t operator()(int64_t x) const { return x >= 0 ? 0 : other_value; } + size_t other_value; +}; + +struct BadTwoValuesHashTable + : raw_hash_set<IntPolicy, BadTwoValuesHash, std::equal_to<int64_t>, + std::allocator<int>> { + using Base = typename BadTwoValuesHashTable::raw_hash_set; + BadTwoValuesHashTable() = default; + using Base::Base; +}; + +TEST(Table, ReservedTableRehashWithoutGrowthWorksWell) { + if (SwisstableGenerationsEnabled()) { + GTEST_SKIP() << "Generations enabled, so rehash happening earlier."; + } + constexpr int64_t kCoef = 17; + int retries = 0; + for (size_t capacity = 31; capacity < 256; + capacity = NextCapacity(capacity)) { + SCOPED_TRACE(absl::StrCat("capacity: ", capacity)); + // Number of elements we keep empty in order to force a rehash without + // growth. RehashOrGrowToNextCapacityAndPrepareInsert grow if number of full + // slots is greater than 25/32 of capacity, so we leave 7/32 + 5 empty to + // have extra margin. + size_t empty_till_full = (capacity + 1) / 32 * 7 + 5; + int64_t reserve_size = + static_cast<int64_t>(CapacityToGrowth(capacity) - empty_till_full); + + BadTwoValuesHashTable t( + 0, + // Negative number goes to the end of the table. + // Positive numbers hash is 0, so the first Group::kWidth * 2 elements + // will be placed at the beginning of the table. + BadTwoValuesHash(static_cast<size_t>(reserve_size))); + // Remove seed to make table layout deterministic. + RawHashSetTestOnlyAccess::GetCommon(t).set_no_seed_for_testing(); + + t.reserve(static_cast<size_t>(reserve_size)); + for (int64_t i = 1; i <= reserve_size; ++i) { + ASSERT_TRUE(t.insert(i * kCoef).second); + } + ASSERT_EQ(t.size(), reserve_size); + ASSERT_EQ(t.capacity(), capacity); + bool rehashed = false; + int64_t last_erased = 0; + // We erase and insert until we get a lot of tombstones to force a rehash + // without growth. It happens relatively quickly because of the + // intentionally bad hash function that place numbers to the same slot + // depending on the sign. + for (int64_t i = 1; i <= reserve_size; ++i) { + SCOPED_TRACE(absl::StrCat("i: ", i)); + ASSERT_EQ(t.erase(i * kCoef), 1); + size_t tombstones_before = RawHashSetTestOnlyAccess::CountTombstones(t); + ASSERT_TRUE(t.insert(-i * kCoef).second); + size_t tombstones_after = RawHashSetTestOnlyAccess::CountTombstones(t); + if (tombstones_before > 1 && tombstones_after == 0) { + ASSERT_EQ(t.capacity(), capacity) << "capacity must be preserved"; + rehashed = true; + last_erased = i; + break; + } + } + if (!rehashed) { + // In debug mode rehashing may happen earlier with some probability. + // See ShouldRehashForBugDetection for details. + capacity = PreviousCapacity(capacity); + ++retries; + ASSERT_LT(retries, 50) << "Too many retries"; + continue; + } + // Verify that all elements are still in the table after rehash. + for (int64_t i = 1; i <= reserve_size; ++i) { + if (i <= last_erased) { + ASSERT_TRUE(t.contains(-i * kCoef)) << i; + } else { + ASSERT_TRUE(t.contains(i * kCoef)) << i; + } + } + } +} + TYPED_TEST(SooTest, EraseInSmallTables) { for (int64_t size = 0; size < 64; ++size) { TypeParam t; @@ -1193,46 +1303,51 @@ } TYPED_TEST(SooTest, ReserveTwice) { - for (size_t reserve_size = 0; reserve_size < 32; ++reserve_size) { - for (size_t reserve_size2 = reserve_size; reserve_size2 < 32; + for (int reserve_size = 0; reserve_size < 32; ++reserve_size) { + for (int reserve_size2 = reserve_size; reserve_size2 < 32; ++reserve_size2) { SCOPED_TRACE(absl::StrCat("reserve_size: ", reserve_size, ", reserve_size2: ", reserve_size2)); TypeParam t; - t.reserve(reserve_size); + t.reserve(static_cast<size_t>(reserve_size)); { // Insert first batch of elements. size_t cap = t.capacity(); - for (size_t i = 0; i < reserve_size; ++i) { - ASSERT_TRUE(t.insert(static_cast<int>(i)).second) << i; + for (int i = 1; i <= reserve_size; ++i) { + ASSERT_TRUE(t.insert(i).second) << i; } ASSERT_EQ(t.capacity(), cap); } - t.reserve(reserve_size2); + t.reserve(static_cast<size_t>(reserve_size2)); { // Insert second batch of elements. size_t cap = t.capacity(); - for (size_t i = reserve_size; i < reserve_size2; ++i) { - ASSERT_TRUE(t.insert(static_cast<int>(i)).second) << i; + for (int i = reserve_size + 1; i <= reserve_size2; ++i) { + ASSERT_TRUE(t.insert(i).second) << i; } ASSERT_EQ(t.capacity(), cap); } - for (size_t i = 0; i < reserve_size2; ++i) { - ASSERT_TRUE(t.contains(static_cast<int>(i))) << i; + for (int i = 1; i <= reserve_size2; ++i) { + ASSERT_TRUE(t.contains(i)) << i; + // Testing missing value to verify that we correctly have empty slots. + ASSERT_FALSE(t.contains(-i)) << i; } } } } TYPED_TEST(SooTest, GrowAfterReserve) { - for (size_t reserve_size = 1; reserve_size <= 150; ++reserve_size) { - size_t size = reserve_size + 1; + for (int reserve_size = 1; reserve_size <= 150; ++reserve_size) { TypeParam s; - s.reserve(reserve_size); - for (size_t i = 0; i < size; ++i) { - ASSERT_TRUE(s.insert(static_cast<int>(i)).second) << i; + s.reserve(static_cast<size_t>(reserve_size)); + int size = reserve_size + 1; + for (int i = 1; i <= size; ++i) { + ASSERT_TRUE(s.insert(i).second) << i; + // Testing missing value to verify that we correctly have empty slots. + ASSERT_FALSE(s.contains(-i)) << i; } EXPECT_EQ(s.size(), size); - for (size_t i = 0; i < size; ++i) { - ASSERT_TRUE(s.contains(static_cast<int>(i))) << i; + for (int i = 1; i <= size; ++i) { + ASSERT_TRUE(s.contains(i)) << i; + ASSERT_FALSE(s.contains(-i)) << i; } } } @@ -1313,23 +1428,23 @@ } TYPED_TEST(SmallTableResizeTest, ResizeGrowSmallTables) { - for (size_t source_size = 0; source_size < 32; ++source_size) { - for (size_t target_size = source_size; target_size < 32; ++target_size) { + for (int source_size = 0; source_size < 32; ++source_size) { + for (int target_size = source_size; target_size < 32; ++target_size) { for (bool rehash : {false, true}) { SCOPED_TRACE(absl::StrCat("source_size: ", source_size, ", target_size: ", target_size, ", rehash: ", rehash)); TypeParam t; - for (size_t i = 0; i < source_size; ++i) { - t.insert(static_cast<int>(i)); + for (int i = 0; i < source_size; ++i) { + t.insert(i); } if (rehash) { - t.rehash(target_size); + t.rehash(static_cast<size_t>(target_size)); } else { - t.reserve(target_size); + t.reserve(static_cast<size_t>(target_size)); } - for (size_t i = 0; i < source_size; ++i) { - ASSERT_TRUE(t.find(static_cast<int>(i)) != t.end()); + for (int i = 0; i < source_size; ++i) { + ASSERT_TRUE(t.contains(i)); EXPECT_EQ(*t.find(static_cast<int>(i)), static_cast<int>(i)); } }
diff --git a/absl/crc/BUILD.bazel b/absl/crc/BUILD.bazel index 49e916c..88b9ea2 100644 --- a/absl/crc/BUILD.bazel +++ b/absl/crc/BUILD.bazel
@@ -34,21 +34,6 @@ licenses(["notice"]) cc_library( - name = "cpu_detect", - srcs = [ - "internal/cpu_detect.cc", - ], - hdrs = ["internal/cpu_detect.h"], - copts = ABSL_DEFAULT_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - visibility = ["//visibility:private"], - deps = [ - "//absl/base", - "//absl/base:config", - ], -) - -cc_library( name = "crc_internal", srcs = [ "internal/crc.cc", @@ -63,9 +48,9 @@ linkopts = ABSL_DEFAULT_LINKOPTS, visibility = ["//visibility:private"], deps = [ - ":cpu_detect", "//absl/base:config", "//absl/base:core_headers", + "//absl/base:cpu_detect", "//absl/base:endian", "//absl/base:prefetch", "//absl/base:raw_logging_internal", @@ -92,11 +77,11 @@ linkopts = ABSL_DEFAULT_LINKOPTS, visibility = ["//visibility:public"], deps = [ - ":cpu_detect", ":crc_internal", ":non_temporal_memcpy", "//absl/base:config", "//absl/base:core_headers", + "//absl/base:cpu_detect", "//absl/base:endian", "//absl/base:prefetch", "//absl/strings",
diff --git a/absl/crc/CMakeLists.txt b/absl/crc/CMakeLists.txt index 034d0d0..28f0bab 100644 --- a/absl/crc/CMakeLists.txt +++ b/absl/crc/CMakeLists.txt
@@ -15,21 +15,6 @@ # Internal-only target, do not depend on directly. absl_cc_library( NAME - crc_cpu_detect - HDRS - "internal/cpu_detect.h" - SRCS - "internal/cpu_detect.cc" - COPTS - ${ABSL_DEFAULT_COPTS} - DEPS - absl::base - absl::config -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME crc_internal HDRS "internal/crc.h" @@ -41,7 +26,7 @@ COPTS ${ABSL_DEFAULT_COPTS} DEPS - absl::crc_cpu_detect + absl::base_cpu_detect absl::bits absl::config absl::core_headers @@ -67,7 +52,7 @@ COPTS ${ABSL_DEFAULT_COPTS} DEPS - absl::crc_cpu_detect + absl::base_cpu_detect absl::crc_internal absl::non_temporal_memcpy absl::config
diff --git a/absl/crc/internal/crc_memcpy_x86_arm_combined.cc b/absl/crc/internal/crc_memcpy_x86_arm_combined.cc index 247b3aa..fd3ce60 100644 --- a/absl/crc/internal/crc_memcpy_x86_arm_combined.cc +++ b/absl/crc/internal/crc_memcpy_x86_arm_combined.cc
@@ -54,10 +54,10 @@ #include "absl/base/attributes.h" #include "absl/base/config.h" +#include "absl/base/internal/cpu_detect.h" #include "absl/base/optimization.h" #include "absl/base/prefetch.h" #include "absl/crc/crc32c.h" -#include "absl/crc/internal/cpu_detect.h" #include "absl/crc/internal/crc32_x86_arm_combined_simd.h" #include "absl/crc/internal/crc_memcpy.h" #include "absl/strings/string_view.h" @@ -69,6 +69,9 @@ ABSL_NAMESPACE_BEGIN namespace crc_internal { +using ::absl::base_internal::CpuType; +using ::absl::base_internal::GetCpuType; + namespace { inline crc32c_t ShortCrcCopy(char* dst, const char* src, std::size_t length, @@ -427,6 +430,7 @@ case CpuType::kArmNeoverseN2: case CpuType::kArmNeoverseV1: case CpuType::kArmNeoverseV2: + case CpuType::kNvidiaGrace: return { /*.temporal=*/new AcceleratedCrcMemcpyEngine<3, 0>(), /*.non_temporal=*/new CrcNonTemporalMemcpyEngine(),
diff --git a/absl/crc/internal/crc_x86_arm_combined.cc b/absl/crc/internal/crc_x86_arm_combined.cc index 8140378..e44a009 100644 --- a/absl/crc/internal/crc_x86_arm_combined.cc +++ b/absl/crc/internal/crc_x86_arm_combined.cc
@@ -21,9 +21,9 @@ #include "absl/base/attributes.h" #include "absl/base/config.h" +#include "absl/base/internal/cpu_detect.h" #include "absl/base/internal/endian.h" #include "absl/base/prefetch.h" -#include "absl/crc/internal/cpu_detect.h" #include "absl/crc/internal/crc32_x86_arm_combined_simd.h" #include "absl/crc/internal/crc_internal.h" #include "absl/memory/memory.h" @@ -38,6 +38,10 @@ ABSL_NAMESPACE_BEGIN namespace crc_internal { +using ::absl::base_internal::CpuType; +using ::absl::base_internal::GetCpuType; +using ::absl::base_internal::SupportsArmCRC32PMULL; + #if defined(ABSL_INTERNAL_CAN_USE_SIMD_CRC32C) // Implementation details not exported outside of file @@ -772,7 +776,7 @@ case CpuType::kIntelIcelake: case CpuType::kIntelSapphirerapids: case CpuType::kIntelEmeraldrapids: - case CpuType::kIntelGraniterapidsap: + case CpuType::kIntelGraniterapids: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< 3, 2, 0, CutoffStrategy::Fold3>(); // PCLMULQDQ is slow, don't use it. @@ -785,6 +789,7 @@ case CpuType::kArmNeoverseN2: case CpuType::kArmNeoverseV1: case CpuType::kArmNeoverseN3: + case CpuType::kNvidiaGrace: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< 1, 1, 0, CutoffStrategy::Unroll64CRC>(); case CpuType::kAmpereSiryn:
diff --git a/absl/log/BUILD.bazel b/absl/log/BUILD.bazel index e6793b1..b1cff4b 100644 --- a/absl/log/BUILD.bazel +++ b/absl/log/BUILD.bazel
@@ -502,6 +502,7 @@ "//absl/log/internal:test_matchers", "//absl/strings", "//absl/strings:str_format", + "//absl/types:source_location", "@googletest//:gtest", "@googletest//:gtest_main", ],
diff --git a/absl/log/CMakeLists.txt b/absl/log/CMakeLists.txt index b271d09..e0a307b 100644 --- a/absl/log/CMakeLists.txt +++ b/absl/log/CMakeLists.txt
@@ -1017,6 +1017,7 @@ absl::log absl::log_internal_test_matchers absl::scoped_mock_log + absl::source_location absl::str_format absl::strings GTest::gmock_main
diff --git a/absl/log/check.h b/absl/log/check.h index 9e2219b..10674c9 100644 --- a/absl/log/check.h +++ b/absl/log/check.h
@@ -102,11 +102,11 @@ // Check failed: 2 * x == y (6 vs. 5) oops! // // The values must implement the appropriate comparison operator as well as -// `operator<<(std::ostream&, ...)`. Care is taken to ensure that each -// argument is evaluated exactly once, and that anything which is legal to pass -// as a function argument is legal here. In particular, the arguments may be -// temporary expressions which will end up being destroyed at the end of the -// statement, +// either `operator<<(std::ostream&, ...)` or `AbslStringify`. Care is taken to +// ensure that each argument is evaluated exactly once, and that anything which +// is legal to pass as a function argument is legal here. In particular, the +// arguments may be temporary expressions which will end up being destroyed at +// the end of the statement, // // Example: //
diff --git a/absl/log/internal/BUILD.bazel b/absl/log/internal/BUILD.bazel index 6995b26..bc47330 100644 --- a/absl/log/internal/BUILD.bazel +++ b/absl/log/internal/BUILD.bazel
@@ -111,10 +111,7 @@ "//absl:friends", "//absl/log:__pkg__", ], - deps = [ - "//absl/base:config", - "//absl/base:core_headers", - ], + deps = ["//absl/base:config"], ) cc_library(
diff --git a/absl/log/internal/log_message.h b/absl/log/internal/log_message.h index 7e2a86a..b9b533e 100644 --- a/absl/log/internal/log_message.h +++ b/absl/log/internal/log_message.h
@@ -179,6 +179,13 @@ LogMessage& operator<<(wchar_t* absl_nullable v); LogMessage& operator<<(wchar_t v); + // Overload for absl::SourceLocation or the std::source_location alias. + LogMessage& operator<<(const absl::SourceLocation& loc) { + OstreamView view(*data_); + view.stream() << loc.file_name() << ':' << loc.line(); + return *this; + } + // Handle stream manipulators e.g. std::endl. LogMessage& operator<<(std::ostream& (*absl_nonnull m)(std::ostream& os)); LogMessage& operator<<(std::ios_base& (*absl_nonnull m)(std::ios_base& os));
diff --git a/absl/log/log_format_test.cc b/absl/log/log_format_test.cc index b23d90f..06ce2f5 100644 --- a/absl/log/log_format_test.cc +++ b/absl/log/log_format_test.cc
@@ -41,6 +41,7 @@ #include "absl/strings/str_cat.h" #include "absl/strings/str_format.h" #include "absl/strings/string_view.h" +#include "absl/types/source_location.h" namespace { using ::absl::log_internal::AsString; @@ -291,6 +292,21 @@ LOG(INFO) << value.bits; } +TEST(SourceLocationTest, Format) { + absl::ScopedMockLog test_sink(absl::MockLogDefault::kDisallowUnexpected); + EXPECT_CALL(test_sink, Send).Times(0); + + absl::SourceLocation loc = absl::SourceLocation::current(); + std::string expected = absl::StrCat(__FILE__, ":", __LINE__ - 1); + + EXPECT_CALL(test_sink, Send(AllOf(TextMessage(Eq(expected)), + ENCODED_MESSAGE(HasValues(ElementsAre( + ValueWithStr(Eq(expected)))))))); + + test_sink.StartCapturingLogs(); + LOG(INFO) << loc; +} + // Ignore these test cases on GCC due to "is too small to hold all values ..." // warning. #if !defined(__GNUC__) || defined(__clang__)
diff --git a/absl/memory/memory.h b/absl/memory/memory.h index 7be4983..88320e5 100644 --- a/absl/memory/memory.h +++ b/absl/memory/memory.h
@@ -96,6 +96,11 @@ // should use `std::make_unique`. using std::make_unique; +#if defined(__cpp_lib_smart_ptr_for_overwrite) && \ + __cpp_lib_smart_ptr_for_overwrite >= 202002L +using std::make_unique_for_overwrite; +#else + namespace memory_internal { // Traits to select proper overload and return type for @@ -143,6 +148,8 @@ typename memory_internal::MakeUniqueResult<T>::invalid make_unique_for_overwrite(Args&&... /* args */) = delete; +#endif // __cpp_lib_smart_ptr_for_overwrite + // ----------------------------------------------------------------------------- // Function Template: RawPtr() // -----------------------------------------------------------------------------
diff --git a/absl/status/internal/status_internal.h b/absl/status/internal/status_internal.h index 2f615e7..2428069 100644 --- a/absl/status/internal/status_internal.h +++ b/absl/status/internal/status_internal.h
@@ -14,6 +14,8 @@ #ifndef ABSL_STATUS_INTERNAL_STATUS_INTERNAL_H_ #define ABSL_STATUS_INTERNAL_STATUS_INTERNAL_H_ +// IWYU pragma: private, include "absl/status/status.h" + #include <atomic> #include <cstdint> #include <memory>
diff --git a/absl/status/internal/status_matchers.h b/absl/status/internal/status_matchers.h index 2eafd13..d4b35cc 100644 --- a/absl/status/internal/status_matchers.h +++ b/absl/status/internal/status_matchers.h
@@ -30,20 +30,12 @@ ABSL_NAMESPACE_BEGIN namespace status_internal { -// TODO(b/323927127): Remove ABSL_REFACTOR_INLINE once callers are cleaned up -// and move it into a namespace like adl_barrier without types to avoid -// accidental ADL. -ABSL_REFACTOR_INLINE inline const absl::Status& GetStatus( - const absl::Status& status) { +inline const absl::Status& GetStatus(const absl::Status& status) { return status; } -// TODO(b/323927127): Remove ABSL_REFACTOR_INLINE once callers are cleaned up -// and move it into a namespace like adl_barrier without types to avoid -// accidental ADL. template <typename T> -ABSL_REFACTOR_INLINE const absl::Status& GetStatus( - const absl::StatusOr<T>& status) { +const absl::Status& GetStatus(const absl::StatusOr<T>& status) { return status.status(); }
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 805cfc2..4c974ce 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel
@@ -435,7 +435,6 @@ visibility = [ "//absl:friends", "//absl/status:__pkg__", - "//visibility:private", ], deps = [ ":string_view",
diff --git a/absl/strings/ascii.cc b/absl/strings/ascii.cc index 4cd9ff9..b5c7e19 100644 --- a/absl/strings/ascii.cc +++ b/absl/strings/ascii.cc
@@ -195,7 +195,7 @@ for (size_t i = 0; i < size; ++i) { unsigned char v = static_cast<unsigned char>(src[i]); - if ABSL_INTERNAL_CONSTEXPR_SINCE_CXX17 (Naive) { + if constexpr (Naive) { v ^= AsciiInAZRangeNaive<ToUpper>(v) ? kAsciiCaseBitFlip : 0; } else { v ^= AsciiInAZRange<ToUpper>(v) ? kAsciiCaseBitFlip : 0;
diff --git a/absl/strings/escaping.h b/absl/strings/escaping.h index aaacc28..4a23c13 100644 --- a/absl/strings/escaping.h +++ b/absl/strings/escaping.h
@@ -82,7 +82,7 @@ // CEscape() // -// Escapes a 'src' string using C-style escapes sequences +// Escapes a `src` string using C-style escapes sequences // (https://en.cppreference.com/w/cpp/language/escape), escaping other // non-printable/non-whitespace bytes as octal sequences (e.g. "\377"). // @@ -95,7 +95,7 @@ // CHexEscape() // -// Escapes a 'src' string using C-style escape sequences, escaping +// Escapes a `src` string using C-style escape sequences, escaping // other non-printable/non-whitespace bytes as hexadecimal sequences (e.g. // "\xFF"). // @@ -108,7 +108,7 @@ // Utf8SafeCEscape() // -// Escapes a 'src' string using C-style escape sequences, escaping bytes as +// Escapes a `src` string using C-style escape sequences, escaping bytes as // octal sequences, and passing through UTF-8 characters without conversion. // I.e., when encountering any bytes with their high bit set, this function // will not escape those values, whether or not they are valid UTF-8. @@ -116,14 +116,14 @@ // Utf8SafeCHexEscape() // -// Escapes a 'src' string using C-style escape sequences, escaping bytes as +// Escapes a `src` string using C-style escape sequences, escaping bytes as // hexadecimal sequences, and passing through UTF-8 characters without // conversion. std::string Utf8SafeCHexEscape(absl::string_view src); // Base64Escape() // -// Encodes a `src` string into a base64-encoded 'dest' string with padding +// Encodes a `src` string into a base64-encoded `dest` string with padding // characters. This function conforms with RFC 4648 section 4 (base64) and RFC // 2045. std::string Base64Escape(absl::string_view src); @@ -137,7 +137,7 @@ // WebSafeBase64Escape() // // Encodes a `src` string into a base64 string, like Base64Escape() does, but -// outputs '-' instead of '+' and '_' instead of '/', and does not pad 'dest'. +// outputs '-' instead of '+' and '_' instead of '/', and does not pad `dest`. // This function conforms with RFC 4648 section 5 (base64url). std::string WebSafeBase64Escape(absl::string_view src); [[deprecated( @@ -159,10 +159,11 @@ // WebSafeBase64Unescape() // // Converts a `src` string encoded in "web safe" Base64 (RFC 4648 section 5) to -// its binary equivalent, writing it to a `dest` buffer. If `src` contains -// invalid characters, `dest` is cleared and returns `false`. If padding is -// included (note that `WebSafeBase64Escape()` does not produce it), it must be -// correct. In the padding, '=' and '.' are treated identically. +// its binary equivalent, writing it to a `dest` buffer, returning `true` on +// success. If `src` contains invalid characters, `dest` is cleared and returns +// `false`. If padding is included (note that `WebSafeBase64Escape()` does not +// produce it), it must be correct. In the padding, '=' and '.' are treated +// identically. bool WebSafeBase64Unescape(absl::string_view src, std::string* absl_nonnull dest);
diff --git a/absl/strings/str_format.h b/absl/strings/str_format.h index ffa7f11..18a21a9 100644 --- a/absl/strings/str_format.h +++ b/absl/strings/str_format.h
@@ -49,7 +49,8 @@ // * A `FormatSpec` class template fully encapsulates a format string and its // type arguments and is usually provided to `str_format` functions as a // variadic argument of type `FormatSpec<Arg...>`. The `FormatSpec<Args...>` -// template is evaluated at compile-time, providing type safety. +// template is evaluated at compile-time, providing type safety (supported +// on GCC and Clang; on MSVC, these checks are deferred to runtime). // * A `ParsedFormat` instance, which encapsulates a specific, pre-compiled // format string for a specific set of type(s), and which can be passed // between API boundaries. (The `FormatSpec` type should not be used @@ -275,7 +276,9 @@ // any string-like argument, so `std::string`, `std::wstring`, // `absl::string_view`, `const char*`, and `const wchar_t*` are all accepted. // Likewise, `%d` accepts any integer-like argument, etc. - +// +// Note: Compile-time format string checking is supported on GCC and +// Clang. On MSVC, these checks are performed at runtime instead. template <typename... Args> using FormatSpec = str_format_internal::FormatSpecTemplate< str_format_internal::ArgumentToConv<Args>()...>;
diff --git a/absl/time/format.cc b/absl/time/format.cc index bd06f8f..aa2ae2c 100644 --- a/absl/time/format.cc +++ b/absl/time/format.cc
@@ -18,6 +18,7 @@ #include <cstdint> #include <utility> +#include "absl/strings/ascii.h" #include "absl/strings/match.h" #include "absl/strings/string_view.h" #include "absl/time/internal/cctz/include/cctz/time_zone.h" @@ -36,8 +37,8 @@ namespace { -const char kInfiniteFutureStr[] = "infinite-future"; -const char kInfinitePastStr[] = "infinite-past"; +constexpr absl::string_view kInfiniteFutureStr = "infinite-future"; +constexpr absl::string_view kInfinitePastStr = "infinite-past"; struct cctz_parts { cctz::time_point<cctz::seconds> sec; @@ -99,30 +100,19 @@ // the fields with respect to the given TimeZone. bool ParseTime(absl::string_view format, absl::string_view input, absl::TimeZone tz, absl::Time* time, std::string* err) { - auto strip_leading_space = [](absl::string_view* sv) { - while (!sv->empty()) { - if (!std::isspace(sv->front())) return; - sv->remove_prefix(1); - } - }; - - // Portable toolchains means we don't get nice constexpr here. - struct Literal { - const char* name; - size_t size; + static constexpr struct Literal { + absl::string_view name; absl::Time value; + } kLiterals[] = { + {kInfiniteFutureStr, InfiniteFuture()}, + {kInfinitePastStr, InfinitePast()}, }; - static Literal literals[] = { - {kInfiniteFutureStr, strlen(kInfiniteFutureStr), InfiniteFuture()}, - {kInfinitePastStr, strlen(kInfinitePastStr), InfinitePast()}, - }; - strip_leading_space(&input); - for (const auto& lit : literals) { - if (absl::StartsWith(input, absl::string_view(lit.name, lit.size))) { - absl::string_view tail = input; - tail.remove_prefix(lit.size); - strip_leading_space(&tail); - if (tail.empty()) { + input = StripLeadingAsciiWhitespace(input); + for (const auto& lit : kLiterals) { + if (absl::StartsWith(input, lit.name)) { + absl::string_view tail = input.substr(lit.name.size()); + // The trailing portion must be empty or whitespace. + if (StripLeadingAsciiWhitespace(tail).empty()) { *time = lit.value; return true; } @@ -150,13 +140,6 @@ std::string AbslUnparseFlag(absl::Time t) { return absl::FormatTime(RFC3339_full, t, absl::UTCTimeZone()); } -bool ParseFlag(const std::string& text, absl::Time* t, std::string* error) { - return absl::ParseTime(RFC3339_full, text, absl::UTCTimeZone(), t, error); -} - -std::string UnparseFlag(absl::Time t) { - return absl::FormatTime(RFC3339_full, t, absl::UTCTimeZone()); -} ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/time/format_test.cc b/absl/time/format_test.cc index 0e145a8..38c0e3d 100644 --- a/absl/time/format_test.cc +++ b/absl/time/format_test.cc
@@ -250,6 +250,13 @@ EXPECT_FALSE( absl::ParseTime("%Y", std::string("2026\0payload", 12), &t, &err)); EXPECT_THAT(err, HasSubstr("Illegal trailing data")); + + // High-bit character test for sign-extension bugs. + for (int i = 128; i < 256; ++i) { + char c = static_cast<char>(i); + std::string input = std::string(1, c) + "2015-01-02"; + EXPECT_FALSE(absl::ParseTime("%Y-%m-%d", input, &t, &err)); + } } TEST(ParseTime, ExtendedSeconds) {
diff --git a/absl/types/BUILD.bazel b/absl/types/BUILD.bazel index ff76679..2670c0c 100644 --- a/absl/types/BUILD.bazel +++ b/absl/types/BUILD.bazel
@@ -47,11 +47,6 @@ ) cc_library( - name = "bad_any_cast", - deprecation = "bad_any_cast dependency is empty can be removed", -) - -cc_library( name = "source_location", srcs = ["source_location.cc"], hdrs = ["source_location.h"], @@ -193,11 +188,6 @@ ) cc_library( - name = "bad_optional_access", - deprecation = "bad_optional_access dependency is empty can be removed", -) - -cc_library( name = "variant", hdrs = ["variant.h"], copts = ABSL_DEFAULT_COPTS, @@ -209,11 +199,6 @@ ], ) -cc_library( - name = "bad_variant_access", - deprecation = "bad_variant_access dependency is empty can be removed", -) - cc_test( name = "variant_test", size = "small",
diff --git a/absl/types/internal/span.h b/absl/types/internal/span.h index 208216c..711fdef 100644 --- a/absl/types/internal/span.h +++ b/absl/types/internal/span.h
@@ -86,13 +86,13 @@ typename std::enable_if<!std::is_const<T>::value, int>::type; template <template <typename> class SpanT, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool EqualImpl(SpanT<T> a, SpanT<T> b) { +constexpr bool EqualImpl(SpanT<T> a, SpanT<T> b) { static_assert(std::is_const<T>::value, ""); return std::equal(a.begin(), a.end(), b.begin(), b.end()); } template <template <typename> class SpanT, typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool LessThanImpl(SpanT<T> a, SpanT<T> b) { +constexpr bool LessThanImpl(SpanT<T> a, SpanT<T> b) { // We can't use value_type since that is remove_cv_t<T>, so we go the long way // around. static_assert(std::is_const<T>::value, "");
diff --git a/absl/types/span.h b/absl/types/span.h index 2327962..e2f0c9a 100644 --- a/absl/types/span.h +++ b/absl/types/span.h
@@ -531,165 +531,157 @@ // operator== template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator==(Span<T> a, Span<T> b) { +constexpr bool operator==(Span<T> a, Span<T> b) { return span_internal::EqualImpl<Span, const T>(a, b); } template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator==(Span<const T> a, - Span<T> b) { +constexpr bool operator==(Span<const T> a, Span<T> b) { return span_internal::EqualImpl<Span, const T>(a, b); } template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator==(Span<T> a, - Span<const T> b) { +constexpr bool operator==(Span<T> a, Span<const T> b) { return span_internal::EqualImpl<Span, const T>(a, b); } template < typename T, typename U, typename = span_internal::EnableIfConvertibleTo<U, absl::Span<const T>>> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator==(const U& a, Span<T> b) { +constexpr bool operator==(const U& a, Span<T> b) { return span_internal::EqualImpl<Span, const T>(a, b); } template < typename T, typename U, typename = span_internal::EnableIfConvertibleTo<U, absl::Span<const T>>> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator==(Span<T> a, const U& b) { +constexpr bool operator==(Span<T> a, const U& b) { return span_internal::EqualImpl<Span, const T>(a, b); } // operator!= template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator!=(Span<T> a, Span<T> b) { +constexpr bool operator!=(Span<T> a, Span<T> b) { return !(a == b); } template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator!=(Span<const T> a, - Span<T> b) { +constexpr bool operator!=(Span<const T> a, Span<T> b) { return !(a == b); } template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator!=(Span<T> a, - Span<const T> b) { +constexpr bool operator!=(Span<T> a, Span<const T> b) { return !(a == b); } template < typename T, typename U, typename = span_internal::EnableIfConvertibleTo<U, absl::Span<const T>>> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator!=(const U& a, Span<T> b) { +constexpr bool operator!=(const U& a, Span<T> b) { return !(a == b); } template < typename T, typename U, typename = span_internal::EnableIfConvertibleTo<U, absl::Span<const T>>> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator!=(Span<T> a, const U& b) { +constexpr bool operator!=(Span<T> a, const U& b) { return !(a == b); } // operator< template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator<(Span<T> a, Span<T> b) { +constexpr bool operator<(Span<T> a, Span<T> b) { return span_internal::LessThanImpl<Span, const T>(a, b); } template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator<(Span<const T> a, Span<T> b) { +constexpr bool operator<(Span<const T> a, Span<T> b) { return span_internal::LessThanImpl<Span, const T>(a, b); } template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator<(Span<T> a, Span<const T> b) { +constexpr bool operator<(Span<T> a, Span<const T> b) { return span_internal::LessThanImpl<Span, const T>(a, b); } template < typename T, typename U, typename = span_internal::EnableIfConvertibleTo<U, absl::Span<const T>>> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator<(const U& a, Span<T> b) { +constexpr bool operator<(const U& a, Span<T> b) { return span_internal::LessThanImpl<Span, const T>(a, b); } template < typename T, typename U, typename = span_internal::EnableIfConvertibleTo<U, absl::Span<const T>>> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator<(Span<T> a, const U& b) { +constexpr bool operator<(Span<T> a, const U& b) { return span_internal::LessThanImpl<Span, const T>(a, b); } // operator> template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator>(Span<T> a, Span<T> b) { +constexpr bool operator>(Span<T> a, Span<T> b) { return b < a; } template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator>(Span<const T> a, Span<T> b) { +constexpr bool operator>(Span<const T> a, Span<T> b) { return b < a; } template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator>(Span<T> a, Span<const T> b) { +constexpr bool operator>(Span<T> a, Span<const T> b) { return b < a; } template < typename T, typename U, typename = span_internal::EnableIfConvertibleTo<U, absl::Span<const T>>> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator>(const U& a, Span<T> b) { +constexpr bool operator>(const U& a, Span<T> b) { return b < a; } template < typename T, typename U, typename = span_internal::EnableIfConvertibleTo<U, absl::Span<const T>>> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator>(Span<T> a, const U& b) { +constexpr bool operator>(Span<T> a, const U& b) { return b < a; } // operator<= template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator<=(Span<T> a, Span<T> b) { +constexpr bool operator<=(Span<T> a, Span<T> b) { return !(b < a); } template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator<=(Span<const T> a, - Span<T> b) { +constexpr bool operator<=(Span<const T> a, Span<T> b) { return !(b < a); } template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator<=(Span<T> a, - Span<const T> b) { +constexpr bool operator<=(Span<T> a, Span<const T> b) { return !(b < a); } template < typename T, typename U, typename = span_internal::EnableIfConvertibleTo<U, absl::Span<const T>>> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator<=(const U& a, Span<T> b) { +constexpr bool operator<=(const U& a, Span<T> b) { return !(b < a); } template < typename T, typename U, typename = span_internal::EnableIfConvertibleTo<U, absl::Span<const T>>> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator<=(Span<T> a, const U& b) { +constexpr bool operator<=(Span<T> a, const U& b) { return !(b < a); } // operator>= template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator>=(Span<T> a, Span<T> b) { +constexpr bool operator>=(Span<T> a, Span<T> b) { return !(a < b); } template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator>=(Span<const T> a, - Span<T> b) { +constexpr bool operator>=(Span<const T> a, Span<T> b) { return !(a < b); } template <typename T> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator>=(Span<T> a, - Span<const T> b) { +constexpr bool operator>=(Span<T> a, Span<const T> b) { return !(a < b); } template < typename T, typename U, typename = span_internal::EnableIfConvertibleTo<U, absl::Span<const T>>> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator>=(const U& a, Span<T> b) { +constexpr bool operator>=(const U& a, Span<T> b) { return !(a < b); } template < typename T, typename U, typename = span_internal::EnableIfConvertibleTo<U, absl::Span<const T>>> -ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool operator>=(Span<T> a, const U& b) { +constexpr bool operator>=(Span<T> a, const U& b) { return !(a < b); }