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: */