src/stdlib/SDL_qsort.c
author Ryan C. Gordon <icculus@icculus.org>
Mon, 01 Aug 2016 00:20:47 -0400
changeset 10214 4f29bb9e19c3
parent 10116 418691d83f6a
permissions -rw-r--r--
audio: Implemented capture support for Mac OS X CoreAudio. I don't know what iOS wants yet, so this code might work there, too...?
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
     1
/*
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
     2
  Simple DirectMedia Layer
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
     3
  Copyright (C) 1997-2016 Sam Lantinga <slouken@libsdl.org>
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
     4
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
     5
  This software is provided 'as-is', without any express or implied
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
     6
  warranty.  In no event will the authors be held liable for any damages
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
     7
  arising from the use of this software.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
     8
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
     9
  Permission is granted to anyone to use this software for any purpose,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    10
  including commercial applications, and to alter it and redistribute it
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    11
  freely, subject to the following restrictions:
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    12
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    13
  1. The origin of this software must not be misrepresented; you must not
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    14
     claim that you wrote the original software. If you use this software
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    15
     in a product, an acknowledgment in the product documentation would be
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    16
     appreciated but is not required.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    17
  2. Altered source versions must be plainly marked as such, and must not be
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    18
     misrepresented as being the original software.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    19
  3. This notice may not be removed or altered from any source distribution.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    20
*/
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    21
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    22
#if defined(__clang_analyzer__) && !defined(SDL_DISABLE_ANALYZE_MACROS)
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    23
#define SDL_DISABLE_ANALYZE_MACROS 1
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    24
#endif
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    25
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
    26
#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
    27
1354
22f39393668a Fixed build problem with SDL_string.c
Sam Lantinga <slouken@libsdl.org>
parents: 1337
diff changeset
    28
#include "SDL_stdinc.h"
6281
e46d6f4b469e Replaced some assert macros with SDL_assert.
Ryan C. Gordon <icculus@icculus.org>
parents: 3616
diff changeset
    29
#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
    30
7351
668a3dc28361 Removed the inline functions from SDL_stdinc.h
Sam Lantinga <slouken@libsdl.org>
parents: 7003
diff changeset
    31
#if defined(HAVE_QSORT)
7003
eeaf77005c30 Improvements to stdlib.
Ryan C. Gordon <icculus@icculus.org>
parents: 6281
diff changeset
    32
void
eeaf77005c30 Improvements to stdlib.
Ryan C. Gordon <icculus@icculus.org>
parents: 6281
diff changeset
    33
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
    34
{
7351
668a3dc28361 Removed the inline functions from SDL_stdinc.h
Sam Lantinga <slouken@libsdl.org>
parents: 7003
diff changeset
    35
    qsort(base, nmemb, size, compare);
7003
eeaf77005c30 Improvements to stdlib.
Ryan C. Gordon <icculus@icculus.org>
parents: 6281
diff changeset
    36
}
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    37
7003
eeaf77005c30 Improvements to stdlib.
Ryan C. Gordon <icculus@icculus.org>
parents: 6281
diff changeset
    38
#else
eeaf77005c30 Improvements to stdlib.
Ryan C. Gordon <icculus@icculus.org>
parents: 6281
diff changeset
    39
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    40
#ifdef assert
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    41
#undef assert
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
    42
#endif
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    43
#define assert SDL_assert
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    44
#ifdef malloc
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    45
#undef malloc
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
    46
#endif
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    47
#define malloc SDL_malloc
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    48
#ifdef free
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    49
#undef free
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
    50
#endif
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    51
#define free SDL_free
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    52
#ifdef memcpy
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    53
#undef memcpy
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
    54
#endif
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    55
#define memcpy SDL_memcpy
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    56
#ifdef memmove
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    57
#undef memmove
10069
ba33b870b45c Patched to compile on Visual Studio.
Ryan C. Gordon <icculus@icculus.org>
parents: 10068
diff changeset
    58
