src/stdlib/SDL_qsort.c
author Ryan C. Gordon <icculus@icculus.org>
Mon, 15 Feb 2016 03:21:26 -0500
changeset 10069 ba33b870b45c
parent 10068 19998f9082dc
child 10070 734b680cba95
permissions -rw-r--r--
Patched to compile on Visual Studio.
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
10069
ba33b870b45c Patched to compile on Visual Studio.
Ryan C. Gordon <icculus@icculus.org>
parents: 10068
diff changeset
    30
#ifdef qsort
ba33b870b45c Patched to compile on Visual Studio.
Ryan C. Gordon <icculus@icculus.org>
parents: 10068
diff changeset
    31
#undef qsort
ba33b870b45c Patched to compile on Visual Studio.
Ryan C. Gordon <icculus@icculus.org>
parents: 10068
diff changeset
    32
#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
    33
#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
    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
#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
    36
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
/*
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
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
    39
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
    40
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
    41
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
    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
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
    44
--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
    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
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
/* $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
    48
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
/* 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
    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
   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
    52
   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
    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
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
#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
    56
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
#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
    58
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
/* 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
    60
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
   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
    62
   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
    63
   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
    64
   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
    65
*/
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
/* 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
    68
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
    69
{
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
    _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
    71
}
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
    72
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
    73
/* 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
    74
   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
    75
   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
    76
*/
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 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
    78
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
    79
/* 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
    80
#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
    81
#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
    82
#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
    83
/* 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
    84
         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
    85
         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
    86
*/
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
#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
    88
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
    89
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
    90
{
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 * 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
    92
    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
    93
    _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
    94
    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
    95
    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
    96
    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
    97
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
    98
    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
    99
    {
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
   100
        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
   101
        {
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 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
   103
            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
   104
            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
   105
            /* 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
   106
               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
   107
               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
   108
               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
   109
            */
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
            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
   111
            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
   112
            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
   113
            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
   114
            /* 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
   115
            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
   116
            {
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
                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
   118
                {
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
                    /* 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
   120
                    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
   121
                } 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
   122
                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
   123
                {
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
                    /* 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
   125
                    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
   126
                } 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
   127
                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
   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
                    /* 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
   130
                    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
   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
                /* 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
   133
                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
   134
            }
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
            /* 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
   136
            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
   137
            /* 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
   138
            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
   139
            {
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
                /* 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
   141
                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
   142
                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
   143
            }
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
            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
   145
            {
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
                /* 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
   147
                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
   148
                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
   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
        }
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
        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
   152
        {
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
            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
   154
            {
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
                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
   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
                    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
   158
                    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
   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
                        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
   161
                    }
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
            }
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
            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
   165
            {
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
                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
   167
            }
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
            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
   169
            {
19998f9082dc Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents: 9306
diff changeset
   170
                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
   171
            }
19998f9082dc Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents: 9306
diff changeset
   172
        }
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
   173
    }
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
}
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
   175
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
   176
#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
   177
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
   178
#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
   179
#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
   180
#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
   181
#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
   182
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
   183
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
   184
{
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
    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
   186
}
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
   187
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
   188
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
   189
{
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
   190
    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
   191
    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
   192
    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
   193
    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
   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, 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
   196
    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
   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, 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
   199
    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
   200
    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
   201
    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
   202
    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
   203
#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
   204
    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
   205
#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
   206
    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
   207
    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
   208
#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
   209
    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
   210
}
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
   211
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
   212
#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
   213
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
   214
#endif /* HAVE_QSORT */
7003
eeaf77005c30 Improvements to stdlib.
Ryan C. Gordon <icculus@icculus.org>
parents: 6281
diff changeset
   215
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
   216
/* vi: set ts=4 sw=4 expandtab: */