compiler/stdc/qsort.c

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