1 #if defined(__GNUC__) && (__GNUC__ >2 || __GNUC_MINOR__ >=7)
2 #define UNUSED __attribute__ ((unused))
8 static char rcsid
[] UNUSED
= "$Id: ucbqsort.c,v 1.4 2004/01/01 07:06:06 fabio Exp fabio $";
11 /* @(#)qsort.c 4.2 (Berkeley) 3/9/83 */
15 * Our own version of the system qsort routine which is faster by an average
16 * of 25%, with lows and highs of 10% and 50%.
17 * The THRESHold below is the insertion sort threshold, and has been adjusted
18 * for records of size 48 bytes.
19 * The MTHREShold is where we stop finding a better median.
26 typedef int (*QSFP
)(const void *, const void *);
27 extern void qsort ( char *base
, int n
, int size
, QSFP compar
);
29 #define THRESH 4 /* threshold for insertion */
30 #define MTHRESH 6 /* threshold for median */
32 static QSFP qcmp
; /* the comparison routine */
33 static int qsz
; /* size of each record */
34 static int thresh
; /* THRESHold in chars */
35 static int mthresh
; /* MTHRESHold in chars */
37 static void qst (char *base
, char *max
);
45 * First, set up some global parameters for qst to share. Then, quicksort
46 * with qst(), and then a cleanup insertion sort ourselves. Sound simple?
58 register char c
, *i
, *j
, *lo
, *hi
;
65 thresh
= qsz
* THRESH
;
66 mthresh
= qsz
* MTHRESH
;
75 * First put smallest element, which must be in the first THRESH, in
76 * the first position as a sentinel. This is done just by searching
77 * the first THRESH elements (or the first n if n < THRESH), finding
78 * the min, and swapping it into the first position.
80 for (j
= lo
= base
; (lo
+= qsz
) < hi
; )
81 if ((*qcmp
)(j
, lo
) > 0)
84 /* swap j into place */
85 for (i
= base
, hi
= base
+ qsz
; i
< hi
; ) {
92 * With our sentinel in place, we now run the following hyper-fast
93 * insertion sort. For each remaining element, min, from [1] to [n-1],
94 * set hi to the index of the element AFTER which this one goes.
95 * Then, do the standard insertion sort shift on a character at a time
96 * basis for each element in the frob.
98 for (min
= base
; (hi
= min
+= qsz
) < max
; ) {
99 while ((*qcmp
)(hi
-= qsz
, min
) > 0)
101 if ((hi
+= qsz
) != min
) {
102 for (lo
= min
+ qsz
; --lo
>= min
; ) {
104 for (i
= j
= lo
; (j
-= qsz
) >= hi
; i
= j
)
115 * First, find the median element, and put that one in the first place as the
116 * discriminator. (This "median" is just the median of the first, last and
117 * middle elements). (Using this median instead of the first element is a big
118 * win). Then, the usual partitioning/swapping, followed by moving the
119 * discriminator into the right place. Then, figure out the sizes of the two
120 * partions, do the smaller one recursively and the larger one via a repeat of
121 * this code. Stopping when there are less than THRESH elements in a partition
122 * and cleaning up with an insertion sort (in our caller) is a huge win.
123 * All data swaps are done in-line, which is space-losing but time-saving.
124 * (And there are only three places where this is done).
128 qst(char *base
, char *max
)
130 register char c
, *i
, *j
, *jj
;
136 * At the top here, lo is the number of characters of elements in the
137 * current partition. (Which should be max - base).
138 * Find the median of the first, last, and middle element and make
139 * that the middle element. Set j to largest of first and middle.
140 * If max is larger than that guy, then it's that guy, else compare
141 * max with loser of first and take larger. Things are set up to
142 * prefer the middle, then the first in case of ties.
144 lo
= max
- base
; /* number of elements as chars */
146 mid
= i
= base
+ qsz
* ((lo
/ qsz
) >> 1);
148 j
= ((*qcmp
)((jj
= base
), i
) > 0 ? jj
: i
);
149 if ((*qcmp
)(j
, (tmp
= max
- qsz
)) > 0) {
150 /* switch to first loser */
151 j
= (j
== jj
? i
: jj
);
152 if ((*qcmp
)(j
, tmp
) < 0)
165 * Semi-standard quicksort partitioning/swapping
167 for (i
= base
, j
= max
- qsz
; ; ) {
168 while (i
< mid
&& (*qcmp
)(i
, mid
) <= 0)
171 if ((*qcmp
)(mid
, j
) <= 0) {
175 tmp
= i
+ qsz
; /* value of i after swap */
177 /* j <-> mid, new mid is j */
189 /* i <-> mid, new mid is i */
191 tmp
= mid
= i
; /* value of i after swap */
204 * Look at sizes of the two partitions, do the smaller
205 * one first by recursion, then do the larger one by
206 * making sure lo is its size, base and max are update
207 * correctly, and branching back. But only repeat
208 * (recursively or by branching) if the partition is
209 * of at least size THRESH.
212 if ((lo
= j
- base
) <= (hi
= max
- i
)) {
222 } while (lo
>= thresh
);
225 /*---------------------------------------------------------------------------*/
226 /* Static function prototypes */
227 /*---------------------------------------------------------------------------*/