src/stdlib/SDL_qsort.c
changeset 1336 3692456e7b0f
parent 1331 1cbaeee565b1
child 1337 c687f06c7473
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,