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