sdl-ios-xcode: src/stdlib/SDL

annotate src/stdlib/SDL_qsort.c @ 2185:2032348afed1

This code adds support for DirectColor visuals to SDL 1.3. The support uses part of the Xmu library. To ensure that the library is available and to keep people form having to install yet another library I have added the essential parts of Xmu in src/video/extensions/XmuStdCmap and an include file in src/video/extensions. The support makes use of standard X11 mechanisms to create color maps and make sure that an application uses the same color map for each window/visual combination. This should make it possible for gamma support to be implemented based on a single color map per application. Hurm... it looks like "make indent" modified a few extra files. Those are getting committed too.

author	Bob Pendleton <bob@pendleton.com>
date	Thu, 12 Jul 2007 20:00:50 +0000
parents	c121d94672cb
children	dc1eb82ffdaa

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
1337 c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	53 #define assert(X)
c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	54 #define malloc SDL_malloc
c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	55 #define free SDL_free
c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	56 #define memcpy SDL_memcpy
c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	57 #define memmove SDL_memmove
c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	58 #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	59
c687f06c7473 Don't touch code that we brought in from other sources Sam Lantinga <slouken@libsdl.org> parents: 1336 diff changeset	60
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	61 #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	62
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	63 static 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	64
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	65 /* 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	66 * 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	67 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	68 #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	69
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	70 /* 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	71 * 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	72 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	73 #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	74
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows, Sam Lantinga <slouken@libsdl.org> parents: diff changeset	75 /* 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	76 * 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	77 * 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	78 * 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	79 * 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	80 * 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	81 */
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 #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	83 #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	84 #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	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 /* 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	87 * 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	88 * 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	89 */
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 #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	91
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	92 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	93 {
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	94 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	95 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	96 } 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	97 #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	98 #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	99 #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	100 #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	101 #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	102 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	103 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	104 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	105
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 /* 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	107 * 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	108 * 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	109 * 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	110 * 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	111 * 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	112 * 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	113 * 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	114 * 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	115 * 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	116 * 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	117 * 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	118 * 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	119 * 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	120 * 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	121 * 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	122 * 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	123 * 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	124 * 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	125 * 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	126 * 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	127 * 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	128 * 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	129 * 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	130 * 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	131 * 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	132 * 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	133 * 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	134 * 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	135 * 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	136 * 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	137 * 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	138 * 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	139 * 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	140 * 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	141 * 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	142 * 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	143 * 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	144 * 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	145 * 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	146 * 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	147 * 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	148 * 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	149 * - 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	150 * 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	151 * 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	152 * 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	153 * 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	154 * 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	155 * 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	156 * - 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	157 * 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	158 * 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	159 * - 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	160 * 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	161 * 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	162 * 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	163 * 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	164 * 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	165 * 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	166 * - 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	167 * 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	168 * 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	169 */
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
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 /* 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	172 #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	173 { 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	174 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	175 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	176 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	177 } \
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 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	179 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	180 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	181 }
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
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 /* 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	184 #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	185 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	186 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	187 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	188 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	189 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	190 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	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 } \
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 { \
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 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	195 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	196 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	197 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	198 } \
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 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	201 }
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
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 #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	204 #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	205 #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	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 /* 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	208 #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	209 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	210 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	211 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	212 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	213 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	214 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	215 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	216 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	217 } 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	218 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	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 /* 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	222 * 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	223 * 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	224 * 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	225 */
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 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	227 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	228 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	229 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	230 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	231 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	232 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	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 /* 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	235 #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	236 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	237 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	238 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	239 /* 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	240 * 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	241 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	242 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	243 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	244 /* 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	245 * 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	246 * 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	247 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	248 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	249 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	250 } \
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
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 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	254 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	255 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	256 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	257
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 #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	259 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	260 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	261 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	262
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 #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	264 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	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
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	268 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	269 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	270 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	271 {
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	272 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	273 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	274 {
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	275 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	276 #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	277 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	278 #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	279 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	280 (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	281 : (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	282 }
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	283 {
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	284 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	285 #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	286 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	287 #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	288 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	289 (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	290 : (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	291 }
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 = 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	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 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	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 }
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	301 #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	302 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	303 #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	304 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	305 (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	306 : (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	307 }
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
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
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	311 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	312 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	313 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	314 {
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	315
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	316 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	317 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	318 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	319 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	320 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	321 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	322
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	323 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	324 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	325
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	326 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	327 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	328 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	329 /* 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	330 {
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 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	332 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	333 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	334 }
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 /* 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	336 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	337 /* 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	338 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	339 }
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	340 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	341 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	342 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	343 }
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
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	345 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	346 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	347 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	348 {
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
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	350 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	351 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	352 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	353 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	354 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	355 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	356
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	357 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	358 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	359
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	360 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	361 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	362 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	363 /* 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	364 {
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 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	366 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	367 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	368 }
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 /* 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	370 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	371 /* 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	372 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	373 }
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	374 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	375 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	376 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	377 }
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
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	379 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	380 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	381 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	382 {
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	383
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	384 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	385 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	386 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	387 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	388 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	389
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	390 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	391 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	392
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	393 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	394 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	395 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	396 #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	397 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	398 (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	399 (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	400 #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	401 /* 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	402 {
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 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	404 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	405 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	406 (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	407 }
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	408 #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	409 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	410 #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	411 /* 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	412 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	413 /* 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	414 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	415 }
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	416 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	417 /* 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	418 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	419 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	420 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	421 /* 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	422 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	423 (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	424 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	425 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	426 }
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 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	428 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	429 }
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 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	431 }
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
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
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	435 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	436 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	437 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	438 {
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	439
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	440 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	441 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	442 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	443 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	444 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	445 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	446 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	447 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	448 }
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
1331 1cbaeee565b1 A few fixes to get this building on Linux again Sam Lantinga <slouken@libsdl.org> parents: 1330 diff changeset	450 #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	451 /* vi: set ts=4 sw=4 expandtab: */

Mercurial > sdl-ios-xcode

annotate src/stdlib/SDL_qsort.c @ 2185:2032348afed1