]>
Commit | Line | Data |
---|---|---|
28f540f4 RM |
1 | /* Copyright (C) 1991, 1992 Free Software Foundation, Inc. |
2 | This file is part of the GNU C Library. | |
3 | Written by Douglas C. Schmidt (schmidt@ics.uci.edu). | |
4 | ||
5 | The GNU C Library is free software; you can redistribute it and/or | |
6 | modify it under the terms of the GNU Library General Public License as | |
7 | published by the Free Software Foundation; either version 2 of the | |
8 | License, or (at your option) any later version. | |
9 | ||
10 | The GNU C Library is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | Library General Public License for more details. | |
14 | ||
15 | You should have received a copy of the GNU Library General Public | |
16 | License along with the GNU C Library; see the file COPYING.LIB. If | |
17 | not, write to the Free Software Foundation, Inc., 675 Mass Ave, | |
18 | Cambridge, MA 02139, USA. */ | |
19 | ||
20 | #include <ansidecl.h> | |
21 | #include <stdlib.h> | |
22 | #include <string.h> | |
23 | ||
24 | /* Byte-wise swap two items of size SIZE. */ | |
25 | #define SWAP(a, b, size) \ | |
26 | do \ | |
27 | { \ | |
28 | register size_t __size = (size); \ | |
29 | register char *__a = (a), *__b = (b); \ | |
30 | do \ | |
31 | { \ | |
32 | char __tmp = *__a; \ | |
33 | *__a++ = *__b; \ | |
34 | *__b++ = __tmp; \ | |
35 | } while (--__size > 0); \ | |
36 | } while (0) | |
37 | ||
38 | /* Discontinue quicksort algorithm when partition gets below this size. | |
39 | This particular magic number was chosen to work best on a Sun 4/260. */ | |
40 | #define MAX_THRESH 4 | |
41 | ||
42 | /* Stack node declarations used to store unfulfilled partition obligations. */ | |
43 | typedef struct | |
44 | { | |
45 | char *lo; | |
46 | char *hi; | |
47 | } stack_node; | |
48 | ||
49 | /* The next 4 #defines implement a very fast in-line stack abstraction. */ | |
50 | #define STACK_SIZE (8 * sizeof(unsigned long int)) | |
51 | #define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top)) | |
52 | #define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi))) | |
53 | #define STACK_NOT_EMPTY (stack < top) | |
54 | ||
55 | ||
56 | /* Order size using quicksort. This implementation incorporates | |
57 | four optimizations discussed in Sedgewick: | |
58 | ||
59 | 1. Non-recursive, using an explicit stack of pointer that store the | |
60 | next array partition to sort. To save time, this maximum amount | |
61 | of space required to store an array of MAX_INT is allocated on the | |
62 | stack. Assuming a 32-bit integer, this needs only 32 * | |
63 | sizeof(stack_node) == 136 bits. Pretty cheap, actually. | |
64 | ||
65 | 2. Chose the pivot element using a median-of-three decision tree. | |
66 | This reduces the probability of selecting a bad pivot value and | |
67 | eliminates certain extraneous comparisons. | |
68 | ||
69 | 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving | |
70 | insertion sort to order the MAX_THRESH items within each partition. | |
71 | This is a big win, since insertion sort is faster for small, mostly | |
72 | sorted array segements. | |
73 | ||
74 | 4. The larger of the two sub-partitions is always pushed onto the | |
75 | stack first, with the algorithm then concentrating on the | |
76 | smaller partition. This *guarantees* no more than log (n) | |
77 | stack size is needed (actually O(1) in this case)! */ | |
78 | ||
79 | void | |
80 | DEFUN(_quicksort, (pbase, total_elems, size, cmp), | |
81 | PTR CONST pbase AND size_t total_elems AND size_t size AND | |
82 | int EXFUN((*cmp), (CONST PTR, CONST PTR))) | |
83 | { | |
84 | register char *base_ptr = (char *) pbase; | |
85 | ||
86 | /* Allocating SIZE bytes for a pivot buffer facilitates a better | |
87 | algorithm below since we can do comparisons directly on the pivot. */ | |
88 | char *pivot_buffer = (char *) __alloca (size); | |
89 | CONST size_t max_thresh = MAX_THRESH * size; | |
90 | ||
91 | if (total_elems == 0) | |
92 | /* Avoid lossage with unsigned arithmetic below. */ | |
93 | return; | |
94 | ||
95 | if (total_elems > MAX_THRESH) | |
96 | { | |
97 | char *lo = base_ptr; | |
98 | char *hi = &lo[size * (total_elems - 1)]; | |
99 | /* Largest size needed for 32-bit int!!! */ | |
100 | stack_node stack[STACK_SIZE]; | |
101 | stack_node *top = stack + 1; | |
102 | ||
103 | while (STACK_NOT_EMPTY) | |
104 | { | |
105 | char *left_ptr; | |
106 | char *right_ptr; | |
107 | ||
108 | char *pivot = pivot_buffer; | |
109 | ||
110 | /* Select median value from among LO, MID, and HI. Rearrange | |
111 | LO and HI so the three values are sorted. This lowers the | |
112 | probability of picking a pathological pivot value and | |
113 | skips a comparison for both the LEFT_PTR and RIGHT_PTR. */ | |
114 | ||
115 | char *mid = lo + size * ((hi - lo) / size >> 1); | |
116 | ||
117 | if ((*cmp)((PTR) mid, (PTR) lo) < 0) | |
118 | SWAP(mid, lo, size); | |
119 | if ((*cmp)((PTR) hi, (PTR) mid) < 0) | |
120 | SWAP(mid, hi, size); | |
121 | else | |
122 | goto jump_over; | |
123 | if ((*cmp)((PTR) mid, (PTR) lo) < 0) | |
124 | SWAP(mid, lo, size); | |
125 | jump_over:; | |
126 | memcpy(pivot, mid, size); | |
127 | pivot = pivot_buffer; | |
128 | ||
129 | left_ptr = lo + size; | |
130 | right_ptr = hi - size; | |
131 | ||
132 | /* Here's the famous ``collapse the walls'' section of quicksort. | |
133 | Gotta like those tight inner loops! They are the main reason | |
134 | that this algorithm runs much faster than others. */ | |
135 | do | |
136 | { | |
137 | while ((*cmp)((PTR) left_ptr, (PTR) pivot) < 0) | |
138 | left_ptr += size; | |
139 | ||
140 | while ((*cmp)((PTR) pivot, (PTR) right_ptr) < 0) | |
141 | right_ptr -= size; | |
142 | ||
143 | if (left_ptr < right_ptr) | |
144 | { | |
145 | SWAP(left_ptr, right_ptr, size); | |
146 | left_ptr += size; | |
147 | right_ptr -= size; | |
148 | } | |
149 | else if (left_ptr == right_ptr) | |
150 | { | |
151 | left_ptr += size; | |
152 | right_ptr -= size; | |
153 | break; | |
154 | } | |
155 | } | |
156 | while (left_ptr <= right_ptr); | |
157 | ||
158 | /* Set up pointers for next iteration. First determine whether | |
159 | left and right partitions are below the threshold size. If so, | |
160 | ignore one or both. Otherwise, push the larger partition's | |
161 | bounds on the stack and continue sorting the smaller one. */ | |
162 | ||
163 | if ((size_t) (right_ptr - lo) <= max_thresh) | |
164 | { | |
165 | if ((size_t) (hi - left_ptr) <= max_thresh) | |
166 | /* Ignore both small partitions. */ | |
167 | POP(lo, hi); | |
168 | else | |
169 | /* Ignore small left partition. */ | |
170 | lo = left_ptr; | |
171 | } | |
172 | else if ((size_t) (hi - left_ptr) <= max_thresh) | |
173 | /* Ignore small right partition. */ | |
174 | hi = right_ptr; | |
175 | else if ((right_ptr - lo) > (hi - left_ptr)) | |
176 | { | |
177 | /* Push larger left partition indices. */ | |
178 | PUSH(lo, right_ptr); | |
179 | lo = left_ptr; | |
180 | } | |
181 | else | |
182 | { | |
183 | /* Push larger right partition indices. */ | |
184 | PUSH(left_ptr, hi); | |
185 | hi = right_ptr; | |
186 | } | |
187 | } | |
188 | } | |
189 | ||
190 | /* Once the BASE_PTR array is partially sorted by quicksort the rest | |
191 | is completely sorted using insertion sort, since this is efficient | |
192 | for partitions below MAX_THRESH size. BASE_PTR points to the beginning | |
193 | of the array to sort, and END_PTR points at the very last element in | |
194 | the array (*not* one beyond it!). */ | |
195 | ||
196 | #define min(x, y) ((x) < (y) ? (x) : (y)) | |
197 | ||
198 | { | |
199 | char *CONST end_ptr = &base_ptr[size * (total_elems - 1)]; | |
200 | char *tmp_ptr = base_ptr; | |
201 | char *thresh = min(end_ptr, base_ptr + max_thresh); | |
202 | register char *run_ptr; | |
203 | ||
204 | /* Find smallest element in first threshold and place it at the | |
205 | array's beginning. This is the smallest array element, | |
206 | and the operation speeds up insertion sort's inner loop. */ | |
207 | ||
208 | for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size) | |
209 | if ((*cmp)((PTR) run_ptr, (PTR) tmp_ptr) < 0) | |
210 | tmp_ptr = run_ptr; | |
211 | ||
212 | if (tmp_ptr != base_ptr) | |
213 | SWAP(tmp_ptr, base_ptr, size); | |
214 | ||
215 | /* Insertion sort, running from left-hand-side up to right-hand-side. */ | |
216 | ||
217 | run_ptr = base_ptr + size; | |
218 | while ((run_ptr += size) <= end_ptr) | |
219 | { | |
220 | tmp_ptr = run_ptr - size; | |
221 | while ((*cmp)((PTR) run_ptr, (PTR) tmp_ptr) < 0) | |
222 | tmp_ptr -= size; | |
223 | ||
224 | tmp_ptr += size; | |
225 | if (tmp_ptr != run_ptr) | |
226 | { | |
227 | char *trav; | |
228 | ||
229 | trav = run_ptr + size; | |
230 | while (--trav >= run_ptr) | |
231 | { | |
232 | char c = *trav; | |
233 | char *hi, *lo; | |
234 | ||
235 | for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) | |
236 | *hi = *lo; | |
237 | *hi = c; | |
238 | } | |
239 | } | |
240 | } | |
241 | } | |
242 | } | |
243 |