src/stdlib/SDL_qsort.c
changeset 1895 c121d94672cb
parent 1456 84de7511f79f
child 3162 dc1eb82ffdaa
     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: */