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