diff options
Diffstat (limited to 'stdlib/msort.c')
| -rw-r--r-- | stdlib/msort.c | 276 |
1 files changed, 205 insertions, 71 deletions
diff --git a/stdlib/msort.c b/stdlib/msort.c index e69b4011c4..3961e9e981 100644 --- a/stdlib/msort.c +++ b/stdlib/msort.c @@ -1,6 +1,6 @@ /* An alternative to qsort, with an identical interface. This file is part of the GNU C Library. - Copyright (C) 1992,95-97,99,2000,01,02,04 Free Software Foundation, Inc. + Copyright (C) 1992,95-97,99,2000,01,02,04,07 Free Software Foundation, Inc. Written by Mike Haertel, September 1988. The GNU C Library is free software; you can redistribute it and/or @@ -19,20 +19,25 @@ 02111-1307 USA. */ #include <alloca.h> +#include <stdint.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include <memcopy.h> #include <errno.h> -static void msort_with_tmp (void *b, size_t n, size_t s, - __compar_fn_t cmp, char *t); +struct msort_param +{ + size_t s; + size_t var; + __compar_fn_t cmp; + char *t; +}; +static void msort_with_tmp (const struct msort_param *p, void *b, size_t n); static void -msort_with_tmp (void *b, size_t n, size_t s, __compar_fn_t cmp, - char *t) +msort_with_tmp (const struct msort_param *p, void *b, size_t n) { - char *tmp; char *b1, *b2; size_t n1, n2; @@ -42,65 +47,131 @@ msort_with_tmp (void *b, size_t n, size_t s, __compar_fn_t cmp, n1 = n / 2; n2 = n - n1; b1 = b; - b2 = (char *) b + (n1 * s); + b2 = (char *) b + (n1 * p->s); - msort_with_tmp (b1, n1, s, cmp, t); - msort_with_tmp (b2, n2, s, cmp, t); + msort_with_tmp (p, b1, n1); + msort_with_tmp (p, b2, n2); - tmp = t; + char *tmp = p->t; + const size_t s = p->s; + __compar_fn_t cmp = p->cmp; + switch (p->var) + { + case 0: + while (n1 > 0 && n2 > 0) + { + if ((*cmp) (b1, b2) <= 0) + { + *(uint32_t *) tmp = *(uint32_t *) b1; + b1 += sizeof (uint32_t); + --n1; + } + else + { + *(uint32_t *) tmp = *(uint32_t *) b2; + b2 += sizeof (uint32_t); + --n2; + } + tmp += sizeof (uint32_t); + } + break; + case 1: + while (n1 > 0 && n2 > 0) + { + if ((*cmp) (b1, b2) <= 0) + { + *(uint64_t *) tmp = *(uint64_t *) b1; + b1 += sizeof (uint64_t); + --n1; + } + else + { + *(uint64_t *) tmp = *(uint64_t *) b2; + b2 += sizeof (uint64_t); + --n2; + } + tmp += sizeof (uint64_t); + } + break; + case 2: + while (n1 > 0 && n2 > 0) + { + unsigned long *tmpl = (unsigned long *) tmp; + unsigned long *bl; + + tmp += s; + if ((*cmp) (b1, b2) <= 0) + { + bl = (unsigned long *) b1; + b1 += s; + --n1; + } + else + { + bl = (unsigned long *) b2; + b2 += s; + --n2; + } + while (tmpl < (unsigned long *) tmp) + *tmpl++ = *bl++; + } + break; + case 3: + while (n1 > 0 && n2 > 0) + { + if ((*cmp) (*(const void **) b1, *(const void **) b2) <= 0) + { + *(void **) tmp = *(void **) b1; + b1 += sizeof (void *); + --n1; + } + else + { + *(void **) tmp = *(void **) b2; + b2 += sizeof (void *); + --n2; + } + tmp += sizeof (void *); + } + break; + default: + while (n1 > 0 && n2 > 0) + { + if ((*cmp) (b1, b2) <= 0) + { + tmp = (char *) __mempcpy (tmp, b1, s); + b1 += s; + --n1; + } + else + { + tmp = (char *) __mempcpy (tmp, b2, s); + b2 += s; + --n2; + } + } + break; + } - if (s == OPSIZ && (b1 - (char *) 0) % OPSIZ == 0) - /* We are operating on aligned words. Use direct word stores. */ - while (n1 > 0 && n2 > 0) - { - if ((*cmp) (b1, b2) <= 0) - { - --n1; - *((op_t *) tmp) = *((op_t *) b1); - tmp += sizeof (op_t); - b1 += sizeof (op_t); - } - else - { - --n2; - *((op_t *) tmp) = *((op_t *) b2); - tmp += sizeof (op_t); - b2 += sizeof (op_t); - } - } - else - while (n1 > 0 && n2 > 0) - { - if ((*cmp) (b1, b2) <= 0) - { - tmp = (char *) __mempcpy (tmp, b1, s); - b1 += s; - --n1; - } - else - { - tmp = (char *) __mempcpy (tmp, b2, s); - b2 += s; - --n2; - } - } if (n1 > 0) memcpy (tmp, b1, n1 * s); - memcpy (b, t, (n - n2) * s); + memcpy (b, p->t, (n - n2) * s); } void qsort (void *b, size_t n, size_t s, __compar_fn_t cmp) { - const size_t size = n * s; + size_t size = n * s; + char *tmp = NULL; + struct msort_param p; - if (size < 1024) - { - void *buf = __alloca (size); + /* For large object sizes use indirect sorting. */ + if (s > 32) + size = 2 * n * sizeof (void *) + s; - /* The temporary array is small, so put it on the stack. */ - msort_with_tmp (b, n, s, cmp, buf); - } + if (size < 1024) + /* The temporary array is small, so put it on the stack. */ + p.t = __alloca (size); else { /* We should avoid allocating too much memory since this might @@ -135,26 +206,89 @@ qsort (void *b, size_t n, size_t s, __compar_fn_t cmp) /* If the memory requirements are too high don't allocate memory. */ if (size / pagesize > (size_t) phys_pages) - _quicksort (b, n, s, cmp); - else { - /* It's somewhat large, so malloc it. */ - int save = errno; - char *tmp = malloc (size); - if (tmp == NULL) - { - /* Couldn't get space, so use the slower algorithm - that doesn't need a temporary array. */ - __set_errno (save); - _quicksort (b, n, s, cmp); - } - else - { - __set_errno (save); - msort_with_tmp (b, n, s, cmp, tmp); - free (tmp); - } + _quicksort (b, n, s, cmp); + return; + } + + /* It's somewhat large, so malloc it. */ + int save = errno; + tmp = malloc (size); + __set_errno (save); + if (tmp == NULL) + { + /* Couldn't get space, so use the slower algorithm + that doesn't need a temporary array. */ + _quicksort (b, n, s, cmp); + return; + } + p.t = tmp; + } + + p.s = s; + p.cmp = cmp; + p.var = 4; + + if (s > 32) + { + /* Indirect sorting. */ + char *ip = (char *) b; + void **tp = (void **) (p.t + n * sizeof (void *)); + void **t = tp; + void *tmp_storage = (void *) (tp + n); + + while ((void *) t < tmp_storage) + { + *t++ = ip; + ip += s; + } + p.s = sizeof (void *); + p.var = 3; + msort_with_tmp (&p, p.t + n * sizeof (void *), n); + + /* tp[0] .. tp[n - 1] is now sorted, copy around entries of + the original array. Knuth vol. 3 (2nd ed.) exercise 5.2-10. */ + char *kp; + size_t i; + for (i = 0, ip = (char *) b; i < n; i++, ip += s) + if ((kp = tp[i]) != ip) + { + size_t j = i; + char *jp = ip; + memcpy (tmp_storage, ip, s); + + do + { + size_t k = (kp - (char *) b) / s; + tp[j] = jp; + memcpy (jp, kp, s); + j = k; + jp = kp; + kp = tp[k]; + } + while (kp != ip); + + tp[j] = jp; + memcpy (jp, tmp_storage, s); + } + } + else + { + if ((s & (sizeof (uint32_t) - 1)) == 0 + && ((char *) b - (char *) 0) % __alignof__ (uint32_t) == 0) + { + if (s == sizeof (uint32_t)) + p.var = 0; + else if (s == sizeof (uint64_t) + && ((char *) b - (char *) 0) % __alignof__ (uint64_t) == 0) + p.var = 1; + else if ((s & (sizeof (unsigned long) - 1)) == 0 + && ((char *) b - (char *) 0) + % __alignof__ (unsigned long) == 0) + p.var = 2; } + msort_with_tmp (&p, b, n); } + free (tmp); } libc_hidden_def (qsort) |