Contents of /trunk/mkinitrd-magellan/klibc/usr/klibc/qsort.c
Parent Directory | Revision Log
Revision 815 -
(show annotations)
(download)
Fri Apr 24 18:32:46 2009 UTC (15 years ago) by niro
File MIME type: text/plain
File size: 800 byte(s)
Fri Apr 24 18:32:46 2009 UTC (15 years ago) by niro
File MIME type: text/plain
File size: 800 byte(s)
-updated to klibc-1.5.15
1 | /* |
2 | * qsort.c |
3 | * |
4 | * This is actually combsort. It's an O(n log n) algorithm with |
5 | * simplicity/small code size being its main virtue. |
6 | */ |
7 | |
8 | #include <stddef.h> |
9 | #include <stdlib.h> |
10 | #include <string.h> |
11 | |
12 | static inline size_t newgap(size_t gap) |
13 | { |
14 | gap = (gap * 10) / 13; |
15 | if (gap == 9 || gap == 10) |
16 | gap = 11; |
17 | |
18 | if (gap < 1) |
19 | gap = 1; |
20 | return gap; |
21 | } |
22 | |
23 | void qsort(void *base, size_t nmemb, size_t size, |
24 | int (*compar) (const void *, const void *)) |
25 | { |
26 | size_t gap = nmemb; |
27 | size_t i, j; |
28 | char *p1, *p2; |
29 | int swapped; |
30 | |
31 | if (!nmemb) |
32 | return; |
33 | |
34 | do { |
35 | gap = newgap(gap); |
36 | swapped = 0; |
37 | |
38 | for (i = 0, p1 = base; i < nmemb - gap; i++, p1 += size) { |
39 | j = i + gap; |
40 | if (compar(p1, p2 = (char *)base + j * size) > 0) { |
41 | memswap(p1, p2, size); |
42 | swapped = 1; |
43 | } |
44 | } |
45 | } while (gap > 1 || swapped); |
46 | } |