1.1 --- a/razor.c	Wed Sep 12 07:31:18 2007 -0400
     1.2 +++ b/razor.c	Thu Sep 13 10:44:03 2007 -0400
     1.3 @@ -601,22 +601,74 @@
     1.4  	return 0;
     1.5  }
     1.6  
     1.7 -static struct razor_set *qsort_set;
     1.8 +typedef int (*compare_with_data_func_t)(const void *p1,
     1.9 +					const void *p,
    1.10 +					void *data);
    1.11 +
    1.12 +static void
    1.13 +qsort_swap(void *p1, void *p2, size_t size)
    1.14 +{
    1.15 +	char buffer[size];
    1.16 +
    1.17 +	memcpy(buffer, p1, size);
    1.18 +	memcpy(p1, p2, size);
    1.19 +	memcpy(p2, buffer, size);
    1.20 +}
    1.21 +
    1.22 +void
    1.23 +qsort_with_data(void *base, size_t nelem, size_t size,
    1.24 +		compare_with_data_func_t compare, void *data)
    1.25 +{
    1.26 +	void *p, *start, *end, *pivot;
    1.27 +	int left, right, result;
    1.28 +
    1.29 +	p = base;
    1.30 +	start = base;
    1.31 +	end = base + nelem * size;
    1.32 +	pivot = base + (random() % nelem) * size;
    1.33 +	
    1.34 +	while (p < end) {
    1.35 +		result = compare(p, pivot, data);
    1.36 +		if (result < 0) {
    1.37 +			qsort_swap(p, start, size);
    1.38 +			if (start == pivot)
    1.39 +				pivot = p;
    1.40 +			start += size;
    1.41 +			p += size;
    1.42 +		} else if (result == 0) {
    1.43 +			p += size;
    1.44 +		} else {
    1.45 + 			end -= size;
    1.46 +			qsort_swap(p, end, size);
    1.47 +			if (end == pivot)
    1.48 +				pivot = p;
    1.49 +		}
    1.50 +	}
    1.51 +
    1.52 +	left = (start - base) / size;
    1.53 +	right = (base + nelem * size - end) / size;
    1.54 +	if (left > 1)
    1.55 +		qsort_with_data(base, left, size, compare, data);
    1.56 +	if (right > 1)
    1.57 +		qsort_with_data(end, right, size, compare, data);
    1.58 +}
    1.59  
    1.60  static int
    1.61 -compare_packages(const void *p1, const void *p2)
    1.62 +compare_packages(const void *p1, const void *p2, void *data)
    1.63  {
    1.64  	const struct import_package *pkg1 = p1, *pkg2 = p2;
    1.65 -	char *pool = qsort_set->string_pool.data;
    1.66 +	struct razor_set *set = data;
    1.67 +	char *pool = set->string_pool.data;
    1.68  
    1.69  	return strcmp(&pool[pkg1->name], &pool[pkg2->name]);
    1.70  }
    1.71  
    1.72  static int
    1.73 -compare_properties(const void *p1, const void *p2)
    1.74 +compare_properties(const void *p1, const void *p2, void *data)
    1.75  {
    1.76  	const struct import_property *prop1 = p1, *prop2 = p2;
    1.77 -	char *pool = qsort_set->string_pool.data;
    1.78 +	struct razor_set *set = data;
    1.79 +	char *pool = set->string_pool.data;
    1.80  	int result;
    1.81  
    1.82  	result = strcmp(&pool[prop1->name], &pool[prop2->name]);
    1.83 @@ -637,8 +689,11 @@
    1.84  	int i, count, unique;
    1.85  
    1.86  	count = in->size / sizeof(struct import_property);
    1.87 -	qsort(in->data, count,
    1.88 -	      sizeof(struct import_property), compare_properties);
    1.89 +	qsort_with_data(in->data,
    1.90 +			count,
    1.91 +			sizeof(struct import_property),
    1.92 +			compare_properties,
    1.93 +			set);
    1.94  
    1.95  	rp = NULL;
    1.96  	end = in->data + in->size;
    1.97 @@ -731,8 +786,6 @@
    1.98  	struct razor_package *rp;
    1.99  	int i, count;
   1.100  
   1.101 -	qsort_set = ctx->set;
   1.102 -
   1.103  	ctx->requires_map =
   1.104  		uniqueify_properties(ctx->set, 
   1.105  				     &ctx->requires.all,
   1.106 @@ -745,8 +798,11 @@
   1.107  	remap_package_links(ctx);
   1.108  
   1.109  	count = ctx->packages.size / sizeof(struct import_package);
   1.110 -	qsort(ctx->packages.data, count,
   1.111 -	      sizeof(struct import_package), compare_packages);
   1.112 +	qsort_with_data(ctx->packages.data,
   1.113 +			count,
   1.114 +			sizeof(struct import_package),
   1.115 +			compare_packages,
   1.116 +			ctx->set);
   1.117  
   1.118  	ip = ctx->packages.data;
   1.119  	for (i = 0; i < count; i++, ip++, rp++) {