Mercurial > sdl-ios-xcode

annotate src/stdlib/SDL_qsort.c @ 1389:ce65f014190a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fixed X11 library detection Allow passing CFLAGS for the build in the environment
author Sam Lantinga <slouken@libsdl.org>
date Mon, 20 Feb 2006 11:30:29 +0000
parents 22f39393668a
children d910939febfa
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 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
44
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 #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
47 #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
48 #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
49 */
1354
22f39393668a Fixed build problem with SDL_string.c
Sam Lantinga <slouken@libsdl.org>
parents: 1337
diff changeset
50 #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
51
1337
c687f06c7473 Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents: 1336
diff changeset
52 #define assert(X)
c687f06c7473 Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents: 1336
diff changeset
53 #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
54 #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
55 #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
56 #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
57 #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
58
c687f06c7473 Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents: 1336
diff changeset
59
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
60 #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
61
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 static char _ID[]="<qsort.c gjm 1.12 1998-03-19>";
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
63
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 /* 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
65 * 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
66 */
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 #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
68
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 /* 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
70 * 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
71 */
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 #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
73
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 /* 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
75 * 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
76 * 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
77 * 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
78 * 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
79 * 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
80 */
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 #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
82 #define TRUNC_aligned 12
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
83 #define TRUNC_words 12*WORD_BYTES /* nb different meaning */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
84
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 /* 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
86 * 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
87 * 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
88 */
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 #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
90
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
91 typedef struct { char * first; char * last; } stack_entry;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
92 #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
93 #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
94 #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
95 #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
96 #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
97 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
98 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
99 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
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 /* 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
102 * 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
103 * 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
104 * 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
105 * 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
106 * 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
107 * 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
108 * 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
109 * 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
110 * 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
111 * 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
112 * 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
113 * 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
114 * 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
115 * 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
116 * 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
117 * 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
118 * 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
119 * 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
120 * 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
121 * 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
122 * 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
123 * 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
124 * 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
125 * 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
126 * 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
127 * 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
128 * 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
129 * 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
130 * 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
131 * 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
132 * 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
133 * 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
134 * 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
135 * 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
136 * 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
137 * 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
138 * 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
139 * 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
140 * 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
141 * 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
142 * 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
143 * 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
144 * - 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
145 * 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
146 * 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
147 * 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
148 * 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
149 * 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
150 * 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
151 * - 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
152 * 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
153 * 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
154 * - 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
155 * 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
156 * 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
157 * 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
158 * 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
159 * 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
160 * 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
161 * - 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
162 * 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
163 * 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
164 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
165
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
166 /* 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
167 #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
168 { 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
169 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
170 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
171 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
172 } \
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 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
174 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
175 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
176 }
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 /* 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
179 #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
180 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
181 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
182 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
183 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
184 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
185 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
186 } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
187 } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
188 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
189 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
190 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
191 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
192 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
193 } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
194 } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
195 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
196 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
197
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
198 #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
199 #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
200 #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
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 /* 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
203 #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
204 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
205 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
206 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
207 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
208 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
209 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
210 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
211 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
212 } 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
213 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
214 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
215
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
216 /* 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
217 * 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
218 * 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
219 * 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
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 #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
222 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
223 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
224 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
225 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
226 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
227 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
228
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 /* 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
230 #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
231 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
232 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
233 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
234 /* 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
235 * 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
236 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
237 test+=size; \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
238 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
239 /* 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
240 * 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
241 * 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
242 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
243 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
244 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
245 } \
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
246 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
247
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
248 #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
249 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
250 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
251 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
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_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
254 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
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 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
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_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
259 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
260
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
261 /* ---------------------------------------------------------------------- */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
262
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
263 static char * pivot_big(char *first, char *mid, char *last, size_t size,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
264 int compare(const void *, const void *)) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
265 int d=(((last-first)/size)>>3)*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
266 char *m1,*m2,*m3;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
267 { char *a=first, *b=first+d, *c=first+2*d;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
268 #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
269 fprintf(stderr,"< %d %d %d\n",*(int*)a,*(int*)b,*(int*)c);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
270 #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
271 m1 = compare(a,b)<0 ?
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
272 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
273 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
274 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
275 { char *a=mid-d, *b=mid, *c=mid+d;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
276 #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
277 fprintf(stderr,". %d %d %d\n",*(int*)a,*(int*)b,*(int*)c);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
278 #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
279 m2 = compare(a,b)<0 ?
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
280 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
281 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
282 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
283 { char *a=last-2*d, *b=last-d, *c=last;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
284 #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
285 fprintf(stderr,"> %d %d %d\n",*(int*)a,*(int*)b,*(int*)c);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
286 #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
287 m3 = compare(a,b)<0 ?
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
288 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
289 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
290 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
291 #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
292 fprintf(stderr,"-> %d %d %d\n",*(int*)m1,*(int*)m2,*(int*)m3);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
293 #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
294 return compare(m1,m2)<0 ?
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
295 (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1))
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
296 : (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2));
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
297 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
298
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
299 /* ---------------------------------------------------------------------- */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
300
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
301 static void qsort_nonaligned(void *base, size_t nmemb, size_t size,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
302 int (*compare)(const void *, const void *)) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
303
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
304 stack_entry stack[STACK_SIZE];
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
305 int stacktop=0;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
306 char *first,*last;
1337
c687f06c7473 Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents: 1336
diff changeset
307 char *pivot=malloc(size);
1330
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
308 size_t trunc=TRUNC_nonaligned*size;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
309 assert(pivot!=0);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
310
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
311 first=(char*)base; last=first+(nmemb-1)*size;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
312
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
313 if ((size_t)(last-first)>trunc) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
314 char *ffirst=first, *llast=last;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
315 while (1) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
316 /* Select pivot */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
317 { char * mid=first+size*((last-first)/size >> 1);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
318 Pivot(SWAP_nonaligned,size);
1337
c687f06c7473 Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents: 1336
diff changeset
319 memcpy(pivot,mid,size);
1330
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
320 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
321 /* Partition. */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
322 Partition(SWAP_nonaligned,size);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
323 /* Prepare to recurse/iterate. */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
324 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
325 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
326 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
327 PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
328 Insertion(SWAP_nonaligned);
1337
c687f06c7473 Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents: 1336
diff changeset
329 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
330 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
331
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
332 static void qsort_aligned(void *base, size_t nmemb, size_t size,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
333 int (*compare)(const void *, const void *)) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
334
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
335 stack_entry stack[STACK_SIZE];
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
336 int stacktop=0;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
337 char *first,*last;
1337
c687f06c7473 Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents: 1336
diff changeset
338 char *pivot=malloc(size);
1330
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
339 size_t trunc=TRUNC_aligned*size;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
340 assert(pivot!=0);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
341
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
342 first=(char*)base; last=first+(nmemb-1)*size;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
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 if ((size_t)(last-first)>trunc) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
345 char *ffirst=first,*llast=last;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
346 while (1) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
347 /* Select pivot */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
348 { char * mid=first+size*((last-first)/size >> 1);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
349 Pivot(SWAP_aligned,size);
1337
c687f06c7473 Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents: 1336
diff changeset
350 memcpy(pivot,mid,size);
1330
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
351 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
352 /* Partition. */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
353 Partition(SWAP_aligned,size);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
354 /* Prepare to recurse/iterate. */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
355 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
356 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
357 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
358 PreInsertion(SWAP_aligned,TRUNC_aligned,size);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
359 Insertion(SWAP_aligned);
1337
c687f06c7473 Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents: 1336
diff changeset
360 free(pivot);
1330
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
361 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
362
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
363 static void qsort_words(void *base, size_t nmemb,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
364 int (*compare)(const void *, const void *)) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
365
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
366 stack_entry stack[STACK_SIZE];
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
367 int stacktop=0;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
368 char *first,*last;
1337
c687f06c7473 Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents: 1336
diff changeset
369 char *pivot=malloc(WORD_BYTES);
1330
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
370 assert(pivot!=0);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
371
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
372 first=(char*)base; last=first+(nmemb-1)*WORD_BYTES;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
373
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
374 if (last-first>TRUNC_words) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
375 char *ffirst=first, *llast=last;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
376 while (1) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
377 #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
378 fprintf(stderr,"Doing %d:%d: ",
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
379 (first-(char*)base)/WORD_BYTES,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
380 (last-(char*)base)/WORD_BYTES);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
381 #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
382 /* Select pivot */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
383 { char * mid=first+WORD_BYTES*((last-first) / (2*WORD_BYTES));
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
384 Pivot(SWAP_words,WORD_BYTES);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
385 *(int*)pivot=*(int*)mid;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
386 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
387 #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
388 fprintf(stderr,"pivot=%d\n",*(int*)pivot);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
389 #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
390 /* Partition. */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
391 Partition(SWAP_words,WORD_BYTES);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
392 /* Prepare to recurse/iterate. */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
393 Recurse(TRUNC_words)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
394 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
395 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
396 PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
397 /* Now do insertion sort. */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
398 last=((char*)base)+nmemb*WORD_BYTES;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
399 for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
400 /* Find the right place for |first|. My apologies for var reuse */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
401 int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
402 *(int*)pivot=*(int*)first;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
403 for (;compare(pl,pivot)>0;pr=pl,--pl) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
404 *pr=*pl; }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
405 if (pr!=(int*)first) *pr=*(int*)pivot;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
406 }
1337
c687f06c7473 Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents: 1336
diff changeset
407 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
408 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
409
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
410 /* ---------------------------------------------------------------------- */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
411
1337
c687f06c7473 Don't touch code that we brought in from other sources
Sam Lantinga <slouken@libsdl.org>
parents: 1336
diff changeset
412 void qsort(void *base, size_t nmemb, size_t size,
1330
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
413 int (*compare)(const void *, const void *)) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
414
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 if (nmemb<=1) return;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
416 if (((int)base|size)&(WORD_BYTES-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
417 qsort_nonaligned(base,nmemb,size,compare);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
418 else if (size!=WORD_BYTES)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
419 qsort_aligned(base,nmemb,size,compare);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
420 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
421 qsort_words(base,nmemb,compare);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
422 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
423
1331
1cbaeee565b1 A few fixes to get this building on Linux again
Sam Lantinga <slouken@libsdl.org>
parents: 1330
diff changeset
424 #endif /* !HAVE_QSORT */