From: solar Date: Sat, 17 Dec 2005 18:50:23 +0000 (+0000) Subject: Added qsort. X-Git-Tag: v0.4~31 X-Git-Url: https://pd.if.org/git/?p=pdclib;a=commitdiff_plain;h=744bbe0fcec2f59f755dd56fa59d8979f4253dfd Added qsort. --- diff --git a/Readme.txt b/Readme.txt index 4dc0831..b7b43ed 100644 --- a/Readme.txt +++ b/Readme.txt @@ -150,4 +150,4 @@ Adds test drivers, fixes some bugs in . v0.4 - unreleased Implementations for parts of . -(strtol, strtoul, atoi, atol and atoll.) +(strtol, strtoul, atoi, atol, atoll, rand, srand, bsearch, qsort.) diff --git a/functions/stdlib/qsort.c b/functions/stdlib/qsort.c new file mode 100644 index 0000000..8941e6d --- /dev/null +++ b/functions/stdlib/qsort.c @@ -0,0 +1,162 @@ +/* $Id$ */ + +/* Release $Name$ */ + +/* qsort( void *, size_t, size_t, int(*)( const void *, const void * ) ) + + This file is part of the Public Domain C Library (PDCLib). + Permission is granted to use, modify, and / or redistribute at will. +*/ + +#include + +#ifndef REGTEST + +/* This implementation is taken from Paul Edward's PDPCLIB. + + 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. +*/ + +/* Wrapper for _PDCLIB_memswp protects against multiple argument evaluation. */ +static inline void memswp( char * i, char * j, unsigned int size ) +{ + _PDCLIB_memswp( i, j, size ); +} + +/* 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: This is platform-dependent */ +#define STACKSIZE 40 + +void qsort( void * base, size_t nmemb, size_t size, int (*compar)( const void *, const void * ) ) +{ + char * i; + char * j; + size_t thresh = T * size; + char * base_ = (char *)base; + char * limit = base_ + nmemb * size; + PREPARE_STACK; + + for ( ;; ) + { + if ( 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; + } + } + } +} + +#endif + +#ifdef TEST +#include <_PDCLIB_test.h> +#include +#include + +int compare( const void * left, const void * right ) +{ + return *( (unsigned char *)left ) - *( (unsigned char *)right ); +} + +int main() +{ + char presort[] = { "shreicnyjqpvozxmbt" }; + char sorted1[] = { "bcehijmnopqrstvxyz" }; + char sorted2[] = { "bticjqnyozpvreshxm" }; + char s[19]; + BEGIN_TESTS; + 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 ); + qsort( s, 100, 0, compare ); + TESTCASE( strcmp( s, presort ) == 0 ); + return TEST_RESULTS; +} + +#endif diff --git a/includes/stdlib.h b/includes/stdlib.h index e436c6f..252ab92 100644 --- a/includes/stdlib.h +++ b/includes/stdlib.h @@ -59,6 +59,8 @@ void exit(); /* Searching and sorting */ +void * bsearch( const void * key, const void * base, size_t nmemb, size_t size, int (*compar)( const void *, const void * ) ); +void qsort( void * base, size_t nmemb, size_t size, int (*compar)( const void *, const void * ) ); /* Integer arithmetic functions */ diff --git a/internals/_PDCLIB_config.h b/internals/_PDCLIB_config.h index 753080b..d2188ff 100644 --- a/internals/_PDCLIB_config.h +++ b/internals/_PDCLIB_config.h @@ -23,6 +23,11 @@ #define _PDCLIB_SUCCESS 0 #define _PDCLIB_FAILURE -1 +/* qsort() in requires a function that swaps two memory areas. */ +/* Below is a naive implementation that can be improved significantly for */ +/* specific platforms, e.g. by swapping int instead of char. */ +#define _PDCLIB_memswp( i, j, size ) char tmp; do { tmp = *i; *i++ = *j; *j++ = tmp; } while ( --size ); + /* -------------------------------------------------------------------------- */ /* Integers */ /* -------------------------------------------------------------------------- */