mono/sgen/sgen-qsort.h

   1 /*
   2  * sgen-qsort.h: Fast inline sorting
   3  *
   4  * Copyright (C) 2014 Xamarin Inc
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Library General Public
   8  * License 2.0 as published by the Free Software Foundation;
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public
  16  * License 2.0 along with this library; if not, write to the Free
  17  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  */
  19 #ifndef __MONO_SGENQSORT_H__
  20 #define __MONO_SGENQSORT_H__
  21
  22 #define DEF_QSORT_INLINE(NAME,ARRAY_TYPE,COMPARE_FUN)   \
  23 static size_t partition_##NAME (ARRAY_TYPE base[], size_t nel) {        \
  24         size_t pivot_idx = nel >> 1;    \
  25         size_t s, i;    \
  26         ARRAY_TYPE pivot = base [pivot_idx];    \
  27         { ARRAY_TYPE tmp = base [pivot_idx]; base [pivot_idx] = base [nel - 1]; base [nel - 1] = tmp; } \
  28         s = 0;  \
  29         for (i = 0; i < nel - 1; ++i) { \
  30                 if (COMPARE_FUN (base [i], pivot) <= 0) {       \
  31                         { ARRAY_TYPE tmp = base [i]; base [i] = base [s]; base [s] = tmp; }     \
  32                         ++s;    \
  33                 }       \
  34         }       \
  35         { ARRAY_TYPE tmp = base [s]; base [s] = base [nel - 1]; base [nel - 1] = tmp; } \
  36         return s;       \
  37 }       \
  38 static void rec_##NAME (ARRAY_TYPE base[], size_t nel) {        \
  39         size_t pivot_idx;       \
  40         if (nel <= 1)   \
  41                 return; \
  42         pivot_idx = partition_##NAME (base, nel); \
  43         rec_##NAME (base, pivot_idx);   \
  44         if (pivot_idx < nel)    \
  45                 rec_##NAME (&base[pivot_idx + 1], nel - pivot_idx - 1); \
  46 }       \
  47 static void qsort_##NAME (ARRAY_TYPE base[], size_t nel) {      \
  48         rec_##NAME (base, nel); \
  49 }       \
  50
  51
  52 #endif