src/stdlib/SDL_qsort.c
author Ryan C. Gordon <icculus@icculus.org>
Mon, 15 Feb 2016 03:37:01 -0500
changeset 10070 734b680cba95
parent 10069 ba33b870b45c
child 10085 a8e53dc3c5a1
permissions -rw-r--r--
Another attempt to fix Windows build.
     1 #include "../SDL_internal.h"
     2 
     3 #include "SDL_stdinc.h"
     4 #include "SDL_assert.h"
     5 
     6 #if defined(HAVE_QSORT)
     7 void
     8 SDL_qsort(void *base, size_t nmemb, size_t size, int (*compare) (const void *, const void *))
     9 {
    10     qsort(base, nmemb, size, compare);
    11 }
    12 #else
    13 
    14 #ifdef REGTEST
    15 #undef REGTEST
    16 #endif
    17 
    18 #ifdef TEST
    19 #undef TEST
    20 #endif
    21 
    22 #ifndef _PDCLIB_memswp
    23 #define _PDCLIB_memswp( i, j, size ) char tmp; do { tmp = *i; *i++ = *j; *j++ = tmp; } while ( --size );
    24 #endif
    25 
    26 #ifndef _PDCLIB_size_t
    27 #define _PDCLIB_size_t size_t
    28 #endif
    29 
    30 #ifdef qsort
    31 #undef qsort
    32 #endif
    33 #define qsort SDL_qsort
    34 
    35 #define inline SDL_INLINE
    36 
    37 /*
    38 This code came from PDCLib, under the public domain. Specifically this:
    39 https://bitbucket.org/pdclib/pdclib/raw/a82b02d0c7d4ed633b97f2a7639d9a10b1c92ec8/functions/stdlib/qsort.c
    40 The _PDCLIB_memswp macro was from
    41 https://bitbucket.org/pdclib/pdclib/src/a82b02d0c7d4ed633b97f2a7639d9a10b1c92ec8/platform/posix/internals/_PDCLIB_config.h?at=default&fileviewer=file-view-default#_PDCLIB_config.h-28
    42 
    43 Everything below this comment until the HAVE_QSORT #endif was from PDCLib (minor changes noted inline).
    44 --ryan.
    45 */
    46 
    47 /* $Id$ */
    48 
    49 /* qsort( void *, size_t, size_t, int(*)( const void *, const void * ) )
    50 
    51    This file is part of the Public Domain C Library (PDCLib).
    52    Permission is granted to use, modify, and / or redistribute at will.
    53 */
    54 
    55 /* I commented this out. --ryan. #include <stdlib.h> */
    56 
    57 #ifndef REGTEST
    58 
    59 /* This implementation is taken from Paul Edward's PDPCLIB.
    60 
    61    Original code is credited to Raymond Gardner, Englewood CO.
    62    Minor mods are credited to Paul Edwards.
    63    Some reformatting and simplification done by Martin Baute.
    64    All code is still Public Domain.
    65 */
    66 
    67 /* Wrapper for _PDCLIB_memswp protects against multiple argument evaluation. */
    68 static inline void memswp( char * i, char * j, size_t size )
    69 {
    70     _PDCLIB_memswp( i, j, size );
    71 }
    72 
    73 /* For small sets, insertion sort is faster than quicksort.
    74    T is the threshold below which insertion sort will be used.
    75    Must be 3 or larger.
    76 */
    77 #define T 7
    78 
    79 /* Macros for handling the QSort stack */
    80 #define PREPARE_STACK char * stack[STACKSIZE]; char * * stackptr = stack
    81 #define PUSH( base, limit ) stackptr[0] = base; stackptr[1] = limit; stackptr += 2
    82 #define POP( base, limit ) stackptr -= 2; base = stackptr[0]; limit = stackptr[1]
    83 /* TODO: Stack usage is log2( nmemb ) (minus what T shaves off the worst case).
    84          Worst-case nmemb is platform dependent and should probably be 
    85          configured through _PDCLIB_config.h.
    86 */
    87 #define STACKSIZE 64
    88 
    89 void qsort( void * base, size_t nmemb, size_t size, int (*compar)( const void *, const void * ) )
    90 {
    91     char * i;
    92     char * j;
    93     _PDCLIB_size_t thresh = T * size;
    94     char * base_          = (char *)base;
    95     char * limit          = base_ + nmemb * size;
    96     PREPARE_STACK;
    97 
    98     for ( ;; )
    99     {
   100         if ( (size_t)( limit - base_ ) > thresh ) /* QSort for more than T elements. */
   101         {
   102             /* We work from second to last - first will be pivot element. */
   103             i = base_ + size;
   104             j = limit - size;
   105             /* We swap first with middle element, then sort that with second
   106                and last element so that eventually first element is the median
   107                of the three - avoiding pathological pivots.
   108                TODO: Instead of middle element, chose one randomly.
   109             */
   110             memswp( ( ( ( (size_t)( limit - base_ ) ) / size ) / 2 ) * size + base_, base_, size );
   111             if ( compar( i, j ) > 0 ) memswp( i, j, size );
   112             if ( compar( base_, j ) > 0 ) memswp( base_, j, size );
   113             if ( compar( i, base_ ) > 0 ) memswp( i, base_, size );
   114             /* Now we have the median for pivot element, entering main Quicksort. */
   115             for ( ;; )
   116             {
   117                 do
   118                 {
   119                     /* move i right until *i >= pivot */
   120                     i += size;
   121                 } while ( compar( i, base_ ) < 0 );
   122                 do
   123                 {
   124                     /* move j left until *j <= pivot */
   125                     j -= size;
   126                 } while ( compar( j, base_ ) > 0 );
   127                 if ( i > j )
   128                 {
   129                     /* break loop if pointers crossed */
   130                     break;
   131                 }
   132                 /* else swap elements, keep scanning */
   133                 memswp( i, j, size );
   134             }
   135             /* move pivot into correct place */
   136             memswp( base_, j, size );
   137             /* larger subfile base / limit to stack, sort smaller */
   138             if ( j - base_ > limit - i )
   139             {
   140                 /* left is larger */
   141                 PUSH( base_, j );
   142                 base_ = i;
   143             }
   144             else
   145             {
   146                 /* right is larger */
   147                 PUSH( i, limit );
   148                 limit = j;
   149             }
   150         }
   151         else /* insertion sort for less than T elements              */
   152         {
   153             for ( j = base_, i = j + size; i < limit; j = i, i += size )
   154             {
   155                 for ( ; compar( j, j + size ) > 0; j -= size )
   156                 {
   157                     memswp( j, j + size, size );
   158                     if ( j == base_ )
   159                     {
   160                         break;
   161                     }
   162                 }
   163             }
   164             if ( stackptr != stack )           /* if any entries on stack  */
   165             {
   166                 POP( base_, limit );
   167             }
   168             else                       /* else stack empty, done   */
   169             {
   170                 break;
   171             }
   172         }
   173     }
   174 }
   175 
   176 #endif
   177 
   178 #ifdef TEST
   179 #include <_PDCLIB_test.h>
   180 #include <string.h>
   181 #include <limits.h>
   182 
   183 static int compare( const void * left, const void * right )
   184 {
   185     return *( (unsigned char *)left ) - *( (unsigned char *)right );
   186 }
   187 
   188 int main( void )
   189 {
   190     char presort[] = { "shreicnyjqpvozxmbt" };
   191     char sorted1[] = { "bcehijmnopqrstvxyz" };
   192     char sorted2[] = { "bticjqnyozpvreshxm" };
   193     char s[19];
   194     strcpy( s, presort );
   195     qsort( s, 18, 1, compare );
   196     TESTCASE( strcmp( s, sorted1 ) == 0 );
   197     strcpy( s, presort );
   198     qsort( s, 9, 2, compare );
   199     TESTCASE( strcmp( s, sorted2 ) == 0 );
   200     strcpy( s, presort );
   201     qsort( s, 1, 1, compare );
   202     TESTCASE( strcmp( s, presort ) == 0 );
   203 #if defined(REGTEST) && (__BSD_VISIBLE || __APPLE__)
   204     puts( "qsort.c: Skipping test #4 for BSD as it goes into endless loop here." );
   205 #else
   206     qsort( s, 100, 0, compare );
   207     TESTCASE( strcmp( s, presort ) == 0 );
   208 #endif
   209     return TEST_RESULTS;
   210 }
   211 
   212 #endif
   213 
   214 #endif /* HAVE_QSORT */
   215 
   216 /* vi: set ts=4 sw=4 expandtab: */