/* Utilities */
-void sgen_qsort (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*));
+void sgen_qsort (void *array, size_t count, size_t element_size, int (*compare) (const void*, const void*));
gint64 sgen_timestamp (void);
/*
#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 memcpy ((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
#ifndef __MONO_SGENQSORT_H__
#define __MONO_SGENQSORT_H__
-#define DEF_QSORT_INLINE(NAME,ARRAY_TYPE,COMPARE_FUN) \
-static size_t partition_##NAME (ARRAY_TYPE base[], size_t nel) { \
- size_t pivot_idx = nel >> 1; \
- size_t s, i; \
- ARRAY_TYPE pivot = base [pivot_idx]; \
- { ARRAY_TYPE tmp = base [pivot_idx]; base [pivot_idx] = base [nel - 1]; base [nel - 1] = tmp; } \
- s = 0; \
- for (i = 0; i < nel - 1; ++i) { \
- if (COMPARE_FUN (base [i], pivot) <= 0) { \
- { ARRAY_TYPE tmp = base [i]; base [i] = base [s]; base [s] = tmp; } \
- ++s; \
- } \
- } \
- { ARRAY_TYPE tmp = base [s]; base [s] = base [nel - 1]; base [nel - 1] = tmp; } \
- return s; \
+/* Copied from non-inline implementation in sgen-qsort.c */
+#define DEF_QSORT_INLINE(name, type, compare) \
+static inline void \
+qsort_swap_##name (type array[], const ssize_t i, const ssize_t j, type *const swap_tmp) \
+{ \
+ *swap_tmp = array [i]; \
+ array [i] = array [j]; \
+ array [j] = *swap_tmp; \
+} \
+\
+static void \
+qsort_rec_##name ( \
+ type array[], \
+ ssize_t begin, \
+ ssize_t end, \
+ type *const pivot_tmp, \
+ type *const swap_tmp) \
+{ \
+ ssize_t left, right, middle, pivot; \
+ while (begin < end) { \
+ left = begin; \
+ right = end; \
+ middle = begin + (end - begin) / 2; \
+ if (compare (array [middle], array [left]) < 0) \
+ qsort_swap_##name (array, middle, left, swap_tmp); \
+ if (compare (array [right], array [left]) < 0) \
+ qsort_swap_##name (array, right, left, swap_tmp); \
+ if (compare (array [right], array [middle]) < 0) \
+ qsort_swap_##name (array, right, middle, swap_tmp); \
+ pivot = middle; \
+ *pivot_tmp = array [pivot]; \
+ for (;;) { \
+ while (left <= right && compare (array [left], *pivot_tmp) <= 0) \
+ ++left; \
+ while (left <= right && compare (array [right], *pivot_tmp) > 0) \
+ --right; \
+ if (left > right) \
+ break; \
+ qsort_swap_##name (array, left, right, swap_tmp); \
+ if (pivot == right) \
+ pivot = left; \
+ ++left; \
+ --right; \
+ } \
+ array [pivot] = array [right]; \
+ array [right] = *pivot_tmp; \
+ --right; \
+ if (right - begin < end - left) { \
+ qsort_rec_##name (array, begin, right, pivot_tmp, swap_tmp); \
+ begin = left; \
+ } else { \
+ qsort_rec_##name (array, left, end, pivot_tmp, swap_tmp); \
+ end = right; \
+ } \
+ } \
} \
-static void rec_##NAME (ARRAY_TYPE base[], size_t nel) { \
- size_t pivot_idx; \
- if (nel <= 1) \
- return; \
- pivot_idx = partition_##NAME (base, nel); \
- rec_##NAME (base, pivot_idx); \
- if (pivot_idx < nel) \
- rec_##NAME (&base[pivot_idx + 1], nel - pivot_idx - 1); \
-} \
-static void qsort_##NAME (ARRAY_TYPE base[], size_t nel) { \
- rec_##NAME (base, nel); \
-} \
-
+\
+static inline void \
+qsort_##name (type array[], size_t count) \
+{ \
+ type pivot_tmp; \
+ type swap_tmp; \
+ qsort_rec_##name (array, 0, (ssize_t)count - 1, &pivot_tmp, &swap_tmp); \
+}
#endif
qsort (b1, nel, width, compar);
sgen_qsort (b2, nel, width, compar);
- assert (!memcmp (b1, b2, len));
+ /* We can't assert that qsort and sgen_qsort produce the same results
+ * because qsort is not guaranteed to be stable, so they will tend to differ
+ * in adjacent equal elements. Instead, we assert that the array is sorted
+ * according to the comparator.
+ */
+ for (size_t i = 0; i < nel - 1; ++i)
+ assert (compar ((char *)b2 + i * width, (char *)b2 + (i + 1) * width) <= 0);
free (b1);
free (b2);
static void
compare_sorts2 (void *base, size_t nel)
{
- size_t len = nel * sizeof (teststruct_t*);
+ size_t width = sizeof (teststruct_t*);
+ size_t len = nel * width;
void *b1 = malloc (len);
void *b2 = malloc (len);
qsort (b1, nel, sizeof (teststruct_t*), compare_teststructs2);
qsort_test_struct ((teststruct_t **)b2, nel);
- assert (!memcmp (b1, b2, len));
+ for (size_t i = 0; i < nel - 1; ++i)
+ assert (compare_teststructs2 ((char *)b2 + i * width, (char *)b2 + (i + 1) * width) <= 0);
free (b1);
free (b2);
projects / mono.git / commitdiff