X-Git-Url: https://pd.if.org/git/?p=pdclib;a=blobdiff_plain;f=functions%2Fstdlib%2Fqsort.c;h=757cae0f28444a0419a42b823adabc7ddcebda4a;hp=66bc14ba072314676073fc02693ad521d996c89a;hb=da0f3f353d417fed71f358a48d5d5394145e460d;hpb=1d9d92ba957a0b8307c9a65c35867fde68e6533b diff --git a/functions/stdlib/qsort.c b/functions/stdlib/qsort.c index 66bc14b..757cae0 100644 --- a/functions/stdlib/qsort.c +++ b/functions/stdlib/qsort.c @@ -1,158 +1,164 @@ -/* ---------------------------------------------------------------------------- - * $Id$ - * ---------------------------------------------------------------------------- - * Public Domain C Library - http://pdclib.sourceforge.net - * This code is Public Domain. Use, modify, and redistribute at will. - * --------------------------------------------------------------------------*/ +/* qsort( void *, size_t, size_t, int(*)( const void *, const void * ) ) -void qsort( void * base, size_t nelem, size_t size, int (*cmp) ( const void * e1, const void * e2) ) { /* TODO */ }; - -/* PDPC code - unreviewed -/******************************************************************/ -/* qsort.c -- Non-Recursive ISO C qsort() function */ -/* */ -/* Public domain by Raymond Gardner, Englewood CO February 1991 */ -/* Minor mods by Paul Edwards also public domain */ -/* */ -/* Usage: */ -/* qsort(base, nbr_elements, width_bytes, compare_function); */ -/* void *base; */ -/* size_t nbr_elements, width_bytes; */ -/* int (*compare_function)(const void *, const void *); */ -/* */ -/* Sorts an array starting at base, of length nbr_elements, each */ -/* element of size width_bytes, ordered via compare_function, */ -/* which is called as (*compare_function)(ptr_to_element1, */ -/* ptr_to_element2) and returns < 0 if element1 < element2, */ -/* 0 if element1 = element2, > 0 if element1 > element2. */ -/* Most refinements are due to R. Sedgewick. See "Implementing */ -/* Quicksort Programs", Comm. ACM, Oct. 1978, and Corrigendum, */ -/* Comm. ACM, June 1979. */ -/******************************************************************/ - -/* prototypes */ -static void swap_chars(char *, char *, size_t); - -/* -** Compile with -DSWAP_INTS if your machine can access an int at an -** arbitrary location with reasonable efficiency. (Some machines -** cannot access an int at an odd address at all, so be careful.) + This file is part of the Public Domain C Library (PDCLib). + Permission is granted to use, modify, and / or redistribute at will. */ -#ifdef SWAP_INTS - void swap_ints(char *, char *, size_t); - #define SWAP(a, b) (swap_func((char *)(a), (char *)(b), width)) -#else - #define SWAP(a, b) (swap_chars((char *)(a), (char *)(b), size)) -#endif - -#define COMP(a, b) ((*comp)((void *)(a), (void *)(b))) - -#define T 7 /* subfiles of T or fewer elements will */ - /* be sorted by a simple insertion sort */ - /* Note! T must be at least 3 */ +#include -void qsort(void *basep, size_t nelems, size_t size, - int (*comp)(const void *, const void *)) -{ - char *stack[40], **sp; /* stack and stack pointer */ - char *i, *j, *limit; /* scan and limit pointers */ - size_t thresh; /* size of T elements in bytes */ - char *base; /* base pointer as char * */ +#ifndef REGTEST -#ifdef SWAP_INTS - size_t width; /* width of array element */ - void (*swap_func)(char *, char *, size_t); /* swap func pointer*/ +/* This implementation is taken from Paul Edward's PDPCLIB. - width = size; /* save size for swap routine */ - swap_func = swap_chars; /* choose swap function */ - if ( size % sizeof(int) == 0 ) { /* size is multiple of ints */ - width /= sizeof(int); /* set width in ints */ - swap_func = swap_ints; /* use int swap function */ - } -#endif + Original code is credited to Raymond Gardner, Englewood CO. + Minor mods are credited to Paul Edwards. + Some reformatting and simplification done by Martin Baute. + All code is still Public Domain. +*/ - base = (char *)basep; /* set up char * base pointer */ - thresh = T * size; /* init threshold */ - sp = stack; /* init stack pointer */ - limit = base + nelems * size;/* pointer past end of array */ - for ( ;; ) { /* repeat until break... */ - if ( limit - base > thresh ) { /* if more than T elements */ - /* swap base with middle */ - SWAP(((((size_t)(limit-base))/size)/2)*size+base, base); - i = base + size; /* i scans left to right */ - j = limit - size; /* j scans right to left */ - if ( COMP(i, j) > 0 ) /* Sedgewick's */ - SWAP(i, j); /* three-element sort */ - if ( COMP(base, j) > 0 ) /* sets things up */ - SWAP(base, j); /* so that */ - if ( COMP(i, base) > 0 ) /* *i <= *base <= *j */ - SWAP(i, base); /* *base is pivot element */ - for ( ;; ) { /* loop until break */ - do /* move i right */ - i += size; /* until *i >= pivot */ - while ( COMP(i, base) < 0 ); - do /* move j left */ - j -= size; /* until *j <= pivot */ - while ( COMP(j, base) > 0 ); - if ( i > j ) /* if pointers crossed */ - break; /* break loop */ - SWAP(i, j); /* else swap elements, keep scanning*/ - } - SWAP(base, j); /* move pivot into correct place */ - if ( j - base > limit - i ) { /* if left subfile larger */ - sp[0] = base; /* stack left subfile base */ - sp[1] = j; /* and limit */ - base = i; /* sort the right subfile */ - } else { /* else right subfile larger*/ - sp[0] = i; /* stack right subfile base */ - sp[1] = limit; /* and limit */ - limit = j; /* sort the left subfile */ - } - sp += 2; /* increment stack pointer */ - } else { /* else subfile is small, use insertion sort */ - for ( j = base, i = j+size; i < limit; j = i, i += size ) - for ( ; COMP(j, j+size) > 0; j -= size ) { - SWAP(j, j+size); - if ( j == base ) - break; - } - if ( sp != stack ) { /* if any entries on stack */ - sp -= 2; /* pop the base and limit */ - base = sp[0]; - limit = sp[1]; - } else /* else stack empty, done */ - break; - } - } +/* Wrapper for _PDCLIB_memswp protects against multiple argument evaluation. */ +static inline void memswp( char * i, char * j, size_t size ) +{ + _PDCLIB_memswp( i, j, size ); } -/* -** swap nbytes between a and b +/* For small sets, insertion sort is faster than quicksort. + T is the threshold below which insertion sort will be used. + Must be 3 or larger. +*/ +#define T 7 + +/* Macros for handling the QSort stack */ +#define PREPARE_STACK char * stack[STACKSIZE]; char * * stackptr = stack +#define PUSH( base, limit ) stackptr[0] = base; stackptr[1] = limit; stackptr += 2 +#define POP( base, limit ) stackptr -= 2; base = stackptr[0]; limit = stackptr[1] +/* TODO: Stack usage is log2( nmemb ) (minus what T shaves off the worst case). + Worst-case nmemb is platform dependent and should probably be + configured through _PDCLIB_config.h. */ +#define STACKSIZE 64 -static void swap_chars(char *a, char *b, size_t nbytes) +void qsort( void * base, size_t nmemb, size_t size, int (*compar)( const void *, const void * ) ) { - char tmp; - do { - tmp = *a; *a++ = *b; *b++ = tmp; - } while ( --nbytes ); + char * i; + char * j; + _PDCLIB_size_t thresh = T * size; + char * base_ = (char *)base; + char * limit = base_ + nmemb * size; + PREPARE_STACK; + + for ( ;; ) + { + if ( (size_t)( limit - base_ ) > thresh ) /* QSort for more than T elements. */ + { + /* We work from second to last - first will be pivot element. */ + i = base_ + size; + j = limit - size; + /* We swap first with middle element, then sort that with second + and last element so that eventually first element is the median + of the three - avoiding pathological pivots. + TODO: Instead of middle element, chose one randomly. + */ + memswp( ( ( ( (size_t)( limit - base_ ) ) / size ) / 2 ) * size + base_, base_, size ); + if ( compar( i, j ) > 0 ) memswp( i, j, size ); + if ( compar( base_, j ) > 0 ) memswp( base_, j, size ); + if ( compar( i, base_ ) > 0 ) memswp( i, base_, size ); + /* Now we have the median for pivot element, entering main Quicksort. */ + for ( ;; ) + { + do + { + /* move i right until *i >= pivot */ + i += size; + } while ( compar( i, base_ ) < 0 ); + do + { + /* move j left until *j <= pivot */ + j -= size; + } while ( compar( j, base_ ) > 0 ); + if ( i > j ) + { + /* break loop if pointers crossed */ + break; + } + /* else swap elements, keep scanning */ + memswp( i, j, size ); + } + /* move pivot into correct place */ + memswp( base_, j, size ); + /* larger subfile base / limit to stack, sort smaller */ + if ( j - base_ > limit - i ) + { + /* left is larger */ + PUSH( base_, j ); + base_ = i; + } + else + { + /* right is larger */ + PUSH( i, limit ); + limit = j; + } + } + else /* insertion sort for less than T elements */ + { + for ( j = base_, i = j + size; i < limit; j = i, i += size ) + { + for ( ; compar( j, j + size ) > 0; j -= size ) + { + memswp( j, j + size, size ); + if ( j == base_ ) + { + break; + } + } + } + if ( stackptr != stack ) /* if any entries on stack */ + { + POP( base_, limit ); + } + else /* else stack empty, done */ + { + break; + } + } + } } -#ifdef SWAP_INTS +#endif -/* -** swap nints between a and b -*/ +#ifdef TEST +#include "_PDCLIB_test.h" +#include +#include -static void swap_ints(char *ap, char *bp, size_t nints) +static int compare( const void * left, const void * right ) { - int *a = (int *)ap, *b = (int *)bp; - int tmp; - do { - tmp = *a; *a++ = *b; *b++ = tmp; - } while ( --nints ); + return *( (unsigned char *)left ) - *( (unsigned char *)right ); +} + +int main( void ) +{ + char presort[] = { "shreicnyjqpvozxmbt" }; + char sorted1[] = { "bcehijmnopqrstvxyz" }; + char sorted2[] = { "bticjqnyozpvreshxm" }; + char s[19]; + strcpy( s, presort ); + qsort( s, 18, 1, compare ); + TESTCASE( strcmp( s, sorted1 ) == 0 ); + strcpy( s, presort ); + qsort( s, 9, 2, compare ); + TESTCASE( strcmp( s, sorted2 ) == 0 ); + strcpy( s, presort ); + qsort( s, 1, 1, compare ); + TESTCASE( strcmp( s, presort ) == 0 ); +#if defined(REGTEST) && (__BSD_VISIBLE || __APPLE__) + puts( "qsort.c: Skipping test #4 for BSD as it goes into endless loop here." ); +#else + qsort( s, 100, 0, compare ); + TESTCASE( strcmp( s, presort ) == 0 ); +#endif + return TEST_RESULTS; } #endif -*/