src/stdlib/SDL_qsort.c
branchSDL-1.3
changeset 1668 4da1ee79c9af
parent 1662 782fd950bd46
     1.1 --- a/src/stdlib/SDL_qsort.c	Mon May 29 03:53:21 2006 +0000
     1.2 +++ b/src/stdlib/SDL_qsort.c	Mon May 29 04:04:35 2006 +0000
     1.3 @@ -266,59 +266,59 @@
     1.4  /* ---------------------------------------------------------------------- */
     1.5  
     1.6  static char *
     1.7 -pivot_big (char *first, char *mid, char *last, size_t size,
     1.8 -           int compare (const void *, const void *))
     1.9 +pivot_big(char *first, char *mid, char *last, size_t size,
    1.10 +          int compare(const void *, const void *))
    1.11  {
    1.12      size_t d = (((last - first) / size) >> 3) * size;
    1.13      char *m1, *m2, *m3;
    1.14      {
    1.15          char *a = first, *b = first + d, *c = first + 2 * d;
    1.16  #ifdef DEBUG_QSORT
    1.17 -        fprintf (stderr, "< %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
    1.18 +        fprintf(stderr, "< %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
    1.19  #endif
    1.20 -        m1 = compare (a, b) < 0 ?
    1.21 -            (compare (b, c) < 0 ? b : (compare (a, c) < 0 ? c : a))
    1.22 -            : (compare (a, c) < 0 ? a : (compare (b, c) < 0 ? c : b));
    1.23 +        m1 = compare(a, b) < 0 ?
    1.24 +            (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
    1.25 +            : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
    1.26      }
    1.27      {
    1.28          char *a = mid - d, *b = mid, *c = mid + d;
    1.29  #ifdef DEBUG_QSORT
    1.30 -        fprintf (stderr, ". %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
    1.31 +        fprintf(stderr, ". %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
    1.32  #endif
    1.33 -        m2 = compare (a, b) < 0 ?
    1.34 -            (compare (b, c) < 0 ? b : (compare (a, c) < 0 ? c : a))
    1.35 -            : (compare (a, c) < 0 ? a : (compare (b, c) < 0 ? c : b));
    1.36 +        m2 = compare(a, b) < 0 ?
    1.37 +            (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
    1.38 +            : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
    1.39      }
    1.40      {
    1.41          char *a = last - 2 * d, *b = last - d, *c = last;
    1.42  #ifdef DEBUG_QSORT
    1.43 -        fprintf (stderr, "> %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
    1.44 +        fprintf(stderr, "> %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
    1.45  #endif
    1.46 -        m3 = compare (a, b) < 0 ?
    1.47 -            (compare (b, c) < 0 ? b : (compare (a, c) < 0 ? c : a))
    1.48 -            : (compare (a, c) < 0 ? a : (compare (b, c) < 0 ? c : b));
    1.49 +        m3 = compare(a, b) < 0 ?
    1.50 +            (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
    1.51 +            : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
    1.52      }
    1.53  #ifdef DEBUG_QSORT
    1.54 -    fprintf (stderr, "-> %d %d %d\n", *(int *) m1, *(int *) m2, *(int *) m3);
    1.55 +    fprintf(stderr, "-> %d %d %d\n", *(int *) m1, *(int *) m2, *(int *) m3);
    1.56  #endif
    1.57 -    return compare (m1, m2) < 0 ?
    1.58 -        (compare (m2, m3) < 0 ? m2 : (compare (m1, m3) < 0 ? m3 : m1))
    1.59 -        : (compare (m1, m3) < 0 ? m1 : (compare (m2, m3) < 0 ? m3 : m2));
    1.60 +    return compare(m1, m2) < 0 ?
    1.61 +        (compare(m2, m3) < 0 ? m2 : (compare(m1, m3) < 0 ? m3 : m1))
    1.62 +        : (compare(m1, m3) < 0 ? m1 : (compare(m2, m3) < 0 ? m3 : m2));
    1.63  }
    1.64  
    1.65  /* ---------------------------------------------------------------------- */
    1.66  
    1.67  static void
    1.68 -qsort_nonaligned (void *base, size_t nmemb, size_t size,
    1.69 -                  int (*compare) (const void *, const void *))
    1.70 +qsort_nonaligned(void *base, size_t nmemb, size_t size,
    1.71 +                 int (*compare) (const void *, const void *))
    1.72  {
    1.73  
    1.74      stack_entry stack[STACK_SIZE];
    1.75      int stacktop = 0;
    1.76      char *first, *last;
    1.77 -    char *pivot = malloc (size);
    1.78 +    char *pivot = malloc(size);
    1.79      size_t trunc = TRUNC_nonaligned * size;
    1.80 -    assert (pivot != 0);
    1.81 +    assert(pivot != 0);
    1.82  
    1.83      first = (char *) base;
    1.84      last = first + (nmemb - 1) * size;
    1.85 @@ -329,30 +329,30 @@
    1.86              /* Select pivot */
    1.87              {
    1.88                  char *mid = first + size * ((last - first) / size >> 1);
    1.89 -                Pivot (SWAP_nonaligned, size);
    1.90 -                memcpy (pivot, mid, size);
    1.91 +                Pivot(SWAP_nonaligned, size);
    1.92 +                memcpy(pivot, mid, size);
    1.93              }
    1.94              /* Partition. */
    1.95 -            Partition (SWAP_nonaligned, size);
    1.96 +            Partition(SWAP_nonaligned, size);
    1.97              /* Prepare to recurse/iterate. */
    1.98 -        Recurse (trunc)}
    1.99 +        Recurse(trunc)}
   1.100      }
   1.101 -    PreInsertion (SWAP_nonaligned, TRUNC_nonaligned, size);
   1.102 -    Insertion (SWAP_nonaligned);
   1.103 -    free (pivot);
   1.104 +    PreInsertion(SWAP_nonaligned, TRUNC_nonaligned, size);
   1.105 +    Insertion(SWAP_nonaligned);
   1.106 +    free(pivot);
   1.107  }
   1.108  
   1.109  static void
   1.110 -qsort_aligned (void *base, size_t nmemb, size_t size,
   1.111 -               int (*compare) (const void *, const void *))
   1.112 +qsort_aligned(void *base, size_t nmemb, size_t size,
   1.113 +              int (*compare) (const void *, const void *))
   1.114  {
   1.115  
   1.116      stack_entry stack[STACK_SIZE];
   1.117      int stacktop = 0;
   1.118      char *first, *last;
   1.119 -    char *pivot = malloc (size);
   1.120 +    char *pivot = malloc(size);
   1.121      size_t trunc = TRUNC_aligned * size;
   1.122 -    assert (pivot != 0);
   1.123 +    assert(pivot != 0);
   1.124  
   1.125      first = (char *) base;
   1.126      last = first + (nmemb - 1) * size;
   1.127 @@ -363,29 +363,29 @@
   1.128              /* Select pivot */
   1.129              {
   1.130                  char *mid = first + size * ((last - first) / size >> 1);
   1.131 -                Pivot (SWAP_aligned, size);
   1.132 -                memcpy (pivot, mid, size);
   1.133 +                Pivot(SWAP_aligned, size);
   1.134 +                memcpy(pivot, mid, size);
   1.135              }
   1.136              /* Partition. */
   1.137 -            Partition (SWAP_aligned, size);
   1.138 +            Partition(SWAP_aligned, size);
   1.139              /* Prepare to recurse/iterate. */
   1.140 -        Recurse (trunc)}
   1.141 +        Recurse(trunc)}
   1.142      }
   1.143 -    PreInsertion (SWAP_aligned, TRUNC_aligned, size);
   1.144 -    Insertion (SWAP_aligned);
   1.145 -    free (pivot);
   1.146 +    PreInsertion(SWAP_aligned, TRUNC_aligned, size);
   1.147 +    Insertion(SWAP_aligned);
   1.148 +    free(pivot);
   1.149  }
   1.150  
   1.151  static void
   1.152 -qsort_words (void *base, size_t nmemb,
   1.153 -             int (*compare) (const void *, const void *))
   1.154 +qsort_words(void *base, size_t nmemb,
   1.155 +            int (*compare) (const void *, const void *))
   1.156  {
   1.157  
   1.158      stack_entry stack[STACK_SIZE];
   1.159      int stacktop = 0;
   1.160      char *first, *last;
   1.161 -    char *pivot = malloc (WORD_BYTES);
   1.162 -    assert (pivot != 0);
   1.163 +    char *pivot = malloc(WORD_BYTES);
   1.164 +    assert(pivot != 0);
   1.165  
   1.166      first = (char *) base;
   1.167      last = first + (nmemb - 1) * WORD_BYTES;
   1.168 @@ -394,26 +394,26 @@
   1.169          char *ffirst = first, *llast = last;
   1.170          while (1) {
   1.171  #ifdef DEBUG_QSORT
   1.172 -            fprintf (stderr, "Doing %d:%d: ",
   1.173 -                     (first - (char *) base) / WORD_BYTES,
   1.174 -                     (last - (char *) base) / WORD_BYTES);
   1.175 +            fprintf(stderr, "Doing %d:%d: ",
   1.176 +                    (first - (char *) base) / WORD_BYTES,
   1.177 +                    (last - (char *) base) / WORD_BYTES);
   1.178  #endif
   1.179              /* Select pivot */
   1.180              {
   1.181                  char *mid =
   1.182                      first + WORD_BYTES * ((last - first) / (2 * WORD_BYTES));
   1.183 -                Pivot (SWAP_words, WORD_BYTES);
   1.184 +                Pivot(SWAP_words, WORD_BYTES);
   1.185                  *(int *) pivot = *(int *) mid;
   1.186              }
   1.187  #ifdef DEBUG_QSORT
   1.188 -            fprintf (stderr, "pivot=%d\n", *(int *) pivot);
   1.189 +            fprintf(stderr, "pivot=%d\n", *(int *) pivot);
   1.190  #endif
   1.191              /* Partition. */
   1.192 -            Partition (SWAP_words, WORD_BYTES);
   1.193 +            Partition(SWAP_words, WORD_BYTES);
   1.194              /* Prepare to recurse/iterate. */
   1.195 -        Recurse (TRUNC_words)}
   1.196 +        Recurse(TRUNC_words)}
   1.197      }
   1.198 -    PreInsertion (SWAP_words, (TRUNC_words / WORD_BYTES), WORD_BYTES);
   1.199 +    PreInsertion(SWAP_words, (TRUNC_words / WORD_BYTES), WORD_BYTES);
   1.200      /* Now do insertion sort. */
   1.201      last = ((char *) base) + nmemb * WORD_BYTES;
   1.202      for (first = ((char *) base) + WORD_BYTES; first != last;
   1.203 @@ -421,30 +421,30 @@
   1.204          /* Find the right place for |first|. My apologies for var reuse */
   1.205          int *pl = (int *) (first - WORD_BYTES), *pr = (int *) first;
   1.206          *(int *) pivot = *(int *) first;
   1.207 -        for (; compare (pl, pivot) > 0; pr = pl, --pl) {
   1.208 +        for (; compare(pl, pivot) > 0; pr = pl, --pl) {
   1.209              *pr = *pl;
   1.210          }
   1.211          if (pr != (int *) first)
   1.212              *pr = *(int *) pivot;
   1.213      }
   1.214 -    free (pivot);
   1.215 +    free(pivot);
   1.216  }
   1.217  
   1.218  /* ---------------------------------------------------------------------- */
   1.219  
   1.220  void
   1.221 -qsort (void *base, size_t nmemb, size_t size,
   1.222 -       int (*compare) (const void *, const void *))
   1.223 +qsort(void *base, size_t nmemb, size_t size,
   1.224 +      int (*compare) (const void *, const void *))
   1.225  {
   1.226  
   1.227      if (nmemb <= 1)
   1.228          return;
   1.229      if (((uintptr_t) base | size) & (WORD_BYTES - 1))
   1.230 -        qsort_nonaligned (base, nmemb, size, compare);
   1.231 +        qsort_nonaligned(base, nmemb, size, compare);
   1.232      else if (size != WORD_BYTES)
   1.233 -        qsort_aligned (base, nmemb, size, compare);
   1.234 +        qsort_aligned(base, nmemb, size, compare);
   1.235      else
   1.236 -        qsort_words (base, nmemb, compare);
   1.237 +        qsort_words(base, nmemb, compare);
   1.238  }
   1.239  
   1.240  #endif /* !HAVE_QSORT */