1 /* Copyright (C) 1991-2023 Free Software Foundation, Inc.
2 This file is part of the GNU C Library.
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.
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.
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/>. */
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. */
29 /* Swap SIZE bytes between addresses A and B. These helpers are provided
30 along the generic one as an optimization. */
39 /* If this function returns true, elements can be safely copied using word
40 loads and stores. Otherwise, it might not be safe. BASE (as an integer)
41 must be a multiple of the word alignment. SIZE must be a multiple of
42 WORDSIZE. Since WORDSIZE must be a multiple of the word alignment, and
43 WORDSIZE is a power of two on all supported platforms, this function for
44 speed merely checks that BASE and SIZE are both multiples of the word
47 is_aligned (const void *base
, size_t size
, size_t wordsize
)
49 return (((uintptr_t) base
| size
) & (wordsize
- 1)) == 0;
53 swap_words_64 (void * restrict a
, void * restrict b
, size_t n
)
55 typedef uint64_t __attribute__ ((__may_alias__
)) u64_alias_t
;
59 u64_alias_t t
= *(u64_alias_t
*)(a
+ n
);
60 *(u64_alias_t
*)(a
+ n
) = *(u64_alias_t
*)(b
+ n
);
61 *(u64_alias_t
*)(b
+ n
) = t
;
66 swap_words_32 (void * restrict a
, void * restrict b
, size_t n
)
68 typedef uint32_t __attribute__ ((__may_alias__
)) u32_alias_t
;
72 u32_alias_t t
= *(u32_alias_t
*)(a
+ n
);
73 *(u32_alias_t
*)(a
+ n
) = *(u32_alias_t
*)(b
+ n
);
74 *(u32_alias_t
*)(b
+ n
) = t
;
78 /* Replace the indirect call with a serie of if statements. It should help
79 the branch predictor. */
81 do_swap (void * restrict a
, void * restrict b
, size_t size
,
82 enum swap_type_t swap_type
)
84 if (swap_type
== SWAP_WORDS_64
)
85 swap_words_64 (a
, b
, size
);
86 else if (swap_type
== SWAP_WORDS_32
)
87 swap_words_32 (a
, b
, size
);
89 __memswap (a
, b
, size
);
92 /* Discontinue quicksort algorithm when partition gets below this size.
93 This particular magic number was chosen to work best on a Sun 4/260. */
96 /* Stack node declarations used to store unfulfilled partition obligations. */
103 /* The stack needs log (total_elements) entries (we could even subtract
104 log(MAX_THRESH)). Since total_elements has type size_t, we get as
105 upper bound for log (total_elements):
106 bits per byte (CHAR_BIT) * sizeof(size_t). */
107 enum { STACK_SIZE
= CHAR_BIT
* sizeof (size_t) };
109 static inline stack_node
*
110 push (stack_node
*top
, char *lo
, char *hi
)
117 static inline stack_node
*
118 pop (stack_node
*top
, char **lo
, char **hi
)
128 insertion_sort_qsort_partitions (void *const pbase
, size_t total_elems
,
129 size_t size
, enum swap_type_t swap_type
,
130 __compar_d_fn_t cmp
, void *arg
)
132 char *base_ptr
= (char *) pbase
;
133 char *const end_ptr
= &base_ptr
[size
* (total_elems
- 1)];
134 char *tmp_ptr
= base_ptr
;
135 #define min(x, y) ((x) < (y) ? (x) : (y))
136 const size_t max_thresh
= MAX_THRESH
* size
;
137 char *thresh
= min(end_ptr
, base_ptr
+ max_thresh
);
140 /* Find smallest element in first threshold and place it at the
141 array's beginning. This is the smallest array element,
142 and the operation speeds up insertion sort's inner loop. */
144 for (run_ptr
= tmp_ptr
+ size
; run_ptr
<= thresh
; run_ptr
+= size
)
145 if (cmp (run_ptr
, tmp_ptr
, arg
) < 0)
148 if (tmp_ptr
!= base_ptr
)
149 do_swap (tmp_ptr
, base_ptr
, size
, swap_type
);
151 /* Insertion sort, running from left-hand-side up to right-hand-side. */
153 run_ptr
= base_ptr
+ size
;
154 while ((run_ptr
+= size
) <= end_ptr
)
156 tmp_ptr
= run_ptr
- size
;
157 while (cmp (run_ptr
, tmp_ptr
, arg
) < 0)
161 if (tmp_ptr
!= run_ptr
)
165 trav
= run_ptr
+ size
;
166 while (--trav
>= run_ptr
)
171 for (hi
= lo
= trav
; (lo
-= size
) >= tmp_ptr
; hi
= lo
)
179 /* Order size using quicksort. This implementation incorporates
180 four optimizations discussed in Sedgewick:
182 1. Non-recursive, using an explicit stack of pointer that store the
183 next array partition to sort. To save time, this maximum amount
184 of space required to store an array of SIZE_MAX is allocated on the
185 stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
186 only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
187 Pretty cheap, actually.
189 2. Chose the pivot element using a median-of-three decision tree.
190 This reduces the probability of selecting a bad pivot value and
191 eliminates certain extraneous comparisons.
193 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
194 insertion sort to order the MAX_THRESH items within each partition.
195 This is a big win, since insertion sort is faster for small, mostly
196 sorted array segments.
198 4. The larger of the two sub-partitions is always pushed onto the
199 stack first, with the algorithm then concentrating on the
200 smaller partition. This *guarantees* no more than log (total_elems)
201 stack size is needed (actually O(1) in this case)! */
204 _quicksort (void *const pbase
, size_t total_elems
, size_t size
,
205 __compar_d_fn_t cmp
, void *arg
)
207 char *base_ptr
= (char *) pbase
;
209 const size_t max_thresh
= MAX_THRESH
* size
;
211 if (total_elems
== 0)
212 /* Avoid lossage with unsigned arithmetic below. */
215 enum swap_type_t swap_type
;
216 if (is_aligned (pbase
, size
, 8))
217 swap_type
= SWAP_WORDS_64
;
218 else if (is_aligned (pbase
, size
, 4))
219 swap_type
= SWAP_WORDS_32
;
221 swap_type
= SWAP_BYTES
;
223 if (total_elems
> MAX_THRESH
)
226 char *hi
= &lo
[size
* (total_elems
- 1)];
227 stack_node stack
[STACK_SIZE
];
228 stack_node
*top
= stack
+ 1;
235 /* Select median value from among LO, MID, and HI. Rearrange
236 LO and HI so the three values are sorted. This lowers the
237 probability of picking a pathological pivot value and
238 skips a comparison for both the LEFT_PTR and RIGHT_PTR in
241 char *mid
= lo
+ size
* ((hi
- lo
) / size
>> 1);
243 if ((*cmp
) ((void *) mid
, (void *) lo
, arg
) < 0)
244 do_swap (mid
, lo
, size
, swap_type
);
245 if ((*cmp
) ((void *) hi
, (void *) mid
, arg
) < 0)
246 do_swap (mid
, hi
, size
, swap_type
);
249 if ((*cmp
) ((void *) mid
, (void *) lo
, arg
) < 0)
250 do_swap (mid
, lo
, size
, swap_type
);
253 left_ptr
= lo
+ size
;
254 right_ptr
= hi
- size
;
256 /* Here's the famous ``collapse the walls'' section of quicksort.
257 Gotta like those tight inner loops! They are the main reason
258 that this algorithm runs much faster than others. */
261 while ((*cmp
) ((void *) left_ptr
, (void *) mid
, arg
) < 0)
264 while ((*cmp
) ((void *) mid
, (void *) right_ptr
, arg
) < 0)
267 if (left_ptr
< right_ptr
)
269 do_swap (left_ptr
, right_ptr
, size
, swap_type
);
272 else if (mid
== right_ptr
)
277 else if (left_ptr
== right_ptr
)
284 while (left_ptr
<= right_ptr
);
286 /* Set up pointers for next iteration. First determine whether
287 left and right partitions are below the threshold size. If so,
288 ignore one or both. Otherwise, push the larger partition's
289 bounds on the stack and continue sorting the smaller one. */
291 if ((size_t) (right_ptr
- lo
) <= max_thresh
)
293 if ((size_t) (hi
- left_ptr
) <= max_thresh
)
294 /* Ignore both small partitions. */
295 top
= pop (top
, &lo
, &hi
);
297 /* Ignore small left partition. */
300 else if ((size_t) (hi
- left_ptr
) <= max_thresh
)
301 /* Ignore small right partition. */
303 else if ((right_ptr
- lo
) > (hi
- left_ptr
))
305 /* Push larger left partition indices. */
306 top
= push (top
, lo
, right_ptr
);
311 /* Push larger right partition indices. */
312 top
= push (top
, left_ptr
, hi
);
318 /* Once the BASE_PTR array is partially sorted by quicksort the rest
319 is completely sorted using insertion sort, since this is efficient
320 for partitions below MAX_THRESH size. BASE_PTR points to the beginning
321 of the array to sort, and END_PTR points at the very last element in
322 the array (*not* one beyond it!). */
323 insertion_sort_qsort_partitions (pbase
, total_elems
, size
, swap_type
, cmp
,