/*
|
* 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);
|
}
|
