Warning: This file is not a C or C++ file. It does not have highlighting.

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_cast.h>
33#include <__bit/bit_log2.h>
34#include <__config>
35#include <__cstddef/size_t.h>
36#include <__functional/identity.h>
37#include <__iterator/access.h>
38#include <__iterator/distance.h>
39#include <__iterator/iterator_traits.h>
40#include <__iterator/move_iterator.h>
41#include <__iterator/next.h>
42#include <__iterator/reverse_iterator.h>
43#include <__numeric/partial_sum.h>
44#include <__type_traits/decay.h>
45#include <__type_traits/enable_if.h>
46#include <__type_traits/invoke.h>
47#include <__type_traits/is_assignable.h>
48#include <__type_traits/is_enum.h>
49#include <__type_traits/is_integral.h>
50#include <__type_traits/is_unsigned.h>
51#include <__type_traits/make_unsigned.h>
52#include <__type_traits/void_t.h>
53#include <__utility/declval.h>
54#include <__utility/forward.h>
55#include <__utility/integer_sequence.h>
56#include <__utility/move.h>
57#include <__utility/pair.h>
58#include <climits>
59#include <cstdint>
60#include <initializer_list>
61#include <limits>
62
63#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
64# pragma GCC system_header
65#endif
66
67_LIBCPP_PUSH_MACROS
68#include <__undef_macros>
69
70_LIBCPP_BEGIN_NAMESPACE_STD
71
72#if _LIBCPP_STD_VER >= 14
73
74template <class _InputIterator, class _OutputIterator>
75_LIBCPP_HIDE_FROM_ABI constexpr pair<_OutputIterator, __iter_value_type<_InputIterator>>
76__partial_sum_max(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
77 if (__first == __last)
78 return {__result, 0};
79
80 auto __max = *__first;
81 __iter_value_type<_InputIterator> __sum = *__first;
82 *__result = __sum;
83
84 while (++__first != __last) {
85 if (__max < *__first) {
86 __max = *__first;
87 }
88 __sum = std::move(__sum) + *__first;
89 *++__result = __sum;
90 }
91 return {++__result, __max};
92}
93
94template <class _Value, class _Map, class _Radix>
95struct __radix_sort_traits {
96 using __image_type _LIBCPP_NODEBUG = decay_t<__invoke_result_t<_Map, _Value>>;
97 static_assert(is_unsigned<__image_type>::value);
98
99 using __radix_type _LIBCPP_NODEBUG = decay_t<__invoke_result_t<_Radix, __image_type>>;
100 static_assert(is_integral<__radix_type>::value);
101
102 static constexpr auto __radix_value_range = numeric_limits<__radix_type>::max() + 1;
103 static constexpr auto __radix_size = std::__bit_log2<uint64_t>(__radix_value_range);
104 static constexpr auto __radix_count = sizeof(__image_type) * CHAR_BIT / __radix_size;
105};
106
107template <class _Value, class _Map>
108struct __counting_sort_traits {
109 using __image_type _LIBCPP_NODEBUG = decay_t<__invoke_result_t<_Map, _Value>>;
110 static_assert(is_unsigned<__image_type>::value);
111
112 static constexpr const auto __value_range = numeric_limits<__image_type>::max() + 1;
113 static constexpr auto __radix_size = std::__bit_log2<uint64_t>(__value_range);
114};
115
116template <class _Radix, class _Integer>
117_LIBCPP_HIDE_FROM_ABI constexpr auto __nth_radix(size_t __radix_number, _Radix __radix, _Integer __n) {
118 static_assert(is_unsigned<_Integer>::value);
119 using __traits = __counting_sort_traits<_Integer, _Radix>;
120
121 return __radix(static_cast<_Integer>(__n >> __traits::__radix_size * __radix_number));
122}
123
124template <class _ForwardIterator, class _Map, class _RandomAccessIterator>
125_LIBCPP_HIDE_FROM_ABI constexpr void
126__collect(_ForwardIterator __first, _ForwardIterator __last, _Map __map, _RandomAccessIterator __counters) {
127 using __value_type = __iter_value_type<_ForwardIterator>;
128 using __traits = __counting_sort_traits<__value_type, _Map>;
129
130 std::for_each(__first, __last, [&__counters, &__map](const auto& __preimage) { ++__counters[__map(__preimage)]; });
131
132 const auto __counters_end = __counters + __traits::__value_range;
133 std::partial_sum(__counters, __counters_end, __counters);
134}
135
136template <class _ForwardIterator, class _RandomAccessIterator1, class _Map, class _RandomAccessIterator2>
137_LIBCPP_HIDE_FROM_ABI constexpr void
138__dispose(_ForwardIterator __first,
139 _ForwardIterator __last,
140 _RandomAccessIterator1 __result,
141 _Map __map,
142 _RandomAccessIterator2 __counters) {
143 std::for_each(__first, __last, [&__result, &__counters, &__map](auto&& __preimage) {
144 auto __index = __counters[__map(__preimage)]++;
145 __result[__index] = std::move(__preimage);
146 });
147}
148
149template <class _ForwardIterator,
150 class _Map,
151 class _Radix,
152 class _RandomAccessIterator1,
153 class _RandomAccessIterator2,
154 size_t... _Radices>
155_LIBCPP_HIDE_FROM_ABI constexpr bool __collect_impl(
156 _ForwardIterator __first,
157 _ForwardIterator __last,
158 _Map __map,
159 _Radix __radix,
160 _RandomAccessIterator1 __counters,
161 _RandomAccessIterator2 __maximums,
162 index_sequence<_Radices...>) {
163 using __value_type = __iter_value_type<_ForwardIterator>;
164 constexpr auto __radix_value_range = __radix_sort_traits<__value_type, _Map, _Radix>::__radix_value_range;
165
166 auto __previous = numeric_limits<__invoke_result_t<_Map, __value_type>>::min();
167 auto __is_sorted = true;
168 std::for_each(__first, __last, [&__counters, &__map, &__radix, &__previous, &__is_sorted](const auto& __value) {
169 auto __current = __map(__value);
170 __is_sorted &= (__current >= __previous);
171 __previous = __current;
172
173 (++__counters[_Radices][std::__nth_radix(_Radices, __radix, __current)], ...);
174 });
175
176 ((__maximums[_Radices] =
177 std::__partial_sum_max(__counters[_Radices], __counters[_Radices] + __radix_value_range, __counters[_Radices])
178 .second),
179 ...);
180
181 return __is_sorted;
182}
183
184template <class _ForwardIterator, class _Map, class _Radix, class _RandomAccessIterator1, class _RandomAccessIterator2>
185_LIBCPP_HIDE_FROM_ABI constexpr bool
186__collect(_ForwardIterator __first,
187 _ForwardIterator __last,
188 _Map __map,
189 _Radix __radix,
190 _RandomAccessIterator1 __counters,
191 _RandomAccessIterator2 __maximums) {
192 using __value_type = __iter_value_type<_ForwardIterator>;
193 constexpr auto __radix_count = __radix_sort_traits<__value_type, _Map, _Radix>::__radix_count;
194 return std::__collect_impl(
195 __first, __last, __map, __radix, __counters, __maximums, make_index_sequence<__radix_count>());
196}
197
198template <class _BidirectionalIterator, class _RandomAccessIterator1, class _Map, class _RandomAccessIterator2>
199_LIBCPP_HIDE_FROM_ABI constexpr void __dispose_backward(
200 _BidirectionalIterator __first,
201 _BidirectionalIterator __last,
202 _RandomAccessIterator1 __result,
203 _Map __map,
204 _RandomAccessIterator2 __counters) {
205 std::for_each(std::make_reverse_iterator(__last),
206 std::make_reverse_iterator(__first),
207 [&__result, &__counters, &__map](auto&& __preimage) {
208 auto __index = --__counters[__map(__preimage)];
209 __result[__index] = std::move(__preimage);
210 });
211}
212
213template <class _ForwardIterator, class _RandomAccessIterator, class _Map>
214_LIBCPP_HIDE_FROM_ABI constexpr _RandomAccessIterator
215__counting_sort_impl(_ForwardIterator __first, _ForwardIterator __last, _RandomAccessIterator __result, _Map __map) {
216 using __value_type = __iter_value_type<_ForwardIterator>;
217 using __traits = __counting_sort_traits<__value_type, _Map>;
218
219 __iter_diff_t<_RandomAccessIterator> __counters[__traits::__value_range + 1] = {0};
220
221 std::__collect(__first, __last, __map, std::next(std::begin(__counters)));
222 std::__dispose(__first, __last, __result, __map, std::begin(__counters));
223
224 return __result + __counters[__traits::__value_range];
225}
226
227template <class _RandomAccessIterator1,
228 class _RandomAccessIterator2,
229 class _Map,
230 class _Radix,
231 enable_if_t< __radix_sort_traits<__iter_value_type<_RandomAccessIterator1>, _Map, _Radix>::__radix_count == 1,
232 int> = 0>
233_LIBCPP_HIDE_FROM_ABI constexpr void __radix_sort_impl(
234 _RandomAccessIterator1 __first,
235 _RandomAccessIterator1 __last,
236 _RandomAccessIterator2 __buffer,
237 _Map __map,
238 _Radix __radix) {
239 auto __buffer_end = std::__counting_sort_impl(__first, __last, __buffer, [&__map, &__radix](const auto& __value) {
240 return __radix(__map(__value));
241 });
242
243 std::move(__buffer, __buffer_end, __first);
244}
245
246template <
247 class _RandomAccessIterator1,
248 class _RandomAccessIterator2,
249 class _Map,
250 class _Radix,
251 enable_if_t< __radix_sort_traits<__iter_value_type<_RandomAccessIterator1>, _Map, _Radix>::__radix_count % 2 == 0,
252 int> = 0 >
253_LIBCPP_HIDE_FROM_ABI constexpr void __radix_sort_impl(
254 _RandomAccessIterator1 __first,
255 _RandomAccessIterator1 __last,
256 _RandomAccessIterator2 __buffer_begin,
257 _Map __map,
258 _Radix __radix) {
259 using __value_type = __iter_value_type<_RandomAccessIterator1>;
260 using __traits = __radix_sort_traits<__value_type, _Map, _Radix>;
261
262 __iter_diff_t<_RandomAccessIterator1> __counters[__traits::__radix_count][__traits::__radix_value_range] = {{0}};
263 __iter_diff_t<_RandomAccessIterator1> __maximums[__traits::__radix_count] = {0};
264 const auto __is_sorted = std::__collect(__first, __last, __map, __radix, __counters, __maximums);
265 if (!__is_sorted) {
266 const auto __range_size = std::distance(__first, __last);
267 auto __buffer_end = __buffer_begin + __range_size;
268 for (size_t __radix_number = 0; __radix_number < __traits::__radix_count; __radix_number += 2) {
269 const auto __n0th_is_single = __maximums[__radix_number] == __range_size;
270 const auto __n1th_is_single = __maximums[__radix_number + 1] == __range_size;
271
272 if (__n0th_is_single && __n1th_is_single) {
273 continue;
274 }
275
276 if (__n0th_is_single) {
277 std::move(__first, __last, __buffer_begin);
278 } else {
279 auto __n0th = [__radix_number, &__map, &__radix](const auto& __v) {
280 return std::__nth_radix(__radix_number, __radix, __map(__v));
281 };
282 std::__dispose_backward(__first, __last, __buffer_begin, __n0th, __counters[__radix_number]);
283 }
284
285 if (__n1th_is_single) {
286 std::move(__buffer_begin, __buffer_end, __first);
287 } else {
288 auto __n1th = [__radix_number, &__map, &__radix](const auto& __v) {
289 return std::__nth_radix(__radix_number + 1, __radix, __map(__v));
290 };
291 std::__dispose_backward(__buffer_begin, __buffer_end, __first, __n1th, __counters[__radix_number + 1]);
292 }
293 }
294 }
295}
296
297_LIBCPP_HIDE_FROM_ABI constexpr auto __shift_to_unsigned(bool __b) { return __b; }
298
299template <class _Ip>
300_LIBCPP_HIDE_FROM_ABI constexpr auto __shift_to_unsigned(_Ip __n) {
301 constexpr const auto __min_value = numeric_limits<_Ip>::min();
302 return static_cast<make_unsigned_t<_Ip> >(__n ^ __min_value);
303}
304
305template <size_t _Size>
306struct __unsigned_integer_of_size;
307
308template <>
309struct __unsigned_integer_of_size<1> {
310 using type _LIBCPP_NODEBUG = uint8_t;
311};
312
313template <>
314struct __unsigned_integer_of_size<2> {
315 using type _LIBCPP_NODEBUG = uint16_t;
316};
317
318template <>
319struct __unsigned_integer_of_size<4> {
320 using type _LIBCPP_NODEBUG = uint32_t;
321};
322
323template <>
324struct __unsigned_integer_of_size<8> {
325 using type _LIBCPP_NODEBUG = uint64_t;
326};
327
328# if _LIBCPP_HAS_INT128
329template <>
330struct __unsigned_integer_of_size<16> {
331 using type _LIBCPP_NODEBUG = unsigned __int128;
332};
333# endif
334
335template <size_t _Size>
336using __unsigned_integer_of_size_t _LIBCPP_NODEBUG = typename __unsigned_integer_of_size<_Size>::type;
337
338template <class _Sc>
339using __unsigned_representation_for_t _LIBCPP_NODEBUG = __unsigned_integer_of_size_t<sizeof(_Sc)>;
340
341// The function `__to_ordered_integral` is defined for integers and IEEE 754 floating-point numbers.
342// Returns an integer representation such that for any `x` and `y` such that `x < y`, the expression
343// `__to_ordered_integral(x) < __to_ordered_integral(y)` is true, where `x`, `y` are integers or IEEE 754 floats.
344template <class _Integral, enable_if_t< is_integral<_Integral>::value, int> = 0>
345_LIBCPP_HIDE_FROM_ABI constexpr auto __to_ordered_integral(_Integral __n) {
346 return __n;
347}
348
349// An overload for IEEE 754 floating-point numbers
350
351// For the floats conforming to IEEE 754 (IEC 559) standard, we know that:
352// 1. The bit representation of positive floats directly reflects their order:
353// When comparing floats by magnitude, the number with the larger exponent is greater, and if the exponents are
354// equal, the one with the larger mantissa is greater.
355// 2. The bit representation of negative floats reflects their reverse order (for the same reasons).
356// 3. The most significant bit (sign bit) is zero for positive floats and one for negative floats. Therefore, in the raw
357// bit representation, any negative number will be greater than any positive number.
358
359// The only exception from this rule is `NaN`, which is unordered by definition.
360
361// Based on the above, to obtain correctly ordered integral representation of floating-point numbers, we need to:
362// 1. Invert the bit representation (including the sign bit) of negative floats to switch from reverse order to direct
363// order;
364// 2. Invert the sign bit for positive floats.
365
366// Thus, in final integral representation, we have reversed the order for negative floats and made all negative floats
367// smaller than all positive numbers (by inverting the sign bit).
368template <class _Floating, enable_if_t< numeric_limits<_Floating>::is_iec559, int> = 0>
369_LIBCPP_HIDE_FROM_ABI constexpr auto __to_ordered_integral(_Floating __f) {
370 using __integral_type = __unsigned_representation_for_t<_Floating>;
371 constexpr auto __bit_count = std::numeric_limits<__integral_type>::digits;
372 constexpr auto __sign_bit_mask = static_cast<__integral_type>(__integral_type{1} << (__bit_count - 1));
373
374 const auto __u = std::__bit_cast<__integral_type>(__f);
375
376 return static_cast<__integral_type>(__u & __sign_bit_mask ? ~__u : __u ^ __sign_bit_mask);
377}
378
379// There may exist user-defined comparison for enum, so we cannot compare enums just like integers.
380template <class _Enum, enable_if_t< is_enum<_Enum>::value, int> = 0>
381_LIBCPP_HIDE_FROM_ABI constexpr auto __to_ordered_integral(_Enum __e) = delete;
382
383// `long double` varies significantly across platforms and compilers, making it practically
384// impossible to determine its actual bit width for conversion to an ordered integer.
385inline _LIBCPP_HIDE_FROM_ABI constexpr auto __to_ordered_integral(long double) = delete;
386
387template <class _Tp, class = void>
388inline const bool __is_ordered_integer_representable_v = false;
389
390template <class _Tp>
391inline const bool
392 __is_ordered_integer_representable_v<_Tp, __void_t<decltype(std::__to_ordered_integral(std::declval<_Tp>()))>> =
393 true;
394
395struct __low_byte_fn {
396 template <class _Ip>
397 _LIBCPP_HIDE_FROM_ABI constexpr uint8_t operator()(_Ip __integer) const {
398 static_assert(is_unsigned<_Ip>::value);
399
400 return static_cast<uint8_t>(__integer & 0xff);
401 }
402};
403
404template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Map, class _Radix>
405_LIBCPP_HIDE_FROM_ABI constexpr void
406__radix_sort(_RandomAccessIterator1 __first,
407 _RandomAccessIterator1 __last,
408 _RandomAccessIterator2 __buffer,
409 _Map __map,
410 _Radix __radix) {
411 auto __map_to_unsigned = [__map = std::move(__map)](const auto& __x) {
412 return std::__shift_to_unsigned(__map(std::__to_ordered_integral(__x)));
413 };
414 std::__radix_sort_impl(__first, __last, __buffer, __map_to_unsigned, __radix);
415}
416
417template <class _RandomAccessIterator1, class _RandomAccessIterator2>
418_LIBCPP_HIDE_FROM_ABI constexpr void
419__radix_sort(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __buffer) {
420 std::__radix_sort(__first, __last, __buffer, __identity{}, __low_byte_fn{});
421}
422
423#endif // _LIBCPP_STD_VER >= 14
424
425_LIBCPP_END_NAMESPACE_STD
426
427_LIBCPP_POP_MACROS
428
429#endif // _LIBCPP___ALGORITHM_RADIX_SORT_H
430

Warning: This file is not a C or C++ file. It does not have highlighting.

source code of libcxx/include/__algorithm/radix_sort.h