mono/sgen/sgen-qsort.c

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