Mercurial > sdl-ios-xcode

comparison src/stdlib/SDL_qsort.c @ 1895:c121d94672cb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
SDL 1.2 is moving to a branch, and SDL 1.3 is becoming the head.
author Sam Lantinga <slouken@libsdl.org>
date Mon, 10 Jul 2006 21:04:37 +0000
parents 84de7511f79f
children dc1eb82ffdaa
comparison
equal deleted inserted replaced
1894:c69cee13dd76 1895:c121d94672cb
58 #define qsort SDL_qsort 58 #define qsort SDL_qsort
59 59
60 60
61 #ifndef HAVE_QSORT 61 #ifndef HAVE_QSORT
62 62
63 static char _ID[]="<qsort.c gjm 1.12 1998-03-19>"; 63 static char _ID[] = "<qsort.c gjm 1.12 1998-03-19>";
64 64
65 /* How many bytes are there per word? (Must be a power of 2, 65 /* How many bytes are there per word? (Must be a power of 2,
66 * and must in fact equal sizeof(int).) 66 * and must in fact equal sizeof(int).)
67 */ 67 */
68 #define WORD_BYTES sizeof(int) 68 #define WORD_BYTES sizeof(int)
79 * value might work well for the other two cases. Of course 79 * value might work well for the other two cases. Of course
80 * what works well on my machine might work badly on yours. 80 * what works well on my machine might work badly on yours.
81 */ 81 */
82 #define TRUNC_nonaligned 12 82 #define TRUNC_nonaligned 12
83 #define TRUNC_aligned 12 83 #define TRUNC_aligned 12
84 #define TRUNC_words 12*WORD_BYTES /* nb different meaning */ 84 #define TRUNC_words 12*WORD_BYTES /* nb different meaning */
85 85
86 /* We use a simple pivoting algorithm for shortish sub-arrays 86 /* We use a simple pivoting algorithm for shortish sub-arrays
87 * and a more complicated one for larger ones. The threshold 87 * and a more complicated one for larger ones. The threshold
88 * is PIVOT_THRESHOLD. 88 * is PIVOT_THRESHOLD.
89 */ 89 */
90 #define PIVOT_THRESHOLD 40 90 #define PIVOT_THRESHOLD 40
91 91
92 typedef struct { char * first; char * last; } stack_entry; 92 typedef struct
93 {
94 char *first;
95 char *last;
96 } stack_entry;
93 #define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;} 97 #define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;}
94 #define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;} 98 #define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;}
95 #define doLeft {first=ffirst;llast=last;continue;} 99 #define doLeft {first=ffirst;llast=last;continue;}
96 #define doRight {ffirst=first;last=llast;continue;} 100 #define doRight {ffirst=first;last=llast;continue;}
97 #define pop {if (--stacktop<0) break;\ 101 #define pop {if (--stacktop<0) break;\
259 #define SWAP_words(a,b) { \ 263 #define SWAP_words(a,b) { \
260 register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; } 264 register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; }
261 265
262 /* ---------------------------------------------------------------------- */ 266 /* ---------------------------------------------------------------------- */
263 267
264 static char * pivot_big(char *first, char *mid, char *last, size_t size, 268 static char *
265 int compare(const void *, const void *)) { 269 pivot_big(char *first, char *mid, char *last, size_t size,
266 size_t d=(((last-first)/size)>>3)*size; 270 int compare(const void *, const void *))
267 char *m1,*m2,*m3; 271 {
268 { char *a=first, *b=first+d, *c=first+2*d; 272 size_t d = (((last - first) / size) >> 3) * size;
269 #ifdef DEBUG_QSORT 273 char *m1, *m2, *m3;
270 fprintf(stderr,"< %d %d %d\n",*(int*)a,*(int*)b,*(int*)c); 274 {
271 #endif 275 char *a = first, *b = first + d, *c = first + 2 * d;
272 m1 = compare(a,b)<0 ? 276 #ifdef DEBUG_QSORT
273 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) 277 fprintf(stderr, "< %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
274 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); 278 #endif
275 } 279 m1 = compare(a, b) < 0 ?
276 { char *a=mid-d, *b=mid, *c=mid+d; 280 (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
277 #ifdef DEBUG_QSORT 281 : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
278 fprintf(stderr,". %d %d %d\n",*(int*)a,*(int*)b,*(int*)c); 282 }
279 #endif 283 {
280 m2 = compare(a,b)<0 ? 284 char *a = mid - d, *b = mid, *c = mid + d;
281 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) 285 #ifdef DEBUG_QSORT
282 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); 286 fprintf(stderr, ". %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
283 } 287 #endif
284 { char *a=last-2*d, *b=last-d, *c=last; 288 m2 = compare(a, b) < 0 ?
285 #ifdef DEBUG_QSORT 289 (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
286 fprintf(stderr,"> %d %d %d\n",*(int*)a,*(int*)b,*(int*)c); 290 : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
287 #endif 291 }
288 m3 = compare(a,b)<0 ? 292 {
289 (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) 293 char *a = last - 2 * d, *b = last - d, *c = last;
290 : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); 294 #ifdef DEBUG_QSORT
291 } 295 fprintf(stderr, "> %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
292 #ifdef DEBUG_QSORT 296 #endif
293 fprintf(stderr,"-> %d %d %d\n",*(int*)m1,*(int*)m2,*(int*)m3); 297 m3 = compare(a, b) < 0 ?
294 #endif 298 (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
295 return compare(m1,m2)<0 ? 299 : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
296 (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1)) 300 }
297 : (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2)); 301 #ifdef DEBUG_QSORT
302 fprintf(stderr, "-> %d %d %d\n", *(int *) m1, *(int *) m2, *(int *) m3);
303 #endif
304 return compare(m1, m2) < 0 ?
305 (compare(m2, m3) < 0 ? m2 : (compare(m1, m3) < 0 ? m3 : m1))
306 : (compare(m1, m3) < 0 ? m1 : (compare(m2, m3) < 0 ? m3 : m2));
298 } 307 }
299 308
300 /* ---------------------------------------------------------------------- */ 309 /* ---------------------------------------------------------------------- */
301 310
302 static void qsort_nonaligned(void *base, size_t nmemb, size_t size, 311 static void
303 int (*compare)(const void *, const void *)) { 312 qsort_nonaligned(void *base, size_t nmemb, size_t size,
304 313 int (*compare) (const void *, const void *))
305 stack_entry stack[STACK_SIZE]; 314 {
306 int stacktop=0; 315
307 char *first,*last; 316 stack_entry stack[STACK_SIZE];
308 char *pivot=malloc(size); 317 int stacktop = 0;
309 size_t trunc=TRUNC_nonaligned*size; 318 char *first, *last;
310 assert(pivot!=0); 319 char *pivot = malloc(size);
311 320 size_t trunc = TRUNC_nonaligned * size;
312 first=(char*)base; last=first+(nmemb-1)*size; 321 assert(pivot != 0);
313 322
314 if ((size_t)(last-first)>trunc) { 323 first = (char *) base;
315 char *ffirst=first, *llast=last; 324 last = first + (nmemb - 1) * size;
316 while (1) { 325
317 /* Select pivot */ 326 if ((size_t) (last - first) > trunc) {
318 { char * mid=first+size*((last-first)/size >> 1); 327 char *ffirst = first, *llast = last;
319 Pivot(SWAP_nonaligned,size); 328 while (1) {
320 memcpy(pivot,mid,size); 329 /* Select pivot */
321 } 330 {
322 /* Partition. */ 331 char *mid = first + size * ((last - first) / size >> 1);
323 Partition(SWAP_nonaligned,size); 332 Pivot(SWAP_nonaligned, size);
324 /* Prepare to recurse/iterate. */ 333 memcpy(pivot, mid, size);
325 Recurse(trunc) 334 }
326 } 335 /* Partition. */
327 } 336 Partition(SWAP_nonaligned, size);
328 PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size); 337 /* Prepare to recurse/iterate. */
329 Insertion(SWAP_nonaligned); 338 Recurse(trunc)}
330 free(pivot); 339 }
331 } 340 PreInsertion(SWAP_nonaligned, TRUNC_nonaligned, size);
332 341 Insertion(SWAP_nonaligned);
333 static void qsort_aligned(void *base, size_t nmemb, size_t size, 342 free(pivot);
334 int (*compare)(const void *, const void *)) { 343 }
335 344
336 stack_entry stack[STACK_SIZE]; 345 static void
337 int stacktop=0; 346 qsort_aligned(void *base, size_t nmemb, size_t size,
338 char *first,*last; 347 int (*compare) (const void *, const void *))
339 char *pivot=malloc(size); 348 {
340 size_t trunc=TRUNC_aligned*size; 349
341 assert(pivot!=0); 350 stack_entry stack[STACK_SIZE];
342 351 int stacktop = 0;
343 first=(char*)base; last=first+(nmemb-1)*size; 352 char *first, *last;
344 353 char *pivot = malloc(size);
345 if ((size_t)(last-first)>trunc) { 354 size_t trunc = TRUNC_aligned * size;
346 char *ffirst=first,*llast=last; 355 assert(pivot != 0);
347 while (1) { 356
348 /* Select pivot */ 357 first = (char *) base;
349 { char * mid=first+size*((last-first)/size >> 1); 358 last = first + (nmemb - 1) * size;
350 Pivot(SWAP_aligned,size); 359
351 memcpy(pivot,mid,size); 360 if ((size_t) (last - first) > trunc) {
352 } 361 char *ffirst = first, *llast = last;
353 /* Partition. */ 362 while (1) {
354 Partition(SWAP_aligned,size); 363 /* Select pivot */
355 /* Prepare to recurse/iterate. */ 364 {
356 Recurse(trunc) 365 char *mid = first + size * ((last - first) / size >> 1);
357 } 366 Pivot(SWAP_aligned, size);
358 } 367 memcpy(pivot, mid, size);
359 PreInsertion(SWAP_aligned,TRUNC_aligned,size); 368 }
360 Insertion(SWAP_aligned); 369 /* Partition. */
361 free(pivot); 370 Partition(SWAP_aligned, size);
362 } 371 /* Prepare to recurse/iterate. */
363 372 Recurse(trunc)}
364 static void qsort_words(void *base, size_t nmemb, 373 }
365 int (*compare)(const void *, const void *)) { 374 PreInsertion(SWAP_aligned, TRUNC_aligned, size);
366 375 Insertion(SWAP_aligned);
367 stack_entry stack[STACK_SIZE]; 376 free(pivot);
368 int stacktop=0; 377 }
369 char *first,*last; 378
370 char *pivot=malloc(WORD_BYTES); 379 static void
371 assert(pivot!=0); 380 qsort_words(void *base, size_t nmemb,
372 381 int (*compare) (const void *, const void *))
373 first=(char*)base; last=first+(nmemb-1)*WORD_BYTES; 382 {
374 383
375 if (last-first>TRUNC_words) { 384 stack_entry stack[STACK_SIZE];
376 char *ffirst=first, *llast=last; 385 int stacktop = 0;
377 while (1) { 386 char *first, *last;
378 #ifdef DEBUG_QSORT 387 char *pivot = malloc(WORD_BYTES);
379 fprintf(stderr,"Doing %d:%d: ", 388 assert(pivot != 0);
380 (first-(char*)base)/WORD_BYTES, 389
381 (last-(char*)base)/WORD_BYTES); 390 first = (char *) base;
382 #endif 391 last = first + (nmemb - 1) * WORD_BYTES;
383 /* Select pivot */ 392
384 { char * mid=first+WORD_BYTES*((last-first) / (2*WORD_BYTES)); 393 if (last - first > TRUNC_words) {
385 Pivot(SWAP_words,WORD_BYTES); 394 char *ffirst = first, *llast = last;
386 *(int*)pivot=*(int*)mid; 395 while (1) {
387 } 396 #ifdef DEBUG_QSORT
388 #ifdef DEBUG_QSORT 397 fprintf(stderr, "Doing %d:%d: ",
389 fprintf(stderr,"pivot=%d\n",*(int*)pivot); 398 (first - (char *) base) / WORD_BYTES,
390 #endif 399 (last - (char *) base) / WORD_BYTES);
391 /* Partition. */ 400 #endif
392 Partition(SWAP_words,WORD_BYTES); 401 /* Select pivot */
393 /* Prepare to recurse/iterate. */ 402 {
394 Recurse(TRUNC_words) 403 char *mid =
395 } 404 first + WORD_BYTES * ((last - first) / (2 * WORD_BYTES));
396 } 405 Pivot(SWAP_words, WORD_BYTES);
397 PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES); 406 *(int *) pivot = *(int *) mid;
398 /* Now do insertion sort. */ 407 }
399 last=((char*)base)+nmemb*WORD_BYTES; 408 #ifdef DEBUG_QSORT
400 for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) { 409 fprintf(stderr, "pivot=%d\n", *(int *) pivot);
401 /* Find the right place for |first|. My apologies for var reuse */ 410 #endif
402 int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first; 411 /* Partition. */
403 *(int*)pivot=*(int*)first; 412 Partition(SWAP_words, WORD_BYTES);
404 for (;compare(pl,pivot)>0;pr=pl,--pl) { 413 /* Prepare to recurse/iterate. */
405 *pr=*pl; } 414 Recurse(TRUNC_words)}
406 if (pr!=(int*)first) *pr=*(int*)pivot; 415 }
407 } 416 PreInsertion(SWAP_words, (TRUNC_words / WORD_BYTES), WORD_BYTES);
408 free(pivot); 417 /* Now do insertion sort. */
418 last = ((char *) base) + nmemb * WORD_BYTES;
419 for (first = ((char *) base) + WORD_BYTES; first != last;
420 first += WORD_BYTES) {
421 /* Find the right place for |first|. My apologies for var reuse */
422 int *pl = (int *) (first - WORD_BYTES), *pr = (int *) first;
423 *(int *) pivot = *(int *) first;
424 for (; compare(pl, pivot) > 0; pr = pl, --pl) {
425 *pr = *pl;
426 }
427 if (pr != (int *) first)
428 *pr = *(int *) pivot;
429 }
430 free(pivot);
409 } 431 }
410 432
411 /* ---------------------------------------------------------------------- */ 433 /* ---------------------------------------------------------------------- */
412 434
413 void qsort(void *base, size_t nmemb, size_t size, 435 void
414 int (*compare)(const void *, const void *)) { 436 qsort(void *base, size_t nmemb, size_t size,
415 437 int (*compare) (const void *, const void *))
416 if (nmemb<=1) return; 438 {
417 if (((uintptr_t)base|size)&(WORD_BYTES-1)) 439
418 qsort_nonaligned(base,nmemb,size,compare); 440 if (nmemb <= 1)
419 else if (size!=WORD_BYTES) 441 return;
420 qsort_aligned(base,nmemb,size,compare); 442 if (((uintptr_t) base | size) & (WORD_BYTES - 1))
421 else 443 qsort_nonaligned(base, nmemb, size, compare);
422 qsort_words(base,nmemb,compare); 444 else if (size != WORD_BYTES)
445 qsort_aligned(base, nmemb, size, compare);
446 else
447 qsort_words(base, nmemb, compare);
423 } 448 }
424 449
425 #endif /* !HAVE_QSORT */ 450 #endif /* !HAVE_QSORT */
451 /* vi: set ts=4 sw=4 expandtab: */