diff options
author | Ozkan Sezer <sezeroz@gmail.com> | 2019-10-31 17:10:02 +0300 |
---|---|---|
committer | Ozkan Sezer <sezeroz@gmail.com> | 2019-10-31 17:10:02 +0300 |
commit | 4a96006e0da3eb2a7112533cb8de85451abb707d (patch) | |
tree | 992438ef18e79983cd8502fefbf476c0e8de42f2 | |
parent | 7a18b5b6ca4f75f3e65191e227162e44a6258047 (diff) |
SDL_qsort.c: sync comments with version 1.15 from mainstream
-rw-r--r-- | src/stdlib/SDL_qsort.c | 17 |
1 files changed, 11 insertions, 6 deletions
diff --git a/src/stdlib/SDL_qsort.c b/src/stdlib/SDL_qsort.c index d03f64f33b..066d6689b8 100644 --- a/src/stdlib/SDL_qsort.c +++ b/src/stdlib/SDL_qsort.c @@ -64,7 +64,7 @@ SDL_qsort(void *base, size_t nmemb, size_t size, int (*compare) (const void *, c /* This code came from Gareth McCaughan, under the zlib license. -Specifically this: https://www.mccaughan.org.uk/software/qsort.c-1.14 +Specifically this: https://www.mccaughan.org.uk/software/qsort.c-1.15 Everything below this comment until the HAVE_QSORT #endif was from Gareth (any minor changes will be noted inline). @@ -143,6 +143,10 @@ benefit! * 2016-02-21 v1.14 Replace licence with 2-clause BSD, * and clarify a couple of things in * comments. No code changes. + * 2016-03-10 v1.15 Fix bug kindly reported by Ryan Gordon + * (pre-insertion-sort messed up). + * Disable DEBUG_QSORT by default. + * Tweak comments very slightly. */ /* BEGIN SDL CHANGE ... commented this out with an #if 0 block. --ryan. */ @@ -151,9 +155,9 @@ benefit! #include <stdlib.h> #include <string.h> -#define DEBUG_QSORT +#undef DEBUG_QSORT -static char _ID[]="<qsort.c gjm 1.14 2016-02-21>"; +static char _ID[]="<qsort.c gjm 1.15 2016-03-10>"; #endif /* END SDL CHANGE ... commented this out with an #if 0 block. --ryan. */ @@ -316,7 +320,9 @@ typedef struct { char * first; char * last; } stack_entry; * 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|. + * element is in the first |limit| (because our + * quicksort recursion bottoms out only once we + * reach subarrays smaller than |limit|). */ #define PreInsertion(swapper,limit,sz) \ first=base; \ @@ -499,7 +505,7 @@ fprintf(stderr, "after partitioning first=#%lu last=#%lu\n", (first-(char*)base) Recurse(TRUNC_words) } } - PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES); + 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) { @@ -527,7 +533,6 @@ extern void qsortG(void *base, size_t nmemb, size_t size, qsort_words(base,nmemb,compare); } - #endif /* HAVE_QSORT */ /* vi: set ts=4 sw=4 expandtab: */ |