1 /*
2 * $Id: qsort.c,v 1.2 1991/12/05 20:08:26 schrod Exp $
3 *----------------------------------------------------------------------
4 *
5 * This file is part of
6 * MakeIndex - A formatter and format independent index processor
7 *
8 * This file is public domain software donated by
9 * Nelson Beebe (beebe@science.utah.edu).
10 *
11 *
12 * [history at end]
13 */
14
15 /*
16 * qsort.c: Our own version of the system qsort routine which is faster by an
17 * average of 25%, with lows and highs of 10% and 50%. The THRESHold below is
18 * the insertion sort threshold, and has been adjusted for records of size 48
19 * bytes. The MTHREShold is where we stop finding a better median.
20 */
21
22 /* #include <stdio.h> -- mkind.h includes this */
23 #include "mkind.h" /* only for type declarations */
24
25 #define THRESH 4 /* threshold for insertion */
26 #define MTHRESH 6 /* threshold for median */
27
28 static int qsz; /* size of each record */
29 static int thresh; /* THRESHold in chars */
30 static int mthresh; /* MTHRESHold in chars */
31
32 static int (*qcmp) ARGS((char*,char*)); /* the comparison routine */
33 static void qst ARGS((char *base, char *max));
34 /*
35 * qqsort: First, set up some global parameters for qst to share. Then,
36 * quicksort with qst(), and then a cleanup insertion sort ourselves. Sound
37 * simple? It's not...
38 */
39
40 void
qqsort(base,n,size,compar)41 qqsort(base, n, size, compar)
42 char *base;
43 int n;
44 int size;
45 int (*compar) ();
46 {
47 register char *i;
48 register char *j;
49 register char *lo;
50 register char *hi;
51 register char *min;
52 register char c;
53 char *max;
54
55 if (n <= 1)
56 return;
57 qsz = size;
58 qcmp = compar;
59 thresh = qsz * THRESH;
60 mthresh = qsz * MTHRESH;
61 max = base + n * qsz;
62 if (n >= THRESH) {
63 qst(base, max);
64 hi = base + thresh;
65 } else {
66 hi = max;
67 }
68 /*
69 * First put smallest element, which must be in the first THRESH, in the
70 * first position as a sentinel. This is done just by searching the
71 * first THRESH elements (or the first n if n < THRESH), finding the min,
72 * and swapping it into the first position.
73 */
74 for (j = lo = base; (lo += qsz) < hi;) {
75 if ((*qcmp) (j, lo) > 0)
76 j = lo;
77 }
78 if (j != base) { /* swap j into place */
79 for (i = base, hi = base + qsz; i < hi;) {
80 c = *j;
81 *j++ = *i;
82 *i++ = c;
83 }
84 }
85 /*
86 * With our sentinel in place, we now run the following hyper-fast
87 * insertion sort. For each remaining element, min, from [1] to [n-1],
88 * set hi to the index of the element AFTER which this one goes. Then, do
89 * the standard insertion sort shift on a character at a time basis for
90 * each element in the frob.
91 */
92 for (min = base; (hi = min += qsz) < max;) {
93 while ((*qcmp) (hi -= qsz, min) > 0);
94 if ((hi += qsz) != min) {
95 for (lo = min + qsz; --lo >= min;) {
96 c = *lo;
97 for (i = j = lo; (j -= qsz) >= hi; i = j)
98 *i = *j;
99 *i = c;
100 }
101 }
102 }
103 }
104
105
106
107 /*
108 * qst: Do a quicksort. First, find the median element, and put that one in
109 * the first place as the discriminator. (This "median" is just the median
110 * of the first, last and middle elements). (Using this median instead of
111 * the first element is a big win). Then, the usual partitioning/swapping,
112 * followed by moving the discriminator into the right place. Then, figure
113 * out the sizes of the two partions, do the smaller one recursively and the
114 * larger one via a repeat of this code. Stopping when there are less than
115 * THRESH elements in a partition and cleaning up with an insertion sort (in
116 * our caller) is a huge win. All data swaps are done in-line, which is
117 * space-losing but time-saving. (And there are only three places where this
118 * is done).
119 */
120
121 static void
qst(base,max)122 qst(base, max)
123 char *base;
124 char *max;
125 {
126 register char *i;
127 register char *j;
128 register char *jj;
129 register char *mid;
130 register int ii;
131 register char c;
132 char *tmp;
133 int lo;
134 int hi;
135
136 lo = (int)(max - base); /* number of elements as chars */
137 do {
138 /*
139 * At the top here, lo is the number of characters of elements in the
140 * current partition. (Which should be max - base). Find the median
141 * of the first, last, and middle element and make that the middle
142 * element. Set j to largest of first and middle. If max is larger
143 * than that guy, then it's that guy, else compare max with loser of
144 * first and take larger. Things are set up to prefer the middle,
145 * then the first in case of ties.
146 */
147 mid = i = base + qsz * ((unsigned) (lo / qsz) >> 1);
148 if (lo >= mthresh) {
149 j = ((*qcmp) ((jj = base), i) > 0 ? jj : i);
150 if ((*qcmp) (j, (tmp = max - qsz)) > 0) {
151 /* switch to first loser */
152 j = (j == jj ? i : jj);
153 if ((*qcmp) (j, tmp) < 0)
154 j = tmp;
155 }
156 if (j != i) {
157 ii = qsz;
158 do {
159 c = *i;
160 *i++ = *j;
161 *j++ = c;
162 } while (--ii);
163 }
164 }
165 /* Semi-standard quicksort partitioning/swapping */
166 for (i = base, j = max - qsz;;) {
167 while (i < mid && (*qcmp) (i, mid) <= 0)
168 i += qsz;
169 while (j > mid) {
170 if ((*qcmp) (mid, j) <= 0) {
171 j -= qsz;
172 continue;
173 }
174 tmp = i + qsz; /* value of i after swap */
175 if (i == mid) { /* j <-> mid, new mid is j */
176 mid = jj = j;
177 } else { /* i <-> j */
178 jj = j;
179 j -= qsz;
180 }
181 goto swap;
182 }
183 if (i == mid) {
184 break;
185 } else { /* i <-> mid, new mid is i */
186 jj = mid;
187 tmp = mid = i; /* value of i after swap */
188 j -= qsz;
189 }
190 swap:
191 ii = qsz;
192 do {
193 c = *i;
194 *i++ = *jj;
195 *jj++ = c;
196 } while (--ii);
197 i = tmp;
198 }
199 /*
200 * Look at sizes of the two partitions, do the smaller one first by
201 * recursion, then do the larger one by making sure lo is its size,
202 * base and max are update correctly, and branching back. But only
203 * repeat (recursively or by branching) if the partition is of at
204 * least size THRESH.
205 */
206 i = (j = mid) + qsz;
207 if ((lo = (int)(j - base)) <= (hi = (int)(max - i))) {
208 if (lo >= thresh)
209 qst(base, j);
210 base = i;
211 lo = hi;
212 } else {
213 if (hi >= thresh)
214 qst(i, max);
215 max = j;
216 }
217 } while (lo >= thresh);
218 }
219
220
221
222 /*======================================================================
223 *
224 * $Log: qsort.c,v $
225 * Revision 1.2 1991/12/05 20:08:26 schrod
226 * MakeIndex, version 2.9.1.2 [by Joachim Schrod]
227 * == base version, from which development of International MakeIndex starts ==
228 *
229 */
230
231