mono/sgen/sgen-qsort.h

   1 /*
   2  * sgen-qsort.h: Fast inline sorting
   3  *
   4  * Copyright (C) 2014 Xamarin Inc
   5  *
   6  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
   7  */
   8 #ifndef __MONO_SGENQSORT_H__
   9 #define __MONO_SGENQSORT_H__
  10
  11 /* Copied from non-inline implementation in sgen-qsort.c */
  12 #define DEF_QSORT_INLINE(name, type, compare) \
  13 static inline void \
  14 qsort_swap_##name (type array[], const ssize_t i, const ssize_t j, type *const swap_tmp) \
  15 { \
  16         *swap_tmp = array [i]; \
  17         array [i] = array [j]; \
  18         array [j] = *swap_tmp; \
  19 } \
  20 \
  21 static void \
  22 qsort_rec_##name ( \
  23         type array[], \
  24         ssize_t begin, \
  25         ssize_t end, \
  26         type *const pivot_tmp, \
  27         type *const swap_tmp) \
  28 { \
  29         ssize_t left, right, middle, pivot; \
  30         while (begin < end) { \
  31                 left = begin; \
  32                 right = end; \
  33                 middle = begin + (end - begin) / 2; \
  34                 if (compare (array [middle], array [left]) < 0) \
  35                         qsort_swap_##name (array, middle, left, swap_tmp); \
  36                 if (compare (array [right], array [left]) < 0) \
  37                         qsort_swap_##name (array, right, left, swap_tmp); \
  38                 if (compare (array [right], array [middle]) < 0) \
  39                         qsort_swap_##name (array, right, middle, swap_tmp); \
  40                 pivot = middle; \
  41                 *pivot_tmp = array [pivot]; \
  42                 for (;;) { \
  43                         while (left <= right && compare (array [left], *pivot_tmp) <= 0) \
  44                                 ++left; \
  45                         while (left <= right && compare (array [right], *pivot_tmp) > 0) \
  46                                 --right; \
  47                         if (left > right) \
  48                                 break; \
  49                         qsort_swap_##name (array, left, right, swap_tmp); \
  50                         if (pivot == right) \
  51                                 pivot = left; \
  52                         ++left; \
  53                         --right; \
  54                 } \
  55                 array [pivot] = array [right]; \
  56                 array [right] = *pivot_tmp; \
  57                 --right; \
  58                 if (right - begin < end - left) { \
  59                         qsort_rec_##name (array, begin, right, pivot_tmp, swap_tmp); \
  60                         begin = left; \
  61                 } else { \
  62                         qsort_rec_##name (array, left, end, pivot_tmp, swap_tmp); \
  63                         end = right; \
  64                 } \
  65         } \
  66 }       \
  67 \
  68 static inline void \
  69 qsort_##name (type array[], size_t count) \
  70 { \
  71         type pivot_tmp; \
  72         type swap_tmp; \
  73         qsort_rec_##name (array, 0, (ssize_t)count - 1, &pivot_tmp, &swap_tmp); \
  74 }
  75
  76 #endif