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