/**
|
* \file
|
* Fast inline sorting
|
*
|
* Copyright (C) 2014 Xamarin Inc
|
*
|
* Licensed under the MIT license. See LICENSE file in the project root for full license information.
|
*/
|
#ifndef __MONO_SGENQSORT_H__
|
#define __MONO_SGENQSORT_H__
|
|
/* Copied from non-inline implementation in sgen-qsort.c */
|
#define DEF_QSORT_INLINE(name, type, compare) \
|
static inline void \
|
qsort_swap_##name (type array[], const ssize_t i, const ssize_t j, type *const swap_tmp) \
|
{ \
|
*swap_tmp = array [i]; \
|
array [i] = array [j]; \
|
array [j] = *swap_tmp; \
|
} \
|
\
|
static void \
|
qsort_rec_##name ( \
|
type array[], \
|
ssize_t begin, \
|
ssize_t end, \
|
type *const pivot_tmp, \
|
type *const swap_tmp) \
|
{ \
|
ssize_t left, right, middle, pivot; \
|
while (begin < end) { \
|
left = begin; \
|
right = end; \
|
middle = begin + (end - begin) / 2; \
|
if (compare (array [middle], array [left]) < 0) \
|
qsort_swap_##name (array, middle, left, swap_tmp); \
|
if (compare (array [right], array [left]) < 0) \
|
qsort_swap_##name (array, right, left, swap_tmp); \
|
if (compare (array [right], array [middle]) < 0) \
|
qsort_swap_##name (array, right, middle, swap_tmp); \
|
pivot = middle; \
|
*pivot_tmp = array [pivot]; \
|
for (;;) { \
|
while (left <= right && compare (array [left], *pivot_tmp) <= 0) \
|
++left; \
|
while (left <= right && compare (array [right], *pivot_tmp) > 0) \
|
--right; \
|
if (left > right) \
|
break; \
|
qsort_swap_##name (array, left, right, swap_tmp); \
|
if (pivot == right) \
|
pivot = left; \
|
++left; \
|
--right; \
|
} \
|
array [pivot] = array [right]; \
|
array [right] = *pivot_tmp; \
|
--right; \
|
if (right - begin < end - left) { \
|
qsort_rec_##name (array, begin, right, pivot_tmp, swap_tmp); \
|
begin = left; \
|
} else { \
|
qsort_rec_##name (array, left, end, pivot_tmp, swap_tmp); \
|
end = right; \
|
} \
|
} \
|
} \
|
\
|
static inline void \
|
qsort_##name (type array[], size_t count) \
|
{ \
|
type pivot_tmp; \
|
type swap_tmp; \
|
qsort_rec_##name (array, 0, (ssize_t)count - 1, &pivot_tmp, &swap_tmp); \
|
}
|
|
#endif
|
