1 | /* Copyright (C) 1991-2022 Free Software Foundation, Inc. |
---|---|

2 | This file is part of the GNU C Library. |

3 | |

4 | The GNU C Library is free software; you can redistribute it and/or |

5 | modify it under the terms of the GNU Lesser General Public |

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

7 | version 2.1 of the License, or (at your option) any later version. |

8 | |

9 | The GNU C Library is distributed in the hope that it will be useful, |

10 | but WITHOUT ANY WARRANTY; without even the implied warranty of |

11 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |

12 | Lesser General Public License for more details. |

13 | |

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

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

16 | <https://www.gnu.org/licenses/>. */ |

17 | |

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

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

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

21 | |

22 | #include <alloca.h> |

23 | #include <limits.h> |

24 | #include <stdlib.h> |

25 | #include <string.h> |

26 | |

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

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

29 | do \ |

30 | { \ |

31 | size_t __size = (size); \ |

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

33 | do \ |

34 | { \ |

35 | char __tmp = *__a; \ |

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

37 | *__b++ = __tmp; \ |

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

39 | } while (0) |

40 | |

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

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

43 | #define MAX_THRESH 4 |

44 | |

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

46 | typedef struct |

47 | { |

48 | char *lo; |

49 | char *hi; |

50 | } stack_node; |

51 | |

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

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

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

55 | upper bound for log (total_elements): |

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

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

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

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

60 | #define STACK_NOT_EMPTY (stack < top) |

61 | |

62 | |

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

64 | four optimizations discussed in Sedgewick: |

65 | |

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

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

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

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

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

71 | Pretty cheap, actually. |

72 | |

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

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

75 | eliminates certain extraneous comparisons. |

76 | |

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

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

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

80 | sorted array segments. |

81 | |

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

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

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

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

86 | |

87 | void |

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

89 | __compar_d_fn_t cmp, void *arg) |

90 | { |

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

92 | |

93 | const size_t max_thresh = MAX_THRESH * size; |

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 | stack_node stack[STACK_SIZE]; |

104 | stack_node *top = stack; |

105 | |

106 | PUSH (NULL, NULL); |

107 | |

108 | while (STACK_NOT_EMPTY) |

109 | { |

110 | char *left_ptr; |

111 | char *right_ptr; |

112 | |

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

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

115 | probability of picking a pathological pivot value and |

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

117 | the while loops. */ |

118 | |

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

120 | |

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

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

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

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

125 | else |

126 | goto jump_over; |

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

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

129 | jump_over:; |

130 | |

131 | left_ptr = lo + size; |

132 | right_ptr = hi - size; |

133 | |

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

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

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

137 | do |

138 | { |

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

140 | left_ptr += size; |

141 | |

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

143 | right_ptr -= size; |

144 | |

145 | if (left_ptr < right_ptr) |

146 | { |

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

148 | if (mid == left_ptr) |

149 | mid = right_ptr; |

150 | else if (mid == right_ptr) |

151 | mid = left_ptr; |

152 | left_ptr += size; |

153 | right_ptr -= size; |

154 | } |

155 | else if (left_ptr == right_ptr) |

156 | { |

157 | left_ptr += size; |

158 | right_ptr -= size; |

159 | break; |

160 | } |

161 | } |

162 | while (left_ptr <= right_ptr); |

163 | |

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

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

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

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

168 | |

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

170 | { |

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

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

173 | POP (lo, hi); |

174 | else |

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

176 | lo = left_ptr; |

177 | } |

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

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

180 | hi = right_ptr; |

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

182 | { |

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

184 | PUSH (lo, right_ptr); |

185 | lo = left_ptr; |

186 | } |

187 | else |

188 | { |

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

190 | PUSH (left_ptr, hi); |

191 | hi = right_ptr; |

192 | } |

193 | } |

194 | } |

195 | |

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

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

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

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

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

201 | |

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

203 | |

204 | { |

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

206 | char *tmp_ptr = base_ptr; |

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

208 | char *run_ptr; |

209 | |

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

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

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

213 | |

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

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

216 | tmp_ptr = run_ptr; |

217 | |

218 | if (tmp_ptr != base_ptr) |

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

220 | |

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

222 | |

223 | run_ptr = base_ptr + size; |

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

225 | { |

226 | tmp_ptr = run_ptr - size; |

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

228 | tmp_ptr -= size; |

229 | |

230 | tmp_ptr += size; |

231 | if (tmp_ptr != run_ptr) |

232 | { |

233 | char *trav; |

234 | |

235 | trav = run_ptr + size; |

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

237 | { |

238 | char c = *trav; |

239 | char *hi, *lo; |

240 | |

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

242 | *hi = *lo; |

243 | *hi = c; |

244 | } |

245 | } |

246 | } |

247 | } |

248 | } |

249 |