git.sur5r.net Git - u-boot/blob - lib/qsort.c

   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 }