#endif
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    59
#define memmove SDL_memmove
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    60
#ifdef qsortG
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    61
#undef qsortG
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    62
#endif
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    63
#define qsortG SDL_qsort
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
    64
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
/*
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    66
This code came from Gareth McCaughan, under the zlib license.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    67
Specifically this: https://www.mccaughan.org.uk/software/qsort.c-1.14
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
    68
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    69
Everything below this comment until the HAVE_QSORT #endif was from Gareth
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    70
(any minor changes will be noted inline).
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    71
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    72
Thank you to Gareth for relicensing this code under the zlib license for our
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    73
benefit!
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    74
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
    75
--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
    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
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    78
/* This is a drop-in replacement for the C library's |qsort()| routine.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    79
 *
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    80
 * It is intended for use where you know or suspect that your
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    81
 * platform's qsort is bad. If that isn't the case, then you
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    82
 * should probably use the qsort your system gives you in preference
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    83
 * to mine -- it will likely have been tested and tuned better.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    84
 *
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    85
 * Features:
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    86
 *   - Median-of-three pivoting (and more)
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    87
 *   - Truncation and final polishing by a single insertion sort
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    88
 *   - Early truncation when no swaps needed in pivoting step
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    89
 *   - Explicit recursion, guaranteed not to overflow
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    90
 *   - A few little wrinkles stolen from the GNU |qsort()|.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    91
 *     (For the avoidance of doubt, no code was stolen, only
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    92
 *     broad ideas.)
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    93
 *   - separate code for non-aligned / aligned / word-size objects
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    94
 *
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    95
 * Earlier releases of this code used an idiosyncratic licence
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    96
 * I wrote myself, because I'm an idiot. The code is now released
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    97
 * under the "zlib/libpng licence"; you will find the actual
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    98
 * terms in the next comment. I request (but do not require)
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
    99
 * that if you make any changes beyond the name of the exported
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   100
 * routine and reasonable tweaks to the TRUNC_* and
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   101
 * PIVOT_THRESHOLD values, you modify the _ID string so as
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   102
 * to make it clear that you have changed the code.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   103
 *
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   104
 * If you find problems with this code, or find ways of
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   105
 * making it significantly faster, please let me know!
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   106
 * My e-mail address, valid as of early 2016 and for the
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   107
 * foreseeable future, is
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   108
 *    gareth.mccaughan@pobox.com
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   109
 * Thanks!
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   110
 *
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   111
 * Gareth McCaughan
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   112
 */
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
   113
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   114
/* Copyright (c) 1998-2016 Gareth McCaughan
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   115
 *
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   116
 * This software is provided 'as-is', without any express or implied
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   117
 * warranty. In no event will the authors be held liable for any
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   118
 * damages arising from the use of this software.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   119
 *
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   120
 * Permission is granted to anyone to use this software for any purpose,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   121
 * including commercial applications, and to alter it and redistribute it
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   122
 * freely, subject to the following restrictions:
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   123
 *
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   124
 * 1. The origin of this software must not be misrepresented;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   125
 *    you must not claim that you wrote the original software.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   126
 *    If you use this software in a product, an acknowledgment
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   127
 *    in the product documentation would be appreciated but
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   128
 *    is not required.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   129
 *
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   130
 * 2. Altered source versions must be plainly marked as such,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   131
 *    and must not be misrepresented as being the original software.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   132
 *
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   133
 * 3. This notice may not be removed or altered from any source
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   134
 *    distribution.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   135
 */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   136
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   137
/* Revision history since release:
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   138
 *   1998-03-19 v1.12 First release I have any records of.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   139
 *   2007-09-02 v1.13 Fix bug kindly reported by Dan Bodoh
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   140
 *                    (premature termination of recursion).
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   141
 *                    Add a few clarifying comments.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   142
 *                    Minor improvements to debug output.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   143
 *   2016-02-21 v1.14 Replace licence with 2-clause BSD,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   144
 *                    and clarify a couple of things in
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   145
 *                    comments. No code changes.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   146
 */
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
   147
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   148
/* BEGIN SDL CHANGE ... commented this out with an #if 0 block. --ryan. */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   149
#if 0
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   150
#include <assert.h>
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   151
#include <stdlib.h>
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   152
#include <string.h>
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   153
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   154
#define DEBUG_QSORT
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   155
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   156
static char _ID[]="<qsort.c gjm 1.14 2016-02-21>";
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   157
#endif
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   158
/* END SDL CHANGE ... commented this out with an #if 0 block. --ryan. */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   159
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   160
/* How many bytes are there per word? (Must be a power of 2,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   161
 * and must in fact equal sizeof(int).)
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   162
 */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   163
#define WORD_BYTES sizeof(int)
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
   164
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   165
/* How big does our stack need to be? Answer: one entry per
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   166
 * bit in a |size_t|.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   167
 */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   168
