Root/
| Source at commit 1406 created 12 years 10 months ago. By meklort, Revert drivers.c so that kexts are only loaded when OSBundleRequired is set and that value is not safe mode. Added some comments about it too. | |
|---|---|
| 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 | extern void memswap(void *m1, void *m2, size_t n);␊ |
| 13 | ␊ |
| 14 | static inline size_t newgap(size_t gap)␊ |
| 15 | {␊ |
| 16 | ␉gap = (gap * 10) / 13;␊ |
| 17 | ␉if (gap == 9 || gap == 10)␊ |
| 18 | ␉␉gap = 11;␊ |
| 19 | ␊ |
| 20 | ␉if (gap < 1)␊ |
| 21 | ␉␉gap = 1;␊ |
| 22 | ␉return gap;␊ |
| 23 | }␊ |
| 24 | ␊ |
| 25 | void qsort(void *base, size_t nmemb, size_t size,␊ |
| 26 | ␉ int (*compar) (const void *, const void *))␊ |
| 27 | {␊ |
| 28 | ␉size_t gap = nmemb;␊ |
| 29 | ␉size_t i, j;␊ |
| 30 | ␉char *p1, *p2;␊ |
| 31 | ␉int swapped;␊ |
| 32 | ␊ |
| 33 | ␉if (!nmemb)␊ |
| 34 | ␉␉return;␊ |
| 35 | ␊ |
| 36 | ␉do {␊ |
| 37 | ␉␉gap = newgap(gap);␊ |
| 38 | ␉␉swapped = 0;␊ |
| 39 | ␊ |
| 40 | ␉␉for (i = 0, p1 = base; i < nmemb - gap; i++, p1 += size) {␊ |
| 41 | ␉␉␉j = i + gap;␊ |
| 42 | ␉␉␉if (compar(p1, p2 = (char *)base + j * size) > 0) {␊ |
| 43 | ␉␉␉␉memswap(p1, p2, size);␊ |
| 44 | ␉␉␉␉swapped = 1;␊ |
| 45 | ␉␉␉}␊ |
| 46 | ␉␉}␊ |
| 47 | ␉} while (gap > 1 || swapped);␊ |
| 48 | }␊ |
| 49 | |
