sdl-ios-xcode: src/stdlib/SDL

annotate src/stdlib/SDL_qsort.c @ 4347:38f22ed3a433 SDL-1.2

Option to fix bug #851 For some people setting the period size works better (and is what SDL 1.2.13 did), but for most people it's the same or worse. You can use an environment variable to pick which one you want.

author	Sam Lantinga <slouken@libsdl.org>
date	Sat, 17 Oct 2009 06:55:17 +0000
parents	5bacec0933f5
children

rev	line source
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	1 /* qsort.c
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	2 * (c) 1998 Gareth McCaughan
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	3 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	4 * This is a drop-in replacement for the C library's \|qsort()\| routine.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	5 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	6 * Features:
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	7 * - Median-of-three pivoting (and more)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	8 * - Truncation and final polishing by a single insertion sort
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	9 * - Early truncation when no swaps needed in pivoting step
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	10 * - Explicit recursion, guaranteed not to overflow
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	11 * - A few little wrinkles stolen from the GNU \|qsort()\|.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	12 * - separate code for non-aligned / aligned / word-size objects
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	13 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	14 * This code may be reproduced freely provided
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	15 * - this file is retained unaltered apart from minor
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	16 * changes for portability and efficiency
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	17 * - no changes are made to this comment
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	18 * - any changes that are made are clearly flagged
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	19 * - the _ID string below is altered by inserting, after
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	20 * the date, the string " altered" followed at your option
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	21 * by other material. (Exceptions: you may change the name
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	22 * of the exported routine without changing the ID string.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	23 * You may change the values of the macros TRUNC_* and
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	24 * PIVOT_THRESHOLD without changing the ID string, provided
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	25 * they remain constants with TRUNC_nonaligned, TRUNC_aligned
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	26 * and TRUNC_words/WORD_BYTES between 8 and 24, and
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 * PIVOT_THRESHOLD between 32 and 200.)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	28 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	29 * You may use it in anything you like; you may make money
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 * out of it; you may distribute it in object form or as
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	31 * part of an executable without including source code;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	32 * you don't have to credit me. (But it would be nice if
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	33 * you did.)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	34 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	35 * If you find problems with this code, or find ways of
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	36 * making it significantly faster, please let me know!
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	37 * My e-mail address, valid as of early 1998 and certainly
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	38 * OK for at least the next 18 months, is
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	39 * gjm11@dpmms.cam.ac.uk
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	40 * Thanks!
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	41 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	42 * Gareth McCaughan Peterhouse Cambridge 1998
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	43 */
1402 d910939febfa Use consistent identifiers for the various platforms we support. Sam Lantinga <slouken@libsdl.org> parents: 1354 diff changeset	44 #include "SDL_config.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	45
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	46 /*
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	47 #include <assert.h>
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	48 #include <stdlib.h>
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	49 #include <string.h>
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	50 */
1354 22f39393668a Fixed build problem with SDL_string.c Sam Lantinga <slouken@libsdl.org> parents: 1337 diff changeset	51 #include "SDL_stdinc.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	52
4186 5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	53 #ifdef assert
5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	54 #undef assert
5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	55 #endif
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	56 #define assert(X)
4186 5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	57 #ifdef malloc
5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	58 #undef malloc
5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	59 #endif
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	60 #define malloc SDL_malloc
4186 5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	61 #ifdef free
5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	62 #undef free
5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	63 #endif
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	64 #define free SDL_free
4186 5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	65 #ifdef memcpy
5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	66 #undef memcpy
5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	67 #endif
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	68 #define memcpy SDL_memcpy
4186 5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	69 #ifdef memmove
5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	70 #undef memmove
5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	71 #endif
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	72 #define memmove SDL_memmove
4186 5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	73 #ifdef qsort
5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	74 #undef qsort
5bacec0933f5 Fixed compiler warnings on Mac OS X 10.6 SDK. Ryan C. Gordon <icculus@icculus.org> parents: 1456 diff changeset	75 #endif
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	76 #define qsort SDL_qsort
c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	77
c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	78
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	79 #ifndef HAVE_QSORT
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	80
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	81 static char _ID[]="<qsort.c gjm 1.12 1998-03-19>";
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	82
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	83 /* How many bytes are there per word? (Must be a power of 2,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	84 * and must in fact equal sizeof(int).)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	85 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	86 #define WORD_BYTES sizeof(int)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	87
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	88 /* How big does our stack need to be? Answer: one entry per
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	89 * bit in a \|size_t\|.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	90 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	91 #define STACK_SIZE (8*sizeof(size_t))
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	92
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	93 /* Different situations have slightly different requirements,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	94 * and we make life epsilon easier by using different truncation
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	95 * points for the three different cases.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	96 * So far, I have tuned TRUNC_words and guessed that the same
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	97 * value might work well for the other two cases. Of course
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	98 * what works well on my machine might work badly on yours.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	99 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	100 #define TRUNC_nonaligned 12
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	101 #define TRUNC_aligned 12
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	102 #define TRUNC_words 12WORD_BYTES / nb different meaning */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	103
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	104 /* We use a simple pivoting algorithm for shortish sub-arrays
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	105 * and a more complicated one for larger ones. The threshold
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	106 * is PIVOT_THRESHOLD.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	107 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	108 #define PIVOT_THRESHOLD 40
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	109
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	110 typedef struct { char * first; char * last; } stack_entry;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	111 #define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;}
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	112 #define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;}
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	113 #define doLeft {first=ffirst;llast=last;continue;}
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	114 #define doRight {ffirst=first;last=llast;continue;}
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	115 #define pop {if (--stacktop<0) break;\
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	116 first=ffirst=stack[stacktop].first;\
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	117 last=llast=stack[stacktop].last;\
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	118 continue;}
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	119
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	120 /* Some comments on the implementation.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	121 * 1. When we finish partitioning the array into "low"
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	122 * and "high", we forget entirely about short subarrays,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	123 * because they'll be done later by insertion sort.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	124 * Doing lots of little insertion sorts might be a win
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	125 * on large datasets for locality-of-reference reasons,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	126 * but it makes the code much nastier and increases
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	127 * bookkeeping overhead.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	128 * 2. We always save the shorter and get to work on the
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	129 * longer. This guarantees that every time we push
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	130 * an item onto the stack its size is <= 1/2 of that
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	131 * of its parent; so the stack can't need more than
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	132 * log_2(max-array-size) entries.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	133 * 3. We choose a pivot by looking at the first, last
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	134 * and middle elements. We arrange them into order
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	135 * because it's easy to do that in conjunction with
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	136 * choosing the pivot, and it makes things a little
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	137 * easier in the partitioning step. Anyway, the pivot
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	138 * is the middle of these three. It's still possible
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	139 * to construct datasets where the algorithm takes
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	140 * time of order n^2, but it simply never happens in
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	141 * practice.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	142 * 3' Newsflash: On further investigation I find that
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	143 * it's easy to construct datasets where median-of-3
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	144 * simply isn't good enough. So on large-ish subarrays
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	145 * we do a more sophisticated pivoting: we take three
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	146 * sets of 3 elements, find their medians, and then
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	147 * take the median of those.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	148 * 4. We copy the pivot element to a separate place
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	149 * because that way we can always do our comparisons
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	150 * directly against a pointer to that separate place,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	151 * and don't have to wonder "did we move the pivot
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	152 * element?". This makes the inner loop better.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	153 * 5. It's possible to make the pivoting even more
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	154 * reliable by looking at more candidates when n
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	155 * is larger. (Taking this to its logical conclusion
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	156 * results in a variant of quicksort that doesn't
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	157 * have that n^2 worst case.) However, the overhead
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	158 * from the extra bookkeeping means that it's just
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	159 * not worth while.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	160 * 6. This is pretty clean and portable code. Here are
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	161 * all the potential portability pitfalls and problems
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	162 * I know of:
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	163 * - In one place (the insertion sort) I construct
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	164 * a pointer that points just past the end of the
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	165 * supplied array, and assume that (a) it won't
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	166 * compare equal to any pointer within the array,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	167 * and (b) it will compare equal to a pointer
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	168 * obtained by stepping off the end of the array.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	169 * These might fail on some segmented architectures.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	170 * - I assume that there are 8 bits in a \|char\| when
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	171 * computing the size of stack needed. This would
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	172 * fail on machines with 9-bit or 16-bit bytes.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	173 * - I assume that if \|((int)base&(sizeof(int)-1))==0\|
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	174 * and \|(size&(sizeof(int)-1))==0\| then it's safe to
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	175 * get at array elements via \|int*\|s, and that if
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	176 * actually \|size==sizeof(int)\| as well then it's
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	177 * safe to treat the elements as \|int\|s. This might
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	178 * fail on systems that convert pointers to integers
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	179 * in non-standard ways.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	180 * - I assume that \|8*sizeof(size_t)<=INT_MAX\|. This
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	181 * would be false on a machine with 8-bit \|char\|s,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	182 * 16-bit \|int\|s and 4096-bit \|size_t\|s. :-)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	183 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	184
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	185 /* The recursion logic is the same in each case: */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	186 #define Recurse(Trunc) \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	187 { size_t l=last-ffirst,r=llast-first; \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	188 if (l<Trunc) { \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	189 if (r>=Trunc) doRight \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	190 else pop \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	191 } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	192 else if (l<=r) { pushLeft; doRight } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	193 else if (r>=Trunc) { pushRight; doLeft }\
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	194 else doLeft \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	195 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	196
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	197 /* and so is the pivoting logic: */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	198 #define Pivot(swapper,sz) \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	199 if ((size_t)(last-first)>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	200 else { \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	201 if (compare(first,mid)<0) { \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	202 if (compare(mid,last)>0) { \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	203 swapper(mid,last); \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	204 if (compare(first,mid)>0) swapper(first,mid);\
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	205 } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	206 } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	207 else { \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	208 if (compare(mid,last)>0) swapper(first,last)\
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	209 else { \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	210 swapper(first,mid); \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	211 if (compare(mid,last)>0) swapper(mid,last);\
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	212 } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	213 } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	214 first+=sz; last-=sz; \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	215 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	216
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	217 #ifdef DEBUG_QSORT
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	218 #include <stdio.h>
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	219 #endif
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	220
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	221 /* and so is the partitioning logic: */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	222 #define Partition(swapper,sz) { \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	223 int swapped=0; \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	224 do { \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	225 while (compare(first,pivot)<0) first+=sz; \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	226 while (compare(pivot,last)<0) last-=sz; \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	227 if (first<last) { \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	228 swapper(first,last); swapped=1; \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	229 first+=sz; last-=sz; } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	230 else if (first==last) { first+=sz; last-=sz; break; }\
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	231 } while (first<=last); \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	232 if (!swapped) pop \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	233 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	234
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	235 /* and so is the pre-insertion-sort operation of putting
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	236 * the smallest element into place as a sentinel.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	237 * Doing this makes the inner loop nicer. I got this
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	238 * idea from the GNU implementation of qsort().
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	239 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	240 #define PreInsertion(swapper,limit,sz) \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	241 first=base; \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	242 last=first + (nmemb>limit ? limit : nmemb-1)*sz;\
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	243 while (last!=base) { \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	244 if (compare(first,last)>0) first=last; \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	245 last-=sz; } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	246 if (first!=base) swapper(first,(char*)base);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	247
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	248 /* and so is the insertion sort, in the first two cases: */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	249 #define Insertion(swapper) \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	250 last=((char)base)+nmembsize; \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	251 for (first=((char*)base)+size;first!=last;first+=size) { \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	252 char *test; \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	253 /* Find the right place for \|first\|. \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	254 * My apologies for var reuse. */ \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	255 for (test=first-size;compare(test,first)>0;test-=size) ; \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	256 test+=size; \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	257 if (test!=first) { \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	258 /* Shift everything in [test,first) \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	259 * up by one, and place \|first\| \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	260 * where \|test\| is. */ \
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	261 memcpy(pivot,first,size); \
c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	262 memmove(test+size,test,first-test); \
c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	263 memcpy(test,pivot,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	264 } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	265 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	266
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	267 #define SWAP_nonaligned(a,b) { \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	268 register char aa=(a),bb=(b); \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	269 register size_t sz=size; \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	270 do { register char t=aa; aa++=bb; bb++=t; } while (--sz); }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	271
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	272 #define SWAP_aligned(a,b) { \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	273 register int aa=(int)(a),bb=(int)(b); \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	274 register size_t sz=size; \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	275 do { register int t=aa;aa++=bb; bb++=t; } while (sz-=WORD_BYTES); }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	276
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	277 #define SWAP_words(a,b) { \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	278 register int t=((int)a); ((int)a)=((int)b); ((int)b)=t; }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	279
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	280 /* ---------------------------------------------------------------------- */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	281
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	282 static char * pivot_big(char first, char mid, char *last, size_t size,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	283 int compare(const void , const void )) {
1456 84de7511f79f Fixed a bunch of 64-bit compatibility problems Sam Lantinga <slouken@libsdl.org> parents: 1402 diff changeset	284 size_t d=(((last-first)/size)>>3)*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	285 char m1,m2,*m3;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	286 { char a=first, b=first+d, c=first+2d;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	287 #ifdef DEBUG_QSORT
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	288 fprintf(stderr,"< %d %d %d\n",(int)a,(int)b,(int)c);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	289 #endif
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	290 m1 = compare(a,b)<0 ?
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	291 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	292 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	293 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	294 { char a=mid-d, b=mid, *c=mid+d;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	295 #ifdef DEBUG_QSORT
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	296 fprintf(stderr,". %d %d %d\n",(int)a,(int)b,(int)c);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	297 #endif
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	298 m2 = compare(a,b)<0 ?
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	299 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	300 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	301 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	302 { char a=last-2d, b=last-d, c=last;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	303 #ifdef DEBUG_QSORT
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	304 fprintf(stderr,"> %d %d %d\n",(int)a,(int)b,(int)c);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	305 #endif
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	306 m3 = compare(a,b)<0 ?
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	307 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	308 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	309 }
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 #ifdef DEBUG_QSORT
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 fprintf(stderr,"-> %d %d %d\n",(int)m1,(int)m2,(int)m3);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	312 #endif
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	313 return compare(m1,m2)<0 ?
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	314 (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1))
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	315 : (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2));
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	316 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	317
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	318 /* ---------------------------------------------------------------------- */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	319
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	320 static void qsort_nonaligned(void *base, size_t nmemb, size_t size,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	321 int (compare)(const void , const void *)) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	322
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	323 stack_entry stack[STACK_SIZE];
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	324 int stacktop=0;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	325 char first,last;
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	326 char *pivot=malloc(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	327 size_t trunc=TRUNC_nonaligned*size;
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 assert(pivot!=0);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	329
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	330 first=(char)base; last=first+(nmemb-1)size;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	331
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	332 if ((size_t)(last-first)>trunc) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	333 char ffirst=first, llast=last;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	334 while (1) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	335 /* Select pivot */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	336 { char * mid=first+size*((last-first)/size >> 1);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	337 Pivot(SWAP_nonaligned,size);
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	338 memcpy(pivot,mid,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	339 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	340 /* Partition. */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	341 Partition(SWAP_nonaligned,size);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	342 /* Prepare to recurse/iterate. */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	343 Recurse(trunc)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	344 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	345 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	346 PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size);
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 Insertion(SWAP_nonaligned);
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	348 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	349 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	350
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	351 static void qsort_aligned(void *base, size_t nmemb, size_t size,
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 int (compare)(const void , const void *)) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	353
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	354 stack_entry stack[STACK_SIZE];
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	355 int stacktop=0;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	356 char first,last;
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	357 char *pivot=malloc(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	358 size_t trunc=TRUNC_aligned*size;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	359 assert(pivot!=0);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	360
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	361 first=(char)base; last=first+(nmemb-1)size;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	362
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	363 if ((size_t)(last-first)>trunc) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	364 char ffirst=first,llast=last;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	365 while (1) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	366 /* Select pivot */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	367 { char * mid=first+size*((last-first)/size >> 1);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	368 Pivot(SWAP_aligned,size);
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	369 memcpy(pivot,mid,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	370 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	371 /* Partition. */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	372 Partition(SWAP_aligned,size);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	373 /* Prepare to recurse/iterate. */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	374 Recurse(trunc)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	375 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	376 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	377 PreInsertion(SWAP_aligned,TRUNC_aligned,size);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	378 Insertion(SWAP_aligned);
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	379 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	380 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	381
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	382 static void qsort_words(void *base, size_t nmemb,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	383 int (compare)(const void , const void *)) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	384
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	385 stack_entry stack[STACK_SIZE];
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	386 int stacktop=0;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	387 char first,last;
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	388 char *pivot=malloc(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	389 assert(pivot!=0);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	390
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	391 first=(char)base; last=first+(nmemb-1)WORD_BYTES;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	392
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	393 if (last-first>TRUNC_words) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	394 char ffirst=first, llast=last;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	395 while (1) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	396 #ifdef DEBUG_QSORT
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	397 fprintf(stderr,"Doing %d:%d: ",
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	398 (first-(char*)base)/WORD_BYTES,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	399 (last-(char*)base)/WORD_BYTES);
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 #endif
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	401 /* Select pivot */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	402 { char * mid=first+WORD_BYTES((last-first) / (2WORD_BYTES));
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	403 Pivot(SWAP_words,WORD_BYTES);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	404 (int)pivot=(int)mid;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	405 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	406 #ifdef DEBUG_QSORT
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	407 fprintf(stderr,"pivot=%d\n",(int)pivot);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	408 #endif
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	409 /* Partition. */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	410 Partition(SWAP_words,WORD_BYTES);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	411 /* Prepare to recurse/iterate. */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	412 Recurse(TRUNC_words)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	413 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	414 }
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 PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	416 /* Now do insertion sort. */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	417 last=((char)base)+nmembWORD_BYTES;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	418 for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	419 /* Find the right place for \|first\|. My apologies for var reuse */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	420 int pl=(int)(first-WORD_BYTES),pr=(int)first;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	421 (int)pivot=(int)first;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	422 for (;compare(pl,pivot)>0;pr=pl,--pl) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	423 pr=pl; }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	424 if (pr!=(int)first) pr=(int)pivot;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	425 }
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	426 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	427 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	428
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	429 /* ---------------------------------------------------------------------- */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	430
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	431 void qsort(void *base, size_t nmemb, size_t 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	432 int (compare)(const void , const void *)) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	433
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	434 if (nmemb<=1) return;
1456 84de7511f79f Fixed a bunch of 64-bit compatibility problems Sam Lantinga <slouken@libsdl.org> parents: 1402 diff changeset	435 if (((uintptr_t)base\|size)&(WORD_BYTES-1))
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	436 qsort_nonaligned(base,nmemb,size,compare);
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 else if (size!=WORD_BYTES)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	438 qsort_aligned(base,nmemb,size,compare);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	439 else
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	440 qsort_words(base,nmemb,compare);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	441 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	442
1331 1cbaeee565b1 A few fixes to get this building on Linux again Sam Lantinga <slouken@libsdl.org> parents: 1330 diff changeset	443 #endif /* !HAVE_QSORT */

Mercurial > sdl-ios-xcode

annotate src/stdlib/SDL_qsort.c @ 4347:38f22ed3a433 SDL-1.2