--- /dev/null
+/*
+ * QuickSort
+ *
+ * Author: Jeffrey Stedfast <fejj@novell.com>
+ *
+ * (C) 2011 Novell, Inc.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+ * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+ * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+ * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+#include <stdlib.h>
+#include <glib.h>
+
+/* Any segment <= this threshold will be sorted using insertion
+ * sort. OpenBSD seems to use a value of 7 so we'll go with that for
+ * now... */
+#define MAX_THRESHOLD 7
+
+#define STACK_SIZE (8 * sizeof (size_t))
+
+typedef struct _QSortStack {
+ char *array;
+ size_t count;
+} QSortStack;
+
+#define QSORT_PUSH(sp, a, c) (sp->array = a, sp->count = c, sp++)
+#define QSORT_POP(sp, a, c) (sp--, a = sp->array, c = sp->count)
+
+#define SWAPTYPE(TYPE, a, b) { \
+ long __n = size / sizeof (TYPE); \
+ register TYPE *__a = (TYPE *) (a); \
+ register TYPE *__b = (TYPE *) (b); \
+ register TYPE t; \
+ \
+ do { \
+ t = *__a; \
+ *__a++ = *__b; \
+ *__b++ = t; \
+ } while (--__n > 0); \
+}
+
+#define SWAPBYTE(a, b) SWAPTYPE(char, (a), (b))
+#define SWAPLONG(a, b) SWAPTYPE(long, (a), (b))
+#define SWAP(a, b) if (swaplong) SWAPLONG((a), (b)) else SWAPBYTE((a), (b))
+
+/* check if we can swap by longs rather than bytes by making sure that
+ * memory is properly aligned and that the element size is a multiple
+ * of sizeof (long) */
+#define SWAP_INIT() swaplong = (((char *) base) - ((char *) 0)) % sizeof (long) == 0 && (size % sizeof (long)) == 0
+
+void
+g_qsort_with_data (gpointer base, size_t nmemb, size_t size, GCompareDataFunc compare, gpointer user_data)
+{
+ QSortStack stack[STACK_SIZE], *sp;
+ register char *i, *k, *mid;
+ size_t n, n1, n2;
+ char *lo, *hi;
+ int swaplong;
+
+ if (nmemb <= 1)
+ return;
+
+ SWAP_INIT ();
+
+ /* initialize our stack */
+ sp = stack;
+ QSORT_PUSH (sp, base, nmemb);
+
+ do {
+ QSORT_POP (sp, lo, n);
+
+ hi = lo + (n - 1) * size;
+
+ if (n < MAX_THRESHOLD) {
+ /* switch to insertion sort */
+ for (i = lo + size; i <= hi; i += size)
+ for (k = i; k > lo && compare (k - size, k, user_data) > 0; k -= size)
+ SWAP (k - size, k);
+
+ continue;
+ }
+
+ /* calculate the middle element */
+ mid = lo + (n / 2) * size;
+
+ /* once we re-order the lo, mid, and hi elements to be in
+ * ascending order, we'll use mid as our pivot. */
+ if (compare (mid, lo, user_data) < 0) {
+ SWAP (mid, lo);
+ }
+
+ if (compare (hi, mid, user_data) < 0) {
+ SWAP (mid, hi);
+ if (compare (mid, lo, user_data) < 0) {
+ SWAP (mid, lo);
+ }
+ }
+
+ /* since we've already guaranteed that lo <= mid and mid <= hi,
+ * we can skip comparing them again */
+ i = lo + size;
+ k = hi - size;
+
+ do {
+ /* find the first element with a value > pivot value */
+ while (i < k && compare (i, mid, user_data) <= 0)
+ i += size;
+
+ /* find the last element with a value <= pivot value */
+ while (k >= i && compare (mid, k, user_data) < 0)
+ k -= size;
+
+ if (k <= i)
+ break;
+
+ SWAP (i, k);
+
+ /* make sure we keep track of our pivot element */
+ if (mid == i) {
+ mid = k;
+ } else if (mid == k) {
+ mid = i;
+ }
+
+ i += size;
+ k -= size;
+ } while (1);
+
+ if (k != mid) {
+ /* swap the pivot with the last element in the first partition */
+ SWAP (mid, k);
+ }
+
+ /* calculate segment sizes */
+ n2 = (hi - k) / size;
+ n1 = (k - lo) / size;
+
+ /* push our partitions onto the stack, largest first
+ * (to make sure we don't run out of stack space) */
+ if (n2 > n1) {
+ if (n2 > 1) QSORT_PUSH (sp, k + size, n2);
+ if (n1 > 1) QSORT_PUSH (sp, lo, n1);
+ } else {
+ if (n1 > 1) QSORT_PUSH (sp, lo, n1);
+ if (n2 > 1) QSORT_PUSH (sp, k + size, n2);
+ }
+ } while (sp > stack);
+}
projects / mono.git / blobdiff