diff options
Diffstat (limited to 'libc/stdlib/qsort.c')
| -rw-r--r-- | libc/stdlib/qsort.c | 225 |
1 files changed, 103 insertions, 122 deletions
diff --git a/libc/stdlib/qsort.c b/libc/stdlib/qsort.c index b45716c83..7cb1d8ab4 100644 --- a/libc/stdlib/qsort.c +++ b/libc/stdlib/qsort.c @@ -9,159 +9,140 @@ */ #include <string.h> -char *_qbuf = 0; /* pointer to storage for qsort() */ +char *_qbuf = 0; /* pointer to storage for qsort() */ #define PIVOT ((i+j)>>1) #define moveitem(dst,src,size) if(dst != src) memcpy(dst, src, size) -static void -_wqsort(base, lo, hi, cmp) +static void _wqsort(base, lo, hi, cmp) register int *base; register int lo; register int hi; register int (*cmp) (); { - int k; - register int i, j, t; - register int *p = &k; + int k; + register int i, j, t; + register int *p = &k; - while (hi > lo) - { - i = lo; - j = hi; - t = PIVOT; - *p = base[t]; - base[t] = base[i]; - base[i] = *p; - while (i < j) - { - while (((*cmp) ((base + j), p)) > 0) - --j; - base[i] = base[j]; - while ((i < j) && (((*cmp) ((base + i), p)) <= 0)) - ++i; - base[j] = base[i]; - } - base[i] = *p; - if ((i - lo) < (hi - i)) - { - _wqsort(base, lo, (i - 1), cmp); - lo = i + 1; - } - else - { - _wqsort(base, (i + 1), hi, cmp); - hi = i - 1; - } - } + while (hi > lo) { + i = lo; + j = hi; + t = PIVOT; + *p = base[t]; + base[t] = base[i]; + base[i] = *p; + while (i < j) { + while (((*cmp) ((base + j), p)) > 0) + --j; + base[i] = base[j]; + while ((i < j) && (((*cmp) ((base + i), p)) <= 0)) + ++i; + base[j] = base[i]; + } + base[i] = *p; + if ((i - lo) < (hi - i)) { + _wqsort(base, lo, (i - 1), cmp); + lo = i + 1; + } else { + _wqsort(base, (i + 1), hi, cmp); + hi = i - 1; + } + } } -static void -_lqsort(base, lo, hi, cmp) +static void _lqsort(base, lo, hi, cmp) register long *base; register int lo; register int hi; register int (*cmp) (); { - long k; - register int i, j, t; - register long *p = &k; + long k; + register int i, j, t; + register long *p = &k; - while (hi > lo) - { - i = lo; - j = hi; - t = PIVOT; - *p = base[t]; - base[t] = base[i]; - base[i] = *p; - while (i < j) - { - while (((*cmp) ((base + j), p)) > 0) - --j; - base[i] = base[j]; - while ((i < j) && (((*cmp) ((base + i), p)) <= 0)) - ++i; - base[j] = base[i]; - } - base[i] = *p; - if ((i - lo) < (hi - i)) - { - _lqsort(base, lo, (i - 1), cmp); - lo = i + 1; - } - else - { - _lqsort(base, (i + 1), hi, cmp); - hi = i - 1; - } - } + while (hi > lo) { + i = lo; + j = hi; + t = PIVOT; + *p = base[t]; + base[t] = base[i]; + base[i] = *p; + while (i < j) { + while (((*cmp) ((base + j), p)) > 0) + --j; + base[i] = base[j]; + while ((i < j) && (((*cmp) ((base + i), p)) <= 0)) + ++i; + base[j] = base[i]; + } + base[i] = *p; + if ((i - lo) < (hi - i)) { + _lqsort(base, lo, (i - 1), cmp); + lo = i + 1; + } else { + _lqsort(base, (i + 1), hi, cmp); + hi = i - 1; + } + } } -static void -_nqsort(base, lo, hi, size, cmp) +static void _nqsort(base, lo, hi, size, cmp) register char *base; register int lo; register int hi; register int size; register int (*cmp) (); { - register int i, j; - register char *p = _qbuf; + register int i, j; + register char *p = _qbuf; - while (hi > lo) - { - i = lo; - j = hi; - p = (base + size * PIVOT); - moveitem(_qbuf, p, size); - moveitem(p, (base + size * i), size); - moveitem((base + size * i), _qbuf, size); - p = _qbuf; - while (i < j) - { - while (((*cmp) ((base + size * j), p)) > 0) - --j; - moveitem((base + size * i), (base + size * j), size); - while ((i < j) && (((*cmp) ((base + size * i), p)) <= 0)) - ++i; - moveitem((base + size * j), (base + size * i), size); - } - moveitem((base + size * i), p, size); - if ((i - lo) < (hi - i)) - { - _nqsort(base, lo, (i - 1), size, cmp); - lo = i + 1; - } - else - { - _nqsort(base, (i + 1), hi, size, cmp); - hi = i - 1; - } - } + while (hi > lo) { + i = lo; + j = hi; + p = (base + size * PIVOT); + moveitem(_qbuf, p, size); + moveitem(p, (base + size * i), size); + moveitem((base + size * i), _qbuf, size); + p = _qbuf; + while (i < j) { + while (((*cmp) ((base + size * j), p)) > 0) + --j; + moveitem((base + size * i), (base + size * j), size); + while ((i < j) && (((*cmp) ((base + size * i), p)) <= 0)) + ++i; + moveitem((base + size * j), (base + size * i), size); + } + moveitem((base + size * i), p, size); + if ((i - lo) < (hi - i)) { + _nqsort(base, lo, (i - 1), size, cmp); + lo = i + 1; + } else { + _nqsort(base, (i + 1), hi, size, cmp); + hi = i - 1; + } + } } extern int qsort(base, num, size, cmp) char *base; -int num; -int size; -int (*cmp) (); +int num; +int size; +int (*cmp) (); { - char _qtemp[128]; + char _qtemp[128]; - if (_qbuf == 0) - { - if (size > sizeof(_qtemp))/* records too large! */ - return 1; - _qbuf = _qtemp; - } - if (size == 2) - _wqsort(base, 0, num - 1, cmp); - else if (size == 4) - _lqsort(base, 0, num - 1, cmp); - else - _nqsort(base, 0, num - 1, size, cmp); - if (_qbuf == _qtemp) - _qbuf = 0; - return 0; + if (_qbuf == 0) { + if (size > sizeof(_qtemp)) /* records too large! */ + return 1; + _qbuf = _qtemp; + } + if (size == 2) + _wqsort(base, 0, num - 1, cmp); + else if (size == 4) + _lqsort(base, 0, num - 1, cmp); + else + _nqsort(base, 0, num - 1, size, cmp); + if (_qbuf == _qtemp) + _qbuf = 0; + return 0; } |