1 /* qsort( void *, size_t, size_t, int(*)( const void *, const void * ) )
2
3 This file is part of the Public Domain C Library (PDCLib).
4 Permission is granted to use, modify, and / or redistribute at will.
5 */
6
7 #include <stdlib.h>
8
9 #ifndef REGTEST
10
11 /* This implementation is taken from Paul Edward's PDPCLIB.
12
13 Original code is credited to Raymond Gardner, Englewood CO.
14 Minor mods are credited to Paul Edwards.
15 Some reformatting and simplification done by Martin Baute.
16 All code is still Public Domain.
17 */
18
19 /* Wrapper for _PDCLIB_memswp protects against multiple argument evaluation. */
memswp(char * i,char * j,size_t size)20 static _PDCLIB_inline void memswp( char * i, char * j, size_t size )
21 {
22 _PDCLIB_memswp( i, j, size );
23 }
24
25 /* For small sets, insertion sort is faster than quicksort.
26 T is the threshold below which insertion sort will be used.
27 Must be 3 or larger.
28 */
29 #define T 7
30
31 /* Macros for handling the QSort stack */
32 #define PREPARE_STACK char * stack[STACKSIZE]; char ** stackptr = stack
33 #define PUSH( base, limit ) stackptr[0] = base; stackptr[1] = limit; stackptr += 2
34 #define POP( base, limit ) stackptr -= 2; base = stackptr[0]; limit = stackptr[1]
35 /* TODO: Stack usage is log2( nmemb ) (minus what T shaves off the worst case).
36 Worst-case nmemb is platform dependent and should probably be
37 configured through _PDCLIB_config.h.
38 */
39 #define STACKSIZE 64
40
qsort(void * base,size_t nmemb,size_t size,int (* compar)(const void *,const void *))41 void qsort( void * base, size_t nmemb, size_t size, int ( *compar )( const void *, const void * ) )
42 {
43 char * i;
44 char * j;
45 _PDCLIB_size_t thresh = T * size;
46 char * base_ = ( char * )base;
47 char * limit = base_ + nmemb * size;
48 PREPARE_STACK;
49
50 for ( ;; )
51 {
52 if ( ( size_t )( limit - base_ ) > thresh ) /* QSort for more than T elements. */
53 {
54 /* We work from second to last - first will be pivot element. */
55 i = base_ + size;
56 j = limit - size;
57 /* We swap first with middle element, then sort that with second
58 and last element so that eventually first element is the median
59 of the three - avoiding pathological pivots.
60 TODO: Instead of middle element, chose one randomly.
61 */
62 memswp( ( ( ( ( size_t )( limit - base_ ) ) / size ) / 2 ) * size + base_, base_, size );
63
64 if ( compar( i, j ) > 0 )
65 {
66 memswp( i, j, size );
67 }
68
69 if ( compar( base_, j ) > 0 )
70 {
71 memswp( base_, j, size );
72 }
73
74 if ( compar( i, base_ ) > 0 )
75 {
76 memswp( i, base_, size );
77 }
78
79 /* Now we have the median for pivot element, entering main Quicksort. */
80 for ( ;; )
81 {
82 do
83 {
84 /* move i right until *i >= pivot */
85 i += size;
86 } while ( compar( i, base_ ) < 0 );
87
88 do
89 {
90 /* move j left until *j <= pivot */
91 j -= size;
92 } while ( compar( j, base_ ) > 0 );
93
94 if ( i > j )
95 {
96 /* break loop if pointers crossed */
97 break;
98 }
99
100 /* else swap elements, keep scanning */
101 memswp( i, j, size );
102 }
103
104 /* move pivot into correct place */
105 memswp( base_, j, size );
106
107 /* larger subfile base / limit to stack, sort smaller */
108 if ( j - base_ > limit - i )
109 {
110 /* left is larger */
111 PUSH( base_, j );
112 base_ = i;
113 }
114 else
115 {
116 /* right is larger */
117 PUSH( i, limit );
118 limit = j;
119 }
120 }
121 else /* insertion sort for less than T elements */
122 {
123 for ( j = base_, i = j + size; i < limit; j = i, i += size )
124 {
125 for ( ; compar( j, j + size ) > 0; j -= size )
126 {
127 memswp( j, j + size, size );
128
129 if ( j == base_ )
130 {
131 break;
132 }
133 }
134 }
135
136 if ( stackptr != stack ) /* if any entries on stack */
137 {
138 POP( base_, limit );
139 }
140 else /* else stack empty, done */
141 {
142 break;
143 }
144 }
145 }
146 }
147
148 #endif
149
150 #ifdef TEST
151
152 #include "_PDCLIB_test.h"
153
154 #include <string.h>
155 #include <limits.h>
156
compare(const void * left,const void * right)157 static int compare( const void * left, const void * right )
158 {
159 return *( ( unsigned char * )left ) - *( ( unsigned char * )right );
160 }
161
main(void)162 int main( void )
163 {
164 char presort[] = { "shreicnyjqpvozxmbt" };
165 char sorted1[] = { "bcehijmnopqrstvxyz" };
166 char sorted2[] = { "bticjqnyozpvreshxm" };
167 char s[19];
168 strcpy( s, presort );
169 qsort( s, 18, 1, compare );
170 TESTCASE( strcmp( s, sorted1 ) == 0 );
171 strcpy( s, presort );
172 qsort( s, 9, 2, compare );
173 TESTCASE( strcmp( s, sorted2 ) == 0 );
174 strcpy( s, presort );
175 qsort( s, 1, 1, compare );
176 TESTCASE( strcmp( s, presort ) == 0 );
177 #if defined( REGTEST ) && ( defined( __BSD_VISIBLE ) || defined( __APPLE__ ) )
178 puts( "qsort.c: Skipping test #4 for BSD as it goes into endless loop here." );
179 #else
180 qsort( s, 100, 0, compare );
181 TESTCASE( strcmp( s, presort ) == 0 );
182 #endif
183 return TEST_RESULTS;
184 }
185
186 #endif
187