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