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