//===----------------------------------------------------------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// #ifndef _LIBCPP___ALGORITHM_SORT_H #define _LIBCPP___ALGORITHM_SORT_H #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/iter_swap.h> #include <__algorithm/iterator_operations.h> #include <__algorithm/min_element.h> #include <__algorithm/partial_sort.h> #include <__algorithm/unwrap_iter.h> #include <__assert> #include <__bit/blsr.h> #include <__bit/countl.h> #include <__bit/countr.h> #include <__config> #include <__debug_utils/randomize_range.h> #include <__debug_utils/strict_weak_ordering_check.h> #include <__functional/operations.h> #include <__functional/ranges_operations.h> #include <__iterator/iterator_traits.h> #include <__type_traits/conditional.h> #include <__type_traits/desugars_to.h> #include <__type_traits/disjunction.h> #include <__type_traits/is_arithmetic.h> #include <__type_traits/is_constant_evaluated.h> #include <__type_traits/is_trivially_copyable.h> #include <__utility/move.h> #include <__utility/pair.h> #include <climits> #include <cstdint> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header #endif _LIBCPP_PUSH_MACROS #include <__undef_macros> _LIBCPP_BEGIN_NAMESPACE_STD __use_branchless_sort; namespace __detail { // Size in bits for the bitset in use. enum { … }; } // namespace __detail // Ensures that __c(*__x, *__y) is true by swapping *__x and *__y if necessary. template <class _Compare, class _RandomAccessIterator> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool __cond_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _Compare __c) { … } // Ensures that *__x, *__y and *__z are ordered according to the comparator __c, // under the assumption that *__y and *__z are already ordered. template <class _Compare, class _RandomAccessIterator> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool __partially_sorted_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _RandomAccessIterator __z, _Compare __c) { … } // stable, 2-3 compares, 0-2 swaps template <class, class _Compare, class _RandomAccessIterator, __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>, int> = 0> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool __sort3(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _Compare __c) { … } template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>, int> = 0> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool __sort3(_RandomAccessIterator __x, _RandomAccessIterator __y, _RandomAccessIterator __z, _Compare __c) { … } // x <= y && y <= z // stable, 3-6 compares, 0-5 swaps template <class, class _Compare, class _RandomAccessIterator, __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>, int> = 0> inline _LIBCPP_HIDE_FROM_ABI void __sort4(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _RandomAccessIterator __x4, _Compare __c) { … } template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>, int> = 0> inline _LIBCPP_HIDE_FROM_ABI void __sort4(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _RandomAccessIterator __x4, _Compare __c) { … } // stable, 4-10 compares, 0-9 swaps template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>, int> = 0> inline _LIBCPP_HIDE_FROM_ABI void __sort5(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) { … } template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>, int> = 0> inline _LIBCPP_HIDE_FROM_ABI void __sort5(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __comp) { … } // Assumes size > 0 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) { … } // Sort the iterator range [__first, __last) using the comparator __comp using // the insertion sort algorithm. template <class _AlgPolicy, class _Compare, class _BidirectionalIterator> _LIBCPP_HIDE_FROM_ABI void __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) { … } // Sort the iterator range [__first, __last) using the comparator __comp using // the insertion sort algorithm. Insertion sort has two loops, outer and inner. // The implementation below has no bounds check (unguarded) for the inner loop. // Assumes that there is an element in the position (__first - 1) and that each // element in the input range is greater or equal to the element at __first - 1. template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> _LIBCPP_HIDE_FROM_ABI void __insertion_sort_unguarded(_RandomAccessIterator const __first, _RandomAccessIterator __last, _Compare __comp) { … } template <class _AlgPolicy, class _Comp, class _RandomAccessIterator> _LIBCPP_HIDE_FROM_ABI bool __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) { … } template <class _AlgPolicy, class _RandomAccessIterator> inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos( _RandomAccessIterator __first, _RandomAccessIterator __last, uint64_t& __left_bitset, uint64_t& __right_bitset) { … } template <class _Compare, class _RandomAccessIterator, class _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type> inline _LIBCPP_HIDE_FROM_ABI void __populate_left_bitset(_RandomAccessIterator __first, _Compare __comp, _ValueType& __pivot, uint64_t& __left_bitset) { … } template <class _Compare, class _RandomAccessIterator, class _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type> inline _LIBCPP_HIDE_FROM_ABI void __populate_right_bitset(_RandomAccessIterator __lm1, _Compare __comp, _ValueType& __pivot, uint64_t& __right_bitset) { … } template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type> inline _LIBCPP_HIDE_FROM_ABI void __bitset_partition_partial_blocks( _RandomAccessIterator& __first, _RandomAccessIterator& __lm1, _Compare __comp, _ValueType& __pivot, uint64_t& __left_bitset, uint64_t& __right_bitset) { … } template <class _AlgPolicy, class _RandomAccessIterator> inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos_within( _RandomAccessIterator& __first, _RandomAccessIterator& __lm1, uint64_t& __left_bitset, uint64_t& __right_bitset) { … } // Partition [__first, __last) using the comparator __comp. *__first has the // chosen pivot. Elements that are equivalent are kept to the left of the // pivot. Returns the iterator for the pivot and a bool value which is true if // the provided range is already sorted, false otherwise. We assume that the // length of the range is at least three elements. // // __bitset_partition uses bitsets for storing outcomes of the comparisons // between the pivot and other elements. template <class _AlgPolicy, class _RandomAccessIterator, class _Compare> _LIBCPP_HIDE_FROM_ABI std::pair<_RandomAccessIterator, bool> __bitset_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { … } // Partition [__first, __last) using the comparator __comp. *__first has the // chosen pivot. Elements that are equivalent are kept to the right of the // pivot. Returns the iterator for the pivot and a bool value which is true if // the provided range is already sorted, false otherwise. We assume that the // length of the range is at least three elements. template <class _AlgPolicy, class _RandomAccessIterator, class _Compare> _LIBCPP_HIDE_FROM_ABI std::pair<_RandomAccessIterator, bool> __partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { … } // Similar to the above function. Elements equivalent to the pivot are put to // the left of the pivot. Returns the iterator to the pivot element. template <class _AlgPolicy, class _RandomAccessIterator, class _Compare> _LIBCPP_HIDE_FROM_ABI _RandomAccessIterator __partition_with_equals_on_left(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { … } // The main sorting function. Implements introsort combined with other ideas: // - option of using block quick sort for partitioning, // - guarded and unguarded insertion sort for small lengths, // - Tuckey's ninther technique for computing the pivot, // - check on whether partition was not required. // The implementation is partly based on Orson Peters' pattern-defeating // quicksort, published at: <https://github.com/orlp/pdqsort>. template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, bool _UseBitSetPartition> void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __depth, bool __leftmost = true) { … } template <typename _Number> inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) { … } template <class _Comp, class _RandomAccessIterator> void __sort(_RandomAccessIterator, _RandomAccessIterator, _Comp); extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<char>&, char*>(char*, char*, __less<char>&); #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&); #endif extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&); extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&); extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<short>&, short*>(short*, short*, __less<short>&); extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&); extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<int>&, int*>(int*, int*, __less<int>&); extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&); extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<long>&, long*>(long*, long*, __less<long>&); extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&); extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&); extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned long long>&, unsigned long long*>( unsigned long long*, unsigned long long*, __less<unsigned long long>&); extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<float>&, float*>(float*, float*, __less<float>&); extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<double>&, double*>(double*, double*, __less<double>&); extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&); template <class _AlgPolicy, class _RandomAccessIterator, class _Comp> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __sort_dispatch(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { … } __is_any_of; __sort_is_specialized_in_library; template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0> _LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, __less<>&) { … } template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0> _LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, less<_Type>&) { … } #if _LIBCPP_STD_VER >= 14 template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0> _LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, less<>&) { … } #endif #if _LIBCPP_STD_VER >= 20 template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0> _LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, ranges::less&) { … } #endif template <class _AlgPolicy, class _RandomAccessIterator, class _Comp> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { … } template <class _RandomAccessIterator, class _Comp> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) { … } template <class _RandomAccessIterator> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { … } _LIBCPP_END_NAMESPACE_STD _LIBCPP_POP_MACROS #endif // _LIBCPP___ALGORITHM_SORT_H
Codebase Browser
chromium