Atlas - SDL_qsort.c
Home / ext / SDL2 / src / stdlib Lines: 8 | Size: 18557 bytes [Download] [Show on GitHub] [Search similar files] [Raw] [Raw (proxy)][FILE BEGIN]1/* 2 Simple DirectMedia Layer 3 Copyright (C) 1997-2018 Sam Lantinga <[email protected]> 4 5 This software is provided 'as-is', without any express or implied 6 warranty. In no event will the authors be held liable for any damages 7 arising from the use of this software. 8 9 Permission is granted to anyone to use this software for any purpose, 10 including commercial applications, and to alter it and redistribute it 11 freely, subject to the following restrictions: 12 13 1. The origin of this software must not be misrepresented; you must not 14 claim that you wrote the original software. If you use this software 15 in a product, an acknowledgment in the product documentation would be 16 appreciated but is not required. 17 2. Altered source versions must be plainly marked as such, and must not be 18 misrepresented as being the original software. 19 3. This notice may not be removed or altered from any source distribution. 20*/ 21 22#if defined(__clang_analyzer__) && !defined(SDL_DISABLE_ANALYZE_MACROS) 23#define SDL_DISABLE_ANALYZE_MACROS 1 24#endif 25 26#include "../SDL_internal.h" 27 28#include "SDL_stdinc.h" 29#include "SDL_assert.h" 30 31#if defined(HAVE_QSORT) 32void 33SDL_qsort(void *base, size_t nmemb, size_t size, int (*compare) (const void *, const void *)) 34{ 35 qsort(base, nmemb, size, compare); 36} 37 38#else 39 40#ifdef assert 41#undef assert 42#endif 43#define assert SDL_assert 44#ifdef malloc 45#undef malloc 46#endif 47#define malloc SDL_malloc 48#ifdef free 49#undef free 50#endif 51#define free SDL_free 52#ifdef memcpy 53#undef memcpy 54#endif 55#define memcpy SDL_memcpy 56#ifdef memmove 57#undef memmove 58#endif 59#define memmove SDL_memmove 60#ifdef qsortG 61#undef qsortG 62#endif 63#define qsortG SDL_qsort 64 65/* 66This code came from Gareth McCaughan, under the zlib license. 67Specifically this: https://www.mccaughan.org.uk/software/qsort.c-1.14 68 69Everything below this comment until the HAVE_QSORT #endif was from Gareth 70(any minor changes will be noted inline). 71 72Thank you to Gareth for relicensing this code under the zlib license for our 73benefit! 74 75--ryan. 76*/ 77 78/* This is a drop-in replacement for the C library's |qsort()| routine. 79 * 80 * It is intended for use where you know or suspect that your 81 * platform's qsort is bad. If that isn't the case, then you 82 * should probably use the qsort your system gives you in preference 83 * to mine -- it will likely have been tested and tuned better. 84 * 85 * Features: 86 * - Median-of-three pivoting (and more) 87 * - Truncation and final polishing by a single insertion sort 88 * - Early truncation when no swaps needed in pivoting step 89 * - Explicit recursion, guaranteed not to overflow 90 * - A few little wrinkles stolen from the GNU |qsort()|. 91 * (For the avoidance of doubt, no code was stolen, only 92 * broad ideas.) 93 * - separate code for non-aligned / aligned / word-size objects 94 * 95 * Earlier releases of this code used an idiosyncratic licence 96 * I wrote myself, because I'm an idiot. The code is now released 97 * under the "zlib/libpng licence"; you will find the actual 98 * terms in the next comment. I request (but do not require) 99 * that if you make any changes beyond the name of the exported 100 * routine and reasonable tweaks to the TRUNC_* and 101 * PIVOT_THRESHOLD values, you modify the _ID string so as 102 * to make it clear that you have changed the code. 103 * 104 * If you find problems with this code, or find ways of 105 * making it significantly faster, please let me know! 106 * My e-mail address, valid as of early 2016 and for the 107 * foreseeable future, is 108 * [email protected] 109 * Thanks! 110 * 111 * Gareth McCaughan 112 */ 113 114/* Copyright (c) 1998-2016 Gareth McCaughan 115 * 116 * This software is provided 'as-is', without any express or implied 117 * warranty. In no event will the authors be held liable for any 118 * damages arising from the use of this software. 119 * 120 * Permission is granted to anyone to use this software for any purpose, 121 * including commercial applications, and to alter it and redistribute it 122 * freely, subject to the following restrictions: 123 * 124 * 1. The origin of this software must not be misrepresented; 125 * you must not claim that you wrote the original software. 126 * If you use this software in a product, an acknowledgment 127 * in the product documentation would be appreciated but 128 * is not required. 129 * 130 * 2. Altered source versions must be plainly marked as such, 131 * and must not be misrepresented as being the original software. 132 * 133 * 3. This notice may not be removed or altered from any source 134 * distribution. 135 */ 136 137/* Revision history since release: 138 * 1998-03-19 v1.12 First release I have any records of. 139 * 2007-09-02 v1.13 Fix bug kindly reported by Dan Bodoh 140 * (premature termination of recursion). 141 * Add a few clarifying comments. 142 * Minor improvements to debug output. 143 * 2016-02-21 v1.14 Replace licence with 2-clause BSD, 144 * and clarify a couple of things in 145 * comments. No code changes. 146 */ 147 148/* BEGIN SDL CHANGE ... commented this out with an #if 0 block. --ryan. */ 149#if 0 150#include <assert.h> 151#include <stdlib.h> 152#include <string.h> 153 154#define DEBUG_QSORT 155 156static char _ID[]="<qsort.c gjm 1.14 2016-02-21>"; 157#endif 158/* END SDL CHANGE ... commented this out with an #if 0 block. --ryan. */ 159 160/* How many bytes are there per word? (Must be a power of 2, 161 * and must in fact equal sizeof(int).) 162 */ 163#define WORD_BYTES sizeof(int) 164 165/* How big does our stack need to be? Answer: one entry per 166 * bit in a |size_t|. 167 */ 168#define STACK_SIZE (8*sizeof(size_t)) 169 170/* Different situations have slightly different requirements, 171 * and we make life epsilon easier by using different truncation 172 * points for the three different cases. 173 * So far, I have tuned TRUNC_words and guessed that the same 174 * value might work well for the other two cases. Of course 175 * what works well on my machine might work badly on yours. 176 */ 177#define TRUNC_nonaligned 12 178#define TRUNC_aligned 12 179#define TRUNC_words 12*WORD_BYTES /* nb different meaning */ 180 181/* We use a simple pivoting algorithm for shortish sub-arrays 182 * and a more complicated one for larger ones. The threshold 183 * is PIVOT_THRESHOLD. 184 */ 185#define PIVOT_THRESHOLD 40 186 187typedef struct { char * first; char * last; } stack_entry; 188#define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;} 189#define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;} 190#define doLeft {first=ffirst;llast=last;continue;} 191#define doRight {ffirst=first;last=llast;continue;} 192#define pop {if (--stacktop<0) break;\ 193 first=ffirst=stack[stacktop].first;\ 194 last=llast=stack[stacktop].last;\ 195 continue;} 196 197/* Some comments on the implementation. 198 * 1. When we finish partitioning the array into "low" 199 * and "high", we forget entirely about short subarrays, 200 * because they'll be done later by insertion sort. 201 * Doing lots of little insertion sorts might be a win 202 * on large datasets for locality-of-reference reasons, 203 * but it makes the code much nastier and increases 204 * bookkeeping overhead. 205 * 2. We always save the shorter and get to work on the 206 * longer. This guarantees that every time we push 207 * an item onto the stack its size is <= 1/2 of that 208 * of its parent; so the stack can't need more than 209 * log_2(max-array-size) entries. 210 * 3. We choose a pivot by looking at the first, last 211 * and middle elements. We arrange them into order 212 * because it's easy to do that in conjunction with 213 * choosing the pivot, and it makes things a little 214 * easier in the partitioning step. Anyway, the pivot 215 * is the middle of these three. It's still possible 216 * to construct datasets where the algorithm takes 217 * time of order n^2, but it simply never happens in 218 * practice. 219 * 3' Newsflash: On further investigation I find that 220 * it's easy to construct datasets where median-of-3 221 * simply isn't good enough. So on large-ish subarrays 222 * we do a more sophisticated pivoting: we take three 223 * sets of 3 elements, find their medians, and then 224 * take the median of those. 225 * 4. We copy the pivot element to a separate place 226 * because that way we can always do our comparisons 227 * directly against a pointer to that separate place, 228 * and don't have to wonder "did we move the pivot 229 * element?". This makes the inner loop better. 230 * 5. It's possible to make the pivoting even more 231 * reliable by looking at more candidates when n 232 * is larger. (Taking this to its logical conclusion 233 * results in a variant of quicksort that doesn't 234 * have that n^2 worst case.) However, the overhead 235 * from the extra bookkeeping means that it's just 236 * not worth while. 237 * 6. This is pretty clean and portable code. Here are 238 * all the potential portability pitfalls and problems 239 * I know of: 240 * - In one place (the insertion sort) I construct 241 * a pointer that points just past the end of the 242 * supplied array, and assume that (a) it won't 243 * compare equal to any pointer within the array, 244 * and (b) it will compare equal to a pointer 245 * obtained by stepping off the end of the array. 246 * These might fail on some segmented architectures. 247 * - I assume that there are 8 bits in a |char| when 248 * computing the size of stack needed. This would 249 * fail on machines with 9-bit or 16-bit bytes. 250 * - I assume that if |((int)base&(sizeof(int)-1))==0| 251 * and |(size&(sizeof(int)-1))==0| then it's safe to 252 * get at array elements via |int*|s, and that if 253 * actually |size==sizeof(int)| as well then it's 254 * safe to treat the elements as |int|s. This might 255 * fail on systems that convert pointers to integers 256 * in non-standard ways. 257 * - I assume that |8*sizeof(size_t)<=INT_MAX|. This 258 * would be false on a machine with 8-bit |char|s, 259 * 16-bit |int|s and 4096-bit |size_t|s. :-) 260 */ 261 262/* The recursion logic is the same in each case. 263 * We keep chopping up until we reach subarrays of size 264 * strictly less than Trunc; we leave these unsorted. */ 265#define Recurse(Trunc) \ 266 { size_t l=last-ffirst,r=llast-first; \ 267 if (l<Trunc) { \ 268 if (r>=Trunc) doRight \ 269 else pop \ 270 } \ 271 else if (l<=r) { pushLeft; doRight } \ 272 else if (r>=Trunc) { pushRight; doLeft }\ 273 else doLeft \ 274 } 275 276/* and so is the pivoting logic (note: last is inclusive): */ 277#define Pivot(swapper,sz) \ 278 if ((size_t)(last-first)>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\ 279 else { \ 280 if (compare(first,mid)<0) { \ 281 if (compare(mid,last)>0) { \ 282 swapper(mid,last); \ 283 if (compare(first,mid)>0) swapper(first,mid);\ 284 } \ 285 } \ 286 else { \ 287 if (compare(mid,last)>0) swapper(first,last)\ 288 else { \ 289 swapper(first,mid); \ 290 if (compare(mid,last)>0) swapper(mid,last);\ 291 } \ 292 } \ 293 first+=sz; last-=sz; \ 294 } 295 296#ifdef DEBUG_QSORT 297#include <stdio.h> 298#endif 299 300/* and so is the partitioning logic: */ 301#define Partition(swapper,sz) { \ 302 do { \ 303 while (compare(first,pivot)<0) first+=sz; \ 304 while (compare(pivot,last)<0) last-=sz; \ 305 if (first<last) { \ 306 swapper(first,last); \ 307 first+=sz; last-=sz; } \ 308 else if (first==last) { first+=sz; last-=sz; break; }\ 309 } while (first<=last); \ 310} 311 312/* and so is the pre-insertion-sort operation of putting 313 * the smallest element into place as a sentinel. 314 * Doing this makes the inner loop nicer. I got this 315 * idea from the GNU implementation of qsort(). 316 * We find the smallest element from the first |nmemb|, 317 * or the first |limit|, whichever is smaller; 318 * therefore we must have ensured that the globally smallest 319 * element is in the first |limit|. 320 */ 321#define PreInsertion(swapper,limit,sz) \ 322 first=base; \ 323 last=first + ((nmemb>limit ? limit : nmemb)-1)*sz;\ 324 while (last!=base) { \ 325 if (compare(first,last)>0) first=last; \ 326 last-=sz; } \ 327 if (first!=base) swapper(first,(char*)base); 328 329/* and so is the insertion sort, in the first two cases: */ 330#define Insertion(swapper) \ 331 last=((char*)base)+nmemb*size; \ 332 for (first=((char*)base)+size;first!=last;first+=size) { \ 333 char *test; \ 334 /* Find the right place for |first|. \ 335 * My apologies for var reuse. */ \ 336 for (test=first-size;compare(test,first)>0;test-=size) ; \ 337 test+=size; \ 338 if (test!=first) { \ 339 /* Shift everything in [test,first) \ 340 * up by one, and place |first| \ 341 * where |test| is. */ \ 342 memcpy(pivot,first,size); \ 343 memmove(test+size,test,first-test); \ 344 memcpy(test,pivot,size); \ 345 } \ 346 } 347 348#define SWAP_nonaligned(a,b) { \ 349 register char *aa=(a),*bb=(b); \ 350 register size_t sz=size; \ 351 do { register char t=*aa; *aa++=*bb; *bb++=t; } while (--sz); } 352 353#define SWAP_aligned(a,b) { \ 354 register int *aa=(int*)(a),*bb=(int*)(b); \ 355 register size_t sz=size; \ 356 do { register int t=*aa;*aa++=*bb; *bb++=t; } while (sz-=WORD_BYTES); } 357 358#define SWAP_words(a,b) { \ 359 register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; } 360 361/* ---------------------------------------------------------------------- */ 362 363static char * pivot_big(char *first, char *mid, char *last, size_t size, 364 int compare(const void *, const void *)) { 365 size_t d=(((last-first)/size)>>3)*size; 366#ifdef DEBUG_QSORT 367fprintf(stderr, "pivot_big: first=%p last=%p size=%lu n=%lu\n", first, (unsigned long)last, size, (unsigned long)((last-first+1)/size)); 368#endif 369 char *m1,*m2,*m3; 370 { char *a=first, *b=first+d, *c=first+2*d; 371#ifdef DEBUG_QSORT 372fprintf(stderr,"< %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c); 373#endif 374 m1 = compare(a,b)<0 ? 375 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) 376 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); 377 } 378 { char *a=mid-d, *b=mid, *c=mid+d; 379#ifdef DEBUG_QSORT 380fprintf(stderr,". %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c); 381#endif 382 m2 = compare(a,b)<0 ? 383 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) 384 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); 385 } 386 { char *a=last-2*d, *b=last-d, *c=last; 387#ifdef DEBUG_QSORT 388fprintf(stderr,"> %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c); 389#endif 390 m3 = compare(a,b)<0 ? 391 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) 392 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); 393 } 394#ifdef DEBUG_QSORT 395fprintf(stderr,"-> %d %d %d @ %p %p %p\n",*(int*)m1,*(int*)m2,*(int*)m3, m1,m2,m3); 396#endif 397 return compare(m1,m2)<0 ? 398 (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1)) 399 : (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2)); 400} 401 402/* ---------------------------------------------------------------------- */ 403 404static void qsort_nonaligned(void *base, size_t nmemb, size_t size, 405 int (*compare)(const void *, const void *)) { 406 407 stack_entry stack[STACK_SIZE]; 408 int stacktop=0; 409 char *first,*last; 410 char *pivot=malloc(size); 411 size_t trunc=TRUNC_nonaligned*size; 412 assert(pivot!=0); 413 414 first=(char*)base; last=first+(nmemb-1)*size; 415 416 if ((size_t)(last-first)>=trunc) { 417 char *ffirst=first, *llast=last; 418 while (1) { 419 /* Select pivot */ 420 { char * mid=first+size*((last-first)/size >> 1); 421 Pivot(SWAP_nonaligned,size); 422 memcpy(pivot,mid,size); 423 } 424 /* Partition. */ 425 Partition(SWAP_nonaligned,size); 426 /* Prepare to recurse/iterate. */ 427 Recurse(trunc) 428 } 429 } 430 PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size); 431 Insertion(SWAP_nonaligned); 432 free(pivot); 433} 434 435static void qsort_aligned(void *base, size_t nmemb, size_t size, 436 int (*compare)(const void *, const void *)) { 437 438 stack_entry stack[STACK_SIZE]; 439 int stacktop=0; 440 char *first,*last; 441 char *pivot=malloc(size); 442 size_t trunc=TRUNC_aligned*size; 443 assert(pivot!=0); 444 445 first=(char*)base; last=first+(nmemb-1)*size; 446 447 if ((size_t)(last-first)>=trunc) { 448 char *ffirst=first,*llast=last; 449 while (1) { 450 /* Select pivot */ 451 { char * mid=first+size*((last-first)/size >> 1); 452 Pivot(SWAP_aligned,size); 453 memcpy(pivot,mid,size); 454 } 455 /* Partition. */ 456 Partition(SWAP_aligned,size); 457 /* Prepare to recurse/iterate. */ 458 Recurse(trunc) 459 } 460 } 461 PreInsertion(SWAP_aligned,TRUNC_aligned,size); 462 Insertion(SWAP_aligned); 463 free(pivot); 464} 465 466static void qsort_words(void *base, size_t nmemb, 467 int (*compare)(const void *, const void *)) { 468 469 stack_entry stack[STACK_SIZE]; 470 int stacktop=0; 471 char *first,*last; 472 char *pivot=malloc(WORD_BYTES); 473 assert(pivot!=0); 474 475 first=(char*)base; last=first+(nmemb-1)*WORD_BYTES; 476 477 if (last-first>=TRUNC_words) { 478 char *ffirst=first, *llast=last; 479 while (1) { 480#ifdef DEBUG_QSORT 481fprintf(stderr,"Doing %d:%d: ", 482 (first-(char*)base)/WORD_BYTES, 483 (last-(char*)base)/WORD_BYTES); 484#endif 485 /* Select pivot */ 486 { char * mid=first+WORD_BYTES*((last-first) / (2*WORD_BYTES)); 487 Pivot(SWAP_words,WORD_BYTES); 488 *(int*)pivot=*(int*)mid; 489#ifdef DEBUG_QSORT 490fprintf(stderr,"pivot = %p = #%lu = %d\n", mid, (unsigned long)(((int*)mid)-((int*)base)), *(int*)mid); 491#endif 492 } 493 /* Partition. */ 494 Partition(SWAP_words,WORD_BYTES); 495#ifdef DEBUG_QSORT 496fprintf(stderr, "after partitioning first=#%lu last=#%lu\n", (first-(char*)base)/4lu, (last-(char*)base)/4lu); 497#endif 498 /* Prepare to recurse/iterate. */ 499 Recurse(TRUNC_words) 500 } 501 } 502 PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES); 503 /* Now do insertion sort. */ 504 last=((char*)base)+nmemb*WORD_BYTES; 505 for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) { 506 /* Find the right place for |first|. My apologies for var reuse */ 507 int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first; 508 *(int*)pivot=*(int*)first; 509 for (;compare(pl,pivot)>0;pr=pl,--pl) { 510 *pr=*pl; } 511 if (pr!=(int*)first) *pr=*(int*)pivot; 512 } 513 free(pivot); 514} 515 516/* ---------------------------------------------------------------------- */ 517 518extern void qsortG(void *base, size_t nmemb, size_t size, 519 int (*compare)(const void *, const void *)) { 520 521 if (nmemb<=1) return; 522 if (((size_t)base|size)&(WORD_BYTES-1)) 523 qsort_nonaligned(base,nmemb,size,compare); 524 else if (size!=WORD_BYTES) 525 qsort_aligned(base,nmemb,size,compare); 526 else 527 qsort_words(base,nmemb,compare); 528} 529 530 531#endif /* HAVE_QSORT */ 532 533/* vi: set ts=4 sw=4 expandtab: */ 534 535[FILE END](C) 2025 0x4248 (C) 2025 4248 Media and 4248 Systems, All part of 0x4248 See LICENCE files for more information. Not all files are by 0x4248 always check Licencing.