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 #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;    \
  14         size_t s, i;    \
  15         ARRAY_TYPE pivot = base [pivot_idx];    \
  16         { ARRAY_TYPE tmp = base [pivot_idx]; base [pivot_idx] = base [nel - 1]; base [nel - 1] = tmp; } \
  17         s = 0;  \
  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; }     \
  21                         ++s;    \
  22                 }       \
  23         }       \
  24         { ARRAY_TYPE tmp = base [s]; base [s] = base [nel - 1]; base [nel - 1] = tmp; } \
  25         return s;       \
  26 }       \
  27 static void rec_##NAME (ARRAY_TYPE base[], size_t nel) {        \
  28         size_t pivot_idx;       \
  29         if (nel <= 1)   \
  30                 return; \
  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); \
  35 }       \
  36 static void qsort_##NAME (ARRAY_TYPE base[], size_t nel) {      \
  37         rec_##NAME (base, nel); \
  38 }       \
  39
  40
  41 #endif