reactos/ntoskrnl/rtl/qsort.c

   1 /* $Id: qsort.c,v 1.2 2003/07/11 01:23:15 royce Exp $
   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  *
 150  * @implemented
 151  */
 152 void
 153 qsort (
 154         void            * a,
 155         size_t          n,
 156         size_t          es,
 157         _pfunccmp_t     cmp
 158         )
 159 {
 160         char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
 161         int d, r, swaptype, swap_cnt;
 162
 163 loop:   SWAPINIT(a, es);
 164         swap_cnt = 0;
 165         if (n < 7)
 166         {
 167                 for (   pm = (char *) a + es;
 168                         pm < (char *) a + n * es;
 169                         pm += es
 170                         )
 171                 {
 172                         for (   pl = pm;
 173                                 pl > (char *) a && cmp(pl - es, pl) > 0;
 174                                 pl -= es
 175                                 )
 176                         {
 177                                 swap(pl, pl - es);
 178                         }
 179                 }
 180                 return;
 181         }
 182         pm = (char *) a + (n / 2) * es;
 183         if (n > 7)
 184         {
 185                 pl = (char *) a;
 186                 pn = (char *) a + (n - 1) * es;
 187                 if (n > 40)
 188                 {
 189                         d = (n / 8) * es;
 190                         pl = med3(pl, pl + d, pl + 2 * d, cmp);
 191                         pm = med3(pm - d, pm, pm + d, cmp);
 192                         pn = med3(pn - 2 * d, pn - d, pn, cmp);
 193                 }
 194                 pm = med3(pl, pm, pn, cmp);
 195         }
 196         swap(a, pm);
 197         pa = pb = (char *) a + es;
 198
 199         pc = pd = (char *) a + (n - 1) * es;
 200         for (;;)
 201         {
 202                 while (pb <= pc && (r = cmp(pb, a)) <= 0)
 203                 {
 204                         if (r == 0)
 205                         {
 206                                 swap_cnt = 1;
 207                                 swap(pa, pb);
 208                                 pa += es;
 209                         }
 210                         pb += es;
 211                 }
 212                 while (pb <= pc && (r = cmp(pc, a)) >= 0)
 213                 {
 214                         if (r == 0)
 215                         {
 216                                 swap_cnt = 1;
 217                                 swap(pc, pd);
 218                                 pd -= es;
 219                         }
 220                         pc -= es;
 221                 }
 222                 if (pb > pc)
 223                 {
 224                         break;
 225                 }
 226                 swap(pb, pc);
 227                 swap_cnt = 1;
 228                 pb += es;
 229                 pc -= es;
 230         }
 231         if (swap_cnt == 0)  /* Switch to insertion sort */
 232         {
 233                 for (   pm = (char *) a + es;
 234                         pm < (char *) a + n * es;
 235                         pm += es
 236                         )
 237                 {
 238                         for (   pl = pm;
 239                                 pl > (char *) a && cmp(pl - es, pl) > 0;
 240                                 pl -= es
 241                                 )
 242                         {
 243                                 swap(pl, pl - es);
 244                         }
 245                 }
 246                 return;
 247         }
 248
 249         pn = (char *) a + n * es;
 250         r = min(pa - (char *)a, pb - pa);
 251         vecswap(a, pb - r, r);
 252         r = min(pd - pc, pn - pd - es);
 253         vecswap(pb, pn - r, r);
 254         if ((r = pb - pa) > es)
 255         {
 256                 qsort(a, r / es, es, cmp);
 257         }
 258         if ((r = pd - pc) > es)
 259         {
 260                 /* Iterate rather than recurse to save stack space */
 261                 a = pn - r;
 262                 n = r / es;
 263                 goto loop;
 264         }
 265 /*              qsort(pn - r, r / es, es, cmp);*/
 266 }
 267
 268
 269 /* EOF */