SDL_qsort.c: sync comments with version 1.15 from mainstream
authorOzkan Sezer <sezeroz@gmail.com>
Thu, 31 Oct 2019 17:10:02 +0300
changeset 132250e512800c68c
parent 13211 59fa401ab8c5
child 13226 294f9fc96e56
SDL_qsort.c: sync comments with version 1.15 from mainstream
src/stdlib/SDL_qsort.c
     1.1 --- a/src/stdlib/SDL_qsort.c	Wed Oct 30 21:12:36 2019 +0100
     1.2 +++ b/src/stdlib/SDL_qsort.c	Thu Oct 31 17:10:02 2019 +0300
     1.3 @@ -64,7 +64,7 @@
     1.4  
     1.5  /*
     1.6  This code came from Gareth McCaughan, under the zlib license.
     1.7 -Specifically this: https://www.mccaughan.org.uk/software/qsort.c-1.14
     1.8 +Specifically this: https://www.mccaughan.org.uk/software/qsort.c-1.15
     1.9  
    1.10  Everything below this comment until the HAVE_QSORT #endif was from Gareth
    1.11  (any minor changes will be noted inline).
    1.12 @@ -143,6 +143,10 @@
    1.13   *   2016-02-21 v1.14 Replace licence with 2-clause BSD,
    1.14   *                    and clarify a couple of things in
    1.15   *                    comments. No code changes.
    1.16 + *   2016-03-10 v1.15 Fix bug kindly reported by Ryan Gordon
    1.17 + *                    (pre-insertion-sort messed up).
    1.18 + *                    Disable DEBUG_QSORT by default.
    1.19 + *                    Tweak comments very slightly.
    1.20   */
    1.21  
    1.22  /* BEGIN SDL CHANGE ... commented this out with an #if 0 block. --ryan. */
    1.23 @@ -151,9 +155,9 @@
    1.24  #include <stdlib.h>
    1.25  #include <string.h>
    1.26  
    1.27 -#define DEBUG_QSORT
    1.28 +#undef DEBUG_QSORT
    1.29  
    1.30 -static char _ID[]="<qsort.c gjm 1.14 2016-02-21>";
    1.31 +static char _ID[]="<qsort.c gjm 1.15 2016-03-10>";
    1.32  #endif
    1.33  /* END SDL CHANGE ... commented this out with an #if 0 block. --ryan. */
    1.34  
    1.35 @@ -316,7 +320,9 @@
    1.36   * We find the smallest element from the first |nmemb|,
    1.37   * or the first |limit|, whichever is smaller;
    1.38   * therefore we must have ensured that the globally smallest
    1.39 - * element is in the first |limit|.
    1.40 + * element is in the first |limit| (because our
    1.41 + * quicksort recursion bottoms out only once we
    1.42 + * reach subarrays smaller than |limit|).
    1.43   */
    1.44  #define PreInsertion(swapper,limit,sz)		\
    1.45    first=base;					\
    1.46 @@ -499,7 +505,7 @@
    1.47        Recurse(TRUNC_words)
    1.48      }
    1.49    }
    1.50 -  PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES);
    1.51 +  PreInsertion(SWAP_words,TRUNC_words/WORD_BYTES,WORD_BYTES);
    1.52    /* Now do insertion sort. */
    1.53    last=((char*)base)+nmemb*WORD_BYTES;
    1.54    for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) {
    1.55 @@ -527,7 +533,6 @@
    1.56      qsort_words(base,nmemb,compare);
    1.57  }
    1.58  
    1.59 -
    1.60  #endif /* HAVE_QSORT */
    1.61  
    1.62  /* vi: set ts=4 sw=4 expandtab: */