1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
/* +++Date last modified: 05-Jul-1997 */
/*
** ssort() -- Fast, small, qsort()-compatible Shell sort
**
** by Ray Gardner, public domain 5/90
*/
/*
* Manuel Novoa III Dec 2000
*
* There were several problems with the qsort code contained in uClibc.
* It assumed sizeof(int) was 2 and sizeof(long) was 4. It then had three
* seperate quiicksort routines based on the width of the data passed: 2, 4,
* or anything else <= 128. If the width was > 128, it returned -1 (although
* qsort should not return a value) and did no sorting. On i386 with
* -Os -fomit-frame-pointer -ffunction-sections, the text segment of qsort.o
* was 1358 bytes, with an additional 4 bytes in bss.
*
* I decided to completely replace the existing code with a small
* implementation of a shell sort. It is a drop-in replacement for the
* standard qsort and, with the same gcc flags as above, the text segment
* size on i386 is only 183 bytes.
*
* Grabbed original file rg_ssort.c from snippets.org.
* Modified original code to avoid possible overflow in wgap calculation.
* Modified wgap calculation in loop and eliminated variables gap and wnel.
*/
#include <stdlib.h>
#include <assert.h>
void qsort (void *base,
size_t nel,
size_t width,
int (*comp)(const void *, const void *))
{
size_t wgap, i, j, k;
char *a, *b, tmp;
/* Note: still conceivable that nel * width could overflow! */
assert(width > 0);
if (nel > 1) {
for (wgap = 0; ++wgap < (nel-1)/3 ; wgap *= 3) {}
wgap *= width;
nel *= width; /* convert nel to 'wnel' */
do {
for (i = wgap; i < nel; i += width) {
for (j = i - wgap; ;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 );
if (j < wgap) {
break;
}
}
}
wgap = (wgap - width)/3;
} while (wgap);
}
}
|
