mono/sgen/sgen-qsort.c

   1 /*
   2  * sgen-qsort.c: Quicksort.
   3  *
   4  * Copyright (C) 2013 Xamarin Inc
   5  *
   6  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
   7  */
   8
   9 #include "config.h"
  10
  11 #ifdef HAVE_SGEN_GC
  12
  13 #include "sgen/sgen-gc.h"
  14
  15 #define ELEM(i)         (((unsigned char*)base) + ((i) * width))
  16 #define SWAP(i,j)       do {                                    \
  17                 size_t __i = (i), __j = (j);                    \
  18                 if (__i != __j) {                               \
  19                         memcpy (swap_tmp, ELEM (__i), width);   \
  20                         memcpy (ELEM (__i), ELEM (__j), width); \
  21                         memcpy (ELEM (__j), swap_tmp, width);   \
  22                 }                                               \
  23         } while (0)
  24
  25 static size_t
  26 partition (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*), unsigned char *pivot_tmp, unsigned char *swap_tmp)
  27 {
  28         size_t pivot_idx = nel >> 1;
  29         size_t s, i;
  30
  31         memcpy (pivot_tmp, ELEM (pivot_idx), width);
  32         SWAP (pivot_idx, nel - 1);
  33         s = 0;
  34         for (i = 0; i < nel - 1; ++i) {
  35                 if (compar (ELEM (i), pivot_tmp) <= 0) {
  36                         SWAP (i, s);
  37                         ++s;
  38                 }
  39         }
  40         SWAP (s, nel - 1);
  41         return s;
  42 }
  43
  44 static void
  45 qsort_rec (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*), unsigned char *pivot_tmp, unsigned char *swap_tmp)
  46 {
  47         size_t pivot_idx;
  48
  49         if (nel <= 1)
  50                 return;
  51
  52         pivot_idx = partition (base, nel, width, compar, pivot_tmp, swap_tmp);
  53         qsort_rec (base, pivot_idx, width, compar, pivot_tmp, swap_tmp);
  54         if (pivot_idx < nel)
  55                 qsort_rec (ELEM (pivot_idx + 1), nel - pivot_idx - 1, width, compar, pivot_tmp, swap_tmp);
  56 }
  57
  58 void
  59 sgen_qsort (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*))
  60 {
  61 #ifndef _MSC_VER
  62         unsigned char pivot_tmp [width];
  63         unsigned char swap_tmp [width];
  64 #else
  65         unsigned char* pivot_tmp = (unsigned char*) alloca(width);
  66         unsigned char* swap_tmp = (unsigned char*) alloca(width);
  67 #endif
  68
  69         qsort_rec (base, nel, width, compar, pivot_tmp, swap_tmp);
  70 }
  71
  72 #endif