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