src/stdlib/SDL_qsort.c
branchSDL-1.2
changeset 10086 2e3396e62aa6
parent 4186 5bacec0933f5
child 10118 2f1eb5fa26ea
     1.1 --- a/src/stdlib/SDL_qsort.c	Sun Nov 01 08:41:08 2015 +0100
     1.2 +++ b/src/stdlib/SDL_qsort.c	Sun Feb 21 13:19:33 2016 -0500
     1.3 @@ -1,54 +1,25 @@
     1.4 -/* qsort.c
     1.5 - * (c) 1998 Gareth McCaughan
     1.6 - *
     1.7 - * This is a drop-in replacement for the C library's |qsort()| routine.
     1.8 - *
     1.9 - * Features:
    1.10 - *   - Median-of-three pivoting (and more)
    1.11 - *   - Truncation and final polishing by a single insertion sort
    1.12 - *   - Early truncation when no swaps needed in pivoting step
    1.13 - *   - Explicit recursion, guaranteed not to overflow
    1.14 - *   - A few little wrinkles stolen from the GNU |qsort()|.
    1.15 - *   - separate code for non-aligned / aligned / word-size objects
    1.16 - *
    1.17 - * This code may be reproduced freely provided
    1.18 - *   - this file is retained unaltered apart from minor
    1.19 - *     changes for portability and efficiency
    1.20 - *   - no changes are made to this comment
    1.21 - *   - any changes that *are* made are clearly flagged
    1.22 - *   - the _ID string below is altered by inserting, after
    1.23 - *     the date, the string " altered" followed at your option
    1.24 - *     by other material. (Exceptions: you may change the name
    1.25 - *     of the exported routine without changing the ID string.
    1.26 - *     You may change the values of the macros TRUNC_* and
    1.27 - *     PIVOT_THRESHOLD without changing the ID string, provided
    1.28 - *     they remain constants with TRUNC_nonaligned, TRUNC_aligned
    1.29 - *     and TRUNC_words/WORD_BYTES between 8 and 24, and
    1.30 - *     PIVOT_THRESHOLD between 32 and 200.)
    1.31 - *
    1.32 - * You may use it in anything you like; you may make money
    1.33 - * out of it; you may distribute it in object form or as
    1.34 - * part of an executable without including source code;
    1.35 - * you don't have to credit me. (But it would be nice if
    1.36 - * you did.)
    1.37 - *
    1.38 - * If you find problems with this code, or find ways of
    1.39 - * making it significantly faster, please let me know!
    1.40 - * My e-mail address, valid as of early 1998 and certainly
    1.41 - * OK for at least the next 18 months, is
    1.42 - *    gjm11@dpmms.cam.ac.uk
    1.43 - * Thanks!
    1.44 - *
    1.45 - * Gareth McCaughan   Peterhouse   Cambridge   1998
    1.46 - */
    1.47 -#include "SDL_config.h"
    1.48 +/*
    1.49 +  Simple DirectMedia Layer
    1.50 +  Copyright (C) 1997-2016 Sam Lantinga <slouken@libsdl.org>
    1.51  
    1.52 -/*
    1.53 -#include <assert.h>
    1.54 -#include <stdlib.h>
    1.55 -#include <string.h>
    1.56 +  This software is provided 'as-is', without any express or implied
    1.57 +  warranty.  In no event will the authors be held liable for any damages
    1.58 +  arising from the use of this software.
    1.59 +
    1.60 +  Permission is granted to anyone to use this software for any purpose,
    1.61 +  including commercial applications, and to alter it and redistribute it
    1.62 +  freely, subject to the following restrictions:
    1.63 +
    1.64 +  1. The origin of this software must not be misrepresented; you must not
    1.65 +     claim that you wrote the original software. If you use this software
    1.66 +     in a product, an acknowledgment in the product documentation would be
    1.67 +     appreciated but is not required.
    1.68 +  2. Altered source versions must be plainly marked as such, and must not be
    1.69 +     misrepresented as being the original software.
    1.70 +  3. This notice may not be removed or altered from any source distribution.
    1.71  */
    1.72 -#include "SDL_stdinc.h"
    1.73 +
    1.74 +#ifndef HAVE_QSORT
    1.75  
    1.76  #ifdef assert
    1.77  #undef assert
    1.78 @@ -57,28 +28,118 @@
    1.79  #ifdef malloc
    1.80  #undef malloc
    1.81  #endif
    1.82 -#define malloc	SDL_malloc
    1.83 +#define malloc SDL_malloc
    1.84  #ifdef free
    1.85  #undef free
    1.86  #endif
    1.87 -#define free	SDL_free
    1.88 +#define free SDL_free
    1.89  #ifdef memcpy
    1.90  #undef memcpy
    1.91  #endif
    1.92 -#define memcpy	SDL_memcpy
    1.93 +#define memcpy SDL_memcpy
    1.94  #ifdef memmove
    1.95  #undef memmove
    1.96  #endif
    1.97 -#define memmove	SDL_memmove
    1.98 -#ifdef qsort
    1.99 -#undef qsort
   1.100 +#define memmove SDL_memmove
   1.101 +#ifdef qsortG
   1.102 +#undef qsortG
   1.103  #endif
   1.104 -#define qsort	SDL_qsort
   1.105 +#define qsortG SDL_qsort
   1.106  
   1.107 +/*
   1.108 +This code came from Gareth McCaughan, under the zlib license.
   1.109 +Specifically this: https://www.mccaughan.org.uk/software/qsort.c-1.14
   1.110  
   1.111 -#ifndef HAVE_QSORT
   1.112 +Everything below this comment until the HAVE_QSORT #endif was from Gareth
   1.113 +(any minor changes will be noted inline).
   1.114  
   1.115 -static char _ID[]="<qsort.c gjm 1.12 1998-03-19>";
   1.116 +Thank you to Gareth for relicensing this code under the zlib license for our
   1.117 +benefit!
   1.118 +
   1.119 +--ryan.
   1.120 +*/
   1.121 +
   1.122 +/* This is a drop-in replacement for the C library's |qsort()| routine.
   1.123 + *
   1.124 + * It is intended for use where you know or suspect that your
   1.125 + * platform's qsort is bad. If that isn't the case, then you
   1.126 + * should probably use the qsort your system gives you in preference
   1.127 + * to mine -- it will likely have been tested and tuned better.
   1.128 + *
   1.129 + * Features:
   1.130 + *   - Median-of-three pivoting (and more)
   1.131 + *   - Truncation and final polishing by a single insertion sort
   1.132 + *   - Early truncation when no swaps needed in pivoting step
   1.133 + *   - Explicit recursion, guaranteed not to overflow
   1.134 + *   - A few little wrinkles stolen from the GNU |qsort()|.
   1.135 + *     (For the avoidance of doubt, no code was stolen, only
   1.136 + *     broad ideas.)
   1.137 + *   - separate code for non-aligned / aligned / word-size objects
   1.138 + *
   1.139 + * Earlier releases of this code used an idiosyncratic licence
   1.140 + * I wrote myself, because I'm an idiot. The code is now released
   1.141 + * under the "zlib/libpng licence"; you will find the actual
   1.142 + * terms in the next comment. I request (but do not require)
   1.143 + * that if you make any changes beyond the name of the exported
   1.144 + * routine and reasonable tweaks to the TRUNC_* and
   1.145 + * PIVOT_THRESHOLD values, you modify the _ID string so as
   1.146 + * to make it clear that you have changed the code.
   1.147 + *
   1.148 + * If you find problems with this code, or find ways of
   1.149 + * making it significantly faster, please let me know!
   1.150 + * My e-mail address, valid as of early 2016 and for the
   1.151 + * foreseeable future, is
   1.152 + *    gareth.mccaughan@pobox.com
   1.153 + * Thanks!
   1.154 + *
   1.155 + * Gareth McCaughan
   1.156 + */
   1.157 +
   1.158 +/* Copyright (c) 1998-2016 Gareth McCaughan
   1.159 + *
   1.160 + * This software is provided 'as-is', without any express or implied
   1.161 + * warranty. In no event will the authors be held liable for any
   1.162 + * damages arising from the use of this software.
   1.163 + *
   1.164 + * Permission is granted to anyone to use this software for any purpose,
   1.165 + * including commercial applications, and to alter it and redistribute it
   1.166 + * freely, subject to the following restrictions:
   1.167 + *
   1.168 + * 1. The origin of this software must not be misrepresented;
   1.169 + *    you must not claim that you wrote the original software.
   1.170 + *    If you use this software in a product, an acknowledgment
   1.171 + *    in the product documentation would be appreciated but
   1.172 + *    is not required.
   1.173 + *
   1.174 + * 2. Altered source versions must be plainly marked as such,
   1.175 + *    and must not be misrepresented as being the original software.
   1.176 + *
   1.177 + * 3. This notice may not be removed or altered from any source
   1.178 + *    distribution.
   1.179 + */
   1.180 +
   1.181 +/* Revision history since release:
   1.182 + *   1998-03-19 v1.12 First release I have any records of.
   1.183 + *   2007-09-02 v1.13 Fix bug kindly reported by Dan Bodoh
   1.184 + *                    (premature termination of recursion).
   1.185 + *                    Add a few clarifying comments.
   1.186 + *                    Minor improvements to debug output.
   1.187 + *   2016-02-21 v1.14 Replace licence with 2-clause BSD,
   1.188 + *                    and clarify a couple of things in
   1.189 + *                    comments. No code changes.
   1.190 + */
   1.191 +
   1.192 +/* BEGIN SDL CHANGE ... commented this out with an #if 0 block. --ryan. */
   1.193 +#if 0
   1.194 +#include <assert.h>
   1.195 +#include <stdlib.h>
   1.196 +#include <string.h>
   1.197 +
   1.198 +#define DEBUG_QSORT
   1.199 +
   1.200 +static char _ID[]="<qsort.c gjm 1.14 2016-02-21>";
   1.201 +#endif
   1.202 +/* END SDL CHANGE ... commented this out with an #if 0 block. --ryan. */
   1.203  
   1.204  /* How many bytes are there per word? (Must be a power of 2,
   1.205   * and must in fact equal sizeof(int).)
   1.206 @@ -182,7 +243,9 @@
   1.207   *        16-bit |int|s and 4096-bit |size_t|s. :-)
   1.208   */
   1.209  
   1.210 -/* The recursion logic is the same in each case: */
   1.211 +/* The recursion logic is the same in each case.
   1.212 + * We keep chopping up until we reach subarrays of size
   1.213 + * strictly less than Trunc; we leave these unsorted. */
   1.214  #define Recurse(Trunc)				\
   1.215        { size_t l=last-ffirst,r=llast-first;	\
   1.216          if (l<Trunc) {				\
   1.217 @@ -194,9 +257,9 @@
   1.218          else doLeft				\
   1.219        }
   1.220  
   1.221 -/* and so is the pivoting logic: */
   1.222 +/* and so is the pivoting logic (note: last is inclusive): */
   1.223  #define Pivot(swapper,sz)			\
   1.224 -  if ((size_t)(last-first)>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\
   1.225 +  if (last-first>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\
   1.226    else {	\
   1.227      if (compare(first,mid)<0) {			\
   1.228        if (compare(mid,last)>0) {		\
   1.229 @@ -220,26 +283,28 @@
   1.230  
   1.231  /* and so is the partitioning logic: */
   1.232  #define Partition(swapper,sz) {			\
   1.233 -  int swapped=0;				\
   1.234    do {						\
   1.235      while (compare(first,pivot)<0) first+=sz;	\
   1.236      while (compare(pivot,last)<0) last-=sz;	\
   1.237      if (first<last) {				\
   1.238 -      swapper(first,last); swapped=1;		\
   1.239 +      swapper(first,last);			\
   1.240        first+=sz; last-=sz; }			\
   1.241      else if (first==last) { first+=sz; last-=sz; break; }\
   1.242    } while (first<=last);			\
   1.243 -  if (!swapped) pop				\
   1.244  }
   1.245  
   1.246  /* and so is the pre-insertion-sort operation of putting
   1.247   * the smallest element into place as a sentinel.
   1.248   * Doing this makes the inner loop nicer. I got this
   1.249   * idea from the GNU implementation of qsort().
   1.250 + * We find the smallest element from the first |nmemb|,
   1.251 + * or the first |limit|, whichever is smaller;
   1.252 + * therefore we must have ensured that the globally smallest
   1.253 + * element is in the first |limit|.
   1.254   */
   1.255  #define PreInsertion(swapper,limit,sz)		\
   1.256    first=base;					\
   1.257 -  last=first + (nmemb>limit ? limit : nmemb-1)*sz;\
   1.258 +  last=first + ((nmemb>limit ? limit : nmemb)-1)*sz;\
   1.259    while (last!=base) {				\
   1.260      if (compare(first,last)>0) first=last;	\
   1.261      last-=sz; }					\
   1.262 @@ -281,11 +346,14 @@
   1.263  
   1.264  static char * pivot_big(char *first, char *mid, char *last, size_t size,
   1.265                          int compare(const void *, const void *)) {
   1.266 -  size_t d=(((last-first)/size)>>3)*size;
   1.267 +  int d=(((last-first)/size)>>3)*size;
   1.268 +#ifdef DEBUG_QSORT
   1.269 +fprintf(stderr, "pivot_big: first=%p last=%p size=%lu n=%lu\n", first, (unsigned long)last, size, (unsigned long)((last-first+1)/size));
   1.270 +#endif
   1.271    char *m1,*m2,*m3;
   1.272    { char *a=first, *b=first+d, *c=first+2*d;
   1.273  #ifdef DEBUG_QSORT
   1.274 -fprintf(stderr,"< %d %d %d\n",*(int*)a,*(int*)b,*(int*)c);
   1.275 +fprintf(stderr,"< %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
   1.276  #endif
   1.277      m1 = compare(a,b)<0 ?
   1.278             (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
   1.279 @@ -293,7 +361,7 @@
   1.280    }
   1.281    { char *a=mid-d, *b=mid, *c=mid+d;
   1.282  #ifdef DEBUG_QSORT
   1.283 -fprintf(stderr,". %d %d %d\n",*(int*)a,*(int*)b,*(int*)c);
   1.284 +fprintf(stderr,". %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
   1.285  #endif
   1.286      m2 = compare(a,b)<0 ?
   1.287             (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
   1.288 @@ -301,14 +369,14 @@
   1.289    }
   1.290    { char *a=last-2*d, *b=last-d, *c=last;
   1.291  #ifdef DEBUG_QSORT
   1.292 -fprintf(stderr,"> %d %d %d\n",*(int*)a,*(int*)b,*(int*)c);
   1.293 +fprintf(stderr,"> %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
   1.294  #endif
   1.295      m3 = compare(a,b)<0 ?
   1.296             (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
   1.297           : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
   1.298    }
   1.299  #ifdef DEBUG_QSORT
   1.300 -fprintf(stderr,"-> %d %d %d\n",*(int*)m1,*(int*)m2,*(int*)m3);
   1.301 +fprintf(stderr,"-> %d %d %d @ %p %p %p\n",*(int*)m1,*(int*)m2,*(int*)m3, m1,m2,m3);
   1.302  #endif
   1.303    return compare(m1,m2)<0 ?
   1.304             (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1))
   1.305 @@ -329,7 +397,7 @@
   1.306  
   1.307    first=(char*)base; last=first+(nmemb-1)*size;
   1.308  
   1.309 -  if ((size_t)(last-first)>trunc) {
   1.310 +  if (last-first>=trunc) {
   1.311      char *ffirst=first, *llast=last;
   1.312      while (1) {
   1.313        /* Select pivot */
   1.314 @@ -343,7 +411,7 @@
   1.315        Recurse(trunc)
   1.316      }
   1.317    }
   1.318 -  PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size);
   1.319 +  PreInsertion(SWAP_nonaligned,TRUNC_nonaligned-1,size);
   1.320    Insertion(SWAP_nonaligned);
   1.321    free(pivot);
   1.322  }
   1.323 @@ -360,7 +428,7 @@
   1.324  
   1.325    first=(char*)base; last=first+(nmemb-1)*size;
   1.326  
   1.327 -  if ((size_t)(last-first)>trunc) {
   1.328 +  if (last-first>=trunc) {
   1.329      char *ffirst=first,*llast=last;
   1.330      while (1) {
   1.331        /* Select pivot */
   1.332 @@ -374,7 +442,7 @@
   1.333        Recurse(trunc)
   1.334      }
   1.335    }
   1.336 -  PreInsertion(SWAP_aligned,TRUNC_aligned,size);
   1.337 +  PreInsertion(SWAP_aligned,TRUNC_aligned-1,size);
   1.338    Insertion(SWAP_aligned);
   1.339    free(pivot);
   1.340  }
   1.341 @@ -390,7 +458,7 @@
   1.342  
   1.343    first=(char*)base; last=first+(nmemb-1)*WORD_BYTES;
   1.344  
   1.345 -  if (last-first>TRUNC_words) {
   1.346 +  if (last-first>=TRUNC_words) {
   1.347      char *ffirst=first, *llast=last;
   1.348      while (1) {
   1.349  #ifdef DEBUG_QSORT
   1.350 @@ -402,17 +470,20 @@
   1.351        { char * mid=first+WORD_BYTES*((last-first) / (2*WORD_BYTES));
   1.352          Pivot(SWAP_words,WORD_BYTES);
   1.353          *(int*)pivot=*(int*)mid;
   1.354 +#ifdef DEBUG_QSORT
   1.355 +fprintf(stderr,"pivot = %p = #%lu = %d\n", mid, (unsigned long)(((int*)mid)-((int*)base)), *(int*)mid);
   1.356 +#endif
   1.357        }
   1.358 -#ifdef DEBUG_QSORT
   1.359 -fprintf(stderr,"pivot=%d\n",*(int*)pivot);
   1.360 -#endif
   1.361        /* Partition. */
   1.362        Partition(SWAP_words,WORD_BYTES);
   1.363 +#ifdef DEBUG_QSORT
   1.364 +fprintf(stderr, "after partitioning first=#%lu last=#%lu\n", (first-(char*)base)/4lu, (last-(char*)base)/4lu);
   1.365 +#endif
   1.366        /* Prepare to recurse/iterate. */
   1.367        Recurse(TRUNC_words)
   1.368      }
   1.369    }
   1.370 -  PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES);
   1.371 +  PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES)-1,WORD_BYTES);
   1.372    /* Now do insertion sort. */
   1.373    last=((char*)base)+nmemb*WORD_BYTES;
   1.374    for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) {
   1.375 @@ -428,11 +499,11 @@
   1.376  
   1.377  /* ---------------------------------------------------------------------- */
   1.378  
   1.379 -void qsort(void *base, size_t nmemb, size_t size,
   1.380 +extern void qsortG(void *base, size_t nmemb, size_t size,
   1.381             int (*compare)(const void *, const void *)) {
   1.382  
   1.383    if (nmemb<=1) return;
   1.384 -  if (((uintptr_t)base|size)&(WORD_BYTES-1))
   1.385 +  if (((int)base|size)&(WORD_BYTES-1))
   1.386      qsort_nonaligned(base,nmemb,size,compare);
   1.387    else if (size!=WORD_BYTES)
   1.388      qsort_aligned(base,nmemb,size,compare);
   1.389 @@ -440,4 +511,7 @@
   1.390      qsort_words(base,nmemb,compare);
   1.391  }
   1.392  
   1.393 -#endif /* !HAVE_QSORT */
   1.394 +#endif /* ifndef HAVE_QSORT */
   1.395 +
   1.396 +/* vi: set ts=4 sw=4 expandtab: */
   1.397 +