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.
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.
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.
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/>. */
36 static void msort_with_tmp (const struct msort_param *p, void *b, size_t n);
39 msort_with_tmp (const struct msort_param *p, void *b, size_t n)
50 b2 = (char *) b + (n1 * p->s);
52 msort_with_tmp (p, b1, n1);
53 msort_with_tmp (p, b2, n2);
56 const size_t s = p->s;
57 __compar_d_fn_t cmp = p->cmp;
62 while (n1 > 0 && n2 > 0)
64 if ((*cmp) (b1, b2, arg) <= 0)
66 *(uint32_t *) tmp = *(uint32_t *) b1;
67 b1 += sizeof (uint32_t);
72 *(uint32_t *) tmp = *(uint32_t *) b2;
73 b2 += sizeof (uint32_t);
76 tmp += sizeof (uint32_t);
80 while (n1 > 0 && n2 > 0)
82 if ((*cmp) (b1, b2, arg) <= 0)
84 *(uint64_t *) tmp = *(uint64_t *) b1;
85 b1 += sizeof (uint64_t);
90 *(uint64_t *) tmp = *(uint64_t *) b2;
91 b2 += sizeof (uint64_t);
94 tmp += sizeof (uint64_t);
98 while (n1 > 0 && n2 > 0)
100 unsigned long *tmpl = (unsigned long *) tmp;
104 if ((*cmp) (b1, b2, arg) <= 0)
106 bl = (unsigned long *) b1;
112 bl = (unsigned long *) b2;
116 while (tmpl < (unsigned long *) tmp)
121 while (n1 > 0 && n2 > 0)
123 if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
125 *(void **) tmp = *(void **) b1;
126 b1 += sizeof (void *);
131 *(void **) tmp = *(void **) b2;
132 b2 += sizeof (void *);
135 tmp += sizeof (void *);
139 while (n1 > 0 && n2 > 0)
141 if ((*cmp) (b1, b2, arg) <= 0)
143 tmp = (char *) __mempcpy (tmp, b1, s);
149 tmp = (char *) __mempcpy (tmp, b2, s);
158 memcpy (tmp, b1, n1 * s);
159 memcpy (b, p->t, (n - n2) * s);
164 __qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
168 struct msort_param p;
170 /* For large object sizes use indirect sorting. */
172 size = 2 * n * sizeof (void *) + s;
175 /* The temporary array is small, so put it on the stack. */
176 p.t = __alloca (size);
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;
186 phys_pages = __sysconf (_SC_PHYS_PAGES);
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);
195 /* The following determines that we will never use more than
196 a quarter of the physical memory. */
199 /* Make sure phys_pages is written to memory. */
200 atomic_write_barrier ();
202 pagesize = __sysconf (_SC_PAGESIZE);
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. */
212 /* If the memory requirements are too high don't allocate memory. */
213 if (size / pagesize > (size_t) phys_pages)
215 _quicksort (b, n, s, cmp, arg);
219 /* It's somewhat large, so malloc it. */
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);
240 /* Indirect sorting. */
241 char *ip = (char *) b;
242 void **tp = (void **) (p.t + n * sizeof (void *));
244 void *tmp_storage = (void *) (tp + n);
246 while ((void *) t < tmp_storage)
251 p.s = sizeof (void *);
253 msort_with_tmp (&p, p.t + n * sizeof (void *), n);
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. */
259 for (i = 0, ip = (char *) b; i < n; i++, ip += s)
260 if ((kp = tp[i]) != ip)
264 memcpy (tmp_storage, ip, s);
268 size_t k = (kp - (char *) b) / s;
278 memcpy (jp, tmp_storage, s);
283 if ((s & (sizeof (uint32_t) - 1)) == 0
284 && ((uintptr_t) b) % __alignof__ (uint32_t) == 0)
286 if (s == sizeof (uint32_t))
288 else if (s == sizeof (uint64_t)
289 && ((uintptr_t) b) % __alignof__ (uint64_t) == 0)
291 else if ((s & (sizeof (unsigned long) - 1)) == 0
293 % __alignof__ (unsigned long) == 0)
296 msort_with_tmp (&p, b, n);
300 libc_hidden_def (__qsort_r)
301 weak_alias (__qsort_r, qsort_r)
305 qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
307 return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
309 libc_hidden_def (qsort)