1 // -*- C++ -*- 2 //===----------------------------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP___ALGORITHM_RADIX_SORT_H 11 #define _LIBCPP___ALGORITHM_RADIX_SORT_H 12 13 // This is an implementation of classic LSD radix sort algorithm, running in linear time and using `O(max(N, M))` 14 // additional memory, where `N` is size of an input range, `M` - maximum value of 15 // a radix of the sorted integer type. Type of the radix and its maximum value are determined at compile time 16 // based on type returned by function `__radix`. The default radix is uint8. 17 18 // The algorithm is equivalent to several consecutive calls of counting sort for each 19 // radix of the sorted numbers from low to high byte. 20 // The algorithm uses a temporary buffer of size equal to size of the input range. Each `i`-th pass 21 // of the algorithm sorts values by `i`-th radix and moves values to the temporary buffer (for each even `i`, counted 22 // from zero), or moves them back to the initial range (for each odd `i`). If there is only one radix in sorted integers 23 // (e.g. int8), the sorted values are placed to the buffer, and then moved back to the initial range. 24 25 // The implementation also has several optimizations: 26 // - the counters for the counting sort are calculated in one pass for all radices; 27 // - if all values of a radix are the same, we do not sort that radix, and just move items to the buffer; 28 // - if two consecutive radices satisfies condition above, we do nothing for these two radices. 29 30 #include <__algorithm/for_each.h> 31 #include <__algorithm/move.h> 32 #include <__bit/bit_log2.h> 33 #include <__bit/countl.h> 34 #include <__config> 35 #include <__functional/identity.h> 36 #include <__iterator/distance.h> 37 #include <__iterator/iterator_traits.h> 38 #include <__iterator/move_iterator.h> 39 #include <__iterator/next.h> 40 #include <__iterator/reverse_iterator.h> 41 #include <__numeric/partial_sum.h> 42 #include <__type_traits/decay.h> 43 #include <__type_traits/enable_if.h> 44 #include <__type_traits/invoke.h> 45 #include <__type_traits/is_assignable.h> 46 #include <__type_traits/is_integral.h> 47 #include <__type_traits/is_unsigned.h> 48 #include <__type_traits/make_unsigned.h> 49 #include <__utility/forward.h> 50 #include <__utility/integer_sequence.h> 51 #include <__utility/move.h> 52 #include <__utility/pair.h> 53 #include <climits> 54 #include <cstdint> 55 #include <initializer_list> 56 #include <limits> 57 58 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 59 # pragma GCC system_header 60 #endif 61 62 _LIBCPP_PUSH_MACROS 63 #include <__undef_macros> 64 65 _LIBCPP_BEGIN_NAMESPACE_STD 66 67 #if _LIBCPP_STD_VER >= 14 68 69 template <class _InputIterator, class _OutputIterator> 70 _LIBCPP_HIDE_FROM_ABI pair<_OutputIterator, __iter_value_type<_InputIterator>> 71 __partial_sum_max(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { 72 if (__first == __last) 73 return {__result, 0}; 74 75 auto __max = *__first; 76 __iter_value_type<_InputIterator> __sum = *__first; 77 *__result = __sum; 78 79 while (++__first != __last) { 80 if (__max < *__first) { 81 __max = *__first; 82 } 83 __sum = std::move(__sum) + *__first; 84 *++__result = __sum; 85 } 86 return {++__result, __max}; 87 } 88 89 template <class _Value, class _Map, class _Radix> 90 struct __radix_sort_traits { 91 using __image_type _LIBCPP_NODEBUG = decay_t<__invoke_result_t<_Map, _Value>>; 92 static_assert(is_unsigned<__image_type>::value); 93 94 using __radix_type _LIBCPP_NODEBUG = decay_t<__invoke_result_t<_Radix, __image_type>>; 95 static_assert(is_integral<__radix_type>::value); 96 97 static constexpr auto __radix_value_range = numeric_limits<__radix_type>::max() + 1; 98 static constexpr auto __radix_size = std::__bit_log2<uint64_t>(__radix_value_range); 99 static constexpr auto __radix_count = sizeof(__image_type) * CHAR_BIT / __radix_size; 100 }; 101 102 template <class _Value, class _Map> 103 struct __counting_sort_traits { 104 using __image_type _LIBCPP_NODEBUG = decay_t<__invoke_result_t<_Map, _Value>>; 105 static_assert(is_unsigned<__image_type>::value); 106 107 static constexpr const auto __value_range = numeric_limits<__image_type>::max() + 1; 108 static constexpr auto __radix_size = std::__bit_log2<uint64_t>(__value_range); 109 }; 110 111 template <class _Radix, class _Integer> 112 _LIBCPP_HIDE_FROM_ABI auto __nth_radix(size_t __radix_number, _Radix __radix, _Integer __n) { 113 static_assert(is_unsigned<_Integer>::value); 114 using __traits = __counting_sort_traits<_Integer, _Radix>; 115 116 return __radix(static_cast<_Integer>(__n >> __traits::__radix_size * __radix_number)); 117 } 118 119 template <class _ForwardIterator, class _Map, class _RandomAccessIterator> 120 _LIBCPP_HIDE_FROM_ABI void 121 __collect(_ForwardIterator __first, _ForwardIterator __last, _Map __map, _RandomAccessIterator __counters) { 122 using __value_type = __iter_value_type<_ForwardIterator>; 123 using __traits = __counting_sort_traits<__value_type, _Map>; 124 125 std::for_each(__first, __last, [&__counters, &__map](const auto& __preimage) { ++__counters[__map(__preimage)]; }); 126 127 const auto __counters_end = __counters + __traits::__value_range; 128 std::partial_sum(__counters, __counters_end, __counters); 129 } 130 131 template <class _ForwardIterator, class _RandomAccessIterator1, class _Map, class _RandomAccessIterator2> 132 _LIBCPP_HIDE_FROM_ABI void 133 __dispose(_ForwardIterator __first, 134 _ForwardIterator __last, 135 _RandomAccessIterator1 __result, 136 _Map __map, 137 _RandomAccessIterator2 __counters) { 138 std::for_each(__first, __last, [&__result, &__counters, &__map](auto&& __preimage) { 139 auto __index = __counters[__map(__preimage)]++; 140 __result[__index] = std::move(__preimage); 141 }); 142 } 143 144 template <class _ForwardIterator, 145 class _Map, 146 class _Radix, 147 class _RandomAccessIterator1, 148 class _RandomAccessIterator2, 149 size_t... _Radices> 150 _LIBCPP_HIDE_FROM_ABI bool __collect_impl( 151 _ForwardIterator __first, 152 _ForwardIterator __last, 153 _Map __map, 154 _Radix __radix, 155 _RandomAccessIterator1 __counters, 156 _RandomAccessIterator2 __maximums, 157 index_sequence<_Radices...>) { 158 using __value_type = __iter_value_type<_ForwardIterator>; 159 constexpr auto __radix_value_range = __radix_sort_traits<__value_type, _Map, _Radix>::__radix_value_range; 160 161 auto __previous = numeric_limits<__invoke_result_t<_Map, __value_type>>::min(); 162 auto __is_sorted = true; 163 std::for_each(__first, __last, [&__counters, &__map, &__radix, &__previous, &__is_sorted](const auto& __value) { 164 auto __current = __map(__value); 165 __is_sorted &= (__current >= __previous); 166 __previous = __current; 167 168 (++__counters[_Radices][std::__nth_radix(_Radices, __radix, __current)], ...); 169 }); 170 171 ((__maximums[_Radices] = 172 std::__partial_sum_max(__counters[_Radices], __counters[_Radices] + __radix_value_range, __counters[_Radices]) 173 .second), 174 ...); 175 176 return __is_sorted; 177 } 178 179 template <class _ForwardIterator, class _Map, class _Radix, class _RandomAccessIterator1, class _RandomAccessIterator2> 180 _LIBCPP_HIDE_FROM_ABI bool 181 __collect(_ForwardIterator __first, 182 _ForwardIterator __last, 183 _Map __map, 184 _Radix __radix, 185 _RandomAccessIterator1 __counters, 186 _RandomAccessIterator2 __maximums) { 187 using __value_type = __iter_value_type<_ForwardIterator>; 188 constexpr auto __radix_count = __radix_sort_traits<__value_type, _Map, _Radix>::__radix_count; 189 return std::__collect_impl( 190 __first, __last, __map, __radix, __counters, __maximums, make_index_sequence<__radix_count>()); 191 } 192 193 template <class _BidirectionalIterator, class _RandomAccessIterator1, class _Map, class _RandomAccessIterator2> 194 _LIBCPP_HIDE_FROM_ABI void __dispose_backward( 195 _BidirectionalIterator __first, 196 _BidirectionalIterator __last, 197 _RandomAccessIterator1 __result, 198 _Map __map, 199 _RandomAccessIterator2 __counters) { 200 std::for_each(std::make_reverse_iterator(__last), 201 std::make_reverse_iterator(__first), 202 [&__result, &__counters, &__map](auto&& __preimage) { 203 auto __index = --__counters[__map(__preimage)]; 204 __result[__index] = std::move(__preimage); 205 }); 206 } 207 208 template <class _ForwardIterator, class _RandomAccessIterator, class _Map> 209 _LIBCPP_HIDE_FROM_ABI _RandomAccessIterator 210 __counting_sort_impl(_ForwardIterator __first, _ForwardIterator __last, _RandomAccessIterator __result, _Map __map) { 211 using __value_type = __iter_value_type<_ForwardIterator>; 212 using __traits = __counting_sort_traits<__value_type, _Map>; 213 214 __iter_diff_t<_RandomAccessIterator> __counters[__traits::__value_range + 1] = {0}; 215 216 std::__collect(__first, __last, __map, std::next(std::begin(__counters))); 217 std::__dispose(__first, __last, __result, __map, std::begin(__counters)); 218 219 return __result + __counters[__traits::__value_range]; 220 } 221 222 template <class _RandomAccessIterator1, 223 class _RandomAccessIterator2, 224 class _Map, 225 class _Radix, 226 enable_if_t< __radix_sort_traits<__iter_value_type<_RandomAccessIterator1>, _Map, _Radix>::__radix_count == 1, 227 int> = 0> 228 _LIBCPP_HIDE_FROM_ABI void __radix_sort_impl( 229 _RandomAccessIterator1 __first, 230 _RandomAccessIterator1 __last, 231 _RandomAccessIterator2 __buffer, 232 _Map __map, 233 _Radix __radix) { 234 auto __buffer_end = std::__counting_sort_impl(__first, __last, __buffer, [&__map, &__radix](const auto& __value) { 235 return __radix(__map(__value)); 236 }); 237 238 std::move(__buffer, __buffer_end, __first); 239 } 240 241 template < 242 class _RandomAccessIterator1, 243 class _RandomAccessIterator2, 244 class _Map, 245 class _Radix, 246 enable_if_t< __radix_sort_traits<__iter_value_type<_RandomAccessIterator1>, _Map, _Radix>::__radix_count % 2 == 0, 247 int> = 0 > 248 _LIBCPP_HIDE_FROM_ABI void __radix_sort_impl( 249 _RandomAccessIterator1 __first, 250 _RandomAccessIterator1 __last, 251 _RandomAccessIterator2 __buffer_begin, 252 _Map __map, 253 _Radix __radix) { 254 using __value_type = __iter_value_type<_RandomAccessIterator1>; 255 using __traits = __radix_sort_traits<__value_type, _Map, _Radix>; 256 257 __iter_diff_t<_RandomAccessIterator1> __counters[__traits::__radix_count][__traits::__radix_value_range] = {{0}}; 258 __iter_diff_t<_RandomAccessIterator1> __maximums[__traits::__radix_count] = {0}; 259 const auto __is_sorted = std::__collect(__first, __last, __map, __radix, __counters, __maximums); 260 if (!__is_sorted) { 261 const auto __range_size = std::distance(__first, __last); 262 auto __buffer_end = __buffer_begin + __range_size; 263 for (size_t __radix_number = 0; __radix_number < __traits::__radix_count; __radix_number += 2) { 264 const auto __n0th_is_single = __maximums[__radix_number] == __range_size; 265 const auto __n1th_is_single = __maximums[__radix_number + 1] == __range_size; 266 267 if (__n0th_is_single && __n1th_is_single) { 268 continue; 269 } 270 271 if (__n0th_is_single) { 272 std::move(__first, __last, __buffer_begin); 273 } else { 274 auto __n0th = [__radix_number, &__map, &__radix](const auto& __v) { 275 return std::__nth_radix(__radix_number, __radix, __map(__v)); 276 }; 277 std::__dispose_backward(__first, __last, __buffer_begin, __n0th, __counters[__radix_number]); 278 } 279 280 if (__n1th_is_single) { 281 std::move(__buffer_begin, __buffer_end, __first); 282 } else { 283 auto __n1th = [__radix_number, &__map, &__radix](const auto& __v) { 284 return std::__nth_radix(__radix_number + 1, __radix, __map(__v)); 285 }; 286 std::__dispose_backward(__buffer_begin, __buffer_end, __first, __n1th, __counters[__radix_number + 1]); 287 } 288 } 289 } 290 } 291 292 _LIBCPP_HIDE_FROM_ABI constexpr auto __shift_to_unsigned(bool __b) { return __b; } 293 294 template <class _Ip> 295 _LIBCPP_HIDE_FROM_ABI constexpr auto __shift_to_unsigned(_Ip __n) { 296 constexpr const auto __min_value = numeric_limits<_Ip>::min(); 297 return static_cast<make_unsigned_t<_Ip> >(__n ^ __min_value); 298 } 299 300 struct __low_byte_fn { 301 template <class _Ip> 302 _LIBCPP_HIDE_FROM_ABI constexpr uint8_t operator()(_Ip __integer) const { 303 static_assert(is_unsigned<_Ip>::value); 304 305 return static_cast<uint8_t>(__integer & 0xff); 306 } 307 }; 308 309 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Map, class _Radix> 310 _LIBCPP_HIDE_FROM_ABI void 311 __radix_sort(_RandomAccessIterator1 __first, 312 _RandomAccessIterator1 __last, 313 _RandomAccessIterator2 __buffer, 314 _Map __map, 315 _Radix __radix) { 316 auto __map_to_unsigned = [__map = std::move(__map)](const auto& __x) { return std::__shift_to_unsigned(__map(__x)); }; 317 std::__radix_sort_impl(__first, __last, __buffer, __map_to_unsigned, __radix); 318 } 319 320 template <class _RandomAccessIterator1, class _RandomAccessIterator2> 321 _LIBCPP_HIDE_FROM_ABI void 322 __radix_sort(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __buffer) { 323 std::__radix_sort(__first, __last, __buffer, __identity{}, __low_byte_fn{}); 324 } 325 326 #endif // _LIBCPP_STD_VER >= 14 327 328 _LIBCPP_END_NAMESPACE_STD 329 330 _LIBCPP_POP_MACROS 331 332 #endif // _LIBCPP___ALGORITHM_RADIX_SORT_H 333