Mercurial > sdl-ios-xcode
comparison src/stdlib/SDL_qsort.c @ 1895:c121d94672cb
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: */ |