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