forked from Qortal/Brooklyn
You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
71 lines
1.6 KiB
71 lines
1.6 KiB
/* |
|
* Code adapted from uClibc-0.9.30.3 |
|
* |
|
* It is therefore covered by the GNU LESSER GENERAL PUBLIC LICENSE |
|
* Version 2.1, February 1999 |
|
* |
|
* Wolfgang Denk <[email protected]> |
|
*/ |
|
|
|
/* This code is derived from a public domain shell sort routine by |
|
* Ray Gardner and found in Bob Stout's snippets collection. The |
|
* original code is included below in an #if 0/#endif block. |
|
* |
|
* I modified it to avoid the possibility of overflow in the wgap |
|
* calculation, as well as to reduce the generated code size with |
|
* bcc and gcc. */ |
|
|
|
#include <linux/types.h> |
|
#include <common.h> |
|
#include <exports.h> |
|
|
|
void qsort(void *base, |
|
size_t nel, |
|
size_t width, |
|
int (*comp)(const void *, const void *)) |
|
{ |
|
size_t wgap, i, j, k; |
|
char tmp; |
|
|
|
if ((nel > 1) && (width > 0)) { |
|
assert(nel <= ((size_t)(-1)) / width); /* check for overflow */ |
|
wgap = 0; |
|
do { |
|
wgap = 3 * wgap + 1; |
|
} while (wgap < (nel-1)/3); |
|
/* From the above, we know that either wgap == 1 < nel or */ |
|
/* ((wgap-1)/3 < (int) ((nel-1)/3) <= (nel-1)/3 ==> wgap < nel. */ |
|
wgap *= width; /* So this can not overflow if wnel doesn't. */ |
|
nel *= width; /* Convert nel to 'wnel' */ |
|
do { |
|
i = wgap; |
|
do { |
|
j = i; |
|
do { |
|
register char *a; |
|
register char *b; |
|
|
|
j -= wgap; |
|
a = j + ((char *)base); |
|
b = a + wgap; |
|
if ((*comp)(a, b) <= 0) { |
|
break; |
|
} |
|
k = width; |
|
do { |
|
tmp = *a; |
|
*a++ = *b; |
|
*b++ = tmp; |
|
} while (--k); |
|
} while (j >= wgap); |
|
i += width; |
|
} while (i < nel); |
|
wgap = (wgap - width)/3; |
|
} while (wgap); |
|
} |
|
} |
|
|
|
int strcmp_compar(const void *p1, const void *p2) |
|
{ |
|
return strcmp(*(const char **)p1, *(const char **)p2); |
|
}
|
|
|