diff options
author | Manuel Novoa III <mjn3@codepoet.org> | 2002-06-18 08:54:53 +0000 |
---|---|---|
committer | Manuel Novoa III <mjn3@codepoet.org> | 2002-06-18 08:54:53 +0000 |
commit | 3bc8ac7796cf6f3ab67316e6df5aa8915a6bb03e (patch) | |
tree | 1fc185f8d9c862e3f94c5acfad837f339ee301c6 /libc/stdlib/qsort.c | |
parent | 5b0c2c6d870cc9f9f2eae32f4d71abc6f9348e20 (diff) |
Remove obsolete files.
Diffstat (limited to 'libc/stdlib/qsort.c')
-rw-r--r-- | libc/stdlib/qsort.c | 71 |
1 files changed, 0 insertions, 71 deletions
diff --git a/libc/stdlib/qsort.c b/libc/stdlib/qsort.c deleted file mode 100644 index cefae8ceb..000000000 --- a/libc/stdlib/qsort.c +++ /dev/null @@ -1,71 +0,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 <stdlib.h> -#include <assert.h> - -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; - - /* Note: still conceivable that nel * width could overflow! */ - assert(width > 0); - - 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); - } -} |