#define STACK_SIZE (8*sizeof(size_t))
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   169
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   170
/* Different situations have slightly different requirements,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   171
 * and we make life epsilon easier by using different truncation
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   172
 * points for the three different cases.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   173
 * So far, I have tuned TRUNC_words and guessed that the same
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   174
 * value might work well for the other two cases. Of course
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   175
 * what works well on my machine might work badly on yours.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   176
 */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   177
#define TRUNC_nonaligned	12
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   178
#define TRUNC_aligned		12
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   179
#define TRUNC_words		12*WORD_BYTES	/* nb different meaning */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   180
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   181
/* We use a simple pivoting algorithm for shortish sub-arrays
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   182
 * and a more complicated one for larger ones. The threshold
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   183
 * is PIVOT_THRESHOLD.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   184
 */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   185
#define PIVOT_THRESHOLD 40
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
   186
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   187
typedef struct { char * first; char * last; } stack_entry;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   188
#define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;}
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   189
#define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;}
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   190
#define doLeft {first=ffirst;llast=last;continue;}
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   191
#define doRight {ffirst=first;last=llast;continue;}
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   192
#define pop {if (--stacktop<0) break;\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   193
  first=ffirst=stack[stacktop].first;\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   194
  last=llast=stack[stacktop].last;\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   195
  continue;}
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
   196
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   197
/* Some comments on the implementation.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   198
 * 1. When we finish partitioning the array into "low"
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   199
 *    and "high", we forget entirely about short subarrays,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   200
 *    because they'll be done later by insertion sort.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   201
 *    Doing lots of little insertion sorts might be a win
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   202
 *    on large datasets for locality-of-reference reasons,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   203
 *    but it makes the code much nastier and increases
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   204
 *    bookkeeping overhead.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   205
 * 2. We always save the shorter and get to work on the
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   206
 *    longer. This guarantees that every time we push
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   207
 *    an item onto the stack its size is <= 1/2 of that
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   208
 *    of its parent; so the stack can't need more than
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   209
 *    log_2(max-array-size) entries.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   210
 * 3. We choose a pivot by looking at the first, last
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   211
 *    and middle elements. We arrange them into order
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   212
 *    because it's easy to do that in conjunction with
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   213
 *    choosing the pivot, and it makes things a little
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   214
 *    easier in the partitioning step. Anyway, the pivot
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   215
 *    is the middle of these three. It's still possible
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   216
 *    to construct datasets where the algorithm takes
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   217
 *    time of order n^2, but it simply never happens in
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   218
 *    practice.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   219
 * 3' Newsflash: On further investigation I find that
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   220
 *    it's easy to construct datasets where median-of-3
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   221
 *    simply isn't good enough. So on large-ish subarrays
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   222
 *    we do a more sophisticated pivoting: we take three
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   223
 *    sets of 3 elements, find their medians, and then
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   224
 *    take the median of those.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   225
 * 4. We copy the pivot element to a separate place
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   226
 *    because that way we can always do our comparisons
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   227
 *    directly against a pointer to that separate place,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   228
 *    and don't have to wonder "did we move the pivot
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   229
 *    element?". This makes the inner loop better.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   230
 * 5. It's possible to make the pivoting even more
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   231
 *    reliable by looking at more candidates when n
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   232
 *    is larger. (Taking this to its logical conclusion
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   233
 *    results in a variant of quicksort that doesn't
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   234
 *    have that n^2 worst case.) However, the overhead
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   235
 *    from the extra bookkeeping means that it's just
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   236
 *    not worth while.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   237
 * 6. This is pretty clean and portable code. Here are
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   238
 *    all the potential portability pitfalls and problems
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   239
 *    I know of:
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   240
 *      - In one place (the insertion sort) I construct
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   241
 *        a pointer that points just past the end of the
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   242
 *        supplied array, and assume that (a) it won't
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   243
 *        compare equal to any pointer within the array,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   244
 *        and (b) it will compare equal to a pointer
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   245
 *        obtained by stepping off the end of the array.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   246
 *        These might fail on some segmented architectures.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   247
 *      - I assume that there are 8 bits in a |char| when
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   248
 *        computing the size of stack needed. This would
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   249
 *        fail on machines with 9-bit or 16-bit bytes.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   250
 *      - I assume that if |((int)base&(sizeof(int)-1))==0|
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   251
 *        and |(size&(sizeof(int)-1))==0| then it's safe to
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   252
 *        get at array elements via |int*|s, and that if
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   253
 *        actually |size==sizeof(int)| as well then it's
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   254
 *        safe to treat the elements as |int|s. This might
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   255
 *        fail on systems that convert pointers to integers
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   256
 *        in non-standard ways.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   257
 *      - I assume that |8*sizeof(size_t)<=INT_MAX|. This
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   258
 *        would be false on a machine with 8-bit |char|s,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   259
 *        16-bit |int|s and 4096-bit |size_t|s. :-)
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   260
 */
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
   261
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   262
/* The recursion logic is the same in each case.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   263
 * We keep chopping up until we reach subarrays of size
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   264
 * strictly less than Trunc; we leave these unsorted. */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   265
