diff options
author | 2016-11-16 16:26:13 +0100 | |
---|---|---|
committer | 2016-11-16 16:28:01 +0100 | |
commit | 47a05778bff9388fc6c479461dd3804c79d7b539 (patch) | |
tree | bb3d4dc8df676b8aa478339b3fd0cd305dc4ac4d /3rdparty/SDL2/src/stdlib/SDL_qsort.c | |
parent | e61b392edfbfe5b9d70908c087632da915a3abd8 (diff) |
Updated SDL2 to 2.0.5 (nw)
Diffstat (limited to '3rdparty/SDL2/src/stdlib/SDL_qsort.c')
-rw-r--r-- | 3rdparty/SDL2/src/stdlib/SDL_qsort.c | 493 |
1 files changed, 273 insertions, 220 deletions
diff --git a/3rdparty/SDL2/src/stdlib/SDL_qsort.c b/3rdparty/SDL2/src/stdlib/SDL_qsort.c index 0d1978424dd..2ef33b15ea1 100644 --- a/3rdparty/SDL2/src/stdlib/SDL_qsort.c +++ b/3rdparty/SDL2/src/stdlib/SDL_qsort.c @@ -1,46 +1,23 @@ -/* qsort.c - * (c) 1998 Gareth McCaughan - * - * This is a drop-in replacement for the C library's |qsort()| routine. - * - * Features: - * - Median-of-three pivoting (and more) - * - Truncation and final polishing by a single insertion sort - * - Early truncation when no swaps needed in pivoting step - * - Explicit recursion, guaranteed not to overflow - * - A few little wrinkles stolen from the GNU |qsort()|. - * - separate code for non-aligned / aligned / word-size objects - * - * This code may be reproduced freely provided - * - this file is retained unaltered apart from minor - * changes for portability and efficiency - * - no changes are made to this comment - * - any changes that *are* made are clearly flagged - * - the _ID string below is altered by inserting, after - * the date, the string " altered" followed at your option - * by other material. (Exceptions: you may change the name - * of the exported routine without changing the ID string. - * You may change the values of the macros TRUNC_* and - * PIVOT_THRESHOLD without changing the ID string, provided - * they remain constants with TRUNC_nonaligned, TRUNC_aligned - * and TRUNC_words/WORD_BYTES between 8 and 24, and - * PIVOT_THRESHOLD between 32 and 200.) - * - * You may use it in anything you like; you may make money - * out of it; you may distribute it in object form or as - * part of an executable without including source code; - * you don't have to credit me. (But it would be nice if - * you did.) - * - * If you find problems with this code, or find ways of - * making it significantly faster, please let me know! - * My e-mail address, valid as of early 1998 and certainly - * OK for at least the next 18 months, is - * gjm11@dpmms.cam.ac.uk - * Thanks! - * - * Gareth McCaughan Peterhouse Cambridge 1998 - */ +/* + Simple DirectMedia Layer + Copyright (C) 1997-2016 Sam Lantinga <slouken@libsdl.org> + + This software is provided 'as-is', without any express or implied + warranty. In no event will the authors be held liable for any damages + arising from the use of this software. + + Permission is granted to anyone to use this software for any purpose, + including commercial applications, and to alter it and redistribute it + freely, subject to the following restrictions: + + 1. The origin of this software must not be misrepresented; you must not + claim that you wrote the original software. If you use this software + in a product, an acknowledgment in the product documentation would be + appreciated but is not required. + 2. Altered source versions must be plainly marked as such, and must not be + misrepresented as being the original software. + 3. This notice may not be removed or altered from any source distribution. +*/ #if defined(__clang_analyzer__) && !defined(SDL_DISABLE_ANALYZE_MACROS) #define SDL_DISABLE_ANALYZE_MACROS 1 @@ -48,11 +25,6 @@ #include "../SDL_internal.h" -/* -#include <assert.h> -#include <stdlib.h> -#include <string.h> -*/ #include "SDL_stdinc.h" #include "SDL_assert.h" @@ -62,34 +34,128 @@ SDL_qsort(void *base, size_t nmemb, size_t size, int (*compare) (const void *, c { qsort(base, nmemb, size, compare); } + #else #ifdef assert #undef assert #endif -#define assert(X) SDL_assert(X) +#define assert SDL_assert #ifdef malloc #undef malloc #endif -#define malloc SDL_malloc +#define malloc SDL_malloc #ifdef free #undef free #endif -#define free SDL_free +#define free SDL_free #ifdef memcpy #undef memcpy #endif -#define memcpy SDL_memcpy +#define memcpy SDL_memcpy #ifdef memmove #undef memmove #endif -#define memmove SDL_memmove -#ifdef qsort -#undef qsort +#define memmove SDL_memmove +#ifdef qsortG +#undef qsortG #endif -#define qsort SDL_qsort +#define qsortG SDL_qsort + +/* +This code came from Gareth McCaughan, under the zlib license. +Specifically this: https://www.mccaughan.org.uk/software/qsort.c-1.14 + +Everything below this comment until the HAVE_QSORT #endif was from Gareth +(any minor changes will be noted inline). + +Thank you to Gareth for relicensing this code under the zlib license for our +benefit! + +--ryan. +*/ + +/* This is a drop-in replacement for the C library's |qsort()| routine. + * + * It is intended for use where you know or suspect that your + * platform's qsort is bad. If that isn't the case, then you + * should probably use the qsort your system gives you in preference + * to mine -- it will likely have been tested and tuned better. + * + * Features: + * - Median-of-three pivoting (and more) + * - Truncation and final polishing by a single insertion sort + * - Early truncation when no swaps needed in pivoting step + * - Explicit recursion, guaranteed not to overflow + * - A few little wrinkles stolen from the GNU |qsort()|. + * (For the avoidance of doubt, no code was stolen, only + * broad ideas.) + * - separate code for non-aligned / aligned / word-size objects + * + * Earlier releases of this code used an idiosyncratic licence + * I wrote myself, because I'm an idiot. The code is now released + * under the "zlib/libpng licence"; you will find the actual + * terms in the next comment. I request (but do not require) + * that if you make any changes beyond the name of the exported + * routine and reasonable tweaks to the TRUNC_* and + * PIVOT_THRESHOLD values, you modify the _ID string so as + * to make it clear that you have changed the code. + * + * If you find problems with this code, or find ways of + * making it significantly faster, please let me know! + * My e-mail address, valid as of early 2016 and for the + * foreseeable future, is + * gareth.mccaughan@pobox.com + * Thanks! + * + * Gareth McCaughan + */ + +/* Copyright (c) 1998-2016 Gareth McCaughan + * + * This software is provided 'as-is', without any express or implied + * warranty. In no event will the authors be held liable for any + * damages arising from the use of this software. + * + * Permission is granted to anyone to use this software for any purpose, + * including commercial applications, and to alter it and redistribute it + * freely, subject to the following restrictions: + * + * 1. The origin of this software must not be misrepresented; + * you must not claim that you wrote the original software. + * If you use this software in a product, an acknowledgment + * in the product documentation would be appreciated but + * is not required. + * + * 2. Altered source versions must be plainly marked as such, + * and must not be misrepresented as being the original software. + * + * 3. This notice may not be removed or altered from any source + * distribution. + */ -static const char _ID[] = "<qsort.c gjm 1.12 1998-03-19>"; +/* Revision history since release: + * 1998-03-19 v1.12 First release I have any records of. + * 2007-09-02 v1.13 Fix bug kindly reported by Dan Bodoh + * (premature termination of recursion). + * Add a few clarifying comments. + * Minor improvements to debug output. + * 2016-02-21 v1.14 Replace licence with 2-clause BSD, + * and clarify a couple of things in + * comments. No code changes. + */ + +/* BEGIN SDL CHANGE ... commented this out with an #if 0 block. --ryan. */ +#if 0 +#include <assert.h> +#include <stdlib.h> +#include <string.h> + +#define DEBUG_QSORT + +static char _ID[]="<qsort.c gjm 1.14 2016-02-21>"; +#endif +/* END SDL CHANGE ... commented this out with an #if 0 block. --ryan. */ /* How many bytes are there per word? (Must be a power of 2, * and must in fact equal sizeof(int).) @@ -110,7 +176,7 @@ static const char _ID[] = "<qsort.c gjm 1.12 1998-03-19>"; */ #define TRUNC_nonaligned 12 #define TRUNC_aligned 12 -#define TRUNC_words 12*WORD_BYTES /* nb different meaning */ +#define TRUNC_words 12*WORD_BYTES /* nb different meaning */ /* We use a simple pivoting algorithm for shortish sub-arrays * and a more complicated one for larger ones. The threshold @@ -118,11 +184,7 @@ static const char _ID[] = "<qsort.c gjm 1.12 1998-03-19>"; */ #define PIVOT_THRESHOLD 40 -typedef struct -{ - char *first; - char *last; -} stack_entry; +typedef struct { char * first; char * last; } stack_entry; #define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;} #define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;} #define doLeft {first=ffirst;llast=last;continue;} @@ -197,7 +259,9 @@ typedef struct * 16-bit |int|s and 4096-bit |size_t|s. :-) */ -/* The recursion logic is the same in each case: */ +/* The recursion logic is the same in each case. + * We keep chopping up until we reach subarrays of size + * strictly less than Trunc; we leave these unsorted. */ #define Recurse(Trunc) \ { size_t l=last-ffirst,r=llast-first; \ if (l<Trunc) { \ @@ -209,9 +273,9 @@ typedef struct else doLeft \ } -/* and so is the pivoting logic: */ +/* and so is the pivoting logic (note: last is inclusive): */ #define Pivot(swapper,sz) \ - if ((size_t)(last-first)>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\ + if (last-first>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\ else { \ if (compare(first,mid)<0) { \ if (compare(mid,last)>0) { \ @@ -235,26 +299,28 @@ typedef struct /* and so is the partitioning logic: */ #define Partition(swapper,sz) { \ - int swapped=0; \ do { \ while (compare(first,pivot)<0) first+=sz; \ while (compare(pivot,last)<0) last-=sz; \ if (first<last) { \ - swapper(first,last); swapped=1; \ + swapper(first,last); \ first+=sz; last-=sz; } \ else if (first==last) { first+=sz; last-=sz; break; }\ } while (first<=last); \ - if (!swapped) pop \ } /* and so is the pre-insertion-sort operation of putting * the smallest element into place as a sentinel. * Doing this makes the inner loop nicer. I got this * idea from the GNU implementation of qsort(). + * We find the smallest element from the first |nmemb|, + * or the first |limit|, whichever is smaller; + * therefore we must have ensured that the globally smallest + * element is in the first |limit|. */ #define PreInsertion(swapper,limit,sz) \ first=base; \ - last=first + (nmemb>limit ? limit : nmemb-1)*sz;\ + last=first + ((nmemb>limit ? limit : nmemb)-1)*sz;\ while (last!=base) { \ if (compare(first,last)>0) first=last; \ last-=sz; } \ @@ -294,188 +360,175 @@ typedef struct /* ---------------------------------------------------------------------- */ -static char * -pivot_big(char *first, char *mid, char *last, size_t size, - int compare(const void *, const void *)) -{ - size_t d = (((last - first) / size) >> 3) * size; - char *m1, *m2, *m3; - { - char *a = first, *b = first + d, *c = first + 2 * d; +static char * pivot_big(char *first, char *mid, char *last, size_t size, + int compare(const void *, const void *)) { + int d=(((last-first)/size)>>3)*size; #ifdef DEBUG_QSORT - fprintf(stderr, "< %d %d %d\n", *(int *) a, *(int *) b, *(int *) c); +fprintf(stderr, "pivot_big: first=%p last=%p size=%lu n=%lu\n", first, (unsigned long)last, size, (unsigned long)((last-first+1)/size)); #endif - m1 = compare(a, b) < 0 ? - (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a)) - : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b)); - } - { - char *a = mid - d, *b = mid, *c = mid + d; + char *m1,*m2,*m3; + { char *a=first, *b=first+d, *c=first+2*d; #ifdef DEBUG_QSORT - fprintf(stderr, ". %d %d %d\n", *(int *) a, *(int *) b, *(int *) c); +fprintf(stderr,"< %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c); #endif - m2 = compare(a, b) < 0 ? - (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a)) - : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b)); - } - { - char *a = last - 2 * d, *b = last - d, *c = last; + m1 = compare(a,b)<0 ? + (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) + : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); + } + { char *a=mid-d, *b=mid, *c=mid+d; #ifdef DEBUG_QSORT - fprintf(stderr, "> %d %d %d\n", *(int *) a, *(int *) b, *(int *) c); +fprintf(stderr,". %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c); #endif - m3 = compare(a, b) < 0 ? - (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a)) - : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b)); - } + m2 = compare(a,b)<0 ? + (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) + : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); + } + { char *a=last-2*d, *b=last-d, *c=last; +#ifdef DEBUG_QSORT +fprintf(stderr,"> %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c); +#endif + m3 = compare(a,b)<0 ? + (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) + : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); + } #ifdef DEBUG_QSORT - fprintf(stderr, "-> %d %d %d\n", *(int *) m1, *(int *) m2, *(int *) m3); +fprintf(stderr,"-> %d %d %d @ %p %p %p\n",*(int*)m1,*(int*)m2,*(int*)m3, m1,m2,m3); #endif - return compare(m1, m2) < 0 ? - (compare(m2, m3) < 0 ? m2 : (compare(m1, m3) < 0 ? m3 : m1)) - : (compare(m1, m3) < 0 ? m1 : (compare(m2, m3) < 0 ? m3 : m2)); + return compare(m1,m2)<0 ? + (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1)) + : (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2)); } /* ---------------------------------------------------------------------- */ -static void -qsort_nonaligned(void *base, size_t nmemb, size_t size, - int (*compare) (const void *, const void *)) -{ - - stack_entry stack[STACK_SIZE]; - int stacktop = 0; - char *first, *last; - char *pivot = malloc(size); - size_t trunc = TRUNC_nonaligned * size; - assert(pivot != 0); - - first = (char *) base; - last = first + (nmemb - 1) * size; - - if ((size_t) (last - first) > trunc) { - char *ffirst = first, *llast = last; - while (1) { - /* Select pivot */ - { - char *mid = first + size * ((last - first) / size >> 1); - Pivot(SWAP_nonaligned, size); - memcpy(pivot, mid, size); - } - /* Partition. */ - Partition(SWAP_nonaligned, size); - /* Prepare to recurse/iterate. */ - Recurse(trunc)} +static void qsort_nonaligned(void *base, size_t nmemb, size_t size, + int (*compare)(const void *, const void *)) { + + stack_entry stack[STACK_SIZE]; + int stacktop=0; + char *first,*last; + char *pivot=malloc(size); + size_t trunc=TRUNC_nonaligned*size; + assert(pivot!=0); + + first=(char*)base; last=first+(nmemb-1)*size; + + if (last-first>=trunc) { + char *ffirst=first, *llast=last; + while (1) { + /* Select pivot */ + { char * mid=first+size*((last-first)/size >> 1); + Pivot(SWAP_nonaligned,size); + memcpy(pivot,mid,size); + } + /* Partition. */ + Partition(SWAP_nonaligned,size); + /* Prepare to recurse/iterate. */ + Recurse(trunc) } - PreInsertion(SWAP_nonaligned, TRUNC_nonaligned, size); - Insertion(SWAP_nonaligned); - free(pivot); + } + PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size); + Insertion(SWAP_nonaligned); + free(pivot); } -static void -qsort_aligned(void *base, size_t nmemb, size_t size, - int (*compare) (const void *, const void *)) -{ - - stack_entry stack[STACK_SIZE]; - int stacktop = 0; - char *first, *last; - char *pivot = malloc(size); - size_t trunc = TRUNC_aligned * size; - assert(pivot != 0); - - first = (char *) base; - last = first + (nmemb - 1) * size; - - if ((size_t) (last - first) > trunc) { - char *ffirst = first, *llast = last; - while (1) { - /* Select pivot */ - { - char *mid = first + size * ((last - first) / size >> 1); - Pivot(SWAP_aligned, size); - memcpy(pivot, mid, size); - } - /* Partition. */ - Partition(SWAP_aligned, size); - /* Prepare to recurse/iterate. */ - Recurse(trunc)} +static void qsort_aligned(void *base, size_t nmemb, size_t size, + int (*compare)(const void *, const void *)) { + + stack_entry stack[STACK_SIZE]; + int stacktop=0; + char *first,*last; + char *pivot=malloc(size); + size_t trunc=TRUNC_aligned*size; + assert(pivot!=0); + + first=(char*)base; last=first+(nmemb-1)*size; + + if (last-first>=trunc) { + char *ffirst=first,*llast=last; + while (1) { + /* Select pivot */ + { char * mid=first+size*((last-first)/size >> 1); + Pivot(SWAP_aligned,size); + memcpy(pivot,mid,size); + } + /* Partition. */ + Partition(SWAP_aligned,size); + /* Prepare to recurse/iterate. */ + Recurse(trunc) } - PreInsertion(SWAP_aligned, TRUNC_aligned, size); - Insertion(SWAP_aligned); - free(pivot); + } + PreInsertion(SWAP_aligned,TRUNC_aligned,size); + Insertion(SWAP_aligned); + free(pivot); } -static void -qsort_words(void *base, size_t nmemb, - int (*compare) (const void *, const void *)) -{ +static void qsort_words(void *base, size_t nmemb, + int (*compare)(const void *, const void *)) { - stack_entry stack[STACK_SIZE]; - int stacktop = 0; - char *first, *last; - char *pivot = malloc(WORD_BYTES); - assert(pivot != 0); + stack_entry stack[STACK_SIZE]; + int stacktop=0; + char *first,*last; + char *pivot=malloc(WORD_BYTES); + assert(pivot!=0); - first = (char *) base; - last = first + (nmemb - 1) * WORD_BYTES; + first=(char*)base; last=first+(nmemb-1)*WORD_BYTES; - if (last - first > TRUNC_words) { - char *ffirst = first, *llast = last; - while (1) { + if (last-first>=TRUNC_words) { + char *ffirst=first, *llast=last; + while (1) { #ifdef DEBUG_QSORT - fprintf(stderr, "Doing %d:%d: ", - (first - (char *) base) / WORD_BYTES, - (last - (char *) base) / WORD_BYTES); +fprintf(stderr,"Doing %d:%d: ", + (first-(char*)base)/WORD_BYTES, + (last-(char*)base)/WORD_BYTES); #endif - /* Select pivot */ - { - char *mid = - first + WORD_BYTES * ((last - first) / (2 * WORD_BYTES)); - Pivot(SWAP_words, WORD_BYTES); - *(int *) pivot = *(int *) mid; - } + /* Select pivot */ + { char * mid=first+WORD_BYTES*((last-first) / (2*WORD_BYTES)); + Pivot(SWAP_words,WORD_BYTES); + *(int*)pivot=*(int*)mid; #ifdef DEBUG_QSORT - fprintf(stderr, "pivot=%d\n", *(int *) pivot); +fprintf(stderr,"pivot = %p = #%lu = %d\n", mid, (unsigned long)(((int*)mid)-((int*)base)), *(int*)mid); #endif - /* Partition. */ - Partition(SWAP_words, WORD_BYTES); - /* Prepare to recurse/iterate. */ - Recurse(TRUNC_words)} - } - PreInsertion(SWAP_words, (TRUNC_words / WORD_BYTES), WORD_BYTES); - /* Now do insertion sort. */ - last = ((char *) base) + nmemb * WORD_BYTES; - for (first = ((char *) base) + WORD_BYTES; first != last; - first += WORD_BYTES) { - /* Find the right place for |first|. My apologies for var reuse */ - int *pl = (int *) (first - WORD_BYTES), *pr = (int *) first; - *(int *) pivot = *(int *) first; - for (; compare(pl, pivot) > 0; pr = pl, --pl) { - *pr = *pl; - } - if (pr != (int *) first) - *pr = *(int *) pivot; + } + /* Partition. */ + Partition(SWAP_words,WORD_BYTES); +#ifdef DEBUG_QSORT +fprintf(stderr, "after partitioning first=#%lu last=#%lu\n", (first-(char*)base)/4lu, (last-(char*)base)/4lu); +#endif + /* Prepare to recurse/iterate. */ + Recurse(TRUNC_words) } - free(pivot); + } + PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES); + /* Now do insertion sort. */ + last=((char*)base)+nmemb*WORD_BYTES; + for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) { + /* Find the right place for |first|. My apologies for var reuse */ + int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first; + *(int*)pivot=*(int*)first; + for (;compare(pl,pivot)>0;pr=pl,--pl) { + *pr=*pl; } + if (pr!=(int*)first) *pr=*(int*)pivot; + } + free(pivot); } /* ---------------------------------------------------------------------- */ -void -qsort(void *base, size_t nmemb, size_t size, - int (*compare) (const void *, const void *)) -{ +extern void qsortG(void *base, size_t nmemb, size_t size, + int (*compare)(const void *, const void *)) { - if (nmemb <= 1) - return; - if (((uintptr_t) base | size) & (WORD_BYTES - 1)) - qsort_nonaligned(base, nmemb, size, compare); - else if (size != WORD_BYTES) - qsort_aligned(base, nmemb, size, compare); - else - qsort_words(base, nmemb, compare); + if (nmemb<=1) return; + if (((int)base|size)&(WORD_BYTES-1)) + qsort_nonaligned(base,nmemb,size,compare); + else if (size!=WORD_BYTES) + qsort_aligned(base,nmemb,size,compare); + else + qsort_words(base,nmemb,compare); } -#endif /* !SDL_qsort */ + +#endif /* HAVE_QSORT */ /* vi: set ts=4 sw=4 expandtab: */ + |