newlib/libc/search/qsort.c

   1 /*
   2 FUNCTION
   3 <<qsort>>---sort an array
   4
   5 INDEX
   6         qsort
   7
   8 SYNOPSIS
   9         #include <stdlib.h>
  10         void qsort(void *<[base]>, size_t <[nmemb]>, size_t <[size]>,
  11                    int (*<[compar]>)(const void *, const void *) );
  12
  13 DESCRIPTION
  14 <<qsort>> sorts an array (beginning at <[base]>) of <[nmemb]> objects.
  15 <[size]> describes the size of each element of the array.
  16
  17 You must supply a pointer to a comparison function, using the argument
  18 shown as <[compar]>.  (This permits sorting objects of unknown
  19 properties.)  Define the comparison function to accept two arguments,
  20 each a pointer to an element of the array starting at <[base]>.  The
  21 result of <<(*<[compar]>)>> must be negative if the first argument is
  22 less than the second, zero if the two arguments match, and positive if
  23 the first argument is greater than the second (where ``less than'' and
  24 ``greater than'' refer to whatever arbitrary ordering is appropriate).
  25
  26 The array is sorted in place; that is, when <<qsort>> returns, the
  27 array elements beginning at <[base]> have been reordered.
  28
  29 RETURNS
  30 <<qsort>> does not return a result.
  31
  32 PORTABILITY
  33 <<qsort>> is required by ANSI (without specifying the sorting algorithm).
  34 */
  35
  36 /*-
  37  * Copyright (c) 1992, 1993
  38  *      The Regents of the University of California.  All rights reserved.
  39  *
  40  * Redistribution and use in source and binary forms, with or without
  41  * modification, are permitted provided that the following conditions
  42  * are met:
  43  * 1. Redistributions of source code must retain the above copyright
  44  *    notice, this list of conditions and the following disclaimer.
  45  * 2. Redistributions in binary form must reproduce the above copyright
  46  *    notice, this list of conditions and the following disclaimer in the
  47  *    documentation and/or other materials provided with the distribution.
  48  * 3. Neither the name of the University nor the names of its contributors
  49  *    may be used to endorse or promote products derived from this software
  50  *    without specific prior written permission.
  51  *
  52  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  53  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  54  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  55  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  56  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  57  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  58  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  59  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  60  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  61  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  62  * SUCH DAMAGE.
  63  */
  64
  65 #include <_ansi.h>
  66 #include <sys/cdefs.h>
  67 #include <stdlib.h>
  68
  69 #ifndef __GNUC__
  70 #define inline
  71 #endif
  72
  73 #if defined(I_AM_QSORT_R)
  74 typedef int              cmp_t(void *, const void *, const void *);
  75 #elif defined(I_AM_GNU_QSORT_R)
  76 typedef int              cmp_t(const void *, const void *, void *);
  77 #else
  78 typedef int              cmp_t(const void *, const void *);
  79 #endif
  80 static inline char      *med3 (char *, char *, char *, cmp_t *, void *);
  81 static inline void       swapfunc (char *, char *, int, int);
  82
  83 #define min(a, b)       (a) < (b) ? a : b
  84
  85 /*
  86  * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
  87  */
  88 #define swapcode(TYPE, parmi, parmj, n) {               \
  89         long i = (n) / sizeof (TYPE);                   \
  90         TYPE *pi = (TYPE *) (parmi);            \
  91         TYPE *pj = (TYPE *) (parmj);            \
  92         do {                                            \
  93                 TYPE    t = *pi;                \
  94                 *pi++ = *pj;                            \
  95                 *pj++ = t;                              \
  96         } while (--i > 0);                              \
  97 }
  98
  99 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
 100         es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
 101
 102 static inline void
 103 swapfunc (char *a,
 104         char *b,
 105         int n,
 106         int swaptype)
 107 {
 108         if(swaptype <= 1)
 109                 swapcode(long, a, b, n)
 110         else
 111                 swapcode(char, a, b, n)
 112 }
 113
 114 #define swap(a, b)                                      \
 115         if (swaptype == 0) {                            \
 116                 long t = *(long *)(a);                  \
 117                 *(long *)(a) = *(long *)(b);            \
 118                 *(long *)(b) = t;                       \
 119         } else                                          \
 120                 swapfunc(a, b, es, swaptype)
 121
 122 #define vecswap(a, b, n)        if ((n) > 0) swapfunc(a, b, n, swaptype)
 123
 124 #if defined(I_AM_QSORT_R)
 125 #define CMP(t, x, y) (cmp((t), (x), (y)))
 126 #elif defined(I_AM_GNU_QSORT_R)
 127 #define CMP(t, x, y) (cmp((x), (y), (t)))
 128 #else
 129 #define CMP(t, x, y) (cmp((x), (y)))
 130 #endif
 131
 132 static inline char *
 133 med3 (char *a,
 134         char *b,
 135         char *c,
 136         cmp_t *cmp,
 137         void *thunk
 138 #if !defined(I_AM_QSORT_R) && !defined(I_AM_GNU_QSORT_R)
 139 __unused
 140 #endif
 141 )
 142 {
 143         return CMP(thunk, a, b) < 0 ?
 144                (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
 145               :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
 146 }
 147
 148 /*
 149  * Classical function call recursion wastes a lot of stack space. Each
 150  * recursion level requires a full stack frame comprising all local variables
 151  * and additional space as dictated by the processor calling convention.
 152  *
 153  * This implementation instead stores the variables that are unique for each
 154  * recursion level in a parameter stack array, and uses iteration to emulate
 155  * recursion. Function call recursion is not used until the array is full.
 156  *
 157  * To ensure the stack consumption isn't worsened by this design, the size of
 158  * the parameter stack array is chosen to be similar to the stack frame
 159  * excluding the array. Each function call recursion level can handle this
 160  * number of iterative recursion levels.
 161  */
 162 #define PARAMETER_STACK_LEVELS 8u
 163
 164 #if defined(I_AM_QSORT_R)
 165 void
 166 __bsd_qsort_r (void *a,
 167         size_t n,
 168         size_t es,
 169         void *thunk,
 170         cmp_t *cmp)
 171 #elif defined(I_AM_GNU_QSORT_R)
 172 void
 173 qsort_r (void *a,
 174         size_t n,
 175         size_t es,
 176         cmp_t *cmp,
 177         void *thunk)
 178 #else
 179 #define thunk NULL
 180 void
 181 qsort (void *a,
 182         size_t n,
 183         size_t es,
 184         cmp_t *cmp)
 185 #endif
 186 {
 187         char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
 188         size_t d, r;
 189         int cmp_result;
 190         int swaptype, swap_cnt;
 191         size_t recursion_level = 0;
 192         struct { void *a; size_t n; } parameter_stack[PARAMETER_STACK_LEVELS];
 193
 194         SWAPINIT(a, es);
 195 loop:   swap_cnt = 0;
 196         if (n < 7) {
 197                 /* Short arrays are insertion sorted. */
 198                 for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
 199                         for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0;
 200                              pl -= es)
 201                                 swap(pl, pl - es);
 202                 goto pop;
 203         }
 204
 205         /* Select a pivot element, move it to the left. */
 206         pm = (char *) a + (n / 2) * es;
 207         if (n > 7) {
 208                 pl = a;
 209                 pn = (char *) a + (n - 1) * es;
 210                 if (n > 40) {
 211                         d = (n / 8) * es;
 212                         pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
 213                         pm = med3(pm - d, pm, pm + d, cmp, thunk);
 214                         pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
 215                 }
 216                 pm = med3(pl, pm, pn, cmp, thunk);
 217         }
 218         swap(a, pm);
 219
 220         /*
 221          * Sort the array relative the pivot in four ranges as follows:
 222          * { elems == pivot, elems < pivot, elems > pivot, elems == pivot }
 223          */
 224         pa = pb = (char *) a + es;
 225         pc = pd = (char *) a + (n - 1) * es;
 226         for (;;) {
 227                 /* Scan left to right stopping at first element > pivot. */
 228                 while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) {
 229                         /* Move elements == pivot to the left (to pa) */
 230                         if (cmp_result == 0) {
 231                                 swap_cnt = 1;
 232                                 swap(pa, pb);
 233                                 pa += es;
 234                         }
 235                         pb += es;
 236                 }
 237                 /* Scan right to left stopping at first element < pivot. */
 238                 while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) {
 239                         /* Move elements == pivot to the right (to pd) */
 240                         if (cmp_result == 0) {
 241                                 swap_cnt = 1;
 242                                 swap(pc, pd);
 243                                 pd -= es;
 244                         }
 245                         pc -= es;
 246                 }
 247                 if (pb > pc)
 248                         break;
 249                 /* The scan has found two elements to swap with each other. */
 250                 swap(pb, pc);
 251                 swap_cnt = 1;
 252                 pb += es;
 253                 pc -= es;
 254         }
 255         if (swap_cnt == 0) {  /* Switch to insertion sort */
 256                 for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
 257                         for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0;
 258                              pl -= es)
 259                                 swap(pl, pl - es);
 260                 goto pop;
 261         }
 262
 263         /*
 264          * Rearrange the array in three parts sorted like this:
 265          * { elements < pivot, elements == pivot, elements > pivot }
 266          */
 267         pn = (char *) a + n * es;
 268         r = min(pa - (char *)a, pb - pa);
 269         vecswap(a, pb - r, r);
 270         r = min(pd - pc, pn - pd - es);
 271         vecswap(pb, pn - r, r);
 272         d = pb - pa; /* d = Size of left part. */
 273         r = pd - pc; /* r = Size of right part. */
 274         pn -= r;     /* pn = Base of right part. */
 275
 276         /*
 277          * Check which of the left and right parts are larger.
 278          * Set (a, n)  to (base, size) of the larger part.
 279          * Set (pa, r) to (base, size) of the smaller part.
 280          */
 281         if (r > d) { /* Right part is the larger part */
 282                 pa = a;
 283                 a = pn;
 284                 n = r;
 285                 r = d;
 286         }
 287         else { /* Left part is the larger part, or both are equal. */
 288                 pa = pn;
 289                 n = d;
 290         }
 291
 292         /*
 293          * The left and right parts each need further sorting if they
 294          * contain two elements or more. If both need sorting we use
 295          * recursion to sort the smaller part and save the larger part
 296          * to be sorted by iteration after the recursion.
 297          * Using recursion only for the smaller part guarantees a
 298          * recursion depth that is bounded to be less than (log2(n)).
 299          */
 300         if (r > es) {  /* Smaller part > 1 element. Both parts need sorting. */
 301                 if (recursion_level < PARAMETER_STACK_LEVELS) {
 302                         /*
 303                          * The smaller part needs to be recursively sorted
 304                          * before the larger part is sorted. To avoid function
 305                          * call recursion the parameters for the larger part
 306                          * are pushed on the parameter_stack array. The smaller
 307                          * part is sorted using iteration and the larger part
 308                          * will be sorted when the parameter_stack is popped
 309                          * after the smaller part has been sorted.
 310                          */
 311                         parameter_stack[recursion_level].a = a;
 312                         parameter_stack[recursion_level].n = n / es;
 313                         recursion_level++;
 314                         a = pa;
 315                         n = r / es;
 316                         goto loop;
 317                 }
 318                 else {
 319                         /*
 320                          * The parameter_stack array is full. The smaller part
 321                          * is sorted using function call recursion. The larger
 322                          * part will be sorted after the function call returns.
 323                          */
 324 #if defined(I_AM_QSORT_R)
 325                         __bsd_qsort_r(pa, r / es, es, thunk, cmp);
 326 #elif defined(I_AM_GNU_QSORT_R)
 327                         qsort_r(pa, r / es, es, cmp, thunk);
 328 #else
 329                         qsort(pa, r / es, es, cmp);
 330 #endif
 331                 }
 332         }
 333         if (n > es) {  /* The larger part needs sorting. Iterate to sort.  */
 334                 n = n / es;
 335                 goto loop;
 336         }
 337         /* Both left and right parts are one element or less - level done. */
 338 pop:
 339         if (recursion_level != 0) {
 340                 recursion_level--;
 341                 a = parameter_stack[recursion_level].a;
 342                 n = parameter_stack[recursion_level].n;
 343                 goto loop;
 344         }
 345 }