#define Recurse(Trunc)				\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   266
      { size_t l=last-ffirst,r=llast-first;	\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   267
        if (l<Trunc) {				\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   268
          if (r>=Trunc) doRight			\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   269
          else pop				\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   270
        }					\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   271
        else if (l<=r) { pushLeft; doRight }	\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   272
        else if (r>=Trunc) { pushRight; doLeft }\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   273
        else doLeft				\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   274
      }
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   275
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   276
/* and so is the pivoting logic (note: last is inclusive): */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   277
#define Pivot(swapper,sz)			\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   278
  if (last-first>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   279
  else {	\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   280
    if (compare(first,mid)<0) {			\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   281
      if (compare(mid,last)>0) {		\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   282
        swapper(mid,last);			\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   283
        if (compare(first,mid)>0) swapper(first,mid);\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   284
      }						\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   285
    }						\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   286
    else {					\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   287
      if (compare(mid,last)>0) swapper(first,last)\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   288
      else {					\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   289
        swapper(first,mid);			\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   290
        if (compare(mid,last)>0) swapper(mid,last);\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   291
      }						\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   292
    }						\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   293
    first+=sz; last-=sz;			\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   294
  }
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   295
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   296
#ifdef DEBUG_QSORT
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   297
#include <stdio.h>
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   298
#endif
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   299
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   300
/* and so is the partitioning logic: */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   301
#define Partition(swapper,sz) {			\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   302
  do {						\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   303
    while (compare(first,pivot)<0) first+=sz;	\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   304
    while (compare(pivot,last)<0) last-=sz;	\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   305
    if (first<last) {				\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   306
      swapper(first,last);			\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   307
      first+=sz; last-=sz; }			\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   308
    else if (first==last) { first+=sz; last-=sz; break; }\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   309
  } while (first<=last);			\
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
   310
}
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
   311
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   312
/* and so is the pre-insertion-sort operation of putting
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   313
 * the smallest element into place as a sentinel.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   314
 * Doing this makes the inner loop nicer. I got this
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   315
 * idea from the GNU implementation of qsort().
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   316
 * We find the smallest element from the first |nmemb|,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   317
 * or the first |limit|, whichever is smaller;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   318
 * therefore we must have ensured that the globally smallest
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   319
 * element is in the first |limit|.
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   320
 */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   321
