Mercurial > sdl-ios-xcode

comparison src/stdlib/SDL_qsort.c @ 1336:3692456e7b0f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Use SDL_ prefixed versions of C library functions. FIXME: Change #include <stdlib.h> to #include "SDL_stdlib.h" Change #include <string.h> to #include "SDL_string.h" Make sure nothing else broke because of this...
author Sam Lantinga <slouken@libsdl.org>
date Tue, 07 Feb 2006 06:59:48 +0000
parents 1cbaeee565b1
children c687f06c7473
comparison
equal deleted inserted replaced
1335:c39265384763 1336:3692456e7b0f
231 test+=size; \ 231 test+=size; \
232 if (test!=first) { \ 232 if (test!=first) { \
233 /* Shift everything in [test,first) \ 233 /* Shift everything in [test,first) \
234 * up by one, and place |first| \ 234 * up by one, and place |first| \
235 * where |test| is. */ \ 235 * where |test| is. */ \
236 memcpy(pivot,first,size); \ 236 SDL_memcpy(pivot,first,size); \
237 memmove(test+size,test,first-test); \ 237 SDL_memmove(test+size,test,first-test); \
238 memcpy(test,pivot,size); \ 238 SDL_memcpy(test,pivot,size); \
239 } \ 239 } \
240 } 240 }
241 241
242 #define SWAP_nonaligned(a,b) { \ 242 #define SWAP_nonaligned(a,b) { \
243 register char *aa=(a),*bb=(b); \ 243 register char *aa=(a),*bb=(b); \
296 int (*compare)(const void *, const void *)) { 296 int (*compare)(const void *, const void *)) {
297 297
298 stack_entry stack[STACK_SIZE]; 298 stack_entry stack[STACK_SIZE];
299 int stacktop=0; 299 int stacktop=0;
300 char *first,*last; 300 char *first,*last;
301 char *pivot=malloc(size); 301 char *pivot=SDL_malloc(size);
302 size_t trunc=TRUNC_nonaligned*size; 302 size_t trunc=TRUNC_nonaligned*size;
303 assert(pivot!=0); 303 assert(pivot!=0);
304 304
305 first=(char*)base; last=first+(nmemb-1)*size; 305 first=(char*)base; last=first+(nmemb-1)*size;
306 306
308 char *ffirst=first, *llast=last; 308 char *ffirst=first, *llast=last;
309 while (1) { 309 while (1) {
310 /* Select pivot */ 310 /* Select pivot */
311 { char * mid=first+size*((last-first)/size >> 1); 311 { char * mid=first+size*((last-first)/size >> 1);
312 Pivot(SWAP_nonaligned,size); 312 Pivot(SWAP_nonaligned,size);
313 memcpy(pivot,mid,size); 313 SDL_memcpy(pivot,mid,size);
314 } 314 }
315 /* Partition. */ 315 /* Partition. */
316 Partition(SWAP_nonaligned,size); 316 Partition(SWAP_nonaligned,size);
317 /* Prepare to recurse/iterate. */ 317 /* Prepare to recurse/iterate. */
318 Recurse(trunc) 318 Recurse(trunc)
319 } 319 }
320 } 320 }
321 PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size); 321 PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size);
322 Insertion(SWAP_nonaligned); 322 Insertion(SWAP_nonaligned);
323 free(pivot); 323 SDL_free(pivot);
324 } 324 }
325 325
326 static void qsort_aligned(void *base, size_t nmemb, size_t size, 326 static void qsort_aligned(void *base, size_t nmemb, size_t size,
327 int (*compare)(const void *, const void *)) { 327 int (*compare)(const void *, const void *)) {
328 328
329 stack_entry stack[STACK_SIZE]; 329 stack_entry stack[STACK_SIZE];
330 int stacktop=0; 330 int stacktop=0;
331 char *first,*last; 331 char *first,*last;
332 char *pivot=malloc(size); 332 char *pivot=SDL_malloc(size);
333 size_t trunc=TRUNC_aligned*size; 333 size_t trunc=TRUNC_aligned*size;
334 assert(pivot!=0); 334 assert(pivot!=0);
335 335
336 first=(char*)base; last=first+(nmemb-1)*size; 336 first=(char*)base; last=first+(nmemb-1)*size;
337 337
339 char *ffirst=first,*llast=last; 339 char *ffirst=first,*llast=last;
340 while (1) { 340 while (1) {
341 /* Select pivot */ 341 /* Select pivot */
342 { char * mid=first+size*((last-first)/size >> 1); 342 { char * mid=first+size*((last-first)/size >> 1);
343 Pivot(SWAP_aligned,size); 343 Pivot(SWAP_aligned,size);
344 memcpy(pivot,mid,size); 344 SDL_memcpy(pivot,mid,size);
345 } 345 }
346 /* Partition. */ 346 /* Partition. */
347 Partition(SWAP_aligned,size); 347 Partition(SWAP_aligned,size);
348 /* Prepare to recurse/iterate. */ 348 /* Prepare to recurse/iterate. */
349 Recurse(trunc) 349 Recurse(trunc)
350 } 350 }
351 } 351 }
352 PreInsertion(SWAP_aligned,TRUNC_aligned,size); 352 PreInsertion(SWAP_aligned,TRUNC_aligned,size);
353 Insertion(SWAP_aligned); 353 Insertion(SWAP_aligned);
354 free(pivot); 354 SDL_free(pivot);
355 } 355 }
356 356
357 static void qsort_words(void *base, size_t nmemb, 357 static void qsort_words(void *base, size_t nmemb,
358 int (*compare)(const void *, const void *)) { 358 int (*compare)(const void *, const void *)) {
359 359
360 stack_entry stack[STACK_SIZE]; 360 stack_entry stack[STACK_SIZE];
361 int stacktop=0; 361 int stacktop=0;
362 char *first,*last; 362 char *first,*last;
363 char *pivot=malloc(WORD_BYTES); 363 char *pivot=SDL_malloc(WORD_BYTES);
364 assert(pivot!=0); 364 assert(pivot!=0);
365 365
366 first=(char*)base; last=first+(nmemb-1)*WORD_BYTES; 366 first=(char*)base; last=first+(nmemb-1)*WORD_BYTES;
367 367
368 if (last-first>TRUNC_words) { 368 if (last-first>TRUNC_words) {
396 *(int*)pivot=*(int*)first; 396 *(int*)pivot=*(int*)first;
397 for (;compare(pl,pivot)>0;pr=pl,--pl) { 397 for (;compare(pl,pivot)>0;pr=pl,--pl) {
398 *pr=*pl; } 398 *pr=*pl; }
399 if (pr!=(int*)first) *pr=*(int*)pivot; 399 if (pr!=(int*)first) *pr=*(int*)pivot;
400 } 400 }
401 free(pivot); 401 SDL_free(pivot);
402 } 402 }
403 403
404 /* ---------------------------------------------------------------------- */ 404 /* ---------------------------------------------------------------------- */
405 405
406 void SDL_qsort(void *base, size_t nmemb, size_t size, 406 void SDL_qsort(void *base, size_t nmemb, size_t size,