StdLib/LibC/StdLib/Qsort.c

   1 /** @file
   2   Quick Sort utility function.
   3
   4   This utility makes use of a comparison function to search arrays of
   5   unspecified type. Where an argument declared as size_t nmemb specifies the
   6   length of the array for a function, nmemb can have the value zero on a call
   7   to that function; the comparison function is not called, a search finds no
   8   matching element. Pointer arguments on such a call shall still have valid
   9   values.
  10
  11   The implementation shall ensure that both arguments of the comparison
  12   function are pointers to elements of the array.
  13
  14   The comparison function shall not alter the contents of the array. The
  15   implementation may reorder elements of the array between calls to the
  16   comparison function, but shall not alter the contents of any individual
  17   element.
  18
  19   When the same objects (consisting of size bytes, irrespective of their
  20   current positions in the array) are passed more than once to the comparison
  21   function, the results shall be consistent with one another. That is, they
  22   define a total ordering on the array.
  23
  24   A sequence point occurs immediately before and immediately after each call to
  25   the comparison function, and also between any call to the comparison function
  26   and any movement of the objects passed as arguments to that call.
  27
  28   Copyright (c) 2010, Intel Corporation. All rights reserved.<BR>
  29  * Copyright (c) 1992, 1993
  30  *  The Regents of the University of California.  All rights reserved.
  31  *
  32  * Redistribution and use in source and binary forms, with or without
  33  * modification, are permitted provided that the following conditions
  34  * are met:
  35  * 1. Redistributions of source code must retain the above copyright
  36  *    notice, this list of conditions and the following disclaimer.
  37  * 2. Redistributions in binary form must reproduce the above copyright
  38  *    notice, this list of conditions and the following disclaimer in the
  39  *    documentation and/or other materials provided with the distribution.
  40  * 4. Neither the name of the University nor the names of its contributors
  41  *    may be used to endorse or promote products derived from this software
  42  *    without specific prior written permission.
  43  *
  44  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  45  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  46  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  47  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  48  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  49  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  50  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  51  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  52  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  53  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  54  * SUCH DAMAGE.
  55
  56   ("$FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.15.2.1.2.1 2009/10/25 01:10:29 kensmith Exp $");
  57  */
  58 #include  <LibConfig.h>
  59
  60 #include  <stdlib.h>
  61
  62 typedef int    cmp_t(const void *, const void *);
  63
  64 static __inline char  *med3(char *, char *, char *, cmp_t *);
  65 static __inline void   swapfunc(char *, char *, size_t, int);
  66
  67 /*
  68  * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
  69  */
  70 #define swapcode(TYPE, parmi, parmj, n) {     \
  71   size_t i = (n) / sizeof (TYPE);       \
  72   TYPE *pi = (TYPE *) (parmi);    \
  73   TYPE *pj = (TYPE *) (parmj);    \
  74   do {            \
  75     TYPE  t = *pi;    \
  76     *pi++ = *pj;        \
  77     *pj++ = t;        \
  78         } while (--i > 0);        \
  79 }
  80
  81 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
  82   es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
  83
  84 static __inline void
  85 swapfunc(char *a, char *b, size_t n, int swaptype)
  86 {
  87   if(swaptype <= 1)
  88     swapcode(long, a, b, n)
  89   else
  90     swapcode(char, a, b, n)
  91 }
  92
  93 #define swap(a, b)          \
  94   if (swaptype == 0) {        \
  95     long t = *(long *)(a);      \
  96     *(long *)(a) = *(long *)(b);    \
  97     *(long *)(b) = t;     \
  98   } else            \
  99     swapfunc(a, b, es, swaptype)
 100
 101 #define vecswap(a, b, n)  if ((n) > 0) swapfunc(a, b, n, swaptype)
 102
 103 static __inline char *
 104 med3(char *a, char *b, char *c, cmp_t *cmp )
 105 {
 106   return cmp(a, b) < 0 ?
 107          (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
 108               :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
 109 }
 110
 111 /*  The qsort function sorts an array of nmemb objects, the initial element of
 112     which is pointed to by base.  The size of each object is specified by size.
 113
 114     The contents of the array are sorted into ascending order according to a
 115     comparison function pointed to by compar, which is called with two
 116     arguments that point to the objects being compared. The function shall
 117     return an integer less than, equal to, or greater than zero if the first
 118     argument is considered to be respectively less than, equal to, or greater
 119     than the second.
 120
 121     If two elements compare as equal, their order in the resulting sorted array
 122     is unspecified.
 123 */
 124 void
 125 qsort(void *a, size_t n, size_t es, cmp_t *cmp)
 126 {
 127   char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
 128   size_t d, r;
 129   int cmp_result;
 130   int swaptype, swap_cnt;
 131
 132 loop: SWAPINIT(a, es);
 133   swap_cnt = 0;
 134   if (n < 7) {
 135     for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
 136       for (pl = pm;
 137            pl > (char *)a && cmp(pl - es, pl) > 0;
 138            pl -= es)
 139         swap(pl, pl - es);
 140     return;
 141   }
 142   pm = (char *)a + (n / 2) * es;
 143   if (n > 7) {
 144     pl = a;
 145     pn = (char *)a + (n - 1) * es;
 146     if (n > 40) {
 147       d = (n / 8) * es;
 148       pl = med3(pl, pl + d, pl + 2 * d, cmp);
 149       pm = med3(pm - d, pm, pm + d, cmp);
 150       pn = med3(pn - 2 * d, pn - d, pn, cmp);
 151     }
 152     pm = med3(pl, pm, pn, cmp);
 153   }
 154   swap(a, pm);
 155   pa = pb = (char *)a + es;
 156
 157   pc = pd = (char *)a + (n - 1) * es;
 158   for (;;) {
 159     while (pb <= pc && (cmp_result = cmp(pb, a)) <= 0) {
 160       if (cmp_result == 0) {
 161         swap_cnt = 1;
 162         swap(pa, pb);
 163         pa += es;
 164       }
 165       pb += es;
 166     }
 167     while (pb <= pc && (cmp_result = cmp(pc, a)) >= 0) {
 168       if (cmp_result == 0) {
 169         swap_cnt = 1;
 170         swap(pc, pd);
 171         pd -= es;
 172       }
 173       pc -= es;
 174     }
 175     if (pb > pc)
 176       break;
 177     swap(pb, pc);
 178     swap_cnt = 1;
 179     pb += es;
 180     pc -= es;
 181   }
 182   if (swap_cnt == 0) {  /* Switch to insertion sort */
 183     for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
 184       for (pl = pm;
 185            pl > (char *)a && cmp(pl - es, pl) > 0;
 186            pl -= es)
 187         swap(pl, pl - es);
 188     return;
 189   }
 190
 191   pn = (char *)a + n * es;
 192   r = MIN(pa - (char *)a, pb - pa);
 193   vecswap(a, pb - r, r);
 194   r = MIN((size_t)(pd - pc), ((size_t)(pn - pd)) - es);
 195   vecswap(pb, pn - r, r);
 196   if ((size_t)(r = pb - pa) > es)
 197     qsort(a, r / es, es, cmp);
 198   if ((size_t)(r = pd - pc) > es) {
 199     /* Iterate rather than recurse to save stack space */
 200     a = pn - r;
 201     n = r / es;
 202     goto loop;
 203   }
 204 /*    qsort(pn - r, r / es, es, cmp);*/
 205 }