#define PreInsertion(swapper,limit,sz)		\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   322
  first=base;					\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   323
  last=first + ((nmemb>limit ? limit : nmemb)-1)*sz;\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   324
  while (last!=base) {				\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   325
    if (compare(first,last)>0) first=last;	\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   326
    last-=sz; }					\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   327
  if (first!=base) swapper(first,(char*)base);
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
   328
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   329
/* and so is the insertion sort, in the first two cases: */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   330
#define Insertion(swapper)			\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   331
  last=((char*)base)+nmemb*size;		\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   332
  for (first=((char*)base)+size;first!=last;first+=size) {	\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   333
    char *test;					\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   334
    /* Find the right place for |first|.	\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   335
     * My apologies for var reuse. */		\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   336
    for (test=first-size;compare(test,first)>0;test-=size) ;	\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   337
    test+=size;					\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   338
    if (test!=first) {				\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   339
      /* Shift everything in [test,first)	\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   340
       * up by one, and place |first|		\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   341
       * where |test| is. */			\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   342
      memcpy(pivot,first,size);			\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   343
      memmove(test+size,test,first-test);	\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   344
      memcpy(test,pivot,size);			\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   345
    }						\
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   346
  }
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
   347
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   348
#define SWAP_nonaligned(a,b) { \
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   349
  register char *aa=(a),*bb=(b); \
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   350
  register size_t sz=size; \
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   351
  do { register char t=*aa; *aa++=*bb; *bb++=t; } while (--sz); }
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
   352
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   353
#define SWAP_aligned(a,b) { \
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   354
  register int *aa=(int*)(a),*bb=(int*)(b); \
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   355
  register size_t sz=size; \
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   356
  do { register int t=*aa;*aa++=*bb; *bb++=t; } while (sz-=WORD_BYTES); }
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   357
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   358
#define SWAP_words(a,b) { \
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   359
  register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; }
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   360
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   361
/* ---------------------------------------------------------------------- */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   362
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   363
static char * pivot_big(char *first, char *mid, char *last, size_t size,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   364
                        int compare(const void *, const void *)) {
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   365
  int d=(((last-first)/size)>>3)*size;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   366
#ifdef DEBUG_QSORT
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   367
fprintf(stderr, "pivot_big: first=%p last=%p size=%lu n=%lu\n", first, (unsigned long)last, size, (unsigned long)((last-first+1)/size));
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   368
#endif
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   369
  char *m1,*m2,*m3;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   370
  { char *a=first, *b=first+d, *c=first+2*d;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   371
#ifdef DEBUG_QSORT
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   372
fprintf(stderr,"< %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   373
#endif
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   374
    m1 = compare(a,b)<0 ?
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   375
           (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   376
         : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   377
  }
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   378
  { char *a=mid-d, *b=mid, *c=mid+d;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   379
#ifdef DEBUG_QSORT
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   380
fprintf(stderr,". %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   381
#endif
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   382
    m2 = compare(a,b)<0 ?
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   383
           (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   384
         : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   385
  }
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   386
  { char *a=last-2*d, *b=last-d, *c=last;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   387
#ifdef DEBUG_QSORT
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   388
fprintf(stderr,"> %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   389
#endif
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   390
    m3 = compare(a,b)<0 ?
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   391
           (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   392
         : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   393
  }
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   394
#ifdef DEBUG_QSORT
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   395
fprintf(stderr,"-> %d %d %d @ %p %p %p\n",*(int*)m1,*(int*)m2,*(int*)m3, m1,m2,m3);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   396
#endif
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   397
  return compare(m1,m2)<0 ?
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   398
           (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1))
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   399
         : (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2));
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
   400
}
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
   401
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   402
/* ---------------------------------------------------------------------- */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   403
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   404
static void qsort_nonaligned(void *base, size_t nmemb, size_t size,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   405
           int (*compare)(const void *, const void *)) {
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   406
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   407
  stack_entry stack[STACK_SIZE];
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   408
  int stacktop=0;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   409
  char *first,*last;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   410
  char *pivot=malloc(size);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   411
  size_t trunc=TRUNC_nonaligned*size;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   412
  assert(pivot!=0);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   413
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   414
  first=(char*)base; last=first+(nmemb-1)*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
   415
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   416
  if (last-first>=trunc) {
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   417
    char *ffirst=first, *llast=last;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   418
    while (1) {
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   419
      /* Select pivot */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   420
      { char * mid=first+size*((last-first)/size >> 1);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   421
        Pivot(SWAP_nonaligned,size);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   422
        memcpy(pivot,mid,size);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   423
      }
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   424
      /* Partition. */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   425
      Partition(SWAP_nonaligned,size);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   426
      /* Prepare to recurse/iterate. */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   427
      Recurse(trunc)
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   428
    }
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   429
  }
10116
418691d83f6a Quick fix for qsort off-by-one error.
Sam Lantinga <slouken@libsdl.org>
parents: 10085
diff changeset
   430
  PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size);
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   431
  Insertion(SWAP_nonaligned);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   432
  free(pivot);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   433
}
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   434
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   435
static void qsort_aligned(void *base, size_t nmemb, size_t size,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   436
           int (*compare)(const void *, const void *)) {
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
   437
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   438
  stack_entry stack[STACK_SIZE];
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   439
  int stacktop=0;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   440
  char *first,*last;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   441
  char *pivot=malloc(size);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   442
  size_t trunc=TRUNC_aligned*size;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   443
  assert(pivot!=0);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   444
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   445
  first=(char*)base; last=first+(nmemb-1)*size;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   446
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   447
  if (last-first>=trunc) {
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   448
    char *ffirst=first,*llast=last;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   449
    while (1) {
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   450
      /* Select pivot */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   451
      { char * mid=first+size*((last-first)/size >> 1);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   452
        Pivot(SWAP_aligned,size);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   453
        memcpy(pivot,mid,size);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   454
      }
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   455
      /* Partition. */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   456
      Partition(SWAP_aligned,size);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   457
      /* Prepare to recurse/iterate. */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   458
      Recurse(trunc)
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   459
    }
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   460
  }
10116
418691d83f6a Quick fix for qsort off-by-one error.
Sam Lantinga <slouken@libsdl.org>
parents: 10085
diff changeset
   461
  PreInsertion(SWAP_aligned,TRUNC_aligned,size);
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   462
  Insertion(SWAP_aligned);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   463
  free(pivot);
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
   464
}
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
   465
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   466
static void qsort_words(void *base, size_t nmemb,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   467
           int (*compare)(const void *, const void *)) {
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   468
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   469
  stack_entry stack[STACK_SIZE];
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   470
  int stacktop=0;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   471
  char *first,*last;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   472
  char *pivot=malloc(WORD_BYTES);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   473
  assert(pivot!=0);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   474
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   475
  first=(char*)base; last=first+(nmemb-1)*WORD_BYTES;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   476
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   477
  if (last-first>=TRUNC_words) {
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   478
    char *ffirst=first, *llast=last;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   479
    while (1) {
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   480
#ifdef DEBUG_QSORT
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   481
fprintf(stderr,"Doing %d:%d: ",
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   482
        (first-(char*)base)/WORD_BYTES,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   483
        (last-(char*)base)/WORD_BYTES);
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
   484
#endif
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   485
      /* Select pivot */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   486
      { char * mid=first+WORD_BYTES*((last-first) / (2*WORD_BYTES));
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   487
        Pivot(SWAP_words,WORD_BYTES);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   488
        *(int*)pivot=*(int*)mid;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   489
#ifdef DEBUG_QSORT
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   490
fprintf(stderr,"pivot = %p = #%lu = %d\n", mid, (unsigned long)(((int*)mid)-((int*)base)), *(int*)mid);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   491
#endif
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   492
      }
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   493
      /* Partition. */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   494
      Partition(SWAP_words,WORD_BYTES);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   495
#ifdef DEBUG_QSORT
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   496
fprintf(stderr, "after partitioning first=#%lu last=#%lu\n", (first-(char*)base)/4lu, (last-(char*)base)/4lu);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   497
#endif
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   498
      /* Prepare to recurse/iterate. */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   499
      Recurse(TRUNC_words)
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   500
    }
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   501
  }
10116
418691d83f6a Quick fix for qsort off-by-one error.
Sam Lantinga <slouken@libsdl.org>
parents: 10085
diff changeset
   502
  PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES);
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   503
  /* Now do insertion sort. */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   504
  last=((char*)base)+nmemb*WORD_BYTES;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   505
  for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) {
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   506
    /* Find the right place for |first|. My apologies for var reuse */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   507
    int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   508
    *(int*)pivot=*(int*)first;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   509
    for (;compare(pl,pivot)>0;pr=pl,--pl) {
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   510
      *pr=*pl; }
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   511
    if (pr!=(int*)first) *pr=*(int*)pivot;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   512
  }
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   513
  free(pivot);
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
   514
}
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
   515
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   516
/* ---------------------------------------------------------------------- */
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   517
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   518
extern void qsortG(void *base, size_t nmemb, size_t size,
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   519
           int (*compare)(const void *, const void *)) {
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   520
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   521
  if (nmemb<=1) return;
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   522
  if (((int)base|size)&(WORD_BYTES-1))
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   523
    qsort_nonaligned(base,nmemb,size,compare);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   524
  else if (size!=WORD_BYTES)
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   525
    qsort_aligned(base,nmemb,size,compare);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   526
  else
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   527
    qsort_words(base,nmemb,compare);
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   528
}
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   529
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
   530
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
   531
#endif /* HAVE_QSORT */
7003
eeaf77005c30 Improvements to stdlib.
Ryan C. Gordon <icculus@icculus.org>
parents: 6281
diff changeset
   532
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
   533
/* vi: set ts=4 sw=4 expandtab: */
10085
a8e53dc3c5a1 stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents: 10070
diff changeset
   534