Skip to content

Commit

Permalink
1.2 stdlib: Updated qsort with licensing resolved (thanks, Gareth!).
Browse files Browse the repository at this point in the history
  • Loading branch information
@icculus
icculus committed Feb 21, 2016
1 parent 96879da commit 4f98cab
Showing 1 changed file with 155 additions and 81 deletions.
236 changes: 155 additions & 81 deletions src/stdlib/SDL_qsort.c
View file
@@ -1,54 +1,25 @@
/* 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
*/
#include "SDL_config.h"

/*
#include <assert.h>
#include <stdlib.h>
#include <string.h>
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.
*/
#include "SDL_stdinc.h"

#ifndef HAVE_QSORT

#ifdef assert
#undef assert
Expand All @@ -57,28 +28,118 @@
#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).
#ifndef HAVE_QSORT
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.
*/

/* 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.
*/

static char _ID[]="<qsort.c gjm 1.12 1998-03-19>";
/* 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).)
Expand Down Expand Up @@ -182,7 +243,9 @@ typedef struct { char * first; char * last; } stack_entry;
* 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) { \
Expand All @@ -194,9 +257,9 @@ typedef struct { char * first; char * last; } stack_entry;
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) { \
Expand All @@ -220,26 +283,28 @@ typedef struct { char * first; char * last; } stack_entry;

/* 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; } \
Expand Down Expand Up @@ -281,34 +346,37 @@ typedef struct { char * first; char * last; } stack_entry;

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;
int d=(((last-first)/size)>>3)*size;
#ifdef DEBUG_QSORT
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
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
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
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\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));
}
#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))
Expand All @@ -329,7 +397,7 @@ static void qsort_nonaligned(void *base, size_t nmemb, size_t size,

first=(char*)base; last=first+(nmemb-1)*size;

if ((size_t)(last-first)>trunc) {
if (last-first>=trunc) {
char *ffirst=first, *llast=last;
while (1) {
/* Select pivot */
Expand All @@ -343,7 +411,7 @@ static void qsort_nonaligned(void *base, size_t nmemb, size_t size,
Recurse(trunc)
}
}
PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size);
PreInsertion(SWAP_nonaligned,TRUNC_nonaligned-1,size);
Insertion(SWAP_nonaligned);
free(pivot);
}
Expand All @@ -360,7 +428,7 @@ static void qsort_aligned(void *base, size_t nmemb, size_t size,

first=(char*)base; last=first+(nmemb-1)*size;

if ((size_t)(last-first)>trunc) {
if (last-first>=trunc) {
char *ffirst=first,*llast=last;
while (1) {
/* Select pivot */
Expand All @@ -374,7 +442,7 @@ static void qsort_aligned(void *base, size_t nmemb, size_t size,
Recurse(trunc)
}
}
PreInsertion(SWAP_aligned,TRUNC_aligned,size);
PreInsertion(SWAP_aligned,TRUNC_aligned-1,size);
Insertion(SWAP_aligned);
free(pivot);
}
Expand All @@ -390,7 +458,7 @@ static void qsort_words(void *base, size_t nmemb,

first=(char*)base; last=first+(nmemb-1)*WORD_BYTES;

if (last-first>TRUNC_words) {
if (last-first>=TRUNC_words) {
char *ffirst=first, *llast=last;
while (1) {
#ifdef DEBUG_QSORT
Expand All @@ -402,17 +470,20 @@ fprintf(stderr,"Doing %d:%d: ",
{ 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);
#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)
}
}
PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES);
PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES)-1,WORD_BYTES);
/* Now do insertion sort. */
last=((char*)base)+nmemb*WORD_BYTES;
for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) {
Expand All @@ -428,16 +499,19 @@ fprintf(stderr,"pivot=%d\n",*(int*)pivot);

/* ---------------------------------------------------------------------- */

void qsort(void *base, size_t nmemb, size_t size,
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))
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 /* !HAVE_QSORT */
#endif /* ifndef HAVE_QSORT */

/* vi: set ts=4 sw=4 expandtab: */

0 comments on commit 4f98cab

Please sign in to comment.