1.1 --- a/src/stdlib/SDL_qsort.c Thu Jul 06 18:01:37 2006 +0000
1.2 +++ b/src/stdlib/SDL_qsort.c Mon Jul 10 21:04:37 2006 +0000
1.3 @@ -60,7 +60,7 @@
1.4
1.5 #ifndef HAVE_QSORT
1.6
1.7 -static char _ID[]="<qsort.c gjm 1.12 1998-03-19>";
1.8 +static char _ID[] = "<qsort.c gjm 1.12 1998-03-19>";
1.9
1.10 /* How many bytes are there per word? (Must be a power of 2,
1.11 * and must in fact equal sizeof(int).)
1.12 @@ -81,7 +81,7 @@
1.13 */
1.14 #define TRUNC_nonaligned 12
1.15 #define TRUNC_aligned 12
1.16 -#define TRUNC_words 12*WORD_BYTES /* nb different meaning */
1.17 +#define TRUNC_words 12*WORD_BYTES /* nb different meaning */
1.18
1.19 /* We use a simple pivoting algorithm for shortish sub-arrays
1.20 * and a more complicated one for larger ones. The threshold
1.21 @@ -89,7 +89,11 @@
1.22 */
1.23 #define PIVOT_THRESHOLD 40
1.24
1.25 -typedef struct { char * first; char * last; } stack_entry;
1.26 +typedef struct
1.27 +{
1.28 + char *first;
1.29 + char *last;
1.30 +} stack_entry;
1.31 #define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;}
1.32 #define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;}
1.33 #define doLeft {first=ffirst;llast=last;continue;}
1.34 @@ -261,165 +265,187 @@
1.35
1.36 /* ---------------------------------------------------------------------- */
1.37
1.38 -static char * pivot_big(char *first, char *mid, char *last, size_t size,
1.39 - int compare(const void *, const void *)) {
1.40 - size_t d=(((last-first)/size)>>3)*size;
1.41 - char *m1,*m2,*m3;
1.42 - { char *a=first, *b=first+d, *c=first+2*d;
1.43 +static char *
1.44 +pivot_big(char *first, char *mid, char *last, size_t size,
1.45 + int compare(const void *, const void *))
1.46 +{
1.47 + size_t d = (((last - first) / size) >> 3) * size;
1.48 + char *m1, *m2, *m3;
1.49 + {
1.50 + char *a = first, *b = first + d, *c = first + 2 * d;
1.51 #ifdef DEBUG_QSORT
1.52 -fprintf(stderr,"< %d %d %d\n",*(int*)a,*(int*)b,*(int*)c);
1.53 + fprintf(stderr, "< %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
1.54 #endif
1.55 - m1 = compare(a,b)<0 ?
1.56 - (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
1.57 - : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
1.58 - }
1.59 - { char *a=mid-d, *b=mid, *c=mid+d;
1.60 + m1 = compare(a, b) < 0 ?
1.61 + (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
1.62 + : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
1.63 + }
1.64 + {
1.65 + char *a = mid - d, *b = mid, *c = mid + d;
1.66 #ifdef DEBUG_QSORT
1.67 -fprintf(stderr,". %d %d %d\n",*(int*)a,*(int*)b,*(int*)c);
1.68 + fprintf(stderr, ". %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
1.69 #endif
1.70 - m2 = compare(a,b)<0 ?
1.71 - (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
1.72 - : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
1.73 - }
1.74 - { char *a=last-2*d, *b=last-d, *c=last;
1.75 + m2 = compare(a, b) < 0 ?
1.76 + (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
1.77 + : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
1.78 + }
1.79 + {
1.80 + char *a = last - 2 * d, *b = last - d, *c = last;
1.81 #ifdef DEBUG_QSORT
1.82 -fprintf(stderr,"> %d %d %d\n",*(int*)a,*(int*)b,*(int*)c);
1.83 + fprintf(stderr, "> %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
1.84 #endif
1.85 - m3 = compare(a,b)<0 ?
1.86 - (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
1.87 - : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
1.88 - }
1.89 + m3 = compare(a, b) < 0 ?
1.90 + (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
1.91 + : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
1.92 + }
1.93 #ifdef DEBUG_QSORT
1.94 -fprintf(stderr,"-> %d %d %d\n",*(int*)m1,*(int*)m2,*(int*)m3);
1.95 + fprintf(stderr, "-> %d %d %d\n", *(int *) m1, *(int *) m2, *(int *) m3);
1.96 #endif
1.97 - return compare(m1,m2)<0 ?
1.98 - (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1))
1.99 - : (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2));
1.100 + return compare(m1, m2) < 0 ?
1.101 + (compare(m2, m3) < 0 ? m2 : (compare(m1, m3) < 0 ? m3 : m1))
1.102 + : (compare(m1, m3) < 0 ? m1 : (compare(m2, m3) < 0 ? m3 : m2));
1.103 }
1.104
1.105 /* ---------------------------------------------------------------------- */
1.106
1.107 -static void qsort_nonaligned(void *base, size_t nmemb, size_t size,
1.108 - int (*compare)(const void *, const void *)) {
1.109 +static void
1.110 +qsort_nonaligned(void *base, size_t nmemb, size_t size,
1.111 + int (*compare) (const void *, const void *))
1.112 +{
1.113
1.114 - stack_entry stack[STACK_SIZE];
1.115 - int stacktop=0;
1.116 - char *first,*last;
1.117 - char *pivot=malloc(size);
1.118 - size_t trunc=TRUNC_nonaligned*size;
1.119 - assert(pivot!=0);
1.120 + stack_entry stack[STACK_SIZE];
1.121 + int stacktop = 0;
1.122 + char *first, *last;
1.123 + char *pivot = malloc(size);
1.124 + size_t trunc = TRUNC_nonaligned * size;
1.125 + assert(pivot != 0);
1.126
1.127 - first=(char*)base; last=first+(nmemb-1)*size;
1.128 + first = (char *) base;
1.129 + last = first + (nmemb - 1) * size;
1.130
1.131 - if ((size_t)(last-first)>trunc) {
1.132 - char *ffirst=first, *llast=last;
1.133 - while (1) {
1.134 - /* Select pivot */
1.135 - { char * mid=first+size*((last-first)/size >> 1);
1.136 - Pivot(SWAP_nonaligned,size);
1.137 - memcpy(pivot,mid,size);
1.138 - }
1.139 - /* Partition. */
1.140 - Partition(SWAP_nonaligned,size);
1.141 - /* Prepare to recurse/iterate. */
1.142 - Recurse(trunc)
1.143 + if ((size_t) (last - first) > trunc) {
1.144 + char *ffirst = first, *llast = last;
1.145 + while (1) {
1.146 + /* Select pivot */
1.147 + {
1.148 + char *mid = first + size * ((last - first) / size >> 1);
1.149 + Pivot(SWAP_nonaligned, size);
1.150 + memcpy(pivot, mid, size);
1.151 + }
1.152 + /* Partition. */
1.153 + Partition(SWAP_nonaligned, size);
1.154 + /* Prepare to recurse/iterate. */
1.155 + Recurse(trunc)}
1.156 }
1.157 - }
1.158 - PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size);
1.159 - Insertion(SWAP_nonaligned);
1.160 - free(pivot);
1.161 + PreInsertion(SWAP_nonaligned, TRUNC_nonaligned, size);
1.162 + Insertion(SWAP_nonaligned);
1.163 + free(pivot);
1.164 }
1.165
1.166 -static void qsort_aligned(void *base, size_t nmemb, size_t size,
1.167 - int (*compare)(const void *, const void *)) {
1.168 +static void
1.169 +qsort_aligned(void *base, size_t nmemb, size_t size,
1.170 + int (*compare) (const void *, const void *))
1.171 +{
1.172
1.173 - stack_entry stack[STACK_SIZE];
1.174 - int stacktop=0;
1.175 - char *first,*last;
1.176 - char *pivot=malloc(size);
1.177 - size_t trunc=TRUNC_aligned*size;
1.178 - assert(pivot!=0);
1.179 + stack_entry stack[STACK_SIZE];
1.180 + int stacktop = 0;
1.181 + char *first, *last;
1.182 + char *pivot = malloc(size);
1.183 + size_t trunc = TRUNC_aligned * size;
1.184 + assert(pivot != 0);
1.185
1.186 - first=(char*)base; last=first+(nmemb-1)*size;
1.187 + first = (char *) base;
1.188 + last = first + (nmemb - 1) * size;
1.189
1.190 - if ((size_t)(last-first)>trunc) {
1.191 - char *ffirst=first,*llast=last;
1.192 - while (1) {
1.193 - /* Select pivot */
1.194 - { char * mid=first+size*((last-first)/size >> 1);
1.195 - Pivot(SWAP_aligned,size);
1.196 - memcpy(pivot,mid,size);
1.197 - }
1.198 - /* Partition. */
1.199 - Partition(SWAP_aligned,size);
1.200 - /* Prepare to recurse/iterate. */
1.201 - Recurse(trunc)
1.202 + if ((size_t) (last - first) > trunc) {
1.203 + char *ffirst = first, *llast = last;
1.204 + while (1) {
1.205 + /* Select pivot */
1.206 + {
1.207 + char *mid = first + size * ((last - first) / size >> 1);
1.208 + Pivot(SWAP_aligned, size);
1.209 + memcpy(pivot, mid, size);
1.210 + }
1.211 + /* Partition. */
1.212 + Partition(SWAP_aligned, size);
1.213 + /* Prepare to recurse/iterate. */
1.214 + Recurse(trunc)}
1.215 }
1.216 - }
1.217 - PreInsertion(SWAP_aligned,TRUNC_aligned,size);
1.218 - Insertion(SWAP_aligned);
1.219 - free(pivot);
1.220 + PreInsertion(SWAP_aligned, TRUNC_aligned, size);
1.221 + Insertion(SWAP_aligned);
1.222 + free(pivot);
1.223 }
1.224
1.225 -static void qsort_words(void *base, size_t nmemb,
1.226 - int (*compare)(const void *, const void *)) {
1.227 +static void
1.228 +qsort_words(void *base, size_t nmemb,
1.229 + int (*compare) (const void *, const void *))
1.230 +{
1.231
1.232 - stack_entry stack[STACK_SIZE];
1.233 - int stacktop=0;
1.234 - char *first,*last;
1.235 - char *pivot=malloc(WORD_BYTES);
1.236 - assert(pivot!=0);
1.237 + stack_entry stack[STACK_SIZE];
1.238 + int stacktop = 0;
1.239 + char *first, *last;
1.240 + char *pivot = malloc(WORD_BYTES);
1.241 + assert(pivot != 0);
1.242
1.243 - first=(char*)base; last=first+(nmemb-1)*WORD_BYTES;
1.244 + first = (char *) base;
1.245 + last = first + (nmemb - 1) * WORD_BYTES;
1.246
1.247 - if (last-first>TRUNC_words) {
1.248 - char *ffirst=first, *llast=last;
1.249 - while (1) {
1.250 + if (last - first > TRUNC_words) {
1.251 + char *ffirst = first, *llast = last;
1.252 + while (1) {
1.253 #ifdef DEBUG_QSORT
1.254 -fprintf(stderr,"Doing %d:%d: ",
1.255 - (first-(char*)base)/WORD_BYTES,
1.256 - (last-(char*)base)/WORD_BYTES);
1.257 + fprintf(stderr, "Doing %d:%d: ",
1.258 + (first - (char *) base) / WORD_BYTES,
1.259 + (last - (char *) base) / WORD_BYTES);
1.260 #endif
1.261 - /* Select pivot */
1.262 - { char * mid=first+WORD_BYTES*((last-first) / (2*WORD_BYTES));
1.263 - Pivot(SWAP_words,WORD_BYTES);
1.264 - *(int*)pivot=*(int*)mid;
1.265 - }
1.266 + /* Select pivot */
1.267 + {
1.268 + char *mid =
1.269 + first + WORD_BYTES * ((last - first) / (2 * WORD_BYTES));
1.270 + Pivot(SWAP_words, WORD_BYTES);
1.271 + *(int *) pivot = *(int *) mid;
1.272 + }
1.273 #ifdef DEBUG_QSORT
1.274 -fprintf(stderr,"pivot=%d\n",*(int*)pivot);
1.275 + fprintf(stderr, "pivot=%d\n", *(int *) pivot);
1.276 #endif
1.277 - /* Partition. */
1.278 - Partition(SWAP_words,WORD_BYTES);
1.279 - /* Prepare to recurse/iterate. */
1.280 - Recurse(TRUNC_words)
1.281 + /* Partition. */
1.282 + Partition(SWAP_words, WORD_BYTES);
1.283 + /* Prepare to recurse/iterate. */
1.284 + Recurse(TRUNC_words)}
1.285 }
1.286 - }
1.287 - PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES);
1.288 - /* Now do insertion sort. */
1.289 - last=((char*)base)+nmemb*WORD_BYTES;
1.290 - for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) {
1.291 - /* Find the right place for |first|. My apologies for var reuse */
1.292 - int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first;
1.293 - *(int*)pivot=*(int*)first;
1.294 - for (;compare(pl,pivot)>0;pr=pl,--pl) {
1.295 - *pr=*pl; }
1.296 - if (pr!=(int*)first) *pr=*(int*)pivot;
1.297 - }
1.298 - free(pivot);
1.299 + PreInsertion(SWAP_words, (TRUNC_words / WORD_BYTES), WORD_BYTES);
1.300 + /* Now do insertion sort. */
1.301 + last = ((char *) base) + nmemb * WORD_BYTES;
1.302 + for (first = ((char *) base) + WORD_BYTES; first != last;
1.303 + first += WORD_BYTES) {
1.304 + /* Find the right place for |first|. My apologies for var reuse */
1.305 + int *pl = (int *) (first - WORD_BYTES), *pr = (int *) first;
1.306 + *(int *) pivot = *(int *) first;
1.307 + for (; compare(pl, pivot) > 0; pr = pl, --pl) {
1.308 + *pr = *pl;
1.309 + }
1.310 + if (pr != (int *) first)
1.311 + *pr = *(int *) pivot;
1.312 + }
1.313 + free(pivot);
1.314 }
1.315
1.316 /* ---------------------------------------------------------------------- */
1.317
1.318 -void qsort(void *base, size_t nmemb, size_t size,
1.319 - int (*compare)(const void *, const void *)) {
1.320 +void
1.321 +qsort(void *base, size_t nmemb, size_t size,
1.322 + int (*compare) (const void *, const void *))
1.323 +{
1.324
1.325 - if (nmemb<=1) return;
1.326 - if (((uintptr_t)base|size)&(WORD_BYTES-1))
1.327 - qsort_nonaligned(base,nmemb,size,compare);
1.328 - else if (size!=WORD_BYTES)
1.329 - qsort_aligned(base,nmemb,size,compare);
1.330 - else
1.331 - qsort_words(base,nmemb,compare);
1.332 + if (nmemb <= 1)
1.333 + return;
1.334 + if (((uintptr_t) base | size) & (WORD_BYTES - 1))
1.335 + qsort_nonaligned(base, nmemb, size, compare);
1.336 + else if (size != WORD_BYTES)
1.337 + qsort_aligned(base, nmemb, size, compare);
1.338 + else
1.339 + qsort_words(base, nmemb, compare);
1.340 }
1.341
1.342 #endif /* !HAVE_QSORT */
1.343 +/* vi: set ts=4 sw=4 expandtab: */