compiler/clib/qsort.c

   1 /*
   2     Copyright © 1995-2003, The AROS Development Team. All rights reserved.
   3     $Id$
   4
   5     ANSI C function qsort().
   6 */
   7 /* Original source from NetBSD */
   8 #include <exec/types.h>
   9 #include <sys/types.h>
  10 #include <stdlib.h>
  11
  12 static inline const char *med3 (const char *, const char *, const char *, int (*)());
  13 static inline void       swapfunc (char *, char *, int, int);
  14
  15 #define min(a, b)       (a) < (b) ? a : b
  16
  17 /*
  18  * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
  19  */
  20 #define swapcode(TYPE, parmi, parmj, n) {               \
  21         long i = (n) / sizeof (TYPE);                   \
  22         register TYPE *pi = (TYPE *) (parmi);           \
  23         register TYPE *pj = (TYPE *) (parmj);           \
  24         do {                                            \
  25                 register TYPE   t = *pi;                \
  26                 *pi++ = *pj;                            \
  27                 *pj++ = t;                              \
  28         } while (--i > 0);                              \
  29 }
  30
  31 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
  32         es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
  33
  34 static inline void
  35 swapfunc (char *a, char *b, int n, int swaptype)
  36 {
  37         if(swaptype <= 1)
  38                 swapcode(long, a, b, n)
  39         else
  40                 swapcode(char, a, b, n)
  41 }
  42
  43 #define swap(a, b)                                      \
  44         if (swaptype == 0) {                            \
  45                 long t = *(long *)(a);                  \
  46                 *(long *)(a) = *(long *)(b);            \
  47                 *(long *)(b) = t;                       \
  48         } else                                          \
  49                 swapfunc(a, b, es, swaptype)
  50
  51 #define vecswap(a, b, n)        if ((n) > 0) swapfunc(a, b, n, swaptype)
  52
  53 static inline const char *
  54 med3(const char *a, const char *b, const char *c, int (*cmp)(const void *, const void *))
  55 {
  56         return cmp(a, b) < 0 ?
  57                (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
  58               :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
  59 }
  60
  61 /*****************************************************************************
  62
  63     NAME */
  64
  65         void qsort (
  66
  67 /*  SYNOPSIS */
  68         void * a,
  69         size_t n,
  70         size_t es,
  71         int (* cmp)(const void *, const void *))
  72
  73 /*  FUNCTION
  74         Sort the array a. It contains n elements of the size es. Elements
  75         are compares using the function cmp().
  76
  77     INPUTS
  78         a - The array to sort
  79         n - The number of elements in the array
  80         es - The size of a single element in the array
  81         cmp - The function which is called when two elements must be
  82                 compared. The function gets the addresses of two elements
  83                 of the array and must return 0 is both are equal, < 0 if
  84                 the first element is less than the second and > 0 otherwise.
  85
  86     RESULT
  87         None.
  88
  89     NOTES
  90
  91     EXAMPLE
  92         // Use this function to compare to stringpointers
  93         int cmp_strptr (const char ** sptr1, const char ** sptr2)
  94         {
  95             return strcmp (*sptr1, *sptr2);
  96         }
  97
  98         // Sort an array of strings
  99         char ** strings;
 100
 101         // fill the array
 102         strings = malloc (sizeof (char *)*4);
 103         strings[0] = strdup ("h");
 104         strings[1] = strdup ("a");
 105         strings[2] = strdup ("f");
 106         strings[3] = strdup ("d");
 107
 108         // Sort it
 109         qsort (strings, sizeof (char *), 4, (void *)cmp_strptr);
 110
 111     BUGS
 112
 113     SEE ALSO
 114         strcmp(), strncmp(), memcmp(), strcasecmp(), strncasecmp()
 115
 116     INTERNALS
 117
 118 ******************************************************************************/
 119 {
 120         char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
 121         int d, r, swaptype, swap_cnt;
 122
 123
 124 loop:   SWAPINIT(a, es);
 125         swap_cnt = 0;
 126         if (n < 7) {
 127                 for (pm = a + es; pm < (char *) a + n * es; pm += es)
 128                         for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
 129                              pl -= es)
 130                                 swap(pl, pl - es);
 131                 return;
 132         }
 133         pm = a + (n / 2) * es;
 134         if (n > 7) {
 135                 pl = a;
 136                 pn = a + (n - 1) * es;
 137                 if (n > 40) {
 138                         d = (n / 8) * es;
 139                         pl = (char *)med3(pl, pl + d, pl + 2 * d, cmp);
 140                         pm = (char *)med3(pm - d, pm, pm + d, cmp);
 141                         pn = (char *)med3(pn - 2 * d, pn - d, pn, cmp);
 142                 }
 143                 pm = (char *)med3(pl, pm, pn, cmp);
 144         }
 145         swap(a, pm);
 146         pa = pb = a + es;
 147
 148         pc = pd = a + (n - 1) * es;
 149         for (;;) {
 150                 while (pb <= pc && (r = cmp(pb, a)) <= 0) {
 151                         if (r == 0) {
 152                                 swap_cnt = 1;
 153                                 swap(pa, pb);
 154                                 pa += es;
 155                         }
 156                         pb += es;
 157                 }
 158                 while (pb <= pc && (r = cmp(pc, a)) >= 0) {
 159                         if (r == 0) {
 160                                 swap_cnt = 1;
 161                                 swap(pc, pd);
 162                                 pd -= es;
 163                         }
 164                         pc -= es;
 165                 }
 166                 if (pb > pc)
 167                         break;
 168                 swap(pb, pc);
 169                 swap_cnt = 1;
 170                 pb += es;
 171                 pc -= es;
 172         }
 173         if (swap_cnt == 0) {  /* Switch to insertion sort */
 174                 for (pm = a + es; pm < (char *) a + n * es; pm += es)
 175                         for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
 176                              pl -= es)
 177                                 swap(pl, pl - es);
 178                 return;
 179         }
 180
 181         pn = a + n * es;
 182         r = min(pa - (char *)a, pb - pa);
 183         vecswap(a, pb - r, r);
 184         r = min(pd - pc, pn - pd - es);
 185         vecswap(pb, pn - r, r);
 186         if ((r = pb - pa) > es)
 187                 qsort(a, r / es, es, cmp);
 188         if ((r = pd - pc) > es) {
 189                 /* Iterate rather than recurse to save stack space */
 190                 a = pn - r;
 191                 n = r / es;
 192                 goto loop;
 193         }
 194 /*              qsort(pn - r, r / es, es, cmp);*/
 195 }