1 /* An alternative to qsort, with an identical interface.
2 This file is part of the GNU C Library.
3 Copyright (C) 1992-2014 Free Software Foundation, Inc.
4 Written by Mike Haertel, September 1988.
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.
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.
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 <http://www.gnu.org/licenses/>. */
37 static void msort_with_tmp (const struct msort_param *p, void *b, size_t n);
40 msort_with_tmp (const struct msort_param *p, void *b, size_t n)
51 b2 = (char *) b + (n1 * p->s);
53 msort_with_tmp (p, b1, n1);
54 msort_with_tmp (p, b2, n2);
57 const size_t s = p->s;
58 __compar_d_fn_t cmp = p->cmp;
63 while (n1 > 0 && n2 > 0)
65 if ((*cmp) (b1, b2, arg) <= 0)
67 *(uint32_t *) tmp = *(uint32_t *) b1;
68 b1 += sizeof (uint32_t);
73 *(uint32_t *) tmp = *(uint32_t *) b2;
74 b2 += sizeof (uint32_t);
77 tmp += sizeof (uint32_t);
81 while (n1 > 0 && n2 > 0)
83 if ((*cmp) (b1, b2, arg) <= 0)
85 *(uint64_t *) tmp = *(uint64_t *) b1;
86 b1 += sizeof (uint64_t);
91 *(uint64_t *) tmp = *(uint64_t *) b2;
92 b2 += sizeof (uint64_t);
95 tmp += sizeof (uint64_t);
99 while (n1 > 0 && n2 > 0)
101 unsigned long *tmpl = (unsigned long *) tmp;
105 if ((*cmp) (b1, b2, arg) <= 0)
107 bl = (unsigned long *) b1;
113 bl = (unsigned long *) b2;
117 while (tmpl < (unsigned long *) tmp)
122 while (n1 > 0 && n2 > 0)
124 if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
126 *(void **) tmp = *(void **) b1;
127 b1 += sizeof (void *);
132 *(void **) tmp = *(void **) b2;
133 b2 += sizeof (void *);
136 tmp += sizeof (void *);
140 while (n1 > 0 && n2 > 0)
142 if ((*cmp) (b1, b2, arg) <= 0)
144 tmp = (char *) __mempcpy (tmp, b1, s);
150 tmp = (char *) __mempcpy (tmp, b2, s);
159 memcpy (tmp, b1, n1 * s);
160 memcpy (b, p->t, (n - n2) * s);
165 qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
169 struct msort_param p;
171 /* For large object sizes use indirect sorting. */
173 size = 2 * n * sizeof (void *) + s;
176 /* The temporary array is small, so put it on the stack. */
177 p.t = __alloca (size);
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;
187 phys_pages = __sysconf (_SC_PHYS_PAGES);
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);
196 /* The following determines that we will never use more than
197 a quarter of the physical memory. */
200 /* Make sure phys_pages is written to memory. */
201 atomic_write_barrier ();
203 pagesize = __sysconf (_SC_PAGESIZE);
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. */
213 /* If the memory requirements are too high don't allocate memory. */
214 if (size / pagesize > (size_t) phys_pages)
216 _quicksort (b, n, s, cmp, arg);
220 /* It's somewhat large, so malloc it. */
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);
241 /* Indirect sorting. */
242 char *ip = (char *) b;
243 void **tp = (void **) (p.t + n * sizeof (void *));
245 void *tmp_storage = (void *) (tp + n);
247 while ((void *) t < tmp_storage)
252 p.s = sizeof (void *);
254 msort_with_tmp (&p, p.t + n * sizeof (void *), n);
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. */
260 for (i = 0, ip = (char *) b; i < n; i++, ip += s)
261 if ((kp = tp[i]) != ip)
265 memcpy (tmp_storage, ip, s);
269 size_t k = (kp - (char *) b) / s;
279 memcpy (jp, tmp_storage, s);
284 if ((s & (sizeof (uint32_t) - 1)) == 0
285 && ((char *) b - (char *) 0) % __alignof__ (uint32_t) == 0)
287 if (s == sizeof (uint32_t))
289 else if (s == sizeof (uint64_t)
290 && ((char *) b - (char *) 0) % __alignof__ (uint64_t) == 0)
292 else if ((s & (sizeof (unsigned long) - 1)) == 0
293 && ((char *) b - (char *) 0)
294 % __alignof__ (unsigned long) == 0)
297 msort_with_tmp (&p, b, n);
301 libc_hidden_def (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)