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