2 Simple DirectMedia Layer
3 Copyright (C) 1997-2020 Sam Lantinga <slouken@libsdl.org>
5 This software is provided 'as-is', without any express or implied
6 warranty. In no event will the authors be held liable for any damages
7 arising from the use of this software.
9 Permission is granted to anyone to use this software for any purpose,
10 including commercial applications, and to alter it and redistribute it
11 freely, subject to the following restrictions:
13 1. The origin of this software must not be misrepresented; you must not
14 claim that you wrote the original software. If you use this software
15 in a product, an acknowledgment in the product documentation would be
16 appreciated but is not required.
17 2. Altered source versions must be plainly marked as such, and must not be
18 misrepresented as being the original software.
19 3. This notice may not be removed or altered from any source distribution.
22 #if defined(__clang_analyzer__) && !defined(SDL_DISABLE_ANALYZE_MACROS)
23 #define SDL_DISABLE_ANALYZE_MACROS 1
26 #include "../SDL_internal.h"
28 #include "SDL_stdinc.h"
30 #if defined(HAVE_QSORT)
32 SDL_qsort(void *base, size_t nmemb, size_t size, int (*compare) (const void *, const void *))
34 qsort(base, nmemb, size, compare);
42 #define assert SDL_assert
46 #define malloc SDL_malloc
54 #define memcpy SDL_memcpy
58 #define memmove SDL_memmove
62 #define qsortG SDL_qsort
65 This code came from Gareth McCaughan, under the zlib license.
66 Specifically this: https://www.mccaughan.org.uk/software/qsort.c-1.15
68 Everything below this comment until the HAVE_QSORT #endif was from Gareth
69 (any minor changes will be noted inline).
71 Thank you to Gareth for relicensing this code under the zlib license for our
77 /* This is a drop-in replacement for the C library's |qsort()| routine.
79 * It is intended for use where you know or suspect that your
80 * platform's qsort is bad. If that isn't the case, then you
81 * should probably use the qsort your system gives you in preference
82 * to mine -- it will likely have been tested and tuned better.
85 * - Median-of-three pivoting (and more)
86 * - Truncation and final polishing by a single insertion sort
87 * - Early truncation when no swaps needed in pivoting step
88 * - Explicit recursion, guaranteed not to overflow
89 * - A few little wrinkles stolen from the GNU |qsort()|.
90 * (For the avoidance of doubt, no code was stolen, only
92 * - separate code for non-aligned / aligned / word-size objects
94 * Earlier releases of this code used an idiosyncratic licence
95 * I wrote myself, because I'm an idiot. The code is now released
96 * under the "zlib/libpng licence"; you will find the actual
97 * terms in the next comment. I request (but do not require)
98 * that if you make any changes beyond the name of the exported
99 * routine and reasonable tweaks to the TRUNC_* and
100 * PIVOT_THRESHOLD values, you modify the _ID string so as
101 * to make it clear that you have changed the code.
103 * If you find problems with this code, or find ways of
104 * making it significantly faster, please let me know!
105 * My e-mail address, valid as of early 2016 and for the
106 * foreseeable future, is
107 * gareth.mccaughan@pobox.com
113 /* Copyright (c) 1998-2016 Gareth McCaughan
115 * This software is provided 'as-is', without any express or implied
116 * warranty. In no event will the authors be held liable for any
117 * damages arising from the use of this software.
119 * Permission is granted to anyone to use this software for any purpose,
120 * including commercial applications, and to alter it and redistribute it
121 * freely, subject to the following restrictions:
123 * 1. The origin of this software must not be misrepresented;
124 * you must not claim that you wrote the original software.
125 * If you use this software in a product, an acknowledgment
126 * in the product documentation would be appreciated but
129 * 2. Altered source versions must be plainly marked as such,
130 * and must not be misrepresented as being the original software.
132 * 3. This notice may not be removed or altered from any source
136 /* Revision history since release:
137 * 1998-03-19 v1.12 First release I have any records of.
138 * 2007-09-02 v1.13 Fix bug kindly reported by Dan Bodoh
139 * (premature termination of recursion).
140 * Add a few clarifying comments.
141 * Minor improvements to debug output.
142 * 2016-02-21 v1.14 Replace licence with 2-clause BSD,
143 * and clarify a couple of things in
144 * comments. No code changes.
145 * 2016-03-10 v1.15 Fix bug kindly reported by Ryan Gordon
146 * (pre-insertion-sort messed up).
147 * Disable DEBUG_QSORT by default.
148 * Tweak comments very slightly.
151 /* BEGIN SDL CHANGE ... commented this out with an #if 0 block. --ryan. */
159 static char _ID[]="<qsort.c gjm 1.15 2016-03-10>";
161 /* END SDL CHANGE ... commented this out with an #if 0 block. --ryan. */
163 /* How many bytes are there per word? (Must be a power of 2,
164 * and must in fact equal sizeof(int).)
166 #define WORD_BYTES sizeof(int)
168 /* How big does our stack need to be? Answer: one entry per
171 #define STACK_SIZE (8*sizeof(size_t))
173 /* Different situations have slightly different requirements,
174 * and we make life epsilon easier by using different truncation
175 * points for the three different cases.
176 * So far, I have tuned TRUNC_words and guessed that the same
177 * value might work well for the other two cases. Of course
178 * what works well on my machine might work badly on yours.
180 #define TRUNC_nonaligned 12
181 #define TRUNC_aligned 12
182 #define TRUNC_words 12*WORD_BYTES /* nb different meaning */
184 /* We use a simple pivoting algorithm for shortish sub-arrays
185 * and a more complicated one for larger ones. The threshold
186 * is PIVOT_THRESHOLD.
188 #define PIVOT_THRESHOLD 40
190 typedef struct { char * first; char * last; } stack_entry;
191 #define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;}
192 #define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;}
193 #define doLeft {first=ffirst;llast=last;continue;}
194 #define doRight {ffirst=first;last=llast;continue;}
195 #define pop {if (--stacktop<0) break;\
196 first=ffirst=stack[stacktop].first;\
197 last=llast=stack[stacktop].last;\
200 /* Some comments on the implementation.
201 * 1. When we finish partitioning the array into "low"
202 * and "high", we forget entirely about short subarrays,
203 * because they'll be done later by insertion sort.
204 * Doing lots of little insertion sorts might be a win
205 * on large datasets for locality-of-reference reasons,
206 * but it makes the code much nastier and increases
207 * bookkeeping overhead.
208 * 2. We always save the shorter and get to work on the
209 * longer. This guarantees that every time we push
210 * an item onto the stack its size is <= 1/2 of that
211 * of its parent; so the stack can't need more than
212 * log_2(max-array-size) entries.
213 * 3. We choose a pivot by looking at the first, last
214 * and middle elements. We arrange them into order
215 * because it's easy to do that in conjunction with
216 * choosing the pivot, and it makes things a little
217 * easier in the partitioning step. Anyway, the pivot
218 * is the middle of these three. It's still possible
219 * to construct datasets where the algorithm takes
220 * time of order n^2, but it simply never happens in
222 * 3' Newsflash: On further investigation I find that
223 * it's easy to construct datasets where median-of-3
224 * simply isn't good enough. So on large-ish subarrays
225 * we do a more sophisticated pivoting: we take three
226 * sets of 3 elements, find their medians, and then
227 * take the median of those.
228 * 4. We copy the pivot element to a separate place
229 * because that way we can always do our comparisons
230 * directly against a pointer to that separate place,
231 * and don't have to wonder "did we move the pivot
232 * element?". This makes the inner loop better.
233 * 5. It's possible to make the pivoting even more
234 * reliable by looking at more candidates when n
235 * is larger. (Taking this to its logical conclusion
236 * results in a variant of quicksort that doesn't
237 * have that n^2 worst case.) However, the overhead
238 * from the extra bookkeeping means that it's just
240 * 6. This is pretty clean and portable code. Here are
241 * all the potential portability pitfalls and problems
243 * - In one place (the insertion sort) I construct
244 * a pointer that points just past the end of the
245 * supplied array, and assume that (a) it won't
246 * compare equal to any pointer within the array,
247 * and (b) it will compare equal to a pointer
248 * obtained by stepping off the end of the array.
249 * These might fail on some segmented architectures.
250 * - I assume that there are 8 bits in a |char| when
251 * computing the size of stack needed. This would
252 * fail on machines with 9-bit or 16-bit bytes.
253 * - I assume that if |((int)base&(sizeof(int)-1))==0|
254 * and |(size&(sizeof(int)-1))==0| then it's safe to
255 * get at array elements via |int*|s, and that if
256 * actually |size==sizeof(int)| as well then it's
257 * safe to treat the elements as |int|s. This might
258 * fail on systems that convert pointers to integers
259 * in non-standard ways.
260 * - I assume that |8*sizeof(size_t)<=INT_MAX|. This
261 * would be false on a machine with 8-bit |char|s,
262 * 16-bit |int|s and 4096-bit |size_t|s. :-)
265 /* The recursion logic is the same in each case.
266 * We keep chopping up until we reach subarrays of size
267 * strictly less than Trunc; we leave these unsorted. */
268 #define Recurse(Trunc) \
269 { size_t l=last-ffirst,r=llast-first; \
271 if (r>=Trunc) doRight \
274 else if (l<=r) { pushLeft; doRight } \
275 else if (r>=Trunc) { pushRight; doLeft }\
279 /* and so is the pivoting logic (note: last is inclusive): */
280 #define Pivot(swapper,sz) \
281 if ((size_t)(last-first)>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\
283 if (compare(first,mid)<0) { \
284 if (compare(mid,last)>0) { \
286 if (compare(first,mid)>0) swapper(first,mid);\
290 if (compare(mid,last)>0) swapper(first,last)\
292 swapper(first,mid); \
293 if (compare(mid,last)>0) swapper(mid,last);\
296 first+=sz; last-=sz; \
303 /* and so is the partitioning logic: */
304 #define Partition(swapper,sz) { \
306 while (compare(first,pivot)<0) first+=sz; \
307 while (compare(pivot,last)<0) last-=sz; \
309 swapper(first,last); \
310 first+=sz; last-=sz; } \
311 else if (first==last) { first+=sz; last-=sz; break; }\
312 } while (first<=last); \
315 /* and so is the pre-insertion-sort operation of putting
316 * the smallest element into place as a sentinel.
317 * Doing this makes the inner loop nicer. I got this
318 * idea from the GNU implementation of qsort().
319 * We find the smallest element from the first |nmemb|,
320 * or the first |limit|, whichever is smaller;
321 * therefore we must have ensured that the globally smallest
322 * element is in the first |limit| (because our
323 * quicksort recursion bottoms out only once we
324 * reach subarrays smaller than |limit|).
326 #define PreInsertion(swapper,limit,sz) \
328 last=first + ((nmemb>limit ? limit : nmemb)-1)*sz;\
329 while (last!=base) { \
330 if (compare(first,last)>0) first=last; \
332 if (first!=base) swapper(first,(char*)base);
334 /* and so is the insertion sort, in the first two cases: */
335 #define Insertion(swapper) \
336 last=((char*)base)+nmemb*size; \
337 for (first=((char*)base)+size;first!=last;first+=size) { \
339 /* Find the right place for |first|. \
340 * My apologies for var reuse. */ \
341 for (test=first-size;compare(test,first)>0;test-=size) ; \
344 /* Shift everything in [test,first) \
345 * up by one, and place |first| \
346 * where |test| is. */ \
347 memcpy(pivot,first,size); \
348 memmove(test+size,test,first-test); \
349 memcpy(test,pivot,size); \
353 #define SWAP_nonaligned(a,b) { \
354 register char *aa=(a),*bb=(b); \
355 register size_t sz=size; \
356 do { register char t=*aa; *aa++=*bb; *bb++=t; } while (--sz); }
358 #define SWAP_aligned(a,b) { \
359 register int *aa=(int*)(a),*bb=(int*)(b); \
360 register size_t sz=size; \
361 do { register int t=*aa;*aa++=*bb; *bb++=t; } while (sz-=WORD_BYTES); }
363 #define SWAP_words(a,b) { \
364 register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; }
366 /* ---------------------------------------------------------------------- */
368 static char * pivot_big(char *first, char *mid, char *last, size_t size,
369 int compare(const void *, const void *)) {
370 size_t d=(((last-first)/size)>>3)*size;
372 fprintf(stderr, "pivot_big: first=%p last=%p size=%lu n=%lu\n", first, (unsigned long)last, size, (unsigned long)((last-first+1)/size));
375 { char *a=first, *b=first+d, *c=first+2*d;
377 fprintf(stderr,"< %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
379 m1 = compare(a,b)<0 ?
380 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
381 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
383 { char *a=mid-d, *b=mid, *c=mid+d;
385 fprintf(stderr,". %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
387 m2 = compare(a,b)<0 ?
388 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
389 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
391 { char *a=last-2*d, *b=last-d, *c=last;
393 fprintf(stderr,"> %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
395 m3 = compare(a,b)<0 ?
396 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
397 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
400 fprintf(stderr,"-> %d %d %d @ %p %p %p\n",*(int*)m1,*(int*)m2,*(int*)m3, m1,m2,m3);
402 return compare(m1,m2)<0 ?
403 (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1))
404 : (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2));
407 /* ---------------------------------------------------------------------- */
409 static void qsort_nonaligned(void *base, size_t nmemb, size_t size,
410 int (*compare)(const void *, const void *)) {
412 stack_entry stack[STACK_SIZE];
415 char *pivot=malloc(size);
416 size_t trunc=TRUNC_nonaligned*size;
419 first=(char*)base; last=first+(nmemb-1)*size;
421 if ((size_t)(last-first)>=trunc) {
422 char *ffirst=first, *llast=last;
425 { char * mid=first+size*((last-first)/size >> 1);
426 Pivot(SWAP_nonaligned,size);
427 memcpy(pivot,mid,size);
430 Partition(SWAP_nonaligned,size);
431 /* Prepare to recurse/iterate. */
435 PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size);
436 Insertion(SWAP_nonaligned);
440 static void qsort_aligned(void *base, size_t nmemb, size_t size,
441 int (*compare)(const void *, const void *)) {
443 stack_entry stack[STACK_SIZE];
446 char *pivot=malloc(size);
447 size_t trunc=TRUNC_aligned*size;
450 first=(char*)base; last=first+(nmemb-1)*size;
452 if ((size_t)(last-first)>=trunc) {
453 char *ffirst=first,*llast=last;
456 { char * mid=first+size*((last-first)/size >> 1);
457 Pivot(SWAP_aligned,size);
458 memcpy(pivot,mid,size);
461 Partition(SWAP_aligned,size);
462 /* Prepare to recurse/iterate. */
466 PreInsertion(SWAP_aligned,TRUNC_aligned,size);
467 Insertion(SWAP_aligned);
471 static void qsort_words(void *base, size_t nmemb,
472 int (*compare)(const void *, const void *)) {
474 stack_entry stack[STACK_SIZE];
477 char *pivot=malloc(WORD_BYTES);
480 first=(char*)base; last=first+(nmemb-1)*WORD_BYTES;
482 if (last-first>=TRUNC_words) {
483 char *ffirst=first, *llast=last;
486 fprintf(stderr,"Doing %d:%d: ",
487 (first-(char*)base)/WORD_BYTES,
488 (last-(char*)base)/WORD_BYTES);
491 { char * mid=first+WORD_BYTES*((last-first) / (2*WORD_BYTES));
492 Pivot(SWAP_words,WORD_BYTES);
493 *(int*)pivot=*(int*)mid;
495 fprintf(stderr,"pivot = %p = #%lu = %d\n", mid, (unsigned long)(((int*)mid)-((int*)base)), *(int*)mid);
499 Partition(SWAP_words,WORD_BYTES);
501 fprintf(stderr, "after partitioning first=#%lu last=#%lu\n", (first-(char*)base)/4lu, (last-(char*)base)/4lu);
503 /* Prepare to recurse/iterate. */
507 PreInsertion(SWAP_words,TRUNC_words/WORD_BYTES,WORD_BYTES);
508 /* Now do insertion sort. */
509 last=((char*)base)+nmemb*WORD_BYTES;
510 for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) {
511 /* Find the right place for |first|. My apologies for var reuse */
512 int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first;
513 *(int*)pivot=*(int*)first;
514 for (;compare(pl,pivot)>0;pr=pl,--pl) {
516 if (pr!=(int*)first) *pr=*(int*)pivot;
521 /* ---------------------------------------------------------------------- */
523 extern void qsortG(void *base, size_t nmemb, size_t size,
524 int (*compare)(const void *, const void *)) {
526 if (nmemb<=1) return;
527 if (((size_t)base|size)&(WORD_BYTES-1))
528 qsort_nonaligned(base,nmemb,size,compare);
529 else if (size!=WORD_BYTES)
530 qsort_aligned(base,nmemb,size,compare);
532 qsort_words(base,nmemb,compare);
535 #endif /* HAVE_QSORT */
537 /* vi: set ts=4 sw=4 expandtab: */