litex/soc/software/libbase/qsort.c

   1 /****************************************************************************
   2  * lib/stdlib/lib_qsort.c
   3  *
   4  *   Copyright (C) 2007, 2009, 2011 Gregory Nutt. All rights reserved.
   5  *   Author: Gregory Nutt <spudmonkey@racsa.co.cr>
   6  *
   7  * Leveraged from:
   8  *
   9  *  Copyright (c) 1992, 1993
  10  *  The Regents of the University of California.  All rights reserved.
  11  *
  12  * Redistribution and use in source and binary forms, with or without
  13  * modification, are permitted provided that the following conditions
  14  * are met:
  15  *
  16  * 1. Redistributions of source code must retain the above copyright
  17  *    notice, this list of conditions and the following disclaimer.
  18  * 2. Redistributions in binary form must reproduce the above copyright
  19  *    notice, this list of conditions and the following disclaimer in the
  20  *    documentation and/or other materials provided with the distribution.
  21  * 3. All advertising materials mentioning features or use of this software
  22  *    must display the following acknowledgement:
  23  *    This product includes software developed by the University of
  24  *    California, Berkeley and its contributors.
  25  * 4. Neither the name of the University nor the names of its contributors
  26  *    may be used to endorse or promote products derived from this software
  27  *    without specific prior written permission.
  28  *
  29  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  30  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  31  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  32  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  33  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  34  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  35  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  36  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  37  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  38  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  39  * SUCH DAMAGE.
  40  *
  41  ****************************************************************************/
  42
  43 #include <stdlib.h>
  44
  45 #define min(a, b)  (a) < (b) ? a : b
  46
  47 #define swapcode(TYPE, parmi, parmj, n) \
  48   { \
  49     long i = (n) / sizeof (TYPE); \
  50     register TYPE *pi = (TYPE *) (parmi); \
  51     register TYPE *pj = (TYPE *) (parmj); \
  52     do { \
  53       register TYPE  t = *pi; \
  54       *pi++ = *pj; \
  55       *pj++ = t; \
  56     } while (--i > 0); \
  57   }
  58
  59 #define SWAPINIT(a, size) \
  60   swaptype = ((char *)a - (char *)0) % sizeof(long) || \
  61   size % sizeof(long) ? 2 : size == sizeof(long)? 0 : 1;
  62
  63 #define swap(a, b) \
  64   if (swaptype == 0) \
  65     { \
  66       long t = *(long *)(a); \
  67       *(long *)(a) = *(long *)(b); \
  68       *(long *)(b) = t; \
  69     } \
  70   else \
  71     { \
  72       swapfunc(a, b, size, swaptype); \
  73     }
  74
  75 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
  76
  77 static inline void swapfunc(char *a, char *b, int n, int swaptype);
  78 static inline char *med3(char *a, char *b, char *c,
  79                          int (*compar)(const void *, const void *));
  80
  81 static inline void swapfunc(char *a, char *b, int n, int swaptype)
  82 {
  83   if(swaptype <= 1)
  84     {
  85       swapcode(long, a, b, n)
  86     }
  87   else
  88     {
  89       swapcode(char, a, b, n)
  90     }
  91 }
  92
  93 static inline char *med3(char *a, char *b, char *c,
  94                          int (*compar)(const void *, const void *))
  95 {
  96   return compar(a, b) < 0 ?
  97          (compar(b, c) < 0 ? b : (compar(a, c) < 0 ? c : a ))
  98               :(compar(b, c) > 0 ? b : (compar(a, c) < 0 ? a : c ));
  99 }
 100
 101 /****************************************************************************
 102  * Name: qsort
 103  *
 104  * Description:
 105  *   Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
 106  *
 107  ****************************************************************************/
 108
 109 void qsort(void *base, size_t nmemb, size_t size,
 110            int(*compar)(const void *, const void *))
 111 {
 112   char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
 113   int d, r, swaptype, swap_cnt;
 114
 115 loop:
 116   SWAPINIT(base, size);
 117   swap_cnt = 0;
 118   if (nmemb < 7)
 119     {
 120       for (pm = (char *) base + size; pm < (char *) base + nmemb * size; pm += size)
 121         {
 122           for (pl = pm; pl > (char *) base && compar(pl - size, pl) > 0; pl -= size)
 123             {
 124               swap(pl, pl - size);
 125             }
 126         }
 127       return;
 128   }
 129
 130   pm = (char *) base + (nmemb / 2) * size;
 131   if (nmemb > 7)
 132     {
 133       pl = base;
 134       pn = (char *) base + (nmemb - 1) * size;
 135       if (nmemb > 40)
 136         {
 137           d = (nmemb / 8) * size;
 138           pl = med3(pl, pl + d, pl + 2 * d, compar);
 139           pm = med3(pm - d, pm, pm + d, compar);
 140           pn = med3(pn - 2 * d, pn - d, pn, compar);
 141         }
 142       pm = med3(pl, pm, pn, compar);
 143     }
 144   swap(base, pm);
 145   pa = pb = (char *) base + size;
 146
 147   pc = pd = (char *) base + (nmemb - 1) * size;
 148   for (;;)
 149     {
 150       while (pb <= pc && (r = compar(pb, base)) <= 0)
 151         {
 152           if (r == 0)
 153             {
 154               swap_cnt = 1;
 155               swap(pa, pb);
 156               pa += size;
 157             }
 158           pb += size;
 159         }
 160       while (pb <= pc && (r = compar(pc, base)) >= 0)
 161         {
 162           if (r == 0)
 163             {
 164               swap_cnt = 1;
 165               swap(pc, pd);
 166               pd -= size;
 167             }
 168           pc -= size;
 169         }
 170
 171       if (pb > pc)
 172         {
 173           break;
 174         }
 175
 176       swap(pb, pc);
 177       swap_cnt = 1;
 178       pb += size;
 179       pc -= size;
 180     }
 181
 182   if (swap_cnt == 0)
 183     {
 184       /* Switch to insertion sort */
 185
 186       for (pm = (char *) base + size; pm < (char *) base + nmemb * size; pm += size)
 187         {
 188           for (pl = pm; pl > (char *) base && compar(pl - size, pl) > 0; pl -= size)
 189             {
 190               swap(pl, pl - size);
 191             }
 192         }
 193       return;
 194     }
 195
 196   pn = (char *) base + nmemb * size;
 197   r = min(pa - (char *)base, pb - pa);
 198   vecswap(base, pb - r, r);
 199   r = min(pd - pc, pn - pd - size);
 200   vecswap(pb, pn - r, r);
 201
 202   if ((r = pb - pa) > size)
 203     {
 204       qsort(base, r / size, size, compar);
 205     }
 206
 207   if ((r = pd - pc) > size)
 208     {
 209       /* Iterate rather than recurse to save stack space */
 210       base = pn - r;
 211       nmemb = r / size;
 212       goto loop;
 213     }
 214 }
 215