Contents of /trunk/mkinitrd-magellan/klibc/usr/klibc/qsort.c
Parent Directory | Revision Log
Revision 532 -
(show annotations)
(download)
Sat Sep 1 22:45:15 2007 UTC (16 years, 8 months ago) by niro
File MIME type: text/plain
File size: 780 byte(s)
Sat Sep 1 22:45:15 2007 UTC (16 years, 8 months ago) by niro
File MIME type: text/plain
File size: 780 byte(s)
-import if magellan mkinitrd; it is a fork of redhats mkinitrd-5.0.8 with all magellan patches and features; deprecates magellan-src/mkinitrd
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 <string.h> |
10 | |
11 | static inline size_t newgap(size_t gap) |
12 | { |
13 | gap = (gap * 10) / 13; |
14 | if (gap == 9 || gap == 10) |
15 | gap = 11; |
16 | |
17 | if (gap < 1) |
18 | gap = 1; |
19 | return gap; |
20 | } |
21 | |
22 | void qsort(void *base, size_t nmemb, size_t size, |
23 | int (*compar) (const void *, const void *)) |
24 | { |
25 | size_t gap = nmemb; |
26 | size_t i, j; |
27 | char *p1, *p2; |
28 | int swapped; |
29 | |
30 | if (!nmemb) |
31 | return; |
32 | |
33 | do { |
34 | gap = newgap(gap); |
35 | swapped = 0; |
36 | |
37 | for (i = 0, p1 = base; i < nmemb - gap; i++, p1 += size) { |
38 | j = i + gap; |
39 | if (compar(p1, p2 = (char *)base + j * size) > 0) { |
40 | memswap(p1, p2, size); |
41 | swapped = 1; |
42 | } |
43 | } |
44 | } while (gap > 1 || swapped); |
45 | } |