Mercurial > sdl-ios-xcode
annotate src/stdlib/SDL_qsort.c @ 1982:3b4ce57c6215
First shot at new audio data types (int32 and float32).
Notable changes:
- Converters between types are autogenerated. Instead of making multiple
passes over the data with seperate filters for endianess, size, signedness,
etc, converting between data types is always one specialized filter. This
simplifies SDL_BuildAudioCVT(), which otherwise had a million edge cases
with the new types, and makes the actually conversions more CPU cache
friendly. Left a stub for adding specific optimized versions of these
routines (SSE/MMX/Altivec, assembler, etc)
- Autogenerated converters are built by SDL/src/audio/sdlgenaudiocvt.pl. This
does not need to be run unless tweaking the code, and thus doesn't need
integration into the build system.
- Went through all the drivers and tried to weed out all the "Uint16"
references that are better specified with the new SDL_AudioFormat typedef.
- Cleaned out a bunch of hardcoded bitwise magic numbers and replaced them
with new SDL_AUDIO_* macros.
- Added initial float32 and int32 support code. Theoretically, existing
drivers will push these through converters to get the data they want to
feed to the hardware.
Still TODO:
- Optimize and debug new converters.
- Update the CoreAudio backend to accept float32 data directly.
- Other backends, too?
- SDL_LoadWAV() needs to be updated to support int32 and float32 .wav files
(both of which exist and can be generated by 'sox' for testing purposes).
- Update the mixer to handle new datatypes.
- Optionally update SDL_sound and SDL_mixer, etc.
author | Ryan C. Gordon <icculus@icculus.org> |
---|---|
date | Thu, 24 Aug 2006 12:10:46 +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 12*WORD_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)+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
|
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: */ |