mono/sgen/sgen-qsort.h

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