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 #include <exports.h> 20 21 void qsort(void *base, 22 size_t nel, 23 size_t width, 24 int (*comp)(const void *, const void *)) 25 { 26 size_t wgap, i, j, k; 27 char tmp; 28 29 if ((nel > 1) && (width > 0)) { 30 assert(nel <= ((size_t)(-1)) / width); /* check for overflow */ 31 wgap = 0; 32 do { 33 wgap = 3 * wgap + 1; 34 } while (wgap < (nel-1)/3); 35 /* From the above, we know that either wgap == 1 < nel or */ 36 /* ((wgap-1)/3 < (int) ((nel-1)/3) <= (nel-1)/3 ==> wgap < nel. */ 37 wgap *= width; /* So this can not overflow if wnel doesn't. */ 38 nel *= width; /* Convert nel to 'wnel' */ 39 do { 40 i = wgap; 41 do { 42 j = i; 43 do { 44 register char *a; 45 register char *b; 46 47 j -= wgap; 48 a = j + ((char *)base); 49 b = a + wgap; 50 if ((*comp)(a, b) <= 0) { 51 break; 52 } 53 k = width; 54 do { 55 tmp = *a; 56 *a++ = *b; 57 *b++ = tmp; 58 } while (--k); 59 } while (j >= wgap); 60 i += width; 61 } while (i < nel); 62 wgap = (wgap - width)/3; 63 } while (wgap); 64 } 65 } 66 67 int strcmp_compar(const void *p1, const void *p2) 68 { 69 return strcmp(*(const char **)p1, *(const char **)p2); 70 } 71