diff options
Diffstat (limited to 'libc/stdlib')
-rw-r--r-- | libc/stdlib/bsearch.c | 39 | ||||
-rw-r--r-- | libc/stdlib/qsort.c | 71 |
2 files changed, 0 insertions, 110 deletions
diff --git a/libc/stdlib/bsearch.c b/libc/stdlib/bsearch.c deleted file mode 100644 index 6f3817b60..000000000 --- a/libc/stdlib/bsearch.c +++ /dev/null @@ -1,39 +0,0 @@ -/* - * This file originally 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." - * - * Reworked by Erik Andersen <andersen@uclibc.org> - */ -#include <stdio.h> - -void * bsearch (const void *key, const void *base, size_t num, size_t size, - int (*cmp) (const void *, const void *)) -{ - int dir; - size_t a, b, c; - const void *p; - - a = 0; - b = num; - while (a < b) - { - c = (a + b) >> 1; /* == ((a + b) / 2) */ - p = (void *)(((const char *) base) + (c * size)); - dir = (*cmp)(key, p); - if (dir < 0) { - b = c; - } else if (dir > 0) { - a = c + 1; - } else { - return (void *)p; - } - } - - return NULL; -} - 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); - } -} |