Mercurial > sdl-ios-xcode
comparison src/stdlib/SDL_qsort.c @ 1337:c687f06c7473
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); |