1 | /* Copyright (C) 1991-2017 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 Lesser General Public |

7 | License as published by the Free Software Foundation; either |

8 | version 2.1 of the 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 | Lesser General Public License for more details. |

14 | |

15 | You should have received a copy of the GNU Lesser General Public |

16 | License along with the GNU C Library; if not, see |

17 | <http://www.gnu.org/licenses/>. */ |

18 | |

19 | /* If you consider tuning this algorithm, you should consult first: |

20 | Engineering a sort function; Jon Bentley and M. Douglas McIlroy; |

21 | Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */ |

22 | |

23 | #include <alloca.h> |

24 | #include <limits.h> |

25 | #include <stdlib.h> |

26 | #include <string.h> |

27 | |

28 | /* Byte-wise swap two items of size SIZE. */ |

29 | #define SWAP(a, b, size) \ |

30 | do \ |

31 | { \ |

32 | size_t __size = (size); \ |

33 | char *__a = (a), *__b = (b); \ |

34 | do \ |

35 | { \ |

36 | char __tmp = *__a; \ |

37 | *__a++ = *__b; \ |

38 | *__b++ = __tmp; \ |

39 | } while (--__size > 0); \ |

40 | } while (0) |

41 | |

42 | /* Discontinue quicksort algorithm when partition gets below this size. |

43 | This particular magic number was chosen to work best on a Sun 4/260. */ |

44 | #define MAX_THRESH 4 |

45 | |

46 | /* Stack node declarations used to store unfulfilled partition obligations. */ |

47 | typedef struct |

48 | { |

49 | char *lo; |

50 | char *hi; |

51 | } stack_node; |

52 | |

53 | /* The next 4 #defines implement a very fast in-line stack abstraction. */ |

54 | /* The stack needs log (total_elements) entries (we could even subtract |

55 | log(MAX_THRESH)). Since total_elements has type size_t, we get as |

56 | upper bound for log (total_elements): |

57 | bits per byte (CHAR_BIT) * sizeof(size_t). */ |

58 | #define STACK_SIZE (CHAR_BIT * sizeof(size_t)) |

59 | #define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top)) |

60 | #define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi))) |

61 | #define STACK_NOT_EMPTY (stack < top) |

62 | |

63 | |

64 | /* Order size using quicksort. This implementation incorporates |

65 | four optimizations discussed in Sedgewick: |

66 | |

67 | 1. Non-recursive, using an explicit stack of pointer that store the |

68 | next array partition to sort. To save time, this maximum amount |

69 | of space required to store an array of SIZE_MAX is allocated on the |

70 | stack. Assuming a 32-bit (64 bit) integer for size_t, this needs |

71 | only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes). |

72 | Pretty cheap, actually. |

73 | |

74 | 2. Chose the pivot element using a median-of-three decision tree. |

75 | This reduces the probability of selecting a bad pivot value and |

76 | eliminates certain extraneous comparisons. |

77 | |

78 | 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving |

79 | insertion sort to order the MAX_THRESH items within each partition. |

80 | This is a big win, since insertion sort is faster for small, mostly |

81 | sorted array segments. |

82 | |

83 | 4. The larger of the two sub-partitions is always pushed onto the |

84 | stack first, with the algorithm then concentrating on the |

85 | smaller partition. This *guarantees* no more than log (total_elems) |

86 | stack size is needed (actually O(1) in this case)! */ |

87 | |

88 | void |

89 | _quicksort (void *const pbase, size_t total_elems, size_t size, |

90 | __compar_d_fn_t cmp, void *arg) |

