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