lib/rosrtl/misc/qsort.c

   1 /* $Id$
   2  *
   3  * FILE: ntoskrnl/rtl/qsort.c
   4  * NOTE: Adapted from CygWin newlib 2000-03-12.
   5  */
   6 /*
   7 FUNCTION
   8 <<qsort>>---sort an array
   9
  10 INDEX
  11         qsort
  12
  13 ANSI_SYNOPSIS
  14         #include <stdlib.h>
  15         void qsort(void *<[base]>, size_t <[nmemb]>, size_t <[size]>,
  16                    int (*<[compar]>)(const void *, const void *) );
  17
  18 TRAD_SYNOPSIS
  19         #include <stdlib.h>
  20         qsort(<[base]>, <[nmemb]>, <[size]>, <[compar]> )
  21         char *<[base]>;
  22         size_t <[nmemb]>;
  23         size_t <[size]>;
  24         int (*<[compar]>)();
  25
  26 DESCRIPTION
  27 <<qsort>> sorts an array (beginning at <[base]>) of <[nmemb]> objects.
  28 <[size]> describes the size of each element of the array.
  29
  30 You must supply a pointer to a comparison function, using the argument
  31 shown as <[compar]>.  (This permits sorting objects of unknown
  32 properties.)  Define the comparison function to accept two arguments,
  33 each a pointer to an element of the array starting at <[base]>.  The
  34 result of <<(*<[compar]>)>> must be negative if the first argument is
  35 less than the second, zero if the two arguments match, and positive if
  36 the first argument is greater than the second (where ``less than'' and
  37 ``greater than'' refer to whatever arbitrary ordering is appropriate).
  38
  39 The array is sorted in place; that is, when <<qsort>> returns, the
  40 array elements beginning at <[base]> have been reordered.
  41
  42 RETURNS
  43 <<qsort>> does not return a result.
  44
  45 PORTABILITY
  46 <<qsort>> is required by ANSI (without specifying the sorting algorithm).
  47 */
  48
  49 /*-
  50  * Copyright (c) 1992, 1993
  51  *      The Regents of the University of California.  All rights reserved.
  52  *
  53  * Redistribution and use in source and binary forms, with or without
  54  * modification, are permitted provided that the following conditions
  55  * are met:
  56  * 1. Redistributions of source code must retain the above copyright
  57  *    notice, this list of conditions and the following disclaimer.
  58  * 2. Redistributions in binary form must reproduce the above copyright
  59  *    notice, this list of conditions and the following disclaimer in the
  60  *    documentation and/or other materials provided with the distribution.
  61  * 3. All advertising materials mentioning features or use of this software
  62  *    must display the following acknowledgement:
  63  *      This product includes software developed by the University of
  64  *      California, Berkeley and its contributors.
  65  * 4. Neither the name of the University nor the names of its contributors
  66  *    may be used to endorse or promote products derived from this software
  67  *    without specific prior written permission.
  68  *
  69  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  70  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  71  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  72  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  73  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  74  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  75  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  76  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  77  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  78  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  79  * SUCH DAMAGE.
  80  */
  81
  82 #ifndef __GNUC__
  83 #define inline
  84 #endif
  85
  86 /* FIXME: these types should be from the default includes */
  87
  88 typedef int (*  _pfunccmp_t) (char *, char *);
  89 typedef int size_t;
  90
  91 #define min(a,b) ((a)<(b)?(a):(b))
  92
  93 /*
  94  * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
  95  */
  96 #define swapcode(TYPE, parmi, parmj, n) {               \
  97         long i = (n) / sizeof (TYPE);                   \
  98         register TYPE *pi = (TYPE *) (parmi);           \
  99         register TYPE *pj = (TYPE *) (parmj);           \
 100         do {                                            \
 101                 register TYPE   t = *pi;                \
 102                 *pi++ = *pj;                            \
 103                 *pj++ = t;                              \
 104         } while (--i > 0);                              \
 105 }
 106
 107 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
 108         es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
 109
 110 static inline void
 111 swapfunc (
 112         char    * a,
 113         char    * b,
 114         int     n,
 115         int     swaptype
 116         )
 117 {
 118         if(swaptype <= 1)
 119                 swapcode(long, a, b, n)
 120         else
 121                 swapcode(char, a, b, n)
 122 }
 123
 124 #define swap(a, b)                                      \
 125         if (swaptype == 0) {                            \
 126                 long t = *(long *)(a);                  \
 127                 *(long *)(a) = *(long *)(b);            \
 128                 *(long *)(b) = t;                       \
 129         } else                                          \
 130                 swapfunc(a, b, es, swaptype)
 131
 132 #define vecswap(a, b, n)        if ((n) > 0) swapfunc(a, b, n, swaptype)
 133
 134 static inline char *
 135 med3 (
 136         char            * a,
 137         char            * b,
 138         char            * c,
 139         _pfunccmp_t     cmp
 140         )
 141 {
 142         return cmp(a, b) < 0 ?
 143                (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
 144               :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
 145 }
 146
 147
 148 /* EXPORTED */
 149 void
 150 qsort (
 151         void            * a,
 152         size_t          n,
 153         size_t          es,
 154         _pfunccmp_t     cmp
 155         )
 156 {
 157         char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
 158         int d, r, swaptype, swap_cnt;
 159
 160 loop:   SWAPINIT(a, es);
 161         swap_cnt = 0;
 162         if (n < 7)
 163         {
 164                 for (   pm = (char *) a + es;
 165                         pm < (char *) a + n * es;
 166                         pm += es
 167                         )
 168                 {
 169                         for (   pl = pm;
 170                                 pl > (char *) a && cmp(pl - es, pl) > 0;
 171                                 pl -= es
 172                                 )
 173                         {
 174                                 swap(pl, pl - es);
 175                         }
 176                 }
 177                 return;
 178         }
 179         pm = (char *) a + (n / 2) * es;
 180         if (n > 7)
 181         {
 182                 pl = (char *) a;
 183                 pn = (char *) a + (n - 1) * es;
 184                 if (n > 40)
 185                 {
 186                         d = (n / 8) * es;
 187                         pl = med3(pl, pl + d, pl + 2 * d, cmp);
 188                         pm = med3(pm - d, pm, pm + d, cmp);
 189                         pn = med3(pn - 2 * d, pn - d, pn, cmp);
 190                 }
 191                 pm = med3(pl, pm, pn, cmp);
 192         }
 193         swap(a, pm);
 194         pa = pb = (char *) a + es;
 195
 196         pc = pd = (char *) a + (n - 1) * es;
 197         for (;;)
 198         {
 199                 while (pb <= pc && (r = cmp(pb, a)) <= 0)
 200                 {
 201                         if (r == 0)
 202                         {
 203                                 swap_cnt = 1;
 204                                 swap(pa, pb);
 205                                 pa += es;
 206                         }
 207                         pb += es;
 208                 }
 209                 while (pb <= pc && (r = cmp(pc, a)) >= 0)
 210                 {
 211                         if (r == 0)
 212                         {
 213                                 swap_cnt = 1;
 214                                 swap(pc, pd);
 215                                 pd -= es;
 216                         }
 217                         pc -= es;
 218                 }
 219                 if (pb > pc)
 220                 {
 221                         break;
 222                 }
 223                 swap(pb, pc);
 224                 swap_cnt = 1;
 225                 pb += es;
 226                 pc -= es;
 227         }
 228         if (swap_cnt == 0)  /* Switch to insertion sort */
 229         {
 230                 for (   pm = (char *) a + es;
 231                         pm < (char *) a + n * es;
 232                         pm += es
 233                         )
 234                 {
 235                         for (   pl = pm;
 236                                 pl > (char *) a && cmp(pl - es, pl) > 0;
 237                                 pl -= es
 238                                 )
 239                         {
 240                                 swap(pl, pl - es);
 241                         }
 242                 }
 243                 return;
 244         }
 245
 246         pn = (char *) a + n * es;
 247         r = min(pa - (char *)a, pb - pa);
 248         vecswap(a, pb - r, r);
 249         r = min(pd - pc, pn - pd - es);
 250         vecswap(pb, pn - r, r);
 251         if ((r = pb - pa) > es)
 252         {
 253                 qsort(a, r / es, es, cmp);
 254         }
 255         if ((r = pd - pc) > es)
 256         {
 257                 /* Iterate rather than recurse to save stack space */
 258                 a = pn - r;
 259                 n = r / es;
 260                 goto loop;
 261         }
 262 /*              qsort(pn - r, r / es, es, cmp);*/
 263 }
 264
 265
 266 /* EOF */