1.1 --- a/util.c	Thu Mar 06 00:55:51 2008 -0500
     1.2 +++ b/util.c	Mon Apr 07 11:56:48 2008 -0400
     1.3 @@ -3,6 +3,7 @@
     1.4  #include <sys/stat.h>
     1.5  #include <stdlib.h>
     1.6  #include <stdio.h>
     1.7 +#include <stdint.h>
     1.8  #include <unistd.h>
     1.9  
    1.10  #include "razor-internal.h"
    1.11 @@ -71,3 +72,96 @@
    1.12  
    1.13  	return 0;
    1.14  }
    1.15 +
    1.16 +struct qsort_context {
    1.17 +	size_t size;
    1.18 +	razor_compare_with_data_func_t compare;
    1.19 +	void *data;
    1.20 +};
    1.21 +
    1.22 +static void
    1.23 +qsort_swap(void *p1, void *p2, size_t size)
    1.24 +{
    1.25 +	char buffer[size];
    1.26 +
    1.27 +	memcpy(buffer, p1, size);
    1.28 +	memcpy(p1, p2, size);
    1.29 +	memcpy(p2, buffer, size);
    1.30 +}
    1.31 +
    1.32 +static void
    1.33 +__qsort_with_data(void *base, size_t nelem, uint32_t *map,
    1.34 +		  struct qsort_context *ctx)
    1.35 +{
    1.36 +	void *p, *start, *end, *pivot;
    1.37 +	uint32_t *mp, *mstart, *mend, tmp;
    1.38 +	int left, right, result;
    1.39 +	size_t size = ctx->size;
    1.40 +
    1.41 +	p = base;
    1.42 +	start = base;
    1.43 +	end = base + nelem * size;
    1.44 +	mp = map;
    1.45 +	mstart = map;
    1.46 +	mend = map + nelem;
    1.47 +	pivot = base + (random() % nelem) * size;
    1.48 +
    1.49 +	while (p < end) {
    1.50 +		result = ctx->compare(p, pivot, ctx->data);
    1.51 +		if (result < 0) {
    1.52 +			qsort_swap(p, start, size);
    1.53 +			tmp = *mp;
    1.54 +			*mp = *mstart;
    1.55 +			*mstart = tmp;
    1.56 +			if (start == pivot)
    1.57 +				pivot = p;
    1.58 +			start += size;
    1.59 +			mstart++;
    1.60 +			p += size;
    1.61 +			mp++;
    1.62 +		} else if (result == 0) {
    1.63 +			p += size;
    1.64 +			mp++;
    1.65 +		} else {
    1.66 + 			end -= size;
    1.67 +			mend--;
    1.68 +			qsort_swap(p, end, size);
    1.69 +			tmp = *mp;
    1.70 +			*mp = *mend;
    1.71 +			*mend = tmp;
    1.72 +			if (end == pivot)
    1.73 +				pivot = p;
    1.74 +		}
    1.75 +	}
    1.76 +
    1.77 +	left = (start - base) / size;
    1.78 +	right = (base + nelem * size - end) / size;
    1.79 +	if (left > 1)
    1.80 +		__qsort_with_data(base, left, map, ctx);
    1.81 +	if (right > 1)
    1.82 +		__qsort_with_data(end, right, mend, ctx);
    1.83 +}
    1.84 +
    1.85 +uint32_t *
    1.86 +razor_qsort_with_data(void *base, size_t nelem, size_t size,
    1.87 +		      razor_compare_with_data_func_t compare, void *data)
    1.88 +{
    1.89 +	struct qsort_context ctx;
    1.90 +	uint32_t *map;
    1.91 +	int i;
    1.92 +
    1.93 +	if (nelem == 0)
    1.94 +		return NULL;
    1.95 +
    1.96 +	ctx.size = size;
    1.97 +	ctx.compare = compare;
    1.98 +	ctx.data = data;
    1.99 +
   1.100 +	map = malloc(nelem * sizeof (uint32_t));
   1.101 +	for (i = 0; i < nelem; i++)
   1.102 +		map[i] = i;
   1.103 +
   1.104 +	__qsort_with_data(base, nelem, map, &ctx);
   1.105 +
   1.106 +	return map;
   1.107 +}