src/stdlib/SDL_qsort.c
changeset 10085 a8e53dc3c5a1
parent 10070 734b680cba95
child 10116 418691d83f6a
equal deleted inserted replaced
10084:3bd08d2d45b0 10085:a8e53dc3c5a1
       
     1 /*
       
     2   Simple DirectMedia Layer
       
     3   Copyright (C) 1997-2016 Sam Lantinga <slouken@libsdl.org>
       
     4 
       
     5   This software is provided 'as-is', without any express or implied
       
     6   warranty.  In no event will the authors be held liable for any damages
       
     7   arising from the use of this software.
       
     8 
       
     9   Permission is granted to anyone to use this software for any purpose,
       
    10   including commercial applications, and to alter it and redistribute it
       
    11   freely, subject to the following restrictions:
       
    12 
       
    13   1. The origin of this software must not be misrepresented; you must not
       
    14      claim that you wrote the original software. If you use this software
       
    15      in a product, an acknowledgment in the product documentation would be
       
    16      appreciated but is not required.
       
    17   2. Altered source versions must be plainly marked as such, and must not be
       
    18      misrepresented as being the original software.
       
    19   3. This notice may not be removed or altered from any source distribution.
       
    20 */
       
    21 
       
    22 #if defined(__clang_analyzer__) && !defined(SDL_DISABLE_ANALYZE_MACROS)
       
    23 #define SDL_DISABLE_ANALYZE_MACROS 1
       
    24 #endif
       
    25 
     1 #include "../SDL_internal.h"
    26 #include "../SDL_internal.h"
     2 
    27 
     3 #include "SDL_stdinc.h"
    28 #include "SDL_stdinc.h"
     4 #include "SDL_assert.h"
    29 #include "SDL_assert.h"
     5 
    30 
     7 void
    32 void
     8 SDL_qsort(void *base, size_t nmemb, size_t size, int (*compare) (const void *, const void *))
    33 SDL_qsort(void *base, size_t nmemb, size_t size, int (*compare) (const void *, const void *))
     9 {
    34 {
    10     qsort(base, nmemb, size, compare);
    35     qsort(base, nmemb, size, compare);
    11 }
    36 }
       
    37 
    12 #else
    38 #else
    13 
    39 
    14 #ifdef REGTEST
    40 #ifdef assert
    15 #undef REGTEST
    41 #undef assert
    16 #endif
    42 #endif
    17 
    43 #define assert SDL_assert
    18 #ifdef TEST
    44 #ifdef malloc
    19 #undef TEST
    45 #undef malloc
    20 #endif
    46 #endif
    21 
    47 #define malloc SDL_malloc
    22 #ifndef _PDCLIB_memswp
    48 #ifdef free
    23 #define _PDCLIB_memswp( i, j, size ) char tmp; do { tmp = *i; *i++ = *j; *j++ = tmp; } while ( --size );
    49 #undef free
    24 #endif
    50 #endif
    25 
    51 #define free SDL_free
    26 #ifndef _PDCLIB_size_t
    52 #ifdef memcpy
    27 #define _PDCLIB_size_t size_t
    53 #undef memcpy
    28 #endif
    54 #endif
    29 
    55 #define memcpy SDL_memcpy
    30 #ifdef qsort
    56 #ifdef memmove
    31 #undef qsort
    57 #undef memmove
    32 #endif
    58 #endif
    33 #define qsort SDL_qsort
    59 #define memmove SDL_memmove
    34 
    60 #ifdef qsortG
    35 #define inline SDL_INLINE
    61 #undef qsortG
       
    62 #endif
       
    63 #define qsortG SDL_qsort
    36 
    64 
    37 /*
    65 /*
    38 This code came from PDCLib, under the public domain. Specifically this:
    66 This code came from Gareth McCaughan, under the zlib license.
    39 https://bitbucket.org/pdclib/pdclib/raw/a82b02d0c7d4ed633b97f2a7639d9a10b1c92ec8/functions/stdlib/qsort.c
    67 Specifically this: https://www.mccaughan.org.uk/software/qsort.c-1.14
    40 The _PDCLIB_memswp macro was from
    68 
    41 https://bitbucket.org/pdclib/pdclib/src/a82b02d0c7d4ed633b97f2a7639d9a10b1c92ec8/platform/posix/internals/_PDCLIB_config.h?at=default&fileviewer=file-view-default#_PDCLIB_config.h-28
    69 Everything below this comment until the HAVE_QSORT #endif was from Gareth
    42 
    70 (any minor changes will be noted inline).
    43 Everything below this comment until the HAVE_QSORT #endif was from PDCLib (minor changes noted inline).
    71 
       
    72 Thank you to Gareth for relicensing this code under the zlib license for our
       
    73 benefit!
       
    74 
    44 --ryan.
    75 --ryan.
    45 */
    76 */
    46 
    77 
    47 /* $Id$ */
    78 /* This is a drop-in replacement for the C library's |qsort()| routine.
    48 
    79  *
    49 /* qsort( void *, size_t, size_t, int(*)( const void *, const void * ) )
    80  * It is intended for use where you know or suspect that your
    50 
    81  * platform's qsort is bad. If that isn't the case, then you
    51    This file is part of the Public Domain C Library (PDCLib).
    82  * should probably use the qsort your system gives you in preference
    52    Permission is granted to use, modify, and / or redistribute at will.
    83  * to mine -- it will likely have been tested and tuned better.
    53 */
    84  *
    54 
    85  * Features:
    55 /* I commented this out. --ryan. #include <stdlib.h> */
    86  *   - Median-of-three pivoting (and more)
    56 
    87  *   - Truncation and final polishing by a single insertion sort
    57 #ifndef REGTEST
    88  *   - Early truncation when no swaps needed in pivoting step
    58 
    89  *   - Explicit recursion, guaranteed not to overflow
    59 /* This implementation is taken from Paul Edward's PDPCLIB.
    90  *   - A few little wrinkles stolen from the GNU |qsort()|.
    60 
    91  *     (For the avoidance of doubt, no code was stolen, only
    61    Original code is credited to Raymond Gardner, Englewood CO.
    92  *     broad ideas.)
    62    Minor mods are credited to Paul Edwards.
    93  *   - separate code for non-aligned / aligned / word-size objects
    63    Some reformatting and simplification done by Martin Baute.
    94  *
    64    All code is still Public Domain.
    95  * Earlier releases of this code used an idiosyncratic licence
    65 */
    96  * I wrote myself, because I'm an idiot. The code is now released
    66 
    97  * under the "zlib/libpng licence"; you will find the actual
    67 /* Wrapper for _PDCLIB_memswp protects against multiple argument evaluation. */
    98  * terms in the next comment. I request (but do not require)
    68 static inline void memswp( char * i, char * j, size_t size )
    99  * that if you make any changes beyond the name of the exported
    69 {
   100  * routine and reasonable tweaks to the TRUNC_* and
    70     _PDCLIB_memswp( i, j, size );
   101  * PIVOT_THRESHOLD values, you modify the _ID string so as
    71 }
   102  * to make it clear that you have changed the code.
    72 
   103  *
    73 /* For small sets, insertion sort is faster than quicksort.
   104  * If you find problems with this code, or find ways of
    74    T is the threshold below which insertion sort will be used.
   105  * making it significantly faster, please let me know!
    75    Must be 3 or larger.
   106  * My e-mail address, valid as of early 2016 and for the
    76 */
   107  * foreseeable future, is
    77 #define T 7
   108  *    gareth.mccaughan@pobox.com
    78 
   109  * Thanks!
    79 /* Macros for handling the QSort stack */
   110  *
    80 #define PREPARE_STACK char * stack[STACKSIZE]; char * * stackptr = stack
   111  * Gareth McCaughan
    81 #define PUSH( base, limit ) stackptr[0] = base; stackptr[1] = limit; stackptr += 2
   112  */
    82 #define POP( base, limit ) stackptr -= 2; base = stackptr[0]; limit = stackptr[1]
   113 
    83 /* TODO: Stack usage is log2( nmemb ) (minus what T shaves off the worst case).
   114 /* Copyright (c) 1998-2016 Gareth McCaughan
    84          Worst-case nmemb is platform dependent and should probably be 
   115  *
    85          configured through _PDCLIB_config.h.
   116  * This software is provided 'as-is', without any express or implied
    86 */
   117  * warranty. In no event will the authors be held liable for any
    87 #define STACKSIZE 64
   118  * damages arising from the use of this software.
    88 
   119  *
    89 void qsort( void * base, size_t nmemb, size_t size, int (*compar)( const void *, const void * ) )
   120  * Permission is granted to anyone to use this software for any purpose,
    90 {
   121  * including commercial applications, and to alter it and redistribute it
    91     char * i;
   122  * freely, subject to the following restrictions:
    92     char * j;
   123  *
    93     _PDCLIB_size_t thresh = T * size;
   124  * 1. The origin of this software must not be misrepresented;
    94     char * base_          = (char *)base;
   125  *    you must not claim that you wrote the original software.
    95     char * limit          = base_ + nmemb * size;
   126  *    If you use this software in a product, an acknowledgment
    96     PREPARE_STACK;
   127  *    in the product documentation would be appreciated but
    97 
   128  *    is not required.
    98     for ( ;; )
   129  *
    99     {
   130  * 2. Altered source versions must be plainly marked as such,
   100         if ( (size_t)( limit - base_ ) > thresh ) /* QSort for more than T elements. */
   131  *    and must not be misrepresented as being the original software.
   101         {
   132  *
   102             /* We work from second to last - first will be pivot element. */
   133  * 3. This notice may not be removed or altered from any source
   103             i = base_ + size;
   134  *    distribution.
   104             j = limit - size;
   135  */
   105             /* We swap first with middle element, then sort that with second
   136 
   106                and last element so that eventually first element is the median
   137 /* Revision history since release:
   107                of the three - avoiding pathological pivots.
   138  *   1998-03-19 v1.12 First release I have any records of.
   108                TODO: Instead of middle element, chose one randomly.
   139  *   2007-09-02 v1.13 Fix bug kindly reported by Dan Bodoh
   109             */
   140  *                    (premature termination of recursion).
   110             memswp( ( ( ( (size_t)( limit - base_ ) ) / size ) / 2 ) * size + base_, base_, size );
   141  *                    Add a few clarifying comments.
   111             if ( compar( i, j ) > 0 ) memswp( i, j, size );
   142  *                    Minor improvements to debug output.
   112             if ( compar( base_, j ) > 0 ) memswp( base_, j, size );
   143  *   2016-02-21 v1.14 Replace licence with 2-clause BSD,
   113             if ( compar( i, base_ ) > 0 ) memswp( i, base_, size );
   144  *                    and clarify a couple of things in
   114             /* Now we have the median for pivot element, entering main Quicksort. */
   145  *                    comments. No code changes.
   115             for ( ;; )
   146  */
   116             {
   147 
   117                 do
   148 /* BEGIN SDL CHANGE ... commented this out with an #if 0 block. --ryan. */
   118                 {
   149 #if 0
   119                     /* move i right until *i >= pivot */
   150 #include <assert.h>
   120                     i += size;
   151 #include <stdlib.h>
   121                 } while ( compar( i, base_ ) < 0 );
   152 #include <string.h>
   122                 do
   153 
   123                 {
   154 #define DEBUG_QSORT
   124                     /* move j left until *j <= pivot */
   155 
   125                     j -= size;
   156 static char _ID[]="<qsort.c gjm 1.14 2016-02-21>";
   126                 } while ( compar( j, base_ ) > 0 );
   157 #endif
   127                 if ( i > j )
   158 /* END SDL CHANGE ... commented this out with an #if 0 block. --ryan. */
   128                 {
   159 
   129                     /* break loop if pointers crossed */
   160 /* How many bytes are there per word? (Must be a power of 2,
   130                     break;
   161  * and must in fact equal sizeof(int).)
   131                 }
   162  */
   132                 /* else swap elements, keep scanning */
   163 #define WORD_BYTES sizeof(int)
   133                 memswp( i, j, size );
   164 
   134             }
   165 /* How big does our stack need to be? Answer: one entry per
   135             /* move pivot into correct place */
   166  * bit in a |size_t|.
   136             memswp( base_, j, size );
   167  */
   137             /* larger subfile base / limit to stack, sort smaller */
   168 #define STACK_SIZE (8*sizeof(size_t))
   138             if ( j - base_ > limit - i )
   169 
   139             {
   170 /* Different situations have slightly different requirements,
   140                 /* left is larger */
   171  * and we make life epsilon easier by using different truncation
   141                 PUSH( base_, j );
   172  * points for the three different cases.
   142                 base_ = i;
   173  * So far, I have tuned TRUNC_words and guessed that the same
   143             }
   174  * value might work well for the other two cases. Of course
   144             else
   175  * what works well on my machine might work badly on yours.
   145             {
   176  */
   146                 /* right is larger */
   177 #define TRUNC_nonaligned	12
   147                 PUSH( i, limit );
   178 #define TRUNC_aligned		12
   148                 limit = j;
   179 #define TRUNC_words		12*WORD_BYTES	/* nb different meaning */
   149             }
   180 
   150         }
   181 /* We use a simple pivoting algorithm for shortish sub-arrays
   151         else /* insertion sort for less than T elements              */
   182  * and a more complicated one for larger ones. The threshold
   152         {
   183  * is PIVOT_THRESHOLD.
   153             for ( j = base_, i = j + size; i < limit; j = i, i += size )
   184  */
   154             {
   185 #define PIVOT_THRESHOLD 40
   155                 for ( ; compar( j, j + size ) > 0; j -= size )
   186 
   156                 {
   187 typedef struct { char * first; char * last; } stack_entry;
   157                     memswp( j, j + size, size );
   188 #define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;}
   158                     if ( j == base_ )
   189 #define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;}
   159                     {
   190 #define doLeft {first=ffirst;llast=last;continue;}
   160                         break;
   191 #define doRight {ffirst=first;last=llast;continue;}
   161                     }
   192 #define pop {if (--stacktop<0) break;\
   162                 }
   193   first=ffirst=stack[stacktop].first;\
   163             }
   194   last=llast=stack[stacktop].last;\
   164             if ( stackptr != stack )           /* if any entries on stack  */
   195   continue;}
   165             {
   196 
   166                 POP( base_, limit );
   197 /* Some comments on the implementation.
   167             }
   198  * 1. When we finish partitioning the array into "low"
   168             else                       /* else stack empty, done   */
   199  *    and "high", we forget entirely about short subarrays,
   169             {
   200  *    because they'll be done later by insertion sort.
   170                 break;
   201  *    Doing lots of little insertion sorts might be a win
   171             }
   202  *    on large datasets for locality-of-reference reasons,
   172         }
   203  *    but it makes the code much nastier and increases
       
   204  *    bookkeeping overhead.
       
   205  * 2. We always save the shorter and get to work on the
       
   206  *    longer. This guarantees that every time we push
       
   207  *    an item onto the stack its size is <= 1/2 of that
       
   208  *    of its parent; so the stack can't need more than
       
   209  *    log_2(max-array-size) entries.
       
   210  * 3. We choose a pivot by looking at the first, last
       
   211  *    and middle elements. We arrange them into order
       
   212  *    because it's easy to do that in conjunction with
       
   213  *    choosing the pivot, and it makes things a little
       
   214  *    easier in the partitioning step. Anyway, the pivot
       
   215  *    is the middle of these three. It's still possible
       
   216  *    to construct datasets where the algorithm takes
       
   217  *    time of order n^2, but it simply never happens in
       
   218  *    practice.
       
   219  * 3' Newsflash: On further investigation I find that
       
   220  *    it's easy to construct datasets where median-of-3
       
   221  *    simply isn't good enough. So on large-ish subarrays
       
   222  *    we do a more sophisticated pivoting: we take three
       
   223  *    sets of 3 elements, find their medians, and then
       
   224  *    take the median of those.
       
   225  * 4. We copy the pivot element to a separate place
       
   226  *    because that way we can always do our comparisons
       
   227  *    directly against a pointer to that separate place,
       
   228  *    and don't have to wonder "did we move the pivot
       
   229  *    element?". This makes the inner loop better.
       
   230  * 5. It's possible to make the pivoting even more
       
   231  *    reliable by looking at more candidates when n
       
   232  *    is larger. (Taking this to its logical conclusion
       
   233  *    results in a variant of quicksort that doesn't
       
   234  *    have that n^2 worst case.) However, the overhead
       
   235  *    from the extra bookkeeping means that it's just
       
   236  *    not worth while.
       
   237  * 6. This is pretty clean and portable code. Here are
       
   238  *    all the potential portability pitfalls and problems
       
   239  *    I know of:
       
   240  *      - In one place (the insertion sort) I construct
       
   241  *        a pointer that points just past the end of the
       
   242  *        supplied array, and assume that (a) it won't
       
   243  *        compare equal to any pointer within the array,
       
   244  *        and (b) it will compare equal to a pointer
       
   245  *        obtained by stepping off the end of the array.
       
   246  *        These might fail on some segmented architectures.
       
   247  *      - I assume that there are 8 bits in a |char| when
       
   248  *        computing the size of stack needed. This would
       
   249  *        fail on machines with 9-bit or 16-bit bytes.
       
   250  *      - I assume that if |((int)base&(sizeof(int)-1))==0|
       
   251  *        and |(size&(sizeof(int)-1))==0| then it's safe to
       
   252  *        get at array elements via |int*|s, and that if
       
   253  *        actually |size==sizeof(int)| as well then it's
       
   254  *        safe to treat the elements as |int|s. This might
       
   255  *        fail on systems that convert pointers to integers
       
   256  *        in non-standard ways.
       
   257  *      - I assume that |8*sizeof(size_t)<=INT_MAX|. This
       
   258  *        would be false on a machine with 8-bit |char|s,
       
   259  *        16-bit |int|s and 4096-bit |size_t|s. :-)
       
   260  */
       
   261 
       
   262 /* The recursion logic is the same in each case.
       
   263  * We keep chopping up until we reach subarrays of size
       
   264  * strictly less than Trunc; we leave these unsorted. */
       
   265 #define Recurse(Trunc)				\
       
   266       { size_t l=last-ffirst,r=llast-first;	\
       
   267         if (l<Trunc) {				\
       
   268           if (r>=Trunc) doRight			\
       
   269           else pop				\
       
   270         }					\
       
   271         else if (l<=r) { pushLeft; doRight }	\
       
   272         else if (r>=Trunc) { pushRight; doLeft }\
       
   273         else doLeft				\
       
   274       }
       
   275 
       
   276 /* and so is the pivoting logic (note: last is inclusive): */
       
   277 #define Pivot(swapper,sz)			\
       
   278   if (last-first>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\
       
   279   else {	\
       
   280     if (compare(first,mid)<0) {			\
       
   281       if (compare(mid,last)>0) {		\
       
   282         swapper(mid,last);			\
       
   283         if (compare(first,mid)>0) swapper(first,mid);\
       
   284       }						\
       
   285     }						\
       
   286     else {					\
       
   287       if (compare(mid,last)>0) swapper(first,last)\
       
   288       else {					\
       
   289         swapper(first,mid);			\
       
   290         if (compare(mid,last)>0) swapper(mid,last);\
       
   291       }						\
       
   292     }						\
       
   293     first+=sz; last-=sz;			\
       
   294   }
       
   295 
       
   296 #ifdef DEBUG_QSORT
       
   297 #include <stdio.h>
       
   298 #endif
       
   299 
       
   300 /* and so is the partitioning logic: */
       
   301 #define Partition(swapper,sz) {			\
       
   302   do {						\
       
   303     while (compare(first,pivot)<0) first+=sz;	\
       
   304     while (compare(pivot,last)<0) last-=sz;	\
       
   305     if (first<last) {				\
       
   306       swapper(first,last);			\
       
   307       first+=sz; last-=sz; }			\
       
   308     else if (first==last) { first+=sz; last-=sz; break; }\
       
   309   } while (first<=last);			\
       
   310 }
       
   311 
       
   312 /* and so is the pre-insertion-sort operation of putting
       
   313  * the smallest element into place as a sentinel.
       
   314  * Doing this makes the inner loop nicer. I got this
       
   315  * idea from the GNU implementation of qsort().
       
   316  * We find the smallest element from the first |nmemb|,
       
   317  * or the first |limit|, whichever is smaller;
       
   318  * therefore we must have ensured that the globally smallest
       
   319  * element is in the first |limit|.
       
   320  */
       
   321 #define PreInsertion(swapper,limit,sz)		\
       
   322   first=base;					\
       
   323   last=first + ((nmemb>limit ? limit : nmemb)-1)*sz;\
       
   324   while (last!=base) {				\
       
   325     if (compare(first,last)>0) first=last;	\
       
   326     last-=sz; }					\
       
   327   if (first!=base) swapper(first,(char*)base);
       
   328 
       
   329 /* and so is the insertion sort, in the first two cases: */
       
   330 #define Insertion(swapper)			\
       
   331   last=((char*)base)+nmemb*size;		\
       
   332   for (first=((char*)base)+size;first!=last;first+=size) {	\
       
   333     char *test;					\
       
   334     /* Find the right place for |first|.	\
       
   335      * My apologies for var reuse. */		\
       
   336     for (test=first-size;compare(test,first)>0;test-=size) ;	\
       
   337     test+=size;					\
       
   338     if (test!=first) {				\
       
   339       /* Shift everything in [test,first)	\
       
   340        * up by one, and place |first|		\
       
   341        * where |test| is. */			\
       
   342       memcpy(pivot,first,size);			\
       
   343       memmove(test+size,test,first-test);	\
       
   344       memcpy(test,pivot,size);			\
       
   345     }						\
       
   346   }
       
   347 
       
   348 #define SWAP_nonaligned(a,b) { \
       
   349   register char *aa=(a),*bb=(b); \
       
   350   register size_t sz=size; \
       
   351   do { register char t=*aa; *aa++=*bb; *bb++=t; } while (--sz); }
       
   352 
       
   353 #define SWAP_aligned(a,b) { \
       
   354   register int *aa=(int*)(a),*bb=(int*)(b); \
       
   355   register size_t sz=size; \
       
   356   do { register int t=*aa;*aa++=*bb; *bb++=t; } while (sz-=WORD_BYTES); }
       
   357 
       
   358 #define SWAP_words(a,b) { \
       
   359   register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; }
       
   360 
       
   361 /* ---------------------------------------------------------------------- */
       
   362 
       
   363 static char * pivot_big(char *first, char *mid, char *last, size_t size,
       
   364                         int compare(const void *, const void *)) {
       
   365   int d=(((last-first)/size)>>3)*size;
       
   366 #ifdef DEBUG_QSORT
       
   367 fprintf(stderr, "pivot_big: first=%p last=%p size=%lu n=%lu\n", first, (unsigned long)last, size, (unsigned long)((last-first+1)/size));
       
   368 #endif
       
   369   char *m1,*m2,*m3;
       
   370   { char *a=first, *b=first+d, *c=first+2*d;
       
   371 #ifdef DEBUG_QSORT
       
   372 fprintf(stderr,"< %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
       
   373 #endif
       
   374     m1 = compare(a,b)<0 ?
       
   375            (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
       
   376          : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
       
   377   }
       
   378   { char *a=mid-d, *b=mid, *c=mid+d;
       
   379 #ifdef DEBUG_QSORT
       
   380 fprintf(stderr,". %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
       
   381 #endif
       
   382     m2 = compare(a,b)<0 ?
       
   383            (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
       
   384          : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
       
   385   }
       
   386   { char *a=last-2*d, *b=last-d, *c=last;
       
   387 #ifdef DEBUG_QSORT
       
   388 fprintf(stderr,"> %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
       
   389 #endif
       
   390     m3 = compare(a,b)<0 ?
       
   391            (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
       
   392          : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
       
   393   }
       
   394 #ifdef DEBUG_QSORT
       
   395 fprintf(stderr,"-> %d %d %d @ %p %p %p\n",*(int*)m1,*(int*)m2,*(int*)m3, m1,m2,m3);
       
   396 #endif
       
   397   return compare(m1,m2)<0 ?
       
   398            (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1))
       
   399          : (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2));
       
   400 }
       
   401 
       
   402 /* ---------------------------------------------------------------------- */
       
   403 
       
   404 static void qsort_nonaligned(void *base, size_t nmemb, size_t size,
       
   405            int (*compare)(const void *, const void *)) {
       
   406 
       
   407   stack_entry stack[STACK_SIZE];
       
   408   int stacktop=0;
       
   409   char *first,*last;
       
   410   char *pivot=malloc(size);
       
   411   size_t trunc=TRUNC_nonaligned*size;
       
   412   assert(pivot!=0);
       
   413 
       
   414   first=(char*)base; last=first+(nmemb-1)*size;
       
   415 
       
   416   if (last-first>=trunc) {
       
   417     char *ffirst=first, *llast=last;
       
   418     while (1) {
       
   419       /* Select pivot */
       
   420       { char * mid=first+size*((last-first)/size >> 1);
       
   421         Pivot(SWAP_nonaligned,size);
       
   422         memcpy(pivot,mid,size);
       
   423       }
       
   424       /* Partition. */
       
   425       Partition(SWAP_nonaligned,size);
       
   426       /* Prepare to recurse/iterate. */
       
   427       Recurse(trunc)
   173     }
   428     }
   174 }
   429   }
   175 
   430   PreInsertion(SWAP_nonaligned,TRUNC_nonaligned-1,size);
   176 #endif
   431   Insertion(SWAP_nonaligned);
   177 
   432   free(pivot);
   178 #ifdef TEST
   433 }
   179 #include <_PDCLIB_test.h>
   434 
   180 #include <string.h>
   435 static void qsort_aligned(void *base, size_t nmemb, size_t size,
   181 #include <limits.h>
   436            int (*compare)(const void *, const void *)) {
   182 
   437 
   183 static int compare( const void * left, const void * right )
   438   stack_entry stack[STACK_SIZE];
   184 {
   439   int stacktop=0;
   185     return *( (unsigned char *)left ) - *( (unsigned char *)right );
   440   char *first,*last;
   186 }
   441   char *pivot=malloc(size);
   187 
   442   size_t trunc=TRUNC_aligned*size;
   188 int main( void )
   443   assert(pivot!=0);
   189 {
   444 
   190     char presort[] = { "shreicnyjqpvozxmbt" };
   445   first=(char*)base; last=first+(nmemb-1)*size;
   191     char sorted1[] = { "bcehijmnopqrstvxyz" };
   446 
   192     char sorted2[] = { "bticjqnyozpvreshxm" };
   447   if (last-first>=trunc) {
   193     char s[19];
   448     char *ffirst=first,*llast=last;
   194     strcpy( s, presort );
   449     while (1) {
   195     qsort( s, 18, 1, compare );
   450       /* Select pivot */
   196     TESTCASE( strcmp( s, sorted1 ) == 0 );
   451       { char * mid=first+size*((last-first)/size >> 1);
   197     strcpy( s, presort );
   452         Pivot(SWAP_aligned,size);
   198     qsort( s, 9, 2, compare );
   453         memcpy(pivot,mid,size);
   199     TESTCASE( strcmp( s, sorted2 ) == 0 );
   454       }
   200     strcpy( s, presort );
   455       /* Partition. */
   201     qsort( s, 1, 1, compare );
   456       Partition(SWAP_aligned,size);
   202     TESTCASE( strcmp( s, presort ) == 0 );
   457       /* Prepare to recurse/iterate. */
   203 #if defined(REGTEST) && (__BSD_VISIBLE || __APPLE__)
   458       Recurse(trunc)
   204     puts( "qsort.c: Skipping test #4 for BSD as it goes into endless loop here." );
   459     }
   205 #else
   460   }
   206     qsort( s, 100, 0, compare );
   461   PreInsertion(SWAP_aligned,TRUNC_aligned-1,size);
   207     TESTCASE( strcmp( s, presort ) == 0 );
   462   Insertion(SWAP_aligned);
   208 #endif
   463   free(pivot);
   209     return TEST_RESULTS;
   464 }
   210 }
   465 
   211 
   466 static void qsort_words(void *base, size_t nmemb,
   212 #endif
   467            int (*compare)(const void *, const void *)) {
       
   468 
       
   469   stack_entry stack[STACK_SIZE];
       
   470   int stacktop=0;
       
   471   char *first,*last;
       
   472   char *pivot=malloc(WORD_BYTES);
       
   473   assert(pivot!=0);
       
   474 
       
   475   first=(char*)base; last=first+(nmemb-1)*WORD_BYTES;
       
   476 
       
   477   if (last-first>=TRUNC_words) {
       
   478     char *ffirst=first, *llast=last;
       
   479     while (1) {
       
   480 #ifdef DEBUG_QSORT
       
   481 fprintf(stderr,"Doing %d:%d: ",
       
   482         (first-(char*)base)/WORD_BYTES,
       
   483         (last-(char*)base)/WORD_BYTES);
       
   484 #endif
       
   485       /* Select pivot */
       
   486       { char * mid=first+WORD_BYTES*((last-first) / (2*WORD_BYTES));
       
   487         Pivot(SWAP_words,WORD_BYTES);
       
   488         *(int*)pivot=*(int*)mid;
       
   489 #ifdef DEBUG_QSORT
       
   490 fprintf(stderr,"pivot = %p = #%lu = %d\n", mid, (unsigned long)(((int*)mid)-((int*)base)), *(int*)mid);
       
   491 #endif
       
   492       }
       
   493       /* Partition. */
       
   494       Partition(SWAP_words,WORD_BYTES);
       
   495 #ifdef DEBUG_QSORT
       
   496 fprintf(stderr, "after partitioning first=#%lu last=#%lu\n", (first-(char*)base)/4lu, (last-(char*)base)/4lu);
       
   497 #endif
       
   498       /* Prepare to recurse/iterate. */
       
   499       Recurse(TRUNC_words)
       
   500     }
       
   501   }
       
   502   PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES)-1,WORD_BYTES);
       
   503   /* Now do insertion sort. */
       
   504   last=((char*)base)+nmemb*WORD_BYTES;
       
   505   for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) {
       
   506     /* Find the right place for |first|. My apologies for var reuse */
       
   507     int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first;
       
   508     *(int*)pivot=*(int*)first;
       
   509     for (;compare(pl,pivot)>0;pr=pl,--pl) {
       
   510       *pr=*pl; }
       
   511     if (pr!=(int*)first) *pr=*(int*)pivot;
       
   512   }
       
   513   free(pivot);
       
   514 }
       
   515 
       
   516 /* ---------------------------------------------------------------------- */
       
   517 
       
   518 extern void qsortG(void *base, size_t nmemb, size_t size,
       
   519            int (*compare)(const void *, const void *)) {
       
   520 
       
   521   if (nmemb<=1) return;
       
   522   if (((int)base|size)&(WORD_BYTES-1))
       
   523     qsort_nonaligned(base,nmemb,size,compare);
       
   524   else if (size!=WORD_BYTES)
       
   525     qsort_aligned(base,nmemb,size,compare);
       
   526   else
       
   527     qsort_words(base,nmemb,compare);
       
   528 }
       
   529 
   213 
   530 
   214 #endif /* HAVE_QSORT */
   531 #endif /* HAVE_QSORT */
   215 
   532 
   216 /* vi: set ts=4 sw=4 expandtab: */
   533 /* vi: set ts=4 sw=4 expandtab: */
       
   534