mono/metadata/sgen-qsort.c

   1 /*
   2  * sgen-qsort.c: Quicksort.
   3  *
   4  * Author:
   5  *      Mark Probst <mark.probst@gmail.com>
   6  *
   7  * Copyright (C) 2013 Xamarin Inc
   8  *
   9  * This library is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU Library General Public
  11  * License 2.0 as published by the Free Software Foundation;
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Library General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Library General Public
  19  * License 2.0 along with this library; if not, write to the Free
  20  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21  */
  22
  23 #include "config.h"
  24
  25 #ifdef HAVE_SGEN_GC
  26
  27 #include "metadata/sgen-gc.h"
  28
  29 #define ELEM(i)         (((unsigned char*)base) + ((i) * width))
  30 #define SWAP(i,j)       do {                                    \
  31                 size_t __i = (i), __j = (j);                    \
  32                 if (__i != __j) {                               \
  33                         memcpy (swap_tmp, ELEM (__i), width);   \
  34                         memcpy (ELEM (__i), ELEM (__j), width); \
  35                         memcpy (ELEM (__j), swap_tmp, width);   \
  36                 }                                               \
  37         } while (0)
  38
  39 static size_t
  40 partition (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*), unsigned char *pivot_tmp, unsigned char *swap_tmp)
  41 {
  42         size_t pivot_idx = nel >> 1;
  43         size_t s, i;
  44
  45         memcpy (pivot_tmp, ELEM (pivot_idx), width);
  46         SWAP (pivot_idx, nel - 1);
  47         s = 0;
  48         for (i = 0; i < nel - 1; ++i) {
  49                 if (compar (ELEM (i), pivot_tmp) <= 0) {
  50                         SWAP (i, s);
  51                         ++s;
  52                 }
  53         }
  54         SWAP (s, nel - 1);
  55         return s;
  56 }
  57
  58 static void
  59 qsort_rec (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*), unsigned char *pivot_tmp, unsigned char *swap_tmp)
  60 {
  61         size_t pivot_idx;
  62
  63         if (nel <= 1)
  64                 return;
  65
  66         pivot_idx = partition (base, nel, width, compar, pivot_tmp, swap_tmp);
  67         qsort_rec (base, pivot_idx, width, compar, pivot_tmp, swap_tmp);
  68         if (pivot_idx < nel)
  69                 qsort_rec (ELEM (pivot_idx + 1), nel - pivot_idx - 1, width, compar, pivot_tmp, swap_tmp);
  70 }
  71
  72 void
  73 sgen_qsort (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*))
  74 {
  75         unsigned char pivot_tmp [width];
  76         unsigned char swap_tmp [width];
  77
  78         qsort_rec (base, nel, width, compar, pivot_tmp, swap_tmp);
  79 }
  80
  81 #ifdef SGEN_QSORT_TEST
  82
  83 static int
  84 compare_ints (const void *pa, const void *pb)
  85 {
  86         int a = *(const int*)pa;
  87         int b = *(const int*)pb;
  88         if (a < b)
  89                 return -1;
  90         if (a == b)
  91                 return 0;
  92         return 1;
  93 }
  94
  95 typedef struct {
  96         int key;
  97         int val;
  98 } teststruct_t;
  99
 100 static int
 101 compare_teststructs (const void *pa, const void *pb)
 102 {
 103         int a = ((const teststruct_t*)pa)->key;
 104         int b = ((const teststruct_t*)pb)->key;
 105         if (a < b)
 106                 return -1;
 107         if (a == b)
 108                 return 0;
 109         return 1;
 110 }
 111
 112 #include <stdlib.h>
 113 #include <assert.h>
 114
 115 static void
 116 compare_sorts (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*))
 117 {
 118         size_t len = nel * width;
 119         void *b1 = malloc (len);
 120         void *b2 = malloc (len);
 121
 122         memcpy (b1, base, len);
 123         memcpy (b2, base, len);
 124
 125         qsort (b1, nel, width, compar);
 126         sgen_qsort (b2, nel, width, compar);
 127
 128         assert (!memcmp (b1, b2, len));
 129
 130         free (b1);
 131         free (b2);
 132 }
 133
 134 int
 135 main (void)
 136 {
 137         int i;
 138         for (i = 0; i < 4000; ++i) {
 139                 int a [i];
 140                 int j;
 141
 142                 for (j = 0; j < i; ++j)
 143                         a [j] = i - j - 1;
 144                 compare_sorts (a, i, sizeof (int), compare_ints);
 145         }
 146
 147         srandomdev ();
 148         for (i = 0; i < 2000; ++i) {
 149                 teststruct_t a [200];
 150                 int j;
 151                 for (j = 0; j < 200; ++j) {
 152                         a [j].key = random ();
 153                         a [j].val = random ();
 154                 }
 155
 156                 compare_sorts (a, 200, sizeof (teststruct_t), compare_teststructs);
 157         }
 158
 159         return 0;
 160 }
 161
 162 #endif
 163
 164 #endif