From ae97a89e1a1a9833080dccc81f6cd26784e1b964 Mon Sep 17 00:00:00 2001 From: Eric Andersen Date: Thu, 11 Jan 2001 11:42:17 +0000 Subject: A large update from Manuel Novoa III . --- libc/stdlib/qsort.c | 220 +++++++++++++++++----------------------------------- 1 file changed, 72 insertions(+), 148 deletions(-) (limited to 'libc/stdlib/qsort.c') diff --git a/libc/stdlib/qsort.c b/libc/stdlib/qsort.c index 7cb1d8ab4..7390c3bd3 100644 --- a/libc/stdlib/qsort.c +++ b/libc/stdlib/qsort.c @@ -1,148 +1,72 @@ -/* - * This file lifted in toto from 'Dlibs' on the atari ST (RdeBath) - * - * - * Dale Schumacher 399 Beacon Ave. - * (alias: Dalnefre') St. Paul, MN 55104 - * dal@syntel.UUCP United States of America - * "It's not reality that's important, but how you perceive things." - */ -#include - -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) -register int *base; -register int lo; -register int hi; -register int (*cmp) (); -{ - 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; - } - } -} - -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; - - 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) -register char *base; -register int lo; -register int hi; -register int size; -register int (*cmp) (); -{ - 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; - } - } -} - -extern int qsort(base, num, size, cmp) -char *base; -int num; -int size; -int (*cmp) (); -{ - 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; -} +/* +++Date last modified: 05-Jul-1997 */ + +/* +** ssort() -- Fast, small, qsort()-compatible Shell sort +** +** by Ray Gardner, public domain 5/90 +*/ + +/* + * Manuel Novoa III Dec 2000 + * + * There were several problems with the qsort code contained in uClibc. + * It assumed sizeof(int) was 2 and sizeof(long) was 4. It then had three + * seperate quiicksort routines based on the width of the data passed: 2, 4, + * or anything else <= 128. If the width was > 128, it returned -1 (although + * qsort should not return a value) and did no sorting. On i386 with + * -Os -fomit-frame-pointer -ffunction-sections, the text segment of qsort.o + * was 1358 bytes, with an additional 4 bytes in bss. + * + * I decided to completely replace the existing code with a small + * implementation of a shell sort. It is a drop-in replacement for the + * standard qsort and, with the same gcc flags as above, the text segment + * size on i386 is only 183 bytes. + * + * Grabbed original file rg_ssort.c from snippets.org. + * Modified original code to avoid possible overflow in wgap calculation. + * Modified wgap calculation in loop and eliminated variables gap and wnel. + */ + + +#include + +void qsort (void *base, + size_t nel, + size_t width, + int (*comp)(const void *, const void *)) +{ + size_t wgap, i, j, k; + char *a, *b, tmp; + +#if 0 + /* Note: still conceivable that nel * width could overflow! */ + assert(width > 0); +#endif + + if (nel > 1) { + for (wgap = 0; ++wgap < (nel-1)/3 ; wgap *= 3) {} + wgap *= width; + nel *= width; /* convert nel to 'wnel' */ + do { + for (i = wgap; i < nel; i += width) { + for (j = i - wgap; ;j -= wgap) { + a = j + ((char *)base); + b = a + wgap; + if ( (*comp)(a, b) <= 0 ) { + break; + } + k = width; + do { + tmp = *a; + *a++ = *b; + *b++ = tmp; + } while ( --k ); + if (j < wgap) { + break; + } + } + } + wgap = (wgap - width)/3; + } while (wgap); + } +} -- cgit v1.2.3