1.1 --- a/debian/copyright Sun Feb 14 21:17:25 2016 -0400
1.2 +++ b/debian/copyright Mon Feb 15 03:16:46 2016 -0500
1.3 @@ -31,10 +31,6 @@
1.4 1995 Brown University
1.5 License: BrownUn_UnCalifornia_ErikCorry
1.6
1.7 -Files: src/stdlib/SDL_qsort.c
1.8 -Copyright: 1998 Gareth McCaughan
1.9 -License: Gareth_McCaughan
1.10 -
1.11 Files: src/test/SDL_test_md5.c
1.12 Copyright: 1997-2016 Sam Lantinga <slouken@libsdl.org>
1.13 1990 RSA Data Security, Inc.
1.14 @@ -270,13 +266,6 @@
1.15 * SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
1.16 */
1.17
1.18 -License: Gareth_McCaughan
1.19 - You may use it in anything you like; you may make money
1.20 - out of it; you may distribute it in object form or as
1.21 - part of an executable without including source code;
1.22 - you don't have to credit me. (But it would be nice if
1.23 - you did.)
1.24 -
1.25 License: Johnson_M._Hart
1.26 Permission is granted for any and all use providing that this
1.27 copyright is properly acknowledged.
2.1 --- a/src/stdlib/SDL_qsort.c Sun Feb 14 21:17:25 2016 -0400
2.2 +++ b/src/stdlib/SDL_qsort.c Mon Feb 15 03:16:46 2016 -0500
2.3 @@ -1,58 +1,5 @@
2.4 -/* qsort.c
2.5 - * (c) 1998 Gareth McCaughan
2.6 - *
2.7 - * This is a drop-in replacement for the C library's |qsort()| routine.
2.8 - *
2.9 - * Features:
2.10 - * - Median-of-three pivoting (and more)
2.11 - * - Truncation and final polishing by a single insertion sort
2.12 - * - Early truncation when no swaps needed in pivoting step
2.13 - * - Explicit recursion, guaranteed not to overflow
2.14 - * - A few little wrinkles stolen from the GNU |qsort()|.
2.15 - * - separate code for non-aligned / aligned / word-size objects
2.16 - *
2.17 - * This code may be reproduced freely provided
2.18 - * - this file is retained unaltered apart from minor
2.19 - * changes for portability and efficiency
2.20 - * - no changes are made to this comment
2.21 - * - any changes that *are* made are clearly flagged
2.22 - * - the _ID string below is altered by inserting, after
2.23 - * the date, the string " altered" followed at your option
2.24 - * by other material. (Exceptions: you may change the name
2.25 - * of the exported routine without changing the ID string.
2.26 - * You may change the values of the macros TRUNC_* and
2.27 - * PIVOT_THRESHOLD without changing the ID string, provided
2.28 - * they remain constants with TRUNC_nonaligned, TRUNC_aligned
2.29 - * and TRUNC_words/WORD_BYTES between 8 and 24, and
2.30 - * PIVOT_THRESHOLD between 32 and 200.)
2.31 - *
2.32 - * You may use it in anything you like; you may make money
2.33 - * out of it; you may distribute it in object form or as
2.34 - * part of an executable without including source code;
2.35 - * you don't have to credit me. (But it would be nice if
2.36 - * you did.)
2.37 - *
2.38 - * If you find problems with this code, or find ways of
2.39 - * making it significantly faster, please let me know!
2.40 - * My e-mail address, valid as of early 1998 and certainly
2.41 - * OK for at least the next 18 months, is
2.42 - * gjm11@dpmms.cam.ac.uk
2.43 - * Thanks!
2.44 - *
2.45 - * Gareth McCaughan Peterhouse Cambridge 1998
2.46 - */
2.47 -
2.48 -#if defined(__clang_analyzer__) && !defined(SDL_DISABLE_ANALYZE_MACROS)
2.49 -#define SDL_DISABLE_ANALYZE_MACROS 1
2.50 -#endif
2.51 -
2.52 #include "../SDL_internal.h"
2.53
2.54 -/*
2.55 -#include <assert.h>
2.56 -#include <stdlib.h>
2.57 -#include <string.h>
2.58 -*/
2.59 #include "SDL_stdinc.h"
2.60 #include "SDL_assert.h"
2.61
2.62 @@ -64,418 +11,203 @@
2.63 }
2.64 #else
2.65
2.66 -#ifdef assert
2.67 -#undef assert
2.68 -#endif
2.69 -#define assert(X) SDL_assert(X)
2.70 -#ifdef malloc
2.71 -#undef malloc
2.72 -#endif
2.73 -#define malloc SDL_malloc
2.74 -#ifdef free
2.75 -#undef free
2.76 -#endif
2.77 -#define free SDL_free
2.78 -#ifdef memcpy
2.79 -#undef memcpy
2.80 -#endif
2.81 -#define memcpy SDL_memcpy
2.82 -#ifdef memmove
2.83 -#undef memmove
2.84 -#endif
2.85 -#define memmove SDL_memmove
2.86 -#ifdef qsort
2.87 -#undef qsort
2.88 -#endif
2.89 -#define qsort SDL_qsort
2.90 -
2.91 -static const char _ID[] = "<qsort.c gjm 1.12 1998-03-19>";
2.92 -
2.93 -/* How many bytes are there per word? (Must be a power of 2,
2.94 - * and must in fact equal sizeof(int).)
2.95 - */
2.96 -#define WORD_BYTES sizeof(int)
2.97 -
2.98 -/* How big does our stack need to be? Answer: one entry per
2.99 - * bit in a |size_t|.
2.100 - */
2.101 -#define STACK_SIZE (8*sizeof(size_t))
2.102 -
2.103 -/* Different situations have slightly different requirements,
2.104 - * and we make life epsilon easier by using different truncation
2.105 - * points for the three different cases.
2.106 - * So far, I have tuned TRUNC_words and guessed that the same
2.107 - * value might work well for the other two cases. Of course
2.108 - * what works well on my machine might work badly on yours.
2.109 - */
2.110 -#define TRUNC_nonaligned 12
2.111 -#define TRUNC_aligned 12
2.112 -#define TRUNC_words 12*WORD_BYTES /* nb different meaning */
2.113 -
2.114 -/* We use a simple pivoting algorithm for shortish sub-arrays
2.115 - * and a more complicated one for larger ones. The threshold
2.116 - * is PIVOT_THRESHOLD.
2.117 - */
2.118 -#define PIVOT_THRESHOLD 40
2.119 -
2.120 -typedef struct
2.121 -{
2.122 - char *first;
2.123 - char *last;
2.124 -} stack_entry;
2.125 -#define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;}
2.126 -#define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;}
2.127 -#define doLeft {first=ffirst;llast=last;continue;}
2.128 -#define doRight {ffirst=first;last=llast;continue;}
2.129 -#define pop {if (--stacktop<0) break;\
2.130 - first=ffirst=stack[stacktop].first;\
2.131 - last=llast=stack[stacktop].last;\
2.132 - continue;}
2.133 -
2.134 -/* Some comments on the implementation.
2.135 - * 1. When we finish partitioning the array into "low"
2.136 - * and "high", we forget entirely about short subarrays,
2.137 - * because they'll be done later by insertion sort.
2.138 - * Doing lots of little insertion sorts might be a win
2.139 - * on large datasets for locality-of-reference reasons,
2.140 - * but it makes the code much nastier and increases
2.141 - * bookkeeping overhead.
2.142 - * 2. We always save the shorter and get to work on the
2.143 - * longer. This guarantees that every time we push
2.144 - * an item onto the stack its size is <= 1/2 of that
2.145 - * of its parent; so the stack can't need more than
2.146 - * log_2(max-array-size) entries.
2.147 - * 3. We choose a pivot by looking at the first, last
2.148 - * and middle elements. We arrange them into order
2.149 - * because it's easy to do that in conjunction with
2.150 - * choosing the pivot, and it makes things a little
2.151 - * easier in the partitioning step. Anyway, the pivot
2.152 - * is the middle of these three. It's still possible
2.153 - * to construct datasets where the algorithm takes
2.154 - * time of order n^2, but it simply never happens in
2.155 - * practice.
2.156 - * 3' Newsflash: On further investigation I find that
2.157 - * it's easy to construct datasets where median-of-3
2.158 - * simply isn't good enough. So on large-ish subarrays
2.159 - * we do a more sophisticated pivoting: we take three
2.160 - * sets of 3 elements, find their medians, and then
2.161 - * take the median of those.
2.162 - * 4. We copy the pivot element to a separate place
2.163 - * because that way we can always do our comparisons
2.164 - * directly against a pointer to that separate place,
2.165 - * and don't have to wonder "did we move the pivot
2.166 - * element?". This makes the inner loop better.
2.167 - * 5. It's possible to make the pivoting even more
2.168 - * reliable by looking at more candidates when n
2.169 - * is larger. (Taking this to its logical conclusion
2.170 - * results in a variant of quicksort that doesn't
2.171 - * have that n^2 worst case.) However, the overhead
2.172 - * from the extra bookkeeping means that it's just
2.173 - * not worth while.
2.174 - * 6. This is pretty clean and portable code. Here are
2.175 - * all the potential portability pitfalls and problems
2.176 - * I know of:
2.177 - * - In one place (the insertion sort) I construct
2.178 - * a pointer that points just past the end of the
2.179 - * supplied array, and assume that (a) it won't
2.180 - * compare equal to any pointer within the array,
2.181 - * and (b) it will compare equal to a pointer
2.182 - * obtained by stepping off the end of the array.
2.183 - * These might fail on some segmented architectures.
2.184 - * - I assume that there are 8 bits in a |char| when
2.185 - * computing the size of stack needed. This would
2.186 - * fail on machines with 9-bit or 16-bit bytes.
2.187 - * - I assume that if |((int)base&(sizeof(int)-1))==0|
2.188 - * and |(size&(sizeof(int)-1))==0| then it's safe to
2.189 - * get at array elements via |int*|s, and that if
2.190 - * actually |size==sizeof(int)| as well then it's
2.191 - * safe to treat the elements as |int|s. This might
2.192 - * fail on systems that convert pointers to integers
2.193 - * in non-standard ways.
2.194 - * - I assume that |8*sizeof(size_t)<=INT_MAX|. This
2.195 - * would be false on a machine with 8-bit |char|s,
2.196 - * 16-bit |int|s and 4096-bit |size_t|s. :-)
2.197 - */
2.198 -
2.199 -/* The recursion logic is the same in each case: */
2.200 -#define Recurse(Trunc) \
2.201 - { size_t l=last-ffirst,r=llast-first; \
2.202 - if (l<Trunc) { \
2.203 - if (r>=Trunc) doRight \
2.204 - else pop \
2.205 - } \
2.206 - else if (l<=r) { pushLeft; doRight } \
2.207 - else if (r>=Trunc) { pushRight; doLeft }\
2.208 - else doLeft \
2.209 - }
2.210 -
2.211 -/* and so is the pivoting logic: */
2.212 -#define Pivot(swapper,sz) \
2.213 - if ((size_t)(last-first)>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\
2.214 - else { \
2.215 - if (compare(first,mid)<0) { \
2.216 - if (compare(mid,last)>0) { \
2.217 - swapper(mid,last); \
2.218 - if (compare(first,mid)>0) swapper(first,mid);\
2.219 - } \
2.220 - } \
2.221 - else { \
2.222 - if (compare(mid,last)>0) swapper(first,last)\
2.223 - else { \
2.224 - swapper(first,mid); \
2.225 - if (compare(mid,last)>0) swapper(mid,last);\
2.226 - } \
2.227 - } \
2.228 - first+=sz; last-=sz; \
2.229 - }
2.230 -
2.231 -#ifdef DEBUG_QSORT
2.232 -#include <stdio.h>
2.233 +#ifdef REGTEST
2.234 +#undef REGTEST
2.235 #endif
2.236
2.237 -/* and so is the partitioning logic: */
2.238 -#define Partition(swapper,sz) { \
2.239 - int swapped=0; \
2.240 - do { \
2.241 - while (compare(first,pivot)<0) first+=sz; \
2.242 - while (compare(pivot,last)<0) last-=sz; \
2.243 - if (first<last) { \
2.244 - swapper(first,last); swapped=1; \
2.245 - first+=sz; last-=sz; } \
2.246 - else if (first==last) { first+=sz; last-=sz; break; }\
2.247 - } while (first<=last); \
2.248 - if (!swapped) pop \
2.249 +#ifdef TEST
2.250 +#undef TEST
2.251 +#endif
2.252 +
2.253 +#ifndef _PDCLIB_memswp
2.254 +#define _PDCLIB_memswp( i, j, size ) char tmp; do { tmp = *i; *i++ = *j; *j++ = tmp; } while ( --size );
2.255 +#endif
2.256 +
2.257 +#ifndef _PDCLIB_size_t
2.258 +#define _PDCLIB_size_t size_t
2.259 +#endif
2.260 +
2.261 +#define qsort SDL_qsort
2.262 +
2.263 +#define inline SDL_INLINE
2.264 +
2.265 +/*
2.266 +This code came from PDCLib, under the public domain. Specifically this:
2.267 +https://bitbucket.org/pdclib/pdclib/raw/a82b02d0c7d4ed633b97f2a7639d9a10b1c92ec8/functions/stdlib/qsort.c
2.268 +The _PDCLIB_memswp macro was from
2.269 +https://bitbucket.org/pdclib/pdclib/src/a82b02d0c7d4ed633b97f2a7639d9a10b1c92ec8/platform/posix/internals/_PDCLIB_config.h?at=default&fileviewer=file-view-default#_PDCLIB_config.h-28
2.270 +
2.271 +Everything below this comment until the HAVE_QSORT #endif was from PDCLib.
2.272 +--ryan.
2.273 +*/
2.274 +
2.275 +/* $Id$ */
2.276 +
2.277 +/* qsort( void *, size_t, size_t, int(*)( const void *, const void * ) )
2.278 +
2.279 + This file is part of the Public Domain C Library (PDCLib).
2.280 + Permission is granted to use, modify, and / or redistribute at will.
2.281 +*/
2.282 +
2.283 +#include <stdlib.h>
2.284 +
2.285 +#ifndef REGTEST
2.286 +
2.287 +/* This implementation is taken from Paul Edward's PDPCLIB.
2.288 +
2.289 + Original code is credited to Raymond Gardner, Englewood CO.
2.290 + Minor mods are credited to Paul Edwards.
2.291 + Some reformatting and simplification done by Martin Baute.
2.292 + All code is still Public Domain.
2.293 +*/
2.294 +
2.295 +/* Wrapper for _PDCLIB_memswp protects against multiple argument evaluation. */
2.296 +static inline void memswp( char * i, char * j, size_t size )
2.297 +{
2.298 + _PDCLIB_memswp( i, j, size );
2.299 }
2.300
2.301 -/* and so is the pre-insertion-sort operation of putting
2.302 - * the smallest element into place as a sentinel.
2.303 - * Doing this makes the inner loop nicer. I got this
2.304 - * idea from the GNU implementation of qsort().
2.305 - */
2.306 -#define PreInsertion(swapper,limit,sz) \
2.307 - first=base; \
2.308 - last=first + (nmemb>limit ? limit : nmemb-1)*sz;\
2.309 - while (last!=base) { \
2.310 - if (compare(first,last)>0) first=last; \
2.311 - last-=sz; } \
2.312 - if (first!=base) swapper(first,(char*)base);
2.313 +/* For small sets, insertion sort is faster than quicksort.
2.314 + T is the threshold below which insertion sort will be used.
2.315 + Must be 3 or larger.
2.316 +*/
2.317 +#define T 7
2.318
2.319 -/* and so is the insertion sort, in the first two cases: */
2.320 -#define Insertion(swapper) \
2.321 - last=((char*)base)+nmemb*size; \
2.322 - for (first=((char*)base)+size;first!=last;first+=size) { \
2.323 - char *test; \
2.324 - /* Find the right place for |first|. \
2.325 - * My apologies for var reuse. */ \
2.326 - for (test=first-size;compare(test,first)>0;test-=size) ; \
2.327 - test+=size; \
2.328 - if (test!=first) { \
2.329 - /* Shift everything in [test,first) \
2.330 - * up by one, and place |first| \
2.331 - * where |test| is. */ \
2.332 - memcpy(pivot,first,size); \
2.333 - memmove(test+size,test,first-test); \
2.334 - memcpy(test,pivot,size); \
2.335 - } \
2.336 - }
2.337 +/* Macros for handling the QSort stack */
2.338 +#define PREPARE_STACK char * stack[STACKSIZE]; char * * stackptr = stack
2.339 +#define PUSH( base, limit ) stackptr[0] = base; stackptr[1] = limit; stackptr += 2
2.340 +#define POP( base, limit ) stackptr -= 2; base = stackptr[0]; limit = stackptr[1]
2.341 +/* TODO: Stack usage is log2( nmemb ) (minus what T shaves off the worst case).
2.342 + Worst-case nmemb is platform dependent and should probably be
2.343 + configured through _PDCLIB_config.h.
2.344 +*/
2.345 +#define STACKSIZE 64
2.346
2.347 -#define SWAP_nonaligned(a,b) { \
2.348 - register char *aa=(a),*bb=(b); \
2.349 - register size_t sz=size; \
2.350 - do { register char t=*aa; *aa++=*bb; *bb++=t; } while (--sz); }
2.351 +void qsort( void * base, size_t nmemb, size_t size, int (*compar)( const void *, const void * ) )
2.352 +{
2.353 + char * i;
2.354 + char * j;
2.355 + _PDCLIB_size_t thresh = T * size;
2.356 + char * base_ = (char *)base;
2.357 + char * limit = base_ + nmemb * size;
2.358 + PREPARE_STACK;
2.359
2.360 -#define SWAP_aligned(a,b) { \
2.361 - register int *aa=(int*)(a),*bb=(int*)(b); \
2.362 - register size_t sz=size; \
2.363 - do { register int t=*aa;*aa++=*bb; *bb++=t; } while (sz-=WORD_BYTES); }
2.364 -
2.365 -#define SWAP_words(a,b) { \
2.366 - register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; }
2.367 -
2.368 -/* ---------------------------------------------------------------------- */
2.369 -
2.370 -static char *
2.371 -pivot_big(char *first, char *mid, char *last, size_t size,
2.372 - int compare(const void *, const void *))
2.373 -{
2.374 - size_t d = (((last - first) / size) >> 3) * size;
2.375 - char *m1, *m2, *m3;
2.376 + for ( ;; )
2.377 {
2.378 - char *a = first, *b = first + d, *c = first + 2 * d;
2.379 -#ifdef DEBUG_QSORT
2.380 - fprintf(stderr, "< %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
2.381 -#endif
2.382 - m1 = compare(a, b) < 0 ?
2.383 - (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
2.384 - : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
2.385 + if ( (size_t)( limit - base_ ) > thresh ) /* QSort for more than T elements. */
2.386 + {
2.387 + /* We work from second to last - first will be pivot element. */
2.388 + i = base_ + size;
2.389 + j = limit - size;
2.390 + /* We swap first with middle element, then sort that with second
2.391 + and last element so that eventually first element is the median
2.392 + of the three - avoiding pathological pivots.
2.393 + TODO: Instead of middle element, chose one randomly.
2.394 + */
2.395 + memswp( ( ( ( (size_t)( limit - base_ ) ) / size ) / 2 ) * size + base_, base_, size );
2.396 + if ( compar( i, j ) > 0 ) memswp( i, j, size );
2.397 + if ( compar( base_, j ) > 0 ) memswp( base_, j, size );
2.398 + if ( compar( i, base_ ) > 0 ) memswp( i, base_, size );
2.399 + /* Now we have the median for pivot element, entering main Quicksort. */
2.400 + for ( ;; )
2.401 + {
2.402 + do
2.403 + {
2.404 + /* move i right until *i >= pivot */
2.405 + i += size;
2.406 + } while ( compar( i, base_ ) < 0 );
2.407 + do
2.408 + {
2.409 + /* move j left until *j <= pivot */
2.410 + j -= size;
2.411 + } while ( compar( j, base_ ) > 0 );
2.412 + if ( i > j )
2.413 + {
2.414 + /* break loop if pointers crossed */
2.415 + break;
2.416 + }
2.417 + /* else swap elements, keep scanning */
2.418 + memswp( i, j, size );
2.419 + }
2.420 + /* move pivot into correct place */
2.421 + memswp( base_, j, size );
2.422 + /* larger subfile base / limit to stack, sort smaller */
2.423 + if ( j - base_ > limit - i )
2.424 + {
2.425 + /* left is larger */
2.426 + PUSH( base_, j );
2.427 + base_ = i;
2.428 + }
2.429 + else
2.430 + {
2.431 + /* right is larger */
2.432 + PUSH( i, limit );
2.433 + limit = j;
2.434 + }
2.435 + }
2.436 + else /* insertion sort for less than T elements */
2.437 + {
2.438 + for ( j = base_, i = j + size; i < limit; j = i, i += size )
2.439 + {
2.440 + for ( ; compar( j, j + size ) > 0; j -= size )
2.441 + {
2.442 + memswp( j, j + size, size );
2.443 + if ( j == base_ )
2.444 + {
2.445 + break;
2.446 + }
2.447 + }
2.448 + }
2.449 + if ( stackptr != stack ) /* if any entries on stack */
2.450 + {
2.451 + POP( base_, limit );
2.452 + }
2.453 + else /* else stack empty, done */
2.454 + {
2.455 + break;
2.456 + }
2.457 + }
2.458 }
2.459 - {
2.460 - char *a = mid - d, *b = mid, *c = mid + d;
2.461 -#ifdef DEBUG_QSORT
2.462 - fprintf(stderr, ". %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
2.463 -#endif
2.464 - m2 = compare(a, b) < 0 ?
2.465 - (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
2.466 - : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
2.467 - }
2.468 - {
2.469 - char *a = last - 2 * d, *b = last - d, *c = last;
2.470 -#ifdef DEBUG_QSORT
2.471 - fprintf(stderr, "> %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
2.472 -#endif
2.473 - m3 = compare(a, b) < 0 ?
2.474 - (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
2.475 - : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
2.476 - }
2.477 -#ifdef DEBUG_QSORT
2.478 - fprintf(stderr, "-> %d %d %d\n", *(int *) m1, *(int *) m2, *(int *) m3);
2.479 -#endif
2.480 - return compare(m1, m2) < 0 ?
2.481 - (compare(m2, m3) < 0 ? m2 : (compare(m1, m3) < 0 ? m3 : m1))
2.482 - : (compare(m1, m3) < 0 ? m1 : (compare(m2, m3) < 0 ? m3 : m2));
2.483 }
2.484
2.485 -/* ---------------------------------------------------------------------- */
2.486 +#endif
2.487
2.488 -static void
2.489 -qsort_nonaligned(void *base, size_t nmemb, size_t size,
2.490 - int (*compare) (const void *, const void *))
2.491 +#ifdef TEST
2.492 +#include <_PDCLIB_test.h>
2.493 +#include <string.h>
2.494 +#include <limits.h>
2.495 +
2.496 +static int compare( const void * left, const void * right )
2.497 {
2.498 -
2.499 - stack_entry stack[STACK_SIZE];
2.500 - int stacktop = 0;
2.501 - char *first, *last;
2.502 - char *pivot = malloc(size);
2.503 - size_t trunc = TRUNC_nonaligned * size;
2.504 - assert(pivot != 0);
2.505 -
2.506 - first = (char *) base;
2.507 - last = first + (nmemb - 1) * size;
2.508 -
2.509 - if ((size_t) (last - first) > trunc) {
2.510 - char *ffirst = first, *llast = last;
2.511 - while (1) {
2.512 - /* Select pivot */
2.513 - {
2.514 - char *mid = first + size * ((last - first) / size >> 1);
2.515 - Pivot(SWAP_nonaligned, size);
2.516 - memcpy(pivot, mid, size);
2.517 - }
2.518 - /* Partition. */
2.519 - Partition(SWAP_nonaligned, size);
2.520 - /* Prepare to recurse/iterate. */
2.521 - Recurse(trunc)}
2.522 - }
2.523 - PreInsertion(SWAP_nonaligned, TRUNC_nonaligned, size);
2.524 - Insertion(SWAP_nonaligned);
2.525 - free(pivot);
2.526 + return *( (unsigned char *)left ) - *( (unsigned char *)right );
2.527 }
2.528
2.529 -static void
2.530 -qsort_aligned(void *base, size_t nmemb, size_t size,
2.531 - int (*compare) (const void *, const void *))
2.532 +int main( void )
2.533 {
2.534 -
2.535 - stack_entry stack[STACK_SIZE];
2.536 - int stacktop = 0;
2.537 - char *first, *last;
2.538 - char *pivot = malloc(size);
2.539 - size_t trunc = TRUNC_aligned * size;
2.540 - assert(pivot != 0);
2.541 -
2.542 - first = (char *) base;
2.543 - last = first + (nmemb - 1) * size;
2.544 -
2.545 - if ((size_t) (last - first) > trunc) {
2.546 - char *ffirst = first, *llast = last;
2.547 - while (1) {
2.548 - /* Select pivot */
2.549 - {
2.550 - char *mid = first + size * ((last - first) / size >> 1);
2.551 - Pivot(SWAP_aligned, size);
2.552 - memcpy(pivot, mid, size);
2.553 - }
2.554 - /* Partition. */
2.555 - Partition(SWAP_aligned, size);
2.556 - /* Prepare to recurse/iterate. */
2.557 - Recurse(trunc)}
2.558 - }
2.559 - PreInsertion(SWAP_aligned, TRUNC_aligned, size);
2.560 - Insertion(SWAP_aligned);
2.561 - free(pivot);
2.562 + char presort[] = { "shreicnyjqpvozxmbt" };
2.563 + char sorted1[] = { "bcehijmnopqrstvxyz" };
2.564 + char sorted2[] = { "bticjqnyozpvreshxm" };
2.565 + char s[19];
2.566 + strcpy( s, presort );
2.567 + qsort( s, 18, 1, compare );
2.568 + TESTCASE( strcmp( s, sorted1 ) == 0 );
2.569 + strcpy( s, presort );
2.570 + qsort( s, 9, 2, compare );
2.571 + TESTCASE( strcmp( s, sorted2 ) == 0 );
2.572 + strcpy( s, presort );
2.573 + qsort( s, 1, 1, compare );
2.574 + TESTCASE( strcmp( s, presort ) == 0 );
2.575 +#if defined(REGTEST) && (__BSD_VISIBLE || __APPLE__)
2.576 + puts( "qsort.c: Skipping test #4 for BSD as it goes into endless loop here." );
2.577 +#else
2.578 + qsort( s, 100, 0, compare );
2.579 + TESTCASE( strcmp( s, presort ) == 0 );
2.580 +#endif
2.581 + return TEST_RESULTS;
2.582 }
2.583
2.584 -static void
2.585 -qsort_words(void *base, size_t nmemb,
2.586 - int (*compare) (const void *, const void *))
2.587 -{
2.588 +#endif
2.589
2.590 - stack_entry stack[STACK_SIZE];
2.591 - int stacktop = 0;
2.592 - char *first, *last;
2.593 - char *pivot = malloc(WORD_BYTES);
2.594 - assert(pivot != 0);
2.595 -
2.596 - first = (char *) base;
2.597 - last = first + (nmemb - 1) * WORD_BYTES;
2.598 -
2.599 - if (last - first > TRUNC_words) {
2.600 - char *ffirst = first, *llast = last;
2.601 - while (1) {
2.602 -#ifdef DEBUG_QSORT
2.603 - fprintf(stderr, "Doing %d:%d: ",
2.604 - (first - (char *) base) / WORD_BYTES,
2.605 - (last - (char *) base) / WORD_BYTES);
2.606 -#endif
2.607 - /* Select pivot */
2.608 - {
2.609 - char *mid =
2.610 - first + WORD_BYTES * ((last - first) / (2 * WORD_BYTES));
2.611 - Pivot(SWAP_words, WORD_BYTES);
2.612 - *(int *) pivot = *(int *) mid;
2.613 - }
2.614 -#ifdef DEBUG_QSORT
2.615 - fprintf(stderr, "pivot=%d\n", *(int *) pivot);
2.616 -#endif
2.617 - /* Partition. */
2.618 - Partition(SWAP_words, WORD_BYTES);
2.619 - /* Prepare to recurse/iterate. */
2.620 - Recurse(TRUNC_words)}
2.621 - }
2.622 - PreInsertion(SWAP_words, (TRUNC_words / WORD_BYTES), WORD_BYTES);
2.623 - /* Now do insertion sort. */
2.624 - last = ((char *) base) + nmemb * WORD_BYTES;
2.625 - for (first = ((char *) base) + WORD_BYTES; first != last;
2.626 - first += WORD_BYTES) {
2.627 - /* Find the right place for |first|. My apologies for var reuse */
2.628 - int *pl = (int *) (first - WORD_BYTES), *pr = (int *) first;
2.629 - *(int *) pivot = *(int *) first;
2.630 - for (; compare(pl, pivot) > 0; pr = pl, --pl) {
2.631 - *pr = *pl;
2.632 - }
2.633 - if (pr != (int *) first)
2.634 - *pr = *(int *) pivot;
2.635 - }
2.636 - free(pivot);
2.637 -}
2.638 -
2.639 -/* ---------------------------------------------------------------------- */
2.640 -
2.641 -void
2.642 -qsort(void *base, size_t nmemb, size_t size,
2.643 - int (*compare) (const void *, const void *))
2.644 -{
2.645 -
2.646 - if (nmemb <= 1)
2.647 - return;
2.648 - if (((uintptr_t) base | size) & (WORD_BYTES - 1))
2.649 - qsort_nonaligned(base, nmemb, size, compare);
2.650 - else if (size != WORD_BYTES)
2.651 - qsort_aligned(base, nmemb, size, compare);
2.652 - else
2.653 - qsort_words(base, nmemb, compare);
2.654 -}
2.655 -
2.656 -#endif /* !SDL_qsort */
2.657 +#endif /* HAVE_QSORT */
2.658
2.659 /* vi: set ts=4 sw=4 expandtab: */