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) \
  16         (((unsigned char*)array) + ((i) * element_size))
  17 #define SET(i,j) \
  18         do memcpy ((i), (j), element_size); while (0)
  19 #define SWAP(i,j) \
  20         do { \
  21                 size_t __i = (i), __j = (j); \
  22                 if (__i != __j) { \
  23                         SET (swap_tmp, ELEM (__i)); \
  24                         SET (ELEM (__i), ELEM (__j)); \
  25                         SET (ELEM (__j), swap_tmp); \
  26                 } \
  27         } while (0)
  28
  29 static void
  30 sgen_qsort_rec (
  31         void *const array,
  32         const size_t element_size,
  33         int (*compare) (const void *, const void *),
  34         ssize_t begin,
  35         ssize_t end,
  36         unsigned char *const pivot_tmp,
  37         unsigned char *const swap_tmp)
  38 {
  39         ssize_t left, right, mid, pivot;
  40         while (begin < end) {
  41                 left = begin;
  42                 right = end;
  43                 mid = begin + (end - begin) / 2;
  44
  45                 /* Choose median of 3 as pivot and pre-sort to avoid O(n^2) case.
  46                  *
  47                  * L --o--o----->
  48                  *     |  |
  49                  * M --o--|--o-->
  50                  *        |  |
  51                  * R -----o--o-->
  52                  */
  53                 if (compare (ELEM (mid), ELEM (left)) < 0)
  54                         SWAP (mid, left);
  55                 if (compare (ELEM (right), ELEM (left)) < 0)
  56                         SWAP (right, left);
  57                 if (compare (ELEM (right), ELEM (mid)) < 0)
  58                         SWAP (right, mid);
  59                 pivot = mid;
  60                 SET (pivot_tmp, ELEM (pivot));
  61
  62                 /* Partition. */
  63                 for (;;) {
  64                         while (left <= right && compare (ELEM (left), pivot_tmp) <= 0)
  65                                 ++left;
  66                         while (left <= right && compare (ELEM (right), pivot_tmp) > 0)
  67                                 --right;
  68                         if (left > right)
  69                                 break;
  70                         SWAP (left, right);
  71                         if (pivot == right)
  72                                 pivot = left;
  73                         ++left;
  74                         --right;
  75                 }
  76                 SET (ELEM (pivot), ELEM (right));
  77                 SET (ELEM (right), pivot_tmp);
  78                 --right;
  79
  80                 /* Recursively sort shorter partition, loop on longer partition. */
  81                 if (right - begin < end - left) {
  82                         sgen_qsort_rec (
  83                                 array,
  84                                 element_size,
  85                                 compare,
  86                                 begin,
  87                                 right,
  88                                 pivot_tmp,
  89                                 swap_tmp);
  90                         begin = left;
  91                 } else {
  92                         sgen_qsort_rec (
  93                                 array,
  94                                 element_size,
  95                                 compare,
  96                                 left,
  97                                 end,
  98                                 pivot_tmp,
  99                                 swap_tmp);
 100                         end = right;
 101                 }
 102         }
 103 }
 104
 105 void sgen_qsort (
 106         void *const array,
 107         const size_t count,
 108         const size_t element_size,
 109         int (*compare) (const void *, const void *))
 110 {
 111 #ifndef _MSC_VER
 112         unsigned char pivot_tmp [element_size];
 113         unsigned char swap_tmp [element_size];
 114 #else
 115         unsigned char *pivot_tmp = (unsigned char *)alloca (element_size);
 116         unsigned char *swap_tmp = (unsigned char *)alloca (element_size);
 117 #endif
 118         sgen_qsort_rec (
 119                 array,
 120                 element_size,
 121                 compare,
 122                 0,
 123                 (ssize_t)count - 1,
 124                 pivot_tmp,
 125                 swap_tmp);
 126 }
 127
 128 #endif