-/*
- * sgen-qsort.c: Quicksort.
+/**
+ * \file
+ * Quicksort.
*
* Copyright (C) 2013 Xamarin Inc
*
#include "sgen/sgen-gc.h"
-#define ELEM(i) (((unsigned char*)base) + ((i) * width))
-#define SWAP(i,j) do { \
- size_t __i = (i), __j = (j); \
- if (__i != __j) { \
- memcpy (swap_tmp, ELEM (__i), width); \
- memcpy (ELEM (__i), ELEM (__j), width); \
- memcpy (ELEM (__j), swap_tmp, width); \
- } \
+#define ELEM(i) \
+ (((unsigned char*)array) + ((i) * element_size))
+#define SET(i,j) \
+ do memmove ((i), (j), element_size); while (0)
+#define SWAP(i,j) \
+ do { \
+ size_t __i = (i), __j = (j); \
+ if (__i != __j) { \
+ SET (swap_tmp, ELEM (__i)); \
+ SET (ELEM (__i), ELEM (__j)); \
+ SET (ELEM (__j), swap_tmp); \
+ } \
} while (0)
-static size_t
-partition (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*), unsigned char *pivot_tmp, unsigned char *swap_tmp)
-{
- size_t pivot_idx = nel >> 1;
- size_t s, i;
-
- memcpy (pivot_tmp, ELEM (pivot_idx), width);
- SWAP (pivot_idx, nel - 1);
- s = 0;
- for (i = 0; i < nel - 1; ++i) {
- if (compar (ELEM (i), pivot_tmp) <= 0) {
- SWAP (i, s);
- ++s;
- }
- }
- SWAP (s, nel - 1);
- return s;
-}
-
static void
-qsort_rec (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*), unsigned char *pivot_tmp, unsigned char *swap_tmp)
+sgen_qsort_rec (
+ void *const array,
+ const size_t element_size,
+ int (*compare) (const void *, const void *),
+ ssize_t begin,
+ ssize_t end,
+ unsigned char *const pivot_tmp,
+ unsigned char *const swap_tmp)
{
- size_t pivot_idx;
+ ssize_t left, right, mid, pivot;
+ while (begin < end) {
+ left = begin;
+ right = end;
+ mid = begin + (end - begin) / 2;
- if (nel <= 1)
- return;
+ /* Choose median of 3 as pivot and pre-sort to avoid O(n^2) case.
+ *
+ * L --o--o----->
+ * | |
+ * M --o--|--o-->
+ * | |
+ * R -----o--o-->
+ */
+ if (compare (ELEM (mid), ELEM (left)) < 0)
+ SWAP (mid, left);
+ if (compare (ELEM (right), ELEM (left)) < 0)
+ SWAP (right, left);
+ if (compare (ELEM (right), ELEM (mid)) < 0)
+ SWAP (right, mid);
+ pivot = mid;
+ SET (pivot_tmp, ELEM (pivot));
- pivot_idx = partition (base, nel, width, compar, pivot_tmp, swap_tmp);
- qsort_rec (base, pivot_idx, width, compar, pivot_tmp, swap_tmp);
- if (pivot_idx < nel)
- qsort_rec (ELEM (pivot_idx + 1), nel - pivot_idx - 1, width, compar, pivot_tmp, swap_tmp);
+ /* Partition. */
+ for (;;) {
+ while (left <= right && compare (ELEM (left), pivot_tmp) <= 0)
+ ++left;
+ while (left <= right && compare (ELEM (right), pivot_tmp) > 0)
+ --right;
+ if (left > right)
+ break;
+ SWAP (left, right);
+ if (pivot == right)
+ pivot = left;
+ ++left;
+ --right;
+ }
+ SET (ELEM (pivot), ELEM (right));
+ SET (ELEM (right), pivot_tmp);
+ --right;
+
+ /* Recursively sort shorter partition, loop on longer partition. */
+ if (right - begin < end - left) {
+ sgen_qsort_rec (
+ array,
+ element_size,
+ compare,
+ begin,
+ right,
+ pivot_tmp,
+ swap_tmp);
+ begin = left;
+ } else {
+ sgen_qsort_rec (
+ array,
+ element_size,
+ compare,
+ left,
+ end,
+ pivot_tmp,
+ swap_tmp);
+ end = right;
+ }
+ }
}
-void
-sgen_qsort (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*))
+void sgen_qsort (
+ void *const array,
+ const size_t count,
+ const size_t element_size,
+ int (*compare) (const void *, const void *))
{
#ifndef _MSC_VER
- unsigned char pivot_tmp [width];
- unsigned char swap_tmp [width];
+ unsigned char pivot_tmp [element_size];
+ unsigned char swap_tmp [element_size];
#else
- unsigned char* pivot_tmp = (unsigned char*) alloca(width);
- unsigned char* swap_tmp = (unsigned char*) alloca(width);
+ unsigned char *pivot_tmp = (unsigned char *)alloca (element_size);
+ unsigned char *swap_tmp = (unsigned char *)alloca (element_size);
#endif
-
- qsort_rec (base, nel, width, compar, pivot_tmp, swap_tmp);
+ sgen_qsort_rec (
+ array,
+ element_size,
+ compare,
+ 0,
+ (ssize_t)count - 1,
+ pivot_tmp,
+ swap_tmp);
}
#endif
projects / mono.git / blobdiff