1 /* 2 * Code adapted from uClibc-0.9.30.3 3 * 4 * It is therefore covered by the GNU LESSER GENERAL PUBLIC LICENSE 5 * Version 2.1, February 1999 6 * 7 * Wolfgang Denk <wd@denx.de> 8 */ 9 10 /* This code is derived from a public domain shell sort routine by 11 * Ray Gardner and found in Bob Stout's snippets collection. The 12 * original code is included below in an #if 0/#endif block. 13 * 14 * I modified it to avoid the possibility of overflow in the wgap 15 * calculation, as well as to reduce the generated code size with 16 * bcc and gcc. */ 17 18 #include <linux/types.h> 19 #if 0 20 #include <assert.h> 21 #else 22 #define assert(arg) 23 #endif 24 25 void qsort(void *base, 26 size_t nel, 27 size_t width, 28 int (*comp)(const void *, const void *)) 29 { 30 size_t wgap, i, j, k; 31 char tmp; 32 33 if ((nel > 1) && (width > 0)) { 34 assert(nel <= ((size_t)(-1)) / width); /* check for overflow */ 35 wgap = 0; 36 do { 37 wgap = 3 * wgap + 1; 38 } while (wgap < (nel-1)/3); 39 /* From the above, we know that either wgap == 1 < nel or */ 40 /* ((wgap-1)/3 < (int) ((nel-1)/3) <= (nel-1)/3 ==> wgap < nel. */ 41 wgap *= width; /* So this can not overflow if wnel doesn't. */ 42 nel *= width; /* Convert nel to 'wnel' */ 43 do { 44 i = wgap; 45 do { 46 j = i; 47 do { 48 register char *a; 49 register char *b; 50 51 j -= wgap; 52 a = j + ((char *)base); 53 b = a + wgap; 54 if ((*comp)(a, b) <= 0) { 55 break; 56 } 57 k = width; 58 do { 59 tmp = *a; 60 *a++ = *b; 61 *b++ = tmp; 62 } while (--k); 63 } while (j >= wgap); 64 i += width; 65 } while (i < nel); 66 wgap = (wgap - width)/3; 67 } while (wgap); 68 } 69 } 70