Mercurial > sdl-ios-xcode
annotate src/stdlib/SDL_qsort.c @ 4167:a6f635e5eaa6 SDL-1.2
Fixed bug #611
From Tim Angus 2008-08-12 11:18:06
I'm one of the maintainers of ioquake3.org, an updated version of the
Quake 3 engine. Relatively recently, we moved ioq3 to use SDL as a
replacement for 95% of the platform specific code that was there. On the
whole it's doing a great job but unfortunately since the move we've been
getting complaints about the quality of the mouse input on the Windows
platform to the point where for many the game is unplayable. Put in
other terms, the current stable SDL 1.2 is basically not fit for purpose
if you need high quality mouse input as you do in a first person shooter.
Over the weekend I decided to pull my finger out and actually figure out
what's going on. There are basically two major problems. Firstly, when
using the "windib" driver, mouse input is gathered via the WM_MOUSEMOVE
message. Googling for this indicates that often this is known to result
in "spurious" and/or "missing" mouse movement events; this is the
primary cause of the poor mouse input. The second problem is that the
"directx" driver does not work at all in combination with OpenGL meaning
that you can't use DirectInput if your application also uses OpenGL. In
other words you're locked into using the "windib" driver and its poor
mouse input.
In order to address these problems I've done the following:
* Remove WM_MOUSEMOVE based motion event generation and replace with
calls to GetCursorPos which seems much more reliable. In order to
achieve this I've moved mouse motion out into a separate function that
is called once per DIB_PumpEvents.
* Remove the restriction on the "directx" driver being inoperable in
combination with OpenGL. There is a bug for this issues that I've
hijacked to a certain extent
(http://bugzilla.libsdl.org/show_bug.cgi?id=265). I'm the first to admit
I don't really understand why this restriction is there in the first
place. The commit message for the bug fix that introduced this
restriction (r581) isn't very elaborate and I couldn't see any other bug
tracking the issue. If anyone has more information on the bug that was
avoided by r581 it would be helpful as I/someone could then look into
addressing the problem without disabling the "directx" driver.
* I've also removed the restriction on not being allowed to use
DirectInput in windowed mode. I couldn't see any reason for this, at
least not from our perspective. I have my suspicions that it'll be
something like matching up the cursor with the mouse coordinates...
* I bumped up the DirectInput API used to version 7 in order to get
access to mouse buttons 4-7. I've had to inject a little bit of the DX7
headers into SDL there as the MinGW ones aren't up to date in this respect.
author | Sam Lantinga <slouken@libsdl.org> |
---|---|
date | Thu, 02 Apr 2009 04:43:36 +0000 |
parents | 84de7511f79f |
children | 782fd950bd46 c121d94672cb 5bacec0933f5 |
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 |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
63 static char _ID[]="<qsort.c gjm 1.12 1998-03-19>"; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
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 |
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 #define TRUNC_words 12*WORD_BYTES /* nb different meaning */ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
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 |
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 typedef struct { char * first; char * last; } stack_entry; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
93 #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
|
94 #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
|
95 #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
|
96 #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
|
97 #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
|
98 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
|
99 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
|
100 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 |
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 /* 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
|
103 * 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
|
104 * 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
|
105 * 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
|
106 * 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
|
107 * 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
|
108 * 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
|
109 * 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
|
110 * 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
|
111 * 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
|
112 * 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
|
113 * 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
|
114 * 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
|
115 * 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
|
116 * 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
|
117 * 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
|
118 * 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
|
119 * 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
|
120 * 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
|
121 * 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
|
122 * 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
|
123 * 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
|
124 * 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
|
125 * 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
|
126 * 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
|
127 * 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
|
128 * 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
|
129 * 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
|
130 * 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
|
131 * 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
|
132 * 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
|
133 * 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
|
134 * 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
|
135 * 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
|
136 * 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
|
137 * 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
|
138 * 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
|
139 * 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
|
140 * 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
|
141 * 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
|
142 * 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
|
143 * 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
|
144 * 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
|
145 * - 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
|
146 * 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
|
147 * 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
|
148 * 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
|
149 * 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
|
150 * 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
|
151 * 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
|
152 * - 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
|
153 * 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
|
154 * 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
|
155 * - 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
|
156 * 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
|
157 * 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
|
158 * 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
|
159 * 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
|
160 * 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
|
161 * 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
|
162 * - 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
|
163 * 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
|
164 * 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
|
165 */ |
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 |
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 /* 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
|
168 #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
|
169 { 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
|
170 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
|
171 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
|
172 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
|
173 } \ |
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 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
|
175 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
|
176 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
|
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 |
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 /* 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
|
180 #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
|
181 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
|
182 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
|
183 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
|
184 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
|
185 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
|
186 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
|
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 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
|
190 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
|
191 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
|
192 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
|
193 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
|
194 } \ |
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 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
|
197 } |
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 #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
|
200 #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
|
201 #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
|
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 /* 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
|
204 #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
|
205 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
|
206 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
|
207 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
|
208 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
|
209 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
|
210 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
|
211 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
|
212 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
|
213 } 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
|
214 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
|
215 } |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
216 |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
217 /* 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
|
218 * 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
|
219 * 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
|
220 * 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
|
221 */ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
222 #define 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
|
223 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
|
224 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
|
225 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
|
226 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
|
227 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
|
228 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
|
229 |
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 /* 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
|
231 #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
|
232 last=((char*)base)+nmemb*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
|
233 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
|
234 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
|
235 /* 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
|
236 * 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
|
237 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
|
238 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
|
239 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
|
240 /* 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
|
241 * 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
|
242 * 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
|
243 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
|
244 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
|
245 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
|
246 } \ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
247 } |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
248 |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
249 #define 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
|
250 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
|
251 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
|
252 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
|
253 |
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 #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
|
255 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
|
256 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
|
257 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
|
258 |
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 #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
|
260 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
|
261 |
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 |
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 static char * pivot_big(char *first, char *mid, char *last, size_t size, |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
265 int compare(const void *, const void *)) { |
1456
84de7511f79f
Fixed a bunch of 64-bit compatibility problems
Sam Lantinga <slouken@libsdl.org>
parents:
1402
diff
changeset
|
266 size_t d=(((last-first)/size)>>3)*size; |
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
267 char *m1,*m2,*m3; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
268 { char *a=first, *b=first+d, *c=first+2*d; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
269 #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
|
270 fprintf(stderr,"< %d %d %d\n",*(int*)a,*(int*)b,*(int*)c); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
271 #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
|
272 m1 = compare(a,b)<0 ? |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
273 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
274 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
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 { char *a=mid-d, *b=mid, *c=mid+d; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
277 #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
|
278 fprintf(stderr,". %d %d %d\n",*(int*)a,*(int*)b,*(int*)c); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
279 #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
|
280 m2 = compare(a,b)<0 ? |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
281 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
282 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
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 { char *a=last-2*d, *b=last-d, *c=last; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
285 #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
|
286 fprintf(stderr,"> %d %d %d\n",*(int*)a,*(int*)b,*(int*)c); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
287 #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
|
288 m3 = compare(a,b)<0 ? |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
289 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
290 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
291 } |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
292 #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
|
293 fprintf(stderr,"-> %d %d %d\n",*(int*)m1,*(int*)m2,*(int*)m3); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
294 #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
|
295 return compare(m1,m2)<0 ? |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
296 (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1)) |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
297 : (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2)); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
298 } |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
299 |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
300 /* ---------------------------------------------------------------------- */ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
301 |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
302 static void qsort_nonaligned(void *base, size_t nmemb, size_t size, |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
303 int (*compare)(const void *, const void *)) { |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
304 |
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 stack_entry stack[STACK_SIZE]; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
306 int stacktop=0; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
307 char *first,*last; |
1337
c687f06c7473
Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents:
1336
diff
changeset
|
308 char *pivot=malloc(size); |
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
309 size_t trunc=TRUNC_nonaligned*size; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
310 assert(pivot!=0); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
311 |
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 first=(char*)base; last=first+(nmemb-1)*size; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
313 |
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 if ((size_t)(last-first)>trunc) { |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
315 char *ffirst=first, *llast=last; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
316 while (1) { |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
317 /* Select pivot */ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
318 { char * mid=first+size*((last-first)/size >> 1); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
319 Pivot(SWAP_nonaligned,size); |
1337
c687f06c7473
Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents:
1336
diff
changeset
|
320 memcpy(pivot,mid,size); |
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
321 } |
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 /* Partition. */ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
323 Partition(SWAP_nonaligned,size); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
324 /* Prepare to recurse/iterate. */ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
325 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
|
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 PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
329 Insertion(SWAP_nonaligned); |
1337
c687f06c7473
Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents:
1336
diff
changeset
|
330 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
|
331 } |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
332 |
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 static void qsort_aligned(void *base, size_t nmemb, size_t size, |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
334 int (*compare)(const void *, const void *)) { |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
335 |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
336 stack_entry stack[STACK_SIZE]; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
337 int stacktop=0; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
338 char *first,*last; |
1337
c687f06c7473
Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents:
1336
diff
changeset
|
339 char *pivot=malloc(size); |
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
340 size_t trunc=TRUNC_aligned*size; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
341 assert(pivot!=0); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
342 |
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 first=(char*)base; last=first+(nmemb-1)*size; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
344 |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
345 if ((size_t)(last-first)>trunc) { |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
346 char *ffirst=first,*llast=last; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
347 while (1) { |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
348 /* Select pivot */ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
349 { char * mid=first+size*((last-first)/size >> 1); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
350 Pivot(SWAP_aligned,size); |
1337
c687f06c7473
Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents:
1336
diff
changeset
|
351 memcpy(pivot,mid,size); |
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
352 } |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
353 /* Partition. */ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
354 Partition(SWAP_aligned,size); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
355 /* Prepare to recurse/iterate. */ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
356 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
|
357 } |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
358 } |
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 PreInsertion(SWAP_aligned,TRUNC_aligned,size); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
360 Insertion(SWAP_aligned); |
1337
c687f06c7473
Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents:
1336
diff
changeset
|
361 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
|
362 } |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
363 |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
364 static void qsort_words(void *base, size_t nmemb, |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
365 int (*compare)(const void *, const void *)) { |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
366 |
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 stack_entry stack[STACK_SIZE]; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
368 int stacktop=0; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
369 char *first,*last; |
1337
c687f06c7473
Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents:
1336
diff
changeset
|
370 char *pivot=malloc(WORD_BYTES); |
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
371 assert(pivot!=0); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
372 |
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 first=(char*)base; last=first+(nmemb-1)*WORD_BYTES; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
374 |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
375 if (last-first>TRUNC_words) { |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
376 char *ffirst=first, *llast=last; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
377 while (1) { |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
378 #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
|
379 fprintf(stderr,"Doing %d:%d: ", |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
380 (first-(char*)base)/WORD_BYTES, |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
381 (last-(char*)base)/WORD_BYTES); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
382 #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
|
383 /* Select pivot */ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
384 { char * mid=first+WORD_BYTES*((last-first) / (2*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
|
385 Pivot(SWAP_words,WORD_BYTES); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
386 *(int*)pivot=*(int*)mid; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
387 } |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
388 #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
|
389 fprintf(stderr,"pivot=%d\n",*(int*)pivot); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
390 #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
|
391 /* Partition. */ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
392 Partition(SWAP_words,WORD_BYTES); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
393 /* Prepare to recurse/iterate. */ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
394 Recurse(TRUNC_words) |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
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 } |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
397 PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
398 /* Now do insertion sort. */ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
399 last=((char*)base)+nmemb*WORD_BYTES; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
400 for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) { |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
401 /* Find the right place for |first|. My apologies for var reuse */ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
402 int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
403 *(int*)pivot=*(int*)first; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
404 for (;compare(pl,pivot)>0;pr=pl,--pl) { |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
405 *pr=*pl; } |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
406 if (pr!=(int*)first) *pr=*(int*)pivot; |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
407 } |
1337
c687f06c7473
Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents:
1336
diff
changeset
|
408 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
|
409 } |
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 |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
411 /* ---------------------------------------------------------------------- */ |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
412 |
1337
c687f06c7473
Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents:
1336
diff
changeset
|
413 void qsort(void *base, size_t nmemb, size_t size, |
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
414 int (*compare)(const void *, const void *)) { |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
415 |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
416 if (nmemb<=1) return; |
1456
84de7511f79f
Fixed a bunch of 64-bit compatibility problems
Sam Lantinga <slouken@libsdl.org>
parents:
1402
diff
changeset
|
417 if (((uintptr_t)base|size)&(WORD_BYTES-1)) |
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
418 qsort_nonaligned(base,nmemb,size,compare); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
419 else if (size!=WORD_BYTES) |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
420 qsort_aligned(base,nmemb,size,compare); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
421 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
|
422 qsort_words(base,nmemb,compare); |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
423 } |
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset
|
424 |
1331
1cbaeee565b1
A few fixes to get this building on Linux again
Sam Lantinga <slouken@libsdl.org>
parents:
1330
diff
changeset
|
425 #endif /* !HAVE_QSORT */ |