Mercurial > sdl-ios-xcode

comparison src/stdlib/SDL_qsort.c @ 1337:c687f06c7473

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Don't touch code that we brought in from other sources
author Sam Lantinga <slouken@libsdl.org>
date Tue, 07 Feb 2006 07:03:29 +0000
parents 3692456e7b0f
children 22f39393668a
comparison
equal deleted inserted replaced
1336:3692456e7b0f 1337:c687f06c7473
45 /* 45 /*
46 #include <assert.h> 46 #include <assert.h>
47 #include <stdlib.h> 47 #include <stdlib.h>
48 #include <string.h> 48 #include <string.h>
49 */ 49 */
50 #define assert(X)
51 #include "SDL_stdlib.h" 50 #include "SDL_stdlib.h"
52 #include "SDL_string.h" 51 #include "SDL_string.h"
52
53 #define assert(X)
54 #define malloc SDL_malloc
55 #define free SDL_free
56 #define memcpy SDL_memcpy
57 #define memmove SDL_memmove
58 #define qsort SDL_qsort
59
53 60
54 #ifndef HAVE_QSORT 61 #ifndef HAVE_QSORT
55 62
56 static char _ID[]="<qsort.c gjm 1.12 1998-03-19>"; 63 static char _ID[]="<qsort.c gjm 1.12 1998-03-19>";
57 64
231 test+=size; \ 238 test+=size; \
232 if (test!=first) { \ 239 if (test!=first) { \
233 /* Shift everything in [test,first) \ 240 /* Shift everything in [test,first) \
234 * up by one, and place |first| \ 241 * up by one, and place |first| \
235 * where |test| is. */ \ 242 * where |test| is. */ \
236 SDL_memcpy(pivot,first,size); \ 243 memcpy(pivot,first,size); \
237 SDL_memmove(test+size,test,first-test); \ 244 memmove(test+size,test,first-test); \
238 SDL_memcpy(test,pivot,size); \ 245 memcpy(test,pivot,size); \
239 } \ 246 } \
240 } 247 }
241 248
242 #define SWAP_nonaligned(a,b) { \ 249 #define SWAP_nonaligned(a,b) { \
243 register char *aa=(a),*bb=(b); \ 250 register char *aa=(a),*bb=(b); \
296 int (*compare)(const void *, const void *)) { 303 int (*compare)(const void *, const void *)) {
297 304
298 stack_entry stack[STACK_SIZE]; 305 stack_entry stack[STACK_SIZE];
299 int stacktop=0; 306 int stacktop=0;
300 char *first,*last; 307 char *first,*last;
301 char *pivot=SDL_malloc(size); 308 char *pivot=malloc(size);
302 size_t trunc=TRUNC_nonaligned*size; 309 size_t trunc=TRUNC_nonaligned*size;
303 assert(pivot!=0); 310 assert(pivot!=0);
304 311
305 first=(char*)base; last=first+(nmemb-1)*size; 312 first=(char*)base; last=first+(nmemb-1)*size;
306 313
308 char *ffirst=first, *llast=last; 315 char *ffirst=first, *llast=last;
309 while (1) { 316 while (1) {
310 /* Select pivot */ 317 /* Select pivot */
311 { char * mid=first+size*((last-first)/size >> 1); 318 { char * mid=first+size*((last-first)/size >> 1);
312 Pivot(SWAP_nonaligned,size); 319 Pivot(SWAP_nonaligned,size);
313 SDL_memcpy(pivot,mid,size); 320 memcpy(pivot,mid,size);
314 } 321 }
315 /* Partition. */ 322 /* Partition. */
316 Partition(SWAP_nonaligned,size); 323 Partition(SWAP_nonaligned,size);
317 /* Prepare to recurse/iterate. */ 324 /* Prepare to recurse/iterate. */
318 Recurse(trunc) 325 Recurse(trunc)
319 } 326 }
320 } 327 }
321 PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size); 328 PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size);
322 Insertion(SWAP_nonaligned); 329 Insertion(SWAP_nonaligned);
323 SDL_free(pivot); 330 free(pivot);
324 } 331 }
325 332
326 static void qsort_aligned(void *base, size_t nmemb, size_t size, 333 static void qsort_aligned(void *base, size_t nmemb, size_t size,
327 int (*compare)(const void *, const void *)) { 334 int (*compare)(const void *, const void *)) {
328 335
329 stack_entry stack[STACK_SIZE]; 336 stack_entry stack[STACK_SIZE];
330 int stacktop=0; 337 int stacktop=0;
331 char *first,*last; 338 char *first,*last;
332 char *pivot=SDL_malloc(size); 339 char *pivot=malloc(size);
333 size_t trunc=TRUNC_aligned*size; 340 size_t trunc=TRUNC_aligned*size;
334 assert(pivot!=0); 341 assert(pivot!=0);
335 342
336 first=(char*)base; last=first+(nmemb-1)*size; 343 first=(char*)base; last=first+(nmemb-1)*size;
337 344
339 char *ffirst=first,*llast=last; 346 char *ffirst=first,*llast=last;
340 while (1) { 347 while (1) {
341 /* Select pivot */ 348 /* Select pivot */
342 { char * mid=first+size*((last-first)/size >> 1); 349 { char * mid=first+size*((last-first)/size >> 1);
343 Pivot(SWAP_aligned,size); 350 Pivot(SWAP_aligned,size);
344 SDL_memcpy(pivot,mid,size); 351 memcpy(pivot,mid,size);
345 } 352 }
346 /* Partition. */ 353 /* Partition. */
347 Partition(SWAP_aligned,size); 354 Partition(SWAP_aligned,size);
348 /* Prepare to recurse/iterate. */ 355 /* Prepare to recurse/iterate. */
349 Recurse(trunc) 356 Recurse(trunc)
350 } 357 }
351 } 358 }
352 PreInsertion(SWAP_aligned,TRUNC_aligned,size); 359 PreInsertion(SWAP_aligned,TRUNC_aligned,size);
353 Insertion(SWAP_aligned); 360 Insertion(SWAP_aligned);
354 SDL_free(pivot); 361 free(pivot);
355 } 362 }
356 363
357 static void qsort_words(void *base, size_t nmemb, 364 static void qsort_words(void *base, size_t nmemb,
358 int (*compare)(const void *, const void *)) { 365 int (*compare)(const void *, const void *)) {
359 366
360 stack_entry stack[STACK_SIZE]; 367 stack_entry stack[STACK_SIZE];
361 int stacktop=0; 368 int stacktop=0;
362 char *first,*last; 369 char *first,*last;
363 char *pivot=SDL_malloc(WORD_BYTES); 370 char *pivot=malloc(WORD_BYTES);
364 assert(pivot!=0); 371 assert(pivot!=0);
365 372
366 first=(char*)base; last=first+(nmemb-1)*WORD_BYTES; 373 first=(char*)base; last=first+(nmemb-1)*WORD_BYTES;
367 374
368 if (last-first>TRUNC_words) { 375 if (last-first>TRUNC_words) {
396 *(int*)pivot=*(int*)first; 403 *(int*)pivot=*(int*)first;
397 for (;compare(pl,pivot)>0;pr=pl,--pl) { 404 for (;compare(pl,pivot)>0;pr=pl,--pl) {
398 *pr=*pl; } 405 *pr=*pl; }
399 if (pr!=(int*)first) *pr=*(int*)pivot; 406 if (pr!=(int*)first) *pr=*(int*)pivot;
400 } 407 }
401 SDL_free(pivot); 408 free(pivot);
402 } 409 }
403 410
404 /* ---------------------------------------------------------------------- */ 411 /* ---------------------------------------------------------------------- */
405 412
406 void SDL_qsort(void *base, size_t nmemb, size_t size, 413 void qsort(void *base, size_t nmemb, size_t size,
407 int (*compare)(const void *, const void *)) { 414 int (*compare)(const void *, const void *)) {
408 415
409 if (nmemb<=1) return; 416 if (nmemb<=1) return;
410 if (((int)base|size)&(WORD_BYTES-1)) 417 if (((int)base|size)&(WORD_BYTES-1))
411 qsort_nonaligned(base,nmemb,size,compare); 418 qsort_nonaligned(base,nmemb,size,compare);