src/stdlib/SDL_qsort.c
changeset 1337 c687f06c7473
parent 1336 3692456e7b0f
child 1354 22f39393668a
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);