Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
authorRyan C. Gordon <icculus@icculus.org>
Mon, 15 Feb 2016 03:16:46 -0500
changeset 1006819998f9082dc
parent 10067 5be0ebfaad70
child 10069 ba33b870b45c
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
debian/copyright
src/stdlib/SDL_qsort.c
     1.1 --- a/debian/copyright	Sun Feb 14 21:17:25 2016 -0400
     1.2 +++ b/debian/copyright	Mon Feb 15 03:16:46 2016 -0500
     1.3 @@ -31,10 +31,6 @@
     1.4             1995 Brown University
     1.5  License: BrownUn_UnCalifornia_ErikCorry
     1.6  
     1.7 -Files: src/stdlib/SDL_qsort.c
     1.8 -Copyright: 1998 Gareth McCaughan
     1.9 -License: Gareth_McCaughan
    1.10 -
    1.11  Files: src/test/SDL_test_md5.c
    1.12  Copyright: 1997-2016 Sam Lantinga <slouken@libsdl.org>
    1.13             1990 RSA Data Security, Inc.
    1.14 @@ -270,13 +266,6 @@
    1.15    * SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
    1.16    */
    1.17  
    1.18 -License: Gareth_McCaughan
    1.19 -  You may use it in anything you like; you may make money
    1.20 -  out of it; you may distribute it in object form or as
    1.21 -  part of an executable without including source code;
    1.22 -  you don't have to credit me. (But it would be nice if
    1.23 -  you did.)
    1.24 -
    1.25  License: Johnson_M._Hart
    1.26    Permission is granted for any and all use providing that this
    1.27    copyright is properly acknowledged.
     2.1 --- a/src/stdlib/SDL_qsort.c	Sun Feb 14 21:17:25 2016 -0400
     2.2 +++ b/src/stdlib/SDL_qsort.c	Mon Feb 15 03:16:46 2016 -0500
     2.3 @@ -1,58 +1,5 @@
     2.4 -/* qsort.c
     2.5 - * (c) 1998 Gareth McCaughan
     2.6 - *
     2.7 - * This is a drop-in replacement for the C library's |qsort()| routine.
     2.8 - *
     2.9 - * Features:
    2.10 - *   - Median-of-three pivoting (and more)
    2.11 - *   - Truncation and final polishing by a single insertion sort
    2.12 - *   - Early truncation when no swaps needed in pivoting step
    2.13 - *   - Explicit recursion, guaranteed not to overflow
    2.14 - *   - A few little wrinkles stolen from the GNU |qsort()|.
    2.15 - *   - separate code for non-aligned / aligned / word-size objects
    2.16 - *
    2.17 - * This code may be reproduced freely provided
    2.18 - *   - this file is retained unaltered apart from minor
    2.19 - *     changes for portability and efficiency
    2.20 - *   - no changes are made to this comment
    2.21 - *   - any changes that *are* made are clearly flagged
    2.22 - *   - the _ID string below is altered by inserting, after
    2.23 - *     the date, the string " altered" followed at your option
    2.24 - *     by other material. (Exceptions: you may change the name
    2.25 - *     of the exported routine without changing the ID string.
    2.26 - *     You may change the values of the macros TRUNC_* and
    2.27 - *     PIVOT_THRESHOLD without changing the ID string, provided
    2.28 - *     they remain constants with TRUNC_nonaligned, TRUNC_aligned
    2.29 - *     and TRUNC_words/WORD_BYTES between 8 and 24, and
    2.30 - *     PIVOT_THRESHOLD between 32 and 200.)
    2.31 - *
    2.32 - * You may use it in anything you like; you may make money
    2.33 - * out of it; you may distribute it in object form or as
    2.34 - * part of an executable without including source code;
    2.35 - * you don't have to credit me. (But it would be nice if
    2.36 - * you did.)
    2.37 - *
    2.38 - * If you find problems with this code, or find ways of
    2.39 - * making it significantly faster, please let me know!
    2.40 - * My e-mail address, valid as of early 1998 and certainly
    2.41 - * OK for at least the next 18 months, is
    2.42 - *    gjm11@dpmms.cam.ac.uk
    2.43 - * Thanks!
    2.44 - *
    2.45 - * Gareth McCaughan   Peterhouse   Cambridge   1998
    2.46 - */
    2.47 -
    2.48 -#if defined(__clang_analyzer__) && !defined(SDL_DISABLE_ANALYZE_MACROS)
    2.49 -#define SDL_DISABLE_ANALYZE_MACROS 1
    2.50 -#endif
    2.51 -
    2.52  #include "../SDL_internal.h"
    2.53  
    2.54 -/*
    2.55 -#include <assert.h>
    2.56 -#include <stdlib.h>
    2.57 -#include <string.h>
    2.58 -*/
    2.59  #include "SDL_stdinc.h"
    2.60  #include "SDL_assert.h"
    2.61  
    2.62 @@ -64,418 +11,203 @@
    2.63  }
    2.64  #else
    2.65  
    2.66 -#ifdef assert
    2.67 -#undef assert
    2.68 -#endif
    2.69 -#define assert(X) SDL_assert(X)
    2.70 -#ifdef malloc
    2.71 -#undef malloc
    2.72 -#endif
    2.73 -#define malloc	SDL_malloc
    2.74 -#ifdef free
    2.75 -#undef free
    2.76 -#endif
    2.77 -#define free	SDL_free
    2.78 -#ifdef memcpy
    2.79 -#undef memcpy
    2.80 -#endif
    2.81 -#define memcpy	SDL_memcpy
    2.82 -#ifdef memmove
    2.83 -#undef memmove
    2.84 -#endif
    2.85 -#define memmove	SDL_memmove
    2.86 -#ifdef qsort
    2.87 -#undef qsort
    2.88 -#endif
    2.89 -#define qsort	SDL_qsort
    2.90 -
    2.91 -static const char _ID[] = "<qsort.c gjm 1.12 1998-03-19>";
    2.92 -
    2.93 -/* How many bytes are there per word? (Must be a power of 2,
    2.94 - * and must in fact equal sizeof(int).)
    2.95 - */
    2.96 -#define WORD_BYTES sizeof(int)
    2.97 -
    2.98 -/* How big does our stack need to be? Answer: one entry per
    2.99 - * bit in a |size_t|.
   2.100 - */
   2.101 -#define STACK_SIZE (8*sizeof(size_t))
   2.102 -
   2.103 -/* Different situations have slightly different requirements,
   2.104 - * and we make life epsilon easier by using different truncation
   2.105 - * points for the three different cases.
   2.106 - * So far, I have tuned TRUNC_words and guessed that the same
   2.107 - * value might work well for the other two cases. Of course
   2.108 - * what works well on my machine might work badly on yours.
   2.109 - */
   2.110 -#define TRUNC_nonaligned	12
   2.111 -#define TRUNC_aligned		12
   2.112 -#define TRUNC_words		12*WORD_BYTES   /* nb different meaning */
   2.113 -
   2.114 -/* We use a simple pivoting algorithm for shortish sub-arrays
   2.115 - * and a more complicated one for larger ones. The threshold
   2.116 - * is PIVOT_THRESHOLD.
   2.117 - */
   2.118 -#define PIVOT_THRESHOLD 40
   2.119 -
   2.120 -typedef struct
   2.121 -{
   2.122 -    char *first;
   2.123 -    char *last;
   2.124 -} stack_entry;
   2.125 -#define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;}
   2.126 -#define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;}
   2.127 -#define doLeft {first=ffirst;llast=last;continue;}
   2.128 -#define doRight {ffirst=first;last=llast;continue;}
   2.129 -#define pop {if (--stacktop<0) break;\
   2.130 -  first=ffirst=stack[stacktop].first;\
   2.131 -  last=llast=stack[stacktop].last;\
   2.132 -  continue;}
   2.133 -
   2.134 -/* Some comments on the implementation.
   2.135 - * 1. When we finish partitioning the array into "low"
   2.136 - *    and "high", we forget entirely about short subarrays,
   2.137 - *    because they'll be done later by insertion sort.
   2.138 - *    Doing lots of little insertion sorts might be a win
   2.139 - *    on large datasets for locality-of-reference reasons,
   2.140 - *    but it makes the code much nastier and increases
   2.141 - *    bookkeeping overhead.
   2.142 - * 2. We always save the shorter and get to work on the
   2.143 - *    longer. This guarantees that every time we push
   2.144 - *    an item onto the stack its size is <= 1/2 of that
   2.145 - *    of its parent; so the stack can't need more than
   2.146 - *    log_2(max-array-size) entries.
   2.147 - * 3. We choose a pivot by looking at the first, last
   2.148 - *    and middle elements. We arrange them into order
   2.149 - *    because it's easy to do that in conjunction with
   2.150 - *    choosing the pivot, and it makes things a little
   2.151 - *    easier in the partitioning step. Anyway, the pivot
   2.152 - *    is the middle of these three. It's still possible
   2.153 - *    to construct datasets where the algorithm takes
   2.154 - *    time of order n^2, but it simply never happens in
   2.155 - *    practice.
   2.156 - * 3' Newsflash: On further investigation I find that
   2.157 - *    it's easy to construct datasets where median-of-3
   2.158 - *    simply isn't good enough. So on large-ish subarrays
   2.159 - *    we do a more sophisticated pivoting: we take three
   2.160 - *    sets of 3 elements, find their medians, and then
   2.161 - *    take the median of those.
   2.162 - * 4. We copy the pivot element to a separate place
   2.163 - *    because that way we can always do our comparisons
   2.164 - *    directly against a pointer to that separate place,
   2.165 - *    and don't have to wonder "did we move the pivot
   2.166 - *    element?". This makes the inner loop better.
   2.167 - * 5. It's possible to make the pivoting even more
   2.168 - *    reliable by looking at more candidates when n
   2.169 - *    is larger. (Taking this to its logical conclusion
   2.170 - *    results in a variant of quicksort that doesn't
   2.171 - *    have that n^2 worst case.) However, the overhead
   2.172 - *    from the extra bookkeeping means that it's just
   2.173 - *    not worth while.
   2.174 - * 6. This is pretty clean and portable code. Here are
   2.175 - *    all the potential portability pitfalls and problems
   2.176 - *    I know of:
   2.177 - *      - In one place (the insertion sort) I construct
   2.178 - *        a pointer that points just past the end of the
   2.179 - *        supplied array, and assume that (a) it won't
   2.180 - *        compare equal to any pointer within the array,
   2.181 - *        and (b) it will compare equal to a pointer
   2.182 - *        obtained by stepping off the end of the array.
   2.183 - *        These might fail on some segmented architectures.
   2.184 - *      - I assume that there are 8 bits in a |char| when
   2.185 - *        computing the size of stack needed. This would
   2.186 - *        fail on machines with 9-bit or 16-bit bytes.
   2.187 - *      - I assume that if |((int)base&(sizeof(int)-1))==0|
   2.188 - *        and |(size&(sizeof(int)-1))==0| then it's safe to
   2.189 - *        get at array elements via |int*|s, and that if
   2.190 - *        actually |size==sizeof(int)| as well then it's
   2.191 - *        safe to treat the elements as |int|s. This might
   2.192 - *        fail on systems that convert pointers to integers
   2.193 - *        in non-standard ways.
   2.194 - *      - I assume that |8*sizeof(size_t)<=INT_MAX|. This
   2.195 - *        would be false on a machine with 8-bit |char|s,
   2.196 - *        16-bit |int|s and 4096-bit |size_t|s. :-)
   2.197 - */
   2.198 -
   2.199 -/* The recursion logic is the same in each case: */
   2.200 -#define Recurse(Trunc)				\
   2.201 -      { size_t l=last-ffirst,r=llast-first;	\
   2.202 -        if (l<Trunc) {				\
   2.203 -          if (r>=Trunc) doRight			\
   2.204 -          else pop				\
   2.205 -        }					\
   2.206 -        else if (l<=r) { pushLeft; doRight }	\
   2.207 -        else if (r>=Trunc) { pushRight; doLeft }\
   2.208 -        else doLeft				\
   2.209 -      }
   2.210 -
   2.211 -/* and so is the pivoting logic: */
   2.212 -#define Pivot(swapper,sz)			\
   2.213 -  if ((size_t)(last-first)>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\
   2.214 -  else {	\
   2.215 -    if (compare(first,mid)<0) {			\
   2.216 -      if (compare(mid,last)>0) {		\
   2.217 -        swapper(mid,last);			\
   2.218 -        if (compare(first,mid)>0) swapper(first,mid);\
   2.219 -      }						\
   2.220 -    }						\
   2.221 -    else {					\
   2.222 -      if (compare(mid,last)>0) swapper(first,last)\
   2.223 -      else {					\
   2.224 -        swapper(first,mid);			\
   2.225 -        if (compare(mid,last)>0) swapper(mid,last);\
   2.226 -      }						\
   2.227 -    }						\
   2.228 -    first+=sz; last-=sz;			\
   2.229 -  }
   2.230 -
   2.231 -#ifdef DEBUG_QSORT
   2.232 -#include <stdio.h>
   2.233 +#ifdef REGTEST
   2.234 +#undef REGTEST
   2.235  #endif
   2.236  
   2.237 -/* and so is the partitioning logic: */
   2.238 -#define Partition(swapper,sz) {			\
   2.239 -  int swapped=0;				\
   2.240 -  do {						\
   2.241 -    while (compare(first,pivot)<0) first+=sz;	\
   2.242 -    while (compare(pivot,last)<0) last-=sz;	\
   2.243 -    if (first<last) {				\
   2.244 -      swapper(first,last); swapped=1;		\
   2.245 -      first+=sz; last-=sz; }			\
   2.246 -    else if (first==last) { first+=sz; last-=sz; break; }\
   2.247 -  } while (first<=last);			\
   2.248 -  if (!swapped) pop				\
   2.249 +#ifdef TEST
   2.250 +#undef TEST
   2.251 +#endif
   2.252 +
   2.253 +#ifndef _PDCLIB_memswp
   2.254 +#define _PDCLIB_memswp( i, j, size ) char tmp; do { tmp = *i; *i++ = *j; *j++ = tmp; } while ( --size );
   2.255 +#endif
   2.256 +
   2.257 +#ifndef _PDCLIB_size_t
   2.258 +#define _PDCLIB_size_t size_t
   2.259 +#endif
   2.260 +
   2.261 +#define qsort SDL_qsort
   2.262 +
   2.263 +#define inline SDL_INLINE
   2.264 +
   2.265 +/*
   2.266 +This code came from PDCLib, under the public domain. Specifically this:
   2.267 +https://bitbucket.org/pdclib/pdclib/raw/a82b02d0c7d4ed633b97f2a7639d9a10b1c92ec8/functions/stdlib/qsort.c
   2.268 +The _PDCLIB_memswp macro was from
   2.269 +https://bitbucket.org/pdclib/pdclib/src/a82b02d0c7d4ed633b97f2a7639d9a10b1c92ec8/platform/posix/internals/_PDCLIB_config.h?at=default&fileviewer=file-view-default#_PDCLIB_config.h-28
   2.270 +
   2.271 +Everything below this comment until the HAVE_QSORT #endif was from PDCLib.
   2.272 +--ryan.
   2.273 +*/
   2.274 +
   2.275 +/* $Id$ */
   2.276 +
   2.277 +/* qsort( void *, size_t, size_t, int(*)( const void *, const void * ) )
   2.278 +
   2.279 +   This file is part of the Public Domain C Library (PDCLib).
   2.280 +   Permission is granted to use, modify, and / or redistribute at will.
   2.281 +*/
   2.282 +
   2.283 +#include <stdlib.h>
   2.284 +
   2.285 +#ifndef REGTEST
   2.286 +
   2.287 +/* This implementation is taken from Paul Edward's PDPCLIB.
   2.288 +
   2.289 +   Original code is credited to Raymond Gardner, Englewood CO.
   2.290 +   Minor mods are credited to Paul Edwards.
   2.291 +   Some reformatting and simplification done by Martin Baute.
   2.292 +   All code is still Public Domain.
   2.293 +*/
   2.294 +
   2.295 +/* Wrapper for _PDCLIB_memswp protects against multiple argument evaluation. */
   2.296 +static inline void memswp( char * i, char * j, size_t size )
   2.297 +{
   2.298 +    _PDCLIB_memswp( i, j, size );
   2.299  }
   2.300  
   2.301 -/* and so is the pre-insertion-sort operation of putting
   2.302 - * the smallest element into place as a sentinel.
   2.303 - * Doing this makes the inner loop nicer. I got this
   2.304 - * idea from the GNU implementation of qsort().
   2.305 - */
   2.306 -#define PreInsertion(swapper,limit,sz)		\
   2.307 -  first=base;					\
   2.308 -  last=first + (nmemb>limit ? limit : nmemb-1)*sz;\
   2.309 -  while (last!=base) {				\
   2.310 -    if (compare(first,last)>0) first=last;	\
   2.311 -    last-=sz; }					\
   2.312 -  if (first!=base) swapper(first,(char*)base);
   2.313 +/* For small sets, insertion sort is faster than quicksort.
   2.314 +   T is the threshold below which insertion sort will be used.
   2.315 +   Must be 3 or larger.
   2.316 +*/
   2.317 +#define T 7
   2.318  
   2.319 -/* and so is the insertion sort, in the first two cases: */
   2.320 -#define Insertion(swapper)			\
   2.321 -  last=((char*)base)+nmemb*size;		\
   2.322 -  for (first=((char*)base)+size;first!=last;first+=size) {	\
   2.323 -    char *test;					\
   2.324 -    /* Find the right place for |first|.	\
   2.325 -     * My apologies for var reuse. */		\
   2.326 -    for (test=first-size;compare(test,first)>0;test-=size) ;	\
   2.327 -    test+=size;					\
   2.328 -    if (test!=first) {				\
   2.329 -      /* Shift everything in [test,first)	\
   2.330 -       * up by one, and place |first|		\
   2.331 -       * where |test| is. */			\
   2.332 -      memcpy(pivot,first,size);			\
   2.333 -      memmove(test+size,test,first-test);	\
   2.334 -      memcpy(test,pivot,size);			\
   2.335 -    }						\
   2.336 -  }
   2.337 +/* Macros for handling the QSort stack */
   2.338 +#define PREPARE_STACK char * stack[STACKSIZE]; char * * stackptr = stack
   2.339 +#define PUSH( base, limit ) stackptr[0] = base; stackptr[1] = limit; stackptr += 2
   2.340 +#define POP( base, limit ) stackptr -= 2; base = stackptr[0]; limit = stackptr[1]
   2.341 +/* TODO: Stack usage is log2( nmemb ) (minus what T shaves off the worst case).
   2.342 +         Worst-case nmemb is platform dependent and should probably be 
   2.343 +         configured through _PDCLIB_config.h.
   2.344 +*/
   2.345 +#define STACKSIZE 64
   2.346  
   2.347 -#define SWAP_nonaligned(a,b) { \
   2.348 -  register char *aa=(a),*bb=(b); \
   2.349 -  register size_t sz=size; \
   2.350 -  do { register char t=*aa; *aa++=*bb; *bb++=t; } while (--sz); }
   2.351 +void qsort( void * base, size_t nmemb, size_t size, int (*compar)( const void *, const void * ) )
   2.352 +{
   2.353 +    char * i;
   2.354 +    char * j;
   2.355 +    _PDCLIB_size_t thresh = T * size;
   2.356 +    char * base_          = (char *)base;
   2.357 +    char * limit          = base_ + nmemb * size;
   2.358 +    PREPARE_STACK;
   2.359  
   2.360 -#define SWAP_aligned(a,b) { \
   2.361 -  register int *aa=(int*)(a),*bb=(int*)(b); \
   2.362 -  register size_t sz=size; \
   2.363 -  do { register int t=*aa;*aa++=*bb; *bb++=t; } while (sz-=WORD_BYTES); }
   2.364 -
   2.365 -#define SWAP_words(a,b) { \
   2.366 -  register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; }
   2.367 -
   2.368 -/* ---------------------------------------------------------------------- */
   2.369 -
   2.370 -static char *
   2.371 -pivot_big(char *first, char *mid, char *last, size_t size,
   2.372 -          int compare(const void *, const void *))
   2.373 -{
   2.374 -    size_t d = (((last - first) / size) >> 3) * size;
   2.375 -    char *m1, *m2, *m3;
   2.376 +    for ( ;; )
   2.377      {
   2.378 -        char *a = first, *b = first + d, *c = first + 2 * d;
   2.379 -#ifdef DEBUG_QSORT
   2.380 -        fprintf(stderr, "< %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
   2.381 -#endif
   2.382 -        m1 = compare(a, b) < 0 ?
   2.383 -            (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
   2.384 -            : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
   2.385 +        if ( (size_t)( limit - base_ ) > thresh ) /* QSort for more than T elements. */
   2.386 +        {
   2.387 +            /* We work from second to last - first will be pivot element. */
   2.388 +            i = base_ + size;
   2.389 +            j = limit - size;
   2.390 +            /* We swap first with middle element, then sort that with second
   2.391 +               and last element so that eventually first element is the median
   2.392 +               of the three - avoiding pathological pivots.
   2.393 +               TODO: Instead of middle element, chose one randomly.
   2.394 +            */
   2.395 +            memswp( ( ( ( (size_t)( limit - base_ ) ) / size ) / 2 ) * size + base_, base_, size );
   2.396 +            if ( compar( i, j ) > 0 ) memswp( i, j, size );
   2.397 +            if ( compar( base_, j ) > 0 ) memswp( base_, j, size );
   2.398 +            if ( compar( i, base_ ) > 0 ) memswp( i, base_, size );
   2.399 +            /* Now we have the median for pivot element, entering main Quicksort. */
   2.400 +            for ( ;; )
   2.401 +            {
   2.402 +                do
   2.403 +                {
   2.404 +                    /* move i right until *i >= pivot */
   2.405 +                    i += size;
   2.406 +                } while ( compar( i, base_ ) < 0 );
   2.407 +                do
   2.408 +                {
   2.409 +                    /* move j left until *j <= pivot */
   2.410 +                    j -= size;
   2.411 +                } while ( compar( j, base_ ) > 0 );
   2.412 +                if ( i > j )
   2.413 +                {
   2.414 +                    /* break loop if pointers crossed */
   2.415 +                    break;
   2.416 +                }
   2.417 +                /* else swap elements, keep scanning */
   2.418 +                memswp( i, j, size );
   2.419 +            }
   2.420 +            /* move pivot into correct place */
   2.421 +            memswp( base_, j, size );
   2.422 +            /* larger subfile base / limit to stack, sort smaller */
   2.423 +            if ( j - base_ > limit - i )
   2.424 +            {
   2.425 +                /* left is larger */
   2.426 +                PUSH( base_, j );
   2.427 +                base_ = i;
   2.428 +            }
   2.429 +            else
   2.430 +            {
   2.431 +                /* right is larger */
   2.432 +                PUSH( i, limit );
   2.433 +                limit = j;
   2.434 +            }
   2.435 +        }
   2.436 +        else /* insertion sort for less than T elements              */
   2.437 +        {
   2.438 +            for ( j = base_, i = j + size; i < limit; j = i, i += size )
   2.439 +            {
   2.440 +                for ( ; compar( j, j + size ) > 0; j -= size )
   2.441 +                {
   2.442 +                    memswp( j, j + size, size );
   2.443 +                    if ( j == base_ )
   2.444 +                    {
   2.445 +                        break;
   2.446 +                    }
   2.447 +                }
   2.448 +            }
   2.449 +            if ( stackptr != stack )           /* if any entries on stack  */
   2.450 +            {
   2.451 +                POP( base_, limit );
   2.452 +            }
   2.453 +            else                       /* else stack empty, done   */
   2.454 +            {
   2.455 +                break;
   2.456 +            }
   2.457 +        }
   2.458      }
   2.459 -    {
   2.460 -        char *a = mid - d, *b = mid, *c = mid + d;
   2.461 -#ifdef DEBUG_QSORT
   2.462 -        fprintf(stderr, ". %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
   2.463 -#endif
   2.464 -        m2 = compare(a, b) < 0 ?
   2.465 -            (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
   2.466 -            : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
   2.467 -    }
   2.468 -    {
   2.469 -        char *a = last - 2 * d, *b = last - d, *c = last;
   2.470 -#ifdef DEBUG_QSORT
   2.471 -        fprintf(stderr, "> %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
   2.472 -#endif
   2.473 -        m3 = compare(a, b) < 0 ?
   2.474 -            (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
   2.475 -            : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
   2.476 -    }
   2.477 -#ifdef DEBUG_QSORT
   2.478 -    fprintf(stderr, "-> %d %d %d\n", *(int *) m1, *(int *) m2, *(int *) m3);
   2.479 -#endif
   2.480 -    return compare(m1, m2) < 0 ?
   2.481 -        (compare(m2, m3) < 0 ? m2 : (compare(m1, m3) < 0 ? m3 : m1))
   2.482 -        : (compare(m1, m3) < 0 ? m1 : (compare(m2, m3) < 0 ? m3 : m2));
   2.483  }
   2.484  
   2.485 -/* ---------------------------------------------------------------------- */
   2.486 +#endif
   2.487  
   2.488 -static void
   2.489 -qsort_nonaligned(void *base, size_t nmemb, size_t size,
   2.490 -                 int (*compare) (const void *, const void *))
   2.491 +#ifdef TEST
   2.492 +#include <_PDCLIB_test.h>
   2.493 +#include <string.h>
   2.494 +#include <limits.h>
   2.495 +
   2.496 +static int compare( const void * left, const void * right )
   2.497  {
   2.498 -
   2.499 -    stack_entry stack[STACK_SIZE];
   2.500 -    int stacktop = 0;
   2.501 -    char *first, *last;
   2.502 -    char *pivot = malloc(size);
   2.503 -    size_t trunc = TRUNC_nonaligned * size;
   2.504 -    assert(pivot != 0);
   2.505 -
   2.506 -    first = (char *) base;
   2.507 -    last = first + (nmemb - 1) * size;
   2.508 -
   2.509 -    if ((size_t) (last - first) > trunc) {
   2.510 -        char *ffirst = first, *llast = last;
   2.511 -        while (1) {
   2.512 -            /* Select pivot */
   2.513 -            {
   2.514 -                char *mid = first + size * ((last - first) / size >> 1);
   2.515 -                Pivot(SWAP_nonaligned, size);
   2.516 -                memcpy(pivot, mid, size);
   2.517 -            }
   2.518 -            /* Partition. */
   2.519 -            Partition(SWAP_nonaligned, size);
   2.520 -            /* Prepare to recurse/iterate. */
   2.521 -        Recurse(trunc)}
   2.522 -    }
   2.523 -    PreInsertion(SWAP_nonaligned, TRUNC_nonaligned, size);
   2.524 -    Insertion(SWAP_nonaligned);
   2.525 -    free(pivot);
   2.526 +    return *( (unsigned char *)left ) - *( (unsigned char *)right );
   2.527  }
   2.528  
   2.529 -static void
   2.530 -qsort_aligned(void *base, size_t nmemb, size_t size,
   2.531 -              int (*compare) (const void *, const void *))
   2.532 +int main( void )
   2.533  {
   2.534 -
   2.535 -    stack_entry stack[STACK_SIZE];
   2.536 -    int stacktop = 0;
   2.537 -    char *first, *last;
   2.538 -    char *pivot = malloc(size);
   2.539 -    size_t trunc = TRUNC_aligned * size;
   2.540 -    assert(pivot != 0);
   2.541 -
   2.542 -    first = (char *) base;
   2.543 -    last = first + (nmemb - 1) * size;
   2.544 -
   2.545 -    if ((size_t) (last - first) > trunc) {
   2.546 -        char *ffirst = first, *llast = last;
   2.547 -        while (1) {
   2.548 -            /* Select pivot */
   2.549 -            {
   2.550 -                char *mid = first + size * ((last - first) / size >> 1);
   2.551 -                Pivot(SWAP_aligned, size);
   2.552 -                memcpy(pivot, mid, size);
   2.553 -            }
   2.554 -            /* Partition. */
   2.555 -            Partition(SWAP_aligned, size);
   2.556 -            /* Prepare to recurse/iterate. */
   2.557 -        Recurse(trunc)}
   2.558 -    }
   2.559 -    PreInsertion(SWAP_aligned, TRUNC_aligned, size);
   2.560 -    Insertion(SWAP_aligned);
   2.561 -    free(pivot);
   2.562 +    char presort[] = { "shreicnyjqpvozxmbt" };
   2.563 +    char sorted1[] = { "bcehijmnopqrstvxyz" };
   2.564 +    char sorted2[] = { "bticjqnyozpvreshxm" };
   2.565 +    char s[19];
   2.566 +    strcpy( s, presort );
   2.567 +    qsort( s, 18, 1, compare );
   2.568 +    TESTCASE( strcmp( s, sorted1 ) == 0 );
   2.569 +    strcpy( s, presort );
   2.570 +    qsort( s, 9, 2, compare );
   2.571 +    TESTCASE( strcmp( s, sorted2 ) == 0 );
   2.572 +    strcpy( s, presort );
   2.573 +    qsort( s, 1, 1, compare );
   2.574 +    TESTCASE( strcmp( s, presort ) == 0 );
   2.575 +#if defined(REGTEST) && (__BSD_VISIBLE || __APPLE__)
   2.576 +    puts( "qsort.c: Skipping test #4 for BSD as it goes into endless loop here." );
   2.577 +#else
   2.578 +    qsort( s, 100, 0, compare );
   2.579 +    TESTCASE( strcmp( s, presort ) == 0 );
   2.580 +#endif
   2.581 +    return TEST_RESULTS;
   2.582  }
   2.583  
   2.584 -static void
   2.585 -qsort_words(void *base, size_t nmemb,
   2.586 -            int (*compare) (const void *, const void *))
   2.587 -{
   2.588 +#endif
   2.589  
   2.590 -    stack_entry stack[STACK_SIZE];
   2.591 -    int stacktop = 0;
   2.592 -    char *first, *last;
   2.593 -    char *pivot = malloc(WORD_BYTES);
   2.594 -    assert(pivot != 0);
   2.595 -
   2.596 -    first = (char *) base;
   2.597 -    last = first + (nmemb - 1) * WORD_BYTES;
   2.598 -
   2.599 -    if (last - first > TRUNC_words) {
   2.600 -        char *ffirst = first, *llast = last;
   2.601 -        while (1) {
   2.602 -#ifdef DEBUG_QSORT
   2.603 -            fprintf(stderr, "Doing %d:%d: ",
   2.604 -                    (first - (char *) base) / WORD_BYTES,
   2.605 -                    (last - (char *) base) / WORD_BYTES);
   2.606 -#endif
   2.607 -            /* Select pivot */
   2.608 -            {
   2.609 -                char *mid =
   2.610 -                    first + WORD_BYTES * ((last - first) / (2 * WORD_BYTES));
   2.611 -                Pivot(SWAP_words, WORD_BYTES);
   2.612 -                *(int *) pivot = *(int *) mid;
   2.613 -            }
   2.614 -#ifdef DEBUG_QSORT
   2.615 -            fprintf(stderr, "pivot=%d\n", *(int *) pivot);
   2.616 -#endif
   2.617 -            /* Partition. */
   2.618 -            Partition(SWAP_words, WORD_BYTES);
   2.619 -            /* Prepare to recurse/iterate. */
   2.620 -        Recurse(TRUNC_words)}
   2.621 -    }
   2.622 -    PreInsertion(SWAP_words, (TRUNC_words / WORD_BYTES), WORD_BYTES);
   2.623 -    /* Now do insertion sort. */
   2.624 -    last = ((char *) base) + nmemb * WORD_BYTES;
   2.625 -    for (first = ((char *) base) + WORD_BYTES; first != last;
   2.626 -         first += WORD_BYTES) {
   2.627 -        /* Find the right place for |first|. My apologies for var reuse */
   2.628 -        int *pl = (int *) (first - WORD_BYTES), *pr = (int *) first;
   2.629 -        *(int *) pivot = *(int *) first;
   2.630 -        for (; compare(pl, pivot) > 0; pr = pl, --pl) {
   2.631 -            *pr = *pl;
   2.632 -        }
   2.633 -        if (pr != (int *) first)
   2.634 -            *pr = *(int *) pivot;
   2.635 -    }
   2.636 -    free(pivot);
   2.637 -}
   2.638 -
   2.639 -/* ---------------------------------------------------------------------- */
   2.640 -
   2.641 -void
   2.642 -qsort(void *base, size_t nmemb, size_t size,
   2.643 -      int (*compare) (const void *, const void *))
   2.644 -{
   2.645 -
   2.646 -    if (nmemb <= 1)
   2.647 -        return;
   2.648 -    if (((uintptr_t) base | size) & (WORD_BYTES - 1))
   2.649 -        qsort_nonaligned(base, nmemb, size, compare);
   2.650 -    else if (size != WORD_BYTES)
   2.651 -        qsort_aligned(base, nmemb, size, compare);
   2.652 -    else
   2.653 -        qsort_words(base, nmemb, compare);
   2.654 -}
   2.655 -
   2.656 -#endif /* !SDL_qsort */
   2.657 +#endif /* HAVE_QSORT */
   2.658  
   2.659  /* vi: set ts=4 sw=4 expandtab: */