1/* An alternative to qsort, with an identical interface.
2 This file is part of the GNU C Library.
3 Copyright (C) 1992-2020 Free Software Foundation, Inc.
4 Written by Mike Haertel, September 1988.
5
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
10
11 The GNU C Library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
15
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; if not, see
18 <https://www.gnu.org/licenses/>. */
19
20#include <alloca.h>
21#include <stdint.h>
22#include <stdlib.h>
23#include <string.h>
24#include <unistd.h>
25#include <memcopy.h>
26#include <errno.h>
27#include <atomic.h>
28
29struct msort_param
30{
31 size_t s;
32 size_t var;
33 __compar_d_fn_t cmp;
34 void *arg;
35 char *t;
36};
37static void msort_with_tmp (const struct msort_param *p, void *b, size_t n);
38
39static void
40msort_with_tmp (const struct msort_param *p, void *b, size_t n)
41{
42 char *b1, *b2;
43 size_t n1, n2;
44
45 if (n <= 1)
46 return;
47
48 n1 = n / 2;
49 n2 = n - n1;
50 b1 = b;
51 b2 = (char *) b + (n1 * p->s);
52
53 msort_with_tmp (p, b1, n1);
54 msort_with_tmp (p, b2, n2);
55
56 char *tmp = p->t;
57 const size_t s = p->s;
58 __compar_d_fn_t cmp = p->cmp;
59 void *arg = p->arg;
60 switch (p->var)
61 {
62 case 0:
63 while (n1 > 0 && n2 > 0)
64 {
65 if ((*cmp) (b1, b2, arg) <= 0)
66 {
67 *(uint32_t *) tmp = *(uint32_t *) b1;
68 b1 += sizeof (uint32_t);
69 --n1;
70 }
71 else
72 {
73 *(uint32_t *) tmp = *(uint32_t *) b2;
74 b2 += sizeof (uint32_t);
75 --n2;
76 }
77 tmp += sizeof (uint32_t);
78 }
79 break;
80 case 1:
81 while (n1 > 0 && n2 > 0)
82 {
83 if ((*cmp) (b1, b2, arg) <= 0)
84 {
85 *(uint64_t *) tmp = *(uint64_t *) b1;
86 b1 += sizeof (uint64_t);
87 --n1;
88 }
89 else
90 {
91 *(uint64_t *) tmp = *(uint64_t *) b2;
92 b2 += sizeof (uint64_t);
93 --n2;
94 }
95 tmp += sizeof (uint64_t);
96 }
97 break;
98 case 2:
99 while (n1 > 0 && n2 > 0)
100 {
101 unsigned long *tmpl = (unsigned long *) tmp;
102 unsigned long *bl;
103
104 tmp += s;
105 if ((*cmp) (b1, b2, arg) <= 0)
106 {
107 bl = (unsigned long *) b1;
108 b1 += s;
109 --n1;
110 }
111 else
112 {
113 bl = (unsigned long *) b2;
114 b2 += s;
115 --n2;
116 }
117 while (tmpl < (unsigned long *) tmp)
118 *tmpl++ = *bl++;
119 }
120 break;
121 case 3:
122 while (n1 > 0 && n2 > 0)
123 {
124 if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
125 {
126 *(void **) tmp = *(void **) b1;
127 b1 += sizeof (void *);
128 --n1;
129 }
130 else
131 {
132 *(void **) tmp = *(void **) b2;
133 b2 += sizeof (void *);
134 --n2;
135 }
136 tmp += sizeof (void *);
137 }
138 break;
139 default:
140 while (n1 > 0 && n2 > 0)
141 {
142 if ((*cmp) (b1, b2, arg) <= 0)
143 {
144 tmp = (char *) __mempcpy (tmp, b1, s);
145 b1 += s;
146 --n1;
147 }
148 else
149 {
150 tmp = (char *) __mempcpy (tmp, b2, s);
151 b2 += s;
152 --n2;
153 }
154 }
155 break;
156 }
157
158 if (n1 > 0)
159 memcpy (tmp, b1, n1 * s);
160 memcpy (b, p->t, (n - n2) * s);
161}
162
163
164void
165__qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
166{
167 size_t size = n * s;
168 char *tmp = NULL;
169 struct msort_param p;
170
171 /* For large object sizes use indirect sorting. */
172 if (s > 32)
173 size = 2 * n * sizeof (void *) + s;
174
175 if (size < 1024)
176 /* The temporary array is small, so put it on the stack. */
177 p.t = __alloca (size);
178 else
179 {
180 /* We should avoid allocating too much memory since this might
181 have to be backed up by swap space. */
182 static long int phys_pages;
183 static int pagesize;
184
185 if (pagesize == 0)
186 {
187 phys_pages = __sysconf (_SC_PHYS_PAGES);
188
189 if (phys_pages == -1)
190 /* Error while determining the memory size. So let's
191 assume there is enough memory. Otherwise the
192 implementer should provide a complete implementation of
193 the `sysconf' function. */
194 phys_pages = (long int) (~0ul >> 1);
195
196 /* The following determines that we will never use more than
197 a quarter of the physical memory. */
198 phys_pages /= 4;
199
200 /* Make sure phys_pages is written to memory. */
201 atomic_write_barrier ();
202
203 pagesize = __sysconf (_SC_PAGESIZE);
204 }
205
206 /* Just a comment here. We cannot compute
207 phys_pages * pagesize
208 and compare the needed amount of memory against this value.
209 The problem is that some systems might have more physical
210 memory then can be represented with a `size_t' value (when
211 measured in bytes. */
212
213 /* If the memory requirements are too high don't allocate memory. */
214 if (size / pagesize > (size_t) phys_pages)
215 {
216 _quicksort (b, n, s, cmp, arg);
217 return;
218 }
219
220 /* It's somewhat large, so malloc it. */
221 int save = errno;
222 tmp = malloc (size);
223 __set_errno (save);
224 if (tmp == NULL)
225 {
226 /* Couldn't get space, so use the slower algorithm
227 that doesn't need a temporary array. */
228 _quicksort (b, n, s, cmp, arg);
229 return;
230 }
231 p.t = tmp;
232 }
233
234 p.s = s;
235 p.var = 4;
236 p.cmp = cmp;
237 p.arg = arg;
238
239 if (s > 32)
240 {
241 /* Indirect sorting. */
242 char *ip = (char *) b;
243 void **tp = (void **) (p.t + n * sizeof (void *));
244 void **t = tp;
245 void *tmp_storage = (void *) (tp + n);
246
247 while ((void *) t < tmp_storage)
248 {
249 *t++ = ip;
250 ip += s;
251 }
252 p.s = sizeof (void *);
253 p.var = 3;
254 msort_with_tmp (&p, p.t + n * sizeof (void *), n);
255
256 /* tp[0] .. tp[n - 1] is now sorted, copy around entries of
257 the original array. Knuth vol. 3 (2nd ed.) exercise 5.2-10. */
258 char *kp;
259 size_t i;
260 for (i = 0, ip = (char *) b; i < n; i++, ip += s)
261 if ((kp = tp[i]) != ip)
262 {
263 size_t j = i;
264 char *jp = ip;
265 memcpy (tmp_storage, ip, s);
266
267 do
268 {
269 size_t k = (kp - (char *) b) / s;
270 tp[j] = jp;
271 memcpy (jp, kp, s);
272 j = k;
273 jp = kp;
274 kp = tp[k];
275 }
276 while (kp != ip);
277
278 tp[j] = jp;
279 memcpy (jp, tmp_storage, s);
280 }
281 }
282 else
283 {
284 if ((s & (sizeof (uint32_t) - 1)) == 0
285 && ((char *) b - (char *) 0) % __alignof__ (uint32_t) == 0)
286 {
287 if (s == sizeof (uint32_t))
288 p.var = 0;
289 else if (s == sizeof (uint64_t)
290 && ((char *) b - (char *) 0) % __alignof__ (uint64_t) == 0)
291 p.var = 1;
292 else if ((s & (sizeof (unsigned long) - 1)) == 0
293 && ((char *) b - (char *) 0)
294 % __alignof__ (unsigned long) == 0)
295 p.var = 2;
296 }
297 msort_with_tmp (&p, b, n);
298 }
299 free (tmp);
300}
301libc_hidden_def (__qsort_r)
302weak_alias (__qsort_r, qsort_r)
303
304
305void
306qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
307{
308 return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
309}
310libc_hidden_def (qsort)
311