2 * sgen-qsort.h: Fast inline sorting
4 * Copyright (C) 2014 Xamarin Inc
6 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
8 #ifndef __MONO_SGENQSORT_H__
9 #define __MONO_SGENQSORT_H__
11 #define DEF_QSORT_INLINE(NAME,ARRAY_TYPE,COMPARE_FUN) \
12 static size_t partition_##NAME (ARRAY_TYPE base[], size_t nel) { \
13 size_t pivot_idx = nel >> 1; \
15 ARRAY_TYPE pivot = base [pivot_idx]; \
16 { ARRAY_TYPE tmp = base [pivot_idx]; base [pivot_idx] = base [nel - 1]; base [nel - 1] = tmp; } \
18 for (i = 0; i < nel - 1; ++i) { \
19 if (COMPARE_FUN (base [i], pivot) <= 0) { \
20 { ARRAY_TYPE tmp = base [i]; base [i] = base [s]; base [s] = tmp; } \
24 { ARRAY_TYPE tmp = base [s]; base [s] = base [nel - 1]; base [nel - 1] = tmp; } \
27 static void rec_##NAME (ARRAY_TYPE base[], size_t nel) { \
31 pivot_idx = partition_##NAME (base, nel); \
32 rec_##NAME (base, pivot_idx); \
33 if (pivot_idx < nel) \
34 rec_##NAME (&base[pivot_idx + 1], nel - pivot_idx - 1); \
36 static void qsort_##NAME (ARRAY_TYPE base[], size_t nel) { \
37 rec_##NAME (base, nel); \