mono/eglib/gqsort.c

   1 /*
   2  * QuickSort
   3  *
   4  * Author: Jeffrey Stedfast <fejj@novell.com>
   5  *
   6  * (C) 2011 Novell, Inc.
   7  *
   8  * Permission is hereby granted, free of charge, to any person obtaining
   9  * a copy of this software and associated documentation files (the
  10  * "Software"), to deal in the Software without restriction, including
  11  * without limitation the rights to use, copy, modify, merge, publish,
  12  * distribute, sublicense, and/or sell copies of the Software, and to
  13  * permit persons to whom the Software is furnished to do so, subject to
  14  * the following conditions:
  15  *
  16  * The above copyright notice and this permission notice shall be
  17  * included in all copies or substantial portions of the Software.
  18  *
  19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  20  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  21  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  22  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  23  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  24  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  25  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  26  */
  27 #include "config.h"
  28 #include <stdlib.h>
  29 #include <glib.h>
  30
  31 /* Any segment <= this threshold will be sorted using insertion
  32  * sort. OpenBSD seems to use a value of 7 so we'll go with that for
  33  * now... */
  34 #define MAX_THRESHOLD 7
  35
  36 #define STACK_SIZE (8 * sizeof (size_t))
  37
  38 typedef struct _QSortStack {
  39         char *array;
  40         size_t count;
  41 } QSortStack;
  42
  43 #define QSORT_PUSH(sp, a, c) ((sp)->array = (char*)(a), (sp)->count = (c), (sp)++)
  44 #define QSORT_POP(sp, a, c) ((sp)--, (a) = (sp)->array, (c) = (sp)->count)
  45
  46 #define SWAPTYPE(TYPE, a, b) {              \
  47         gssize __n = size / sizeof (TYPE);  \
  48         TYPE *__a = (TYPE *) (a);           \
  49         TYPE *__b = (TYPE *) (b);           \
  50         TYPE t;                             \
  51                                             \
  52         do {                                \
  53                 t = *__a;                   \
  54                 *__a++ = *__b;              \
  55                 *__b++ = t;                 \
  56         } while (--__n > 0);                \
  57 }
  58
  59 #define SWAPBYTE(a, b) SWAPTYPE(char, (a), (b))
  60 #define SWAPLONG(a, b) SWAPTYPE(long, (a), (b))
  61 #define SWAP(a, b) if (swaplong) SWAPLONG((a), (b)) else SWAPBYTE((a), (b))
  62
  63 /* check if we can swap by longs rather than bytes by making sure that
  64  * memory is properly aligned and that the element size is a multiple
  65  * of sizeof (long) */
  66 #define SWAP_INIT() swaplong = (((char *) base) - ((char *) 0)) % sizeof (long) == 0 && (size % sizeof (long)) == 0
  67
  68 void
  69 g_qsort_with_data (gpointer base, size_t nmemb, size_t size, GCompareDataFunc compare, gpointer user_data)
  70 {
  71         QSortStack stack[STACK_SIZE], *sp;
  72         char *i, *k, *mid;
  73         size_t n, n1, n2;
  74         char *lo, *hi;
  75         int swaplong;
  76
  77         if (nmemb <= 1)
  78                 return;
  79
  80         SWAP_INIT ();
  81
  82         /* initialize our stack */
  83         sp = stack;
  84         QSORT_PUSH (sp, base, nmemb);
  85
  86         do {
  87                 QSORT_POP (sp, lo, n);
  88
  89                 hi = lo + (n - 1) * size;
  90
  91                 if (n < MAX_THRESHOLD) {
  92                         /* switch to insertion sort */
  93                         for (i = lo + size; i <= hi; i += size)
  94                                 for (k = i; k > lo && compare (k - size, k, user_data) > 0; k -= size)
  95                                         SWAP (k - size, k);
  96
  97                         continue;
  98                 }
  99
 100                 /* calculate the middle element */
 101                 mid = lo + (n / 2) * size;
 102
 103                 /* once we re-order the lo, mid, and hi elements to be in
 104                  * ascending order, we'll use mid as our pivot. */
 105                 if (compare (mid, lo, user_data) < 0) {
 106                         SWAP (mid, lo);
 107                 }
 108
 109                 if (compare (hi, mid, user_data) < 0) {
 110                         SWAP (mid, hi);
 111                         if (compare (mid, lo, user_data) < 0) {
 112                                 SWAP (mid, lo);
 113                         }
 114                 }
 115
 116                 /* since we've already guaranteed that lo <= mid and mid <= hi,
 117                  * we can skip comparing them again */
 118                 i = lo + size;
 119                 k = hi - size;
 120
 121                 do {
 122                         /* find the first element with a value > pivot value */
 123                         while (i < k && compare (i, mid, user_data) <= 0)
 124                                 i += size;
 125
 126                         /* find the last element with a value <= pivot value */
 127                         while (k >= i && compare (mid, k, user_data) < 0)
 128                                 k -= size;
 129
 130                         if (k <= i)
 131                                 break;
 132
 133                         SWAP (i, k);
 134
 135                         /* make sure we keep track of our pivot element */
 136                         if (mid == i) {
 137                                 mid = k;
 138                         } else if (mid == k) {
 139                                 mid = i;
 140                         }
 141
 142                         i += size;
 143                         k -= size;
 144                 } while (1);
 145
 146                 if (k != mid) {
 147                         /* swap the pivot with the last element in the first partition */
 148                         SWAP (mid, k);
 149                 }
 150
 151                 /* calculate segment sizes */
 152                 n2 = (hi - k) / size;
 153                 n1 = (k - lo) / size;
 154
 155                 /* push our partitions onto the stack, largest first
 156                  * (to make sure we don't run out of stack space) */
 157                 if (n2 > n1) {
 158                         if (n2 > 1) QSORT_PUSH (sp, k + size, n2);
 159                         if (n1 > 1) QSORT_PUSH (sp, lo, n1);
 160                 } else {
 161                         if (n1 > 1) QSORT_PUSH (sp, lo, n1);
 162                         if (n2 > 1) QSORT_PUSH (sp, k + size, n2);
 163                 }
 164         } while (sp > stack);
 165 }