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