X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=mono%2Fsgen%2Fsgen-qsort.c;h=e8144244a6c198f78502f058701984e7a0c18895;hb=9d84dcb2fc35af1d75450045a8212bf5ab3ff383;hp=802dd561e9ed260df85cfd512b843034f9d4fcf1;hpb=69f207ee9e4f440e66e98bf5f685807f6527c39d;p=mono.git

diff --git a/mono/sgen/sgen-qsort.c b/mono/sgen/sgen-qsort.c
index 802dd561e9e..e8144244a6c 100644
--- a/mono/sgen/sgen-qsort.c
+++ b/mono/sgen/sgen-qsort.c
@@ -1,5 +1,6 @@
-/*
- * sgen-qsort.c: Quicksort.
+/**
+ * \file
+ * Quicksort.
  *
  * Copyright (C) 2013 Xamarin Inc
  *
@@ -12,61 +13,117 @@
 
 #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