Root/
| Source at commit 1158 created 13 years 16 days ago. By azimutz, Match nvidia.c with the one on my branch (Chazi) adding dev id's from issue 99 and Asus G74SX (0DF4, 1251). | |
|---|---|
| 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 | |