91 | { |

92 | char *base_ptr = (char *) pbase; |

93 | |

94 | const size_t max_thresh = MAX_THRESH * size; |

95 | |

96 | if (total_elems == 0) |

97 | /* Avoid lossage with unsigned arithmetic below. */ |

98 | return; |

99 | |

100 | if (total_elems > MAX_THRESH) |

101 | { |

102 | char *lo = base_ptr; |

103 | char *hi = &lo[size * (total_elems - 1)]; |

104 | stack_node stack[STACK_SIZE]; |

105 | stack_node *top = stack; |

106 | |

107 | PUSH (NULL, NULL); |

108 | |

109 | while (STACK_NOT_EMPTY) |

110 | { |

111 | char *left_ptr; |

112 | char *right_ptr; |

113 | |

114 | /* Select median value from among LO, MID, and HI. Rearrange |

115 | LO and HI so the three values are sorted. This lowers the |

116 | probability of picking a pathological pivot value and |

117 | skips a comparison for both the LEFT_PTR and RIGHT_PTR in |

118 | the while loops. */ |

119 | |

120 | char *mid = lo + size * ((hi - lo) / size >> 1); |

121 | |

122 | if ((*cmp) ((void *) mid, (void *) lo, arg) < 0) |

123 | SWAP (mid, lo, size); |

124 | if ((*cmp) ((void *) hi, (void *) mid, arg) < 0) |

125 | SWAP (mid, hi, size); |

126 | else |

127 | goto jump_over; |

128 | if ((*cmp) ((void *) mid, (void *) lo, arg) < 0) |

129 | SWAP (mid, lo, size); |

130 | jump_over:; |

131 | |

132 | left_ptr = lo + size; |

133 | right_ptr = hi - size; |

134 | |

135 | /* Here's the famous ``collapse the walls'' section of quicksort. |

136 | Gotta like those tight inner loops! They are the main reason |

137 | that this algorithm runs much faster than others. */ |

138 | do |

139 | { |

140 | while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0) |

141 | left_ptr += size; |

142 | |

143 | while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0) |

144 | right_ptr -= size; |

145 | |

146 | if (left_ptr < right_ptr) |

147 | { |

148 | SWAP (left_ptr, right_ptr, size); |

149 | if (mid == left_ptr) |

150 | mid = right_ptr; |

151 | else if (mid == right_ptr) |

152 | mid = left_ptr; |

153 | left_ptr += size; |

154 | right_ptr -= size; |

155 | } |

156 | else if (left_ptr == right_ptr) |

157 | { |

158 | left_ptr += size; |

159 | right_ptr -= size; |

160 | break; |

161 | } |

162 | } |

163 | while (left_ptr <= right_ptr); |

164 | |

165 | /* Set up pointers for next iteration. First determine whether |

166 | left and right partitions are below the threshold size. If so, |

167 | ignore one or both. Otherwise, push the larger partition's |

168 | bounds on the stack and continue sorting the smaller one. */ |

169 | |

170 | if ((size_t) (right_ptr - lo) <= max_thresh) |

171 | { |

172 | if ((size_t) (hi - left_ptr) <= max_thresh) |

173 | /* Ignore both small partitions. */ |

174 | POP (lo, hi); |

175 | else |

176 | /* Ignore small left partition. */ |

177 | lo = left_ptr; |

178 | } |

179 | else if ((size_t) (hi - left_ptr) <= max_thresh) |

180 | /* Ignore small right partition. */ |

181 | hi = right_ptr; |

182 | else if ((right_ptr - lo) > (hi - left_ptr)) |

183 | { |

184 | /* Push larger left partition indices. */ |

185 | PUSH (lo, right_ptr); |

186 | lo = left_ptr; |

187 | } |

188 | else |

189 | { |

190 | /* Push larger right partition indices. */ |

191 | PUSH (left_ptr, hi); |

192 | hi = right_ptr; |

193 | } |

194 | } |

195 | } |

196 | |

197 | /* Once the BASE_PTR array is partially sorted by quicksort the rest |

198 | is completely sorted using insertion sort, since this is efficient |

199 | for partitions below MAX_THRESH size. BASE_PTR points to the beginning |

200 | of the array to sort, and END_PTR points at the very last element in |

201 | the array (*not* one beyond it!). */ |

202 | |

203 | #define min(x, y) ((x) < (y) ? (x) : (y)) |

204 | |

205 | { |

206 | char *const end_ptr = &base_ptr[size * (total_elems - 1)]; |

207 | char *tmp_ptr = base_ptr; |

208 | char *thresh = min(end_ptr, base_ptr + max_thresh); |

209 | char *run_ptr; |

210 | |

211 | /* Find smallest element in first threshold and place it at the |

212 | array's beginning. This is the smallest array element, |

213 | and the operation speeds up insertion sort's inner loop. */ |

214 | |

215 | for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size) |

216 | if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0) |

217 | tmp_ptr = run_ptr; |

218 | |

219 | if (tmp_ptr != base_ptr) |

220 | SWAP (tmp_ptr, base_ptr, size); |

221 | |

222 | /* Insertion sort, running from left-hand-side up to right-hand-side. */ |

223 | |

224 | run_ptr = base_ptr + size; |

225 | while ((run_ptr += size) <= end_ptr) |

226 | { |

227 | tmp_ptr = run_ptr - size; |

228 | while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0) |

229 | tmp_ptr -= size; |

230 | |

231 | tmp_ptr += size; |

232 | if (tmp_ptr != run_ptr) |

233 | { |

234 | char *trav; |

235 | |

236 | trav = run_ptr + size; |

237 | while (--trav >= run_ptr) |

238 | { |

239 | char c = *trav; |

240 | char *hi, *lo; |

241 | |

242 | for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) |

243 | *hi = *lo; |

244 | *hi = c; |

245 | } |

246 | } |

247 | } |

248 | } |

249 | } |

250 |