-/* ----------------------------------------------------------------------------
- * $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 <stdlib.h>
-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 <string.h>
+#include <limits.h>
-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
-*/
projects / pdclib / blobdiff