mono/sgen/sgen-qsort.c

   1 /*
   2  * sgen-qsort.c: Quicksort.
   3  *
   4  * Copyright (C) 2013 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
  20 #include "config.h"
  21
  22 #ifdef HAVE_SGEN_GC
  23
  24 #include "sgen/sgen-gc.h"
  25
  26 #define ELEM(i)         (((unsigned char*)base) + ((i) * width))
  27 #define SWAP(i,j)       do {                                    \
  28                 size_t __i = (i), __j = (j);                    \
  29                 if (__i != __j) {                               \
  30                         memcpy (swap_tmp, ELEM (__i), width);   \
  31                         memcpy (ELEM (__i), ELEM (__j), width); \
  32                         memcpy (ELEM (__j), swap_tmp, width);   \
  33                 }                                               \
  34         } while (0)
  35
  36 static size_t
  37 partition (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*), unsigned char *pivot_tmp, unsigned char *swap_tmp)
  38 {
  39         size_t pivot_idx = nel >> 1;
  40         size_t s, i;
  41
  42         memcpy (pivot_tmp, ELEM (pivot_idx), width);
  43         SWAP (pivot_idx, nel - 1);
  44         s = 0;
  45         for (i = 0; i < nel - 1; ++i) {
  46                 if (compar (ELEM (i), pivot_tmp) <= 0) {
  47                         SWAP (i, s);
  48                         ++s;
  49                 }
  50         }
  51         SWAP (s, nel - 1);
  52         return s;
  53 }
  54
  55 static void
  56 qsort_rec (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*), unsigned char *pivot_tmp, unsigned char *swap_tmp)
  57 {
  58         size_t pivot_idx;
  59
  60         if (nel <= 1)
  61                 return;
  62
  63         pivot_idx = partition (base, nel, width, compar, pivot_tmp, swap_tmp);
  64         qsort_rec (base, pivot_idx, width, compar, pivot_tmp, swap_tmp);
  65         if (pivot_idx < nel)
  66                 qsort_rec (ELEM (pivot_idx + 1), nel - pivot_idx - 1, width, compar, pivot_tmp, swap_tmp);
  67 }
  68
  69 void
  70 sgen_qsort (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*))
  71 {
  72 #ifndef _MSC_VER
  73         unsigned char pivot_tmp [width];
  74         unsigned char swap_tmp [width];
  75 #else
  76         unsigned char* pivot_tmp = (unsigned char*) alloca(width);
  77         unsigned char* swap_tmp = (unsigned char*) alloca(width);
  78 #endif
  79
  80         qsort_rec (base, nel, width, compar, pivot_tmp, swap_tmp);
  81 }
  82
  83 #endif