sdl-ios-xcode: src/stdlib/SDL

annotate src/stdlib/SDL_qsort.c @ 4734:0c7c67d4e6ee

Added On_Char method to Window_Listener for WM_CHAR messages. Removed a lot of TSF code because part of it was wrong and part was too complicated. Added Clear method to clear the window. IME input should work in both windowed mode and fullscreen mode with these changes. I have tested on Windows XP SP3 and Windows 7 Ultimate in VirtualBox. When you type a character (with an IME or not), the console will show the code point as U+XXXX. You use Left Alt+Shift (or whatever you have it set to) to switch input languages as usual. Hit ESC to exit (or close the window in windowed mode). The program will pause before exiting so you can review the console output (press a key to exit).

author	dewyatt
date	Wed, 09 Jun 2010 00:03:54 -0400
parents	0aaa7f52d1c6
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
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	53 #ifdef assert
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	54 #undef assert
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	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)
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	57 #ifdef malloc
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	58 #undef malloc
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	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
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	61 #ifdef free
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	62 #undef free
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	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
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	65 #ifdef memcpy
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	66 #undef memcpy
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	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
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	69 #ifdef memmove
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	70 #undef memmove
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	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
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	73 #ifdef qsort
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	74 #undef qsort
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	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
3162 dc1eb82ffdaa Von: Thomas Zimmermann Sam Lantinga <slouken@libsdl.org> parents: 1895 diff changeset	81 static const char _ID[] = "<qsort.c gjm 1.12 1998-03-19>";
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	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
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	102 #define TRUNC_words 12WORD_BYTES / nb different meaning */
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	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
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	110 typedef struct
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	111 {
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	112 char *first;
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	113 char *last;
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	114 } stack_entry;
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	115 #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	116 #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	117 #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	118 #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	119 #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	120 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	121 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	122 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	123
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 /* 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	125 * 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	126 * 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	127 * 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	128 * 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	129 * 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	130 * 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	131 * 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	132 * 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	133 * 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	134 * 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	135 * 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	136 * 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	137 * 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	138 * 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	139 * 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	140 * 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	141 * 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	142 * 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	143 * 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	144 * 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	145 * 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	146 * 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	147 * 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	148 * 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	149 * 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	150 * 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	151 * 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	152 * 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	153 * 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	154 * 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	155 * 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	156 * 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	157 * 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	158 * 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	159 * 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	160 * 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	161 * 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	162 * 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	163 * 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	164 * 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	165 * 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	166 * 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	167 * - 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	168 * 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	169 * 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	170 * 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	171 * 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	172 * 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	173 * 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	174 * - 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	175 * 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	176 * 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	177 * - 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	178 * 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	179 * 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	180 * 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	181 * 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	182 * 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	183 * 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	184 * - 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	185 * 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	186 * 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	187 */
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
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 /* 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	190 #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	191 { 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	192 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	193 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	194 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	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 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	197 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	198 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	199 }
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
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 /* 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	202 #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	203 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	204 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	205 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	206 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	207 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	208 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	209 } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	210 } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	211 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	212 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	213 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	214 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	215 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	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 } \
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 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	219 }
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 #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	222 #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	223 #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	224
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 /* 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	226 #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	227 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	228 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	229 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	230 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	231 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	232 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	233 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	234 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	235 } 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	236 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	237 }
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
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 /* 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	240 * 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	241 * 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	242 * 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	243 */
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 #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	245 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	246 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	247 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	248 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	249 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	250 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	251
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 /* 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	253 #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	254 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	255 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	256 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	257 /* 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	258 * 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	259 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	260 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	261 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	262 /* 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	263 * 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	264 * 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	265 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	266 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	267 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	268 } \
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 }
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
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 #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	272 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	273 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	274 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	275
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 #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	277 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	278 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	279 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	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 #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	282 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	283
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	284 /* ---------------------------------------------------------------------- */
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
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	286 static char *
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	287 pivot_big(char first, char mid, char *last, size_t size,
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	288 int compare(const void , const void ))
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	289 {
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	290 size_t d = (((last - first) / size) >> 3) * size;
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	291 char m1, m2, *m3;
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	292 {
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	293 char a = first, b = first + d, c = first + 2 d;
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	294 #ifdef DEBUG_QSORT
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	295 fprintf(stderr, "< %d %d %d\n", (int ) a, (int ) b, (int ) c);
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	296 #endif
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	297 m1 = compare(a, b) < 0 ?
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	298 (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
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	299 : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
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	300 }
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	301 {
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	302 char a = mid - d, b = mid, *c = mid + d;
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	303 #ifdef DEBUG_QSORT
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	304 fprintf(stderr, ". %d %d %d\n", (int ) a, (int ) b, (int ) c);
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	305 #endif
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	306 m2 = compare(a, b) < 0 ?
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	307 (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
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	308 : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
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	309 }
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	310 {
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	311 char a = last - 2 d, b = last - d, c = 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	312 #ifdef DEBUG_QSORT
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	313 fprintf(stderr, "> %d %d %d\n", (int ) a, (int ) b, (int ) c);
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	314 #endif
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	315 m3 = compare(a, b) < 0 ?
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	316 (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
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	317 : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
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	318 }
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	319 #ifdef DEBUG_QSORT
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	320 fprintf(stderr, "-> %d %d %d\n", (int ) m1, (int ) m2, (int ) m3);
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	321 #endif
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	322 return compare(m1, m2) < 0 ?
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	323 (compare(m2, m3) < 0 ? m2 : (compare(m1, m3) < 0 ? m3 : m1))
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	324 : (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	325 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	326
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 /* ---------------------------------------------------------------------- */
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
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	329 static void
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	330 qsort_nonaligned(void *base, size_t nmemb, size_t size,
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	331 int (compare) (const void , const void *))
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	332 {
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	333
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	334 stack_entry stack[STACK_SIZE];
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	335 int stacktop = 0;
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	336 char first, last;
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	337 char *pivot = malloc(size);
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	338 size_t trunc = TRUNC_nonaligned * size;
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	339 assert(pivot != 0);
1330 450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	340
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	341 first = (char *) base;
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	342 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	343
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	344 if ((size_t) (last - first) > trunc) {
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	345 char ffirst = first, llast = last;
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	346 while (1) {
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	347 /* Select pivot */
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	348 {
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	349 char mid = first + size ((last - first) / size >> 1);
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	350 Pivot(SWAP_nonaligned, size);
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	351 memcpy(pivot, mid, size);
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	352 }
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	353 /* Partition. */
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	354 Partition(SWAP_nonaligned, size);
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	355 /* Prepare to recurse/iterate. */
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	356 Recurse(trunc)}
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	357 }
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	358 PreInsertion(SWAP_nonaligned, TRUNC_nonaligned, size);
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	359 Insertion(SWAP_nonaligned);
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	360 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	361 }
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
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	363 static void
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	364 qsort_aligned(void *base, size_t nmemb, size_t size,
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	365 int (compare) (const void , const void *))
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	366 {
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	367
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	368 stack_entry stack[STACK_SIZE];
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	369 int stacktop = 0;
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	370 char first, last;
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	371 char *pivot = malloc(size);
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	372 size_t trunc = TRUNC_aligned * size;
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	373 assert(pivot != 0);
1330 450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	374
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	375 first = (char *) base;
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	376 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	377
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	378 if ((size_t) (last - first) > trunc) {
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	379 char ffirst = first, llast = last;
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	380 while (1) {
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	381 /* Select pivot */
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	382 {
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	383 char mid = first + size ((last - first) / size >> 1);
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	384 Pivot(SWAP_aligned, size);
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	385 memcpy(pivot, mid, size);
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	386 }
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	387 /* Partition. */
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	388 Partition(SWAP_aligned, size);
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	389 /* Prepare to recurse/iterate. */
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	390 Recurse(trunc)}
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	391 }
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	392 PreInsertion(SWAP_aligned, TRUNC_aligned, size);
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	393 Insertion(SWAP_aligned);
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	394 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	395 }
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
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	397 static void
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	398 qsort_words(void *base, size_t nmemb,
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	399 int (compare) (const void , const void *))
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	400 {
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	401
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	402 stack_entry stack[STACK_SIZE];
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	403 int stacktop = 0;
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	404 char first, last;
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	405 char *pivot = malloc(WORD_BYTES);
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	406 assert(pivot != 0);
1330 450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	407
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	408 first = (char *) base;
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	409 last = first + (nmemb - 1) * 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	410
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	411 if (last - first > TRUNC_words) {
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	412 char ffirst = first, llast = last;
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	413 while (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	414 #ifdef DEBUG_QSORT
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	415 fprintf(stderr, "Doing %d:%d: ",
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	416 (first - (char *) base) / WORD_BYTES,
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	417 (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	418 #endif
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	419 /* Select pivot */
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	420 {
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	421 char *mid =
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	422 first + WORD_BYTES * ((last - first) / (2 * WORD_BYTES));
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	423 Pivot(SWAP_words, WORD_BYTES);
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	424 (int ) pivot = (int ) mid;
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	425 }
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	426 #ifdef DEBUG_QSORT
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	427 fprintf(stderr, "pivot=%d\n", (int ) 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	428 #endif
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	429 /* Partition. */
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	430 Partition(SWAP_words, WORD_BYTES);
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	431 /* Prepare to recurse/iterate. */
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	432 Recurse(TRUNC_words)}
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	433 }
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	434 PreInsertion(SWAP_words, (TRUNC_words / WORD_BYTES), WORD_BYTES);
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	435 /* Now do insertion sort. */
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	436 last = ((char ) base) + nmemb WORD_BYTES;
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	437 for (first = ((char *) base) + WORD_BYTES; first != last;
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	438 first += WORD_BYTES) {
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	439 /* Find the right place for \|first\|. My apologies for var reuse */
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	440 int pl = (int ) (first - WORD_BYTES), pr = (int ) first;
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	441 (int ) pivot = (int ) first;
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	442 for (; compare(pl, pivot) > 0; pr = pl, --pl) {
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	443 pr = pl;
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	444 }
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	445 if (pr != (int *) first)
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	446 pr = (int *) pivot;
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	447 }
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	448 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	449 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	450
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	451 /* ---------------------------------------------------------------------- */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	452
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	453 void
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	454 qsort(void *base, size_t nmemb, size_t size,
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	455 int (compare) (const void , const void *))
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	456 {
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	457
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	458 if (nmemb <= 1)
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	459 return;
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	460 if (((uintptr_t) base \| size) & (WORD_BYTES - 1))
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	461 qsort_nonaligned(base, nmemb, size, compare);
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	462 else if (size != WORD_BYTES)
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	463 qsort_aligned(base, nmemb, size, compare);
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	464 else
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	465 qsort_words(base, nmemb, compare);
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	466 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	467
1331 1cbaeee565b1 A few fixes to get this building on Linux again Sam Lantinga <slouken@libsdl.org> parents: 1330 diff changeset	468 #endif /* !HAVE_QSORT */
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	469 /* vi: set ts=4 sw=4 expandtab: */

Mercurial > sdl-ios-xcode

annotate src/stdlib/SDL_qsort.c @ 4734:0c7c67d4e6ee