.
[glibc/history.git] / stdlib / msort.c
blob35cd4d03117e211b50e2068a9898da46e3cb6fd5
1 /* An alternative to qsort, with an identical interface.
2 This file is part of the GNU C Library.
3 Copyright (C) 1992,95-97,99,2000,01,02,04,07 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, write to the Free
18 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19 02111-1307 USA. */
21 #include <alloca.h>
22 #include <stdint.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <unistd.h>
26 #include <memcopy.h>
27 #include <errno.h>
29 struct msort_param
31 size_t s;
32 size_t var;
33 __compar_d_fn_t cmp;
34 void *arg;
35 char *t;
37 static void msort_with_tmp (const struct msort_param *p, void *b, size_t n);
39 static void
40 msort_with_tmp (const struct msort_param *p, void *b, size_t n)
42 char *b1, *b2;
43 size_t n1, n2;
45 if (n <= 1)
46 return;
48 n1 = n / 2;
49 n2 = n - n1;
50 b1 = b;
51 b2 = (char *) b + (n1 * p->s);
53 msort_with_tmp (p, b1, n1);
54 msort_with_tmp (p, b2, n2);
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)
62 case 0:
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);
69 --n1;
71 else
73 *(uint32_t *) tmp = *(uint32_t *) b2;
74 b2 += sizeof (uint32_t);
75 --n2;
77 tmp += sizeof (uint32_t);
79 break;
80 case 1:
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);
87 --n1;
89 else
91 *(uint64_t *) tmp = *(uint64_t *) b2;
92 b2 += sizeof (uint64_t);
93 --n2;
95 tmp += sizeof (uint64_t);
97 break;
98 case 2:
99 while (n1 > 0 && n2 > 0)
101 unsigned long *tmpl = (unsigned long *) tmp;
102 unsigned long *bl;
104 tmp += s;
105 if ((*cmp) (b1, b2, arg) <= 0)
107 bl = (unsigned long *) b1;
108 b1 += s;
109 --n1;
111 else
113 bl = (unsigned long *) b2;
114 b2 += s;
115 --n2;
117 while (tmpl < (unsigned long *) tmp)
118 *tmpl++ = *bl++;
120 break;
121 case 3:
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 *);
128 --n1;
130 else
132 *(void **) tmp = *(void **) b2;
133 b2 += sizeof (void *);
134 --n2;
136 tmp += sizeof (void *);
138 break;
139 default:
140 while (n1 > 0 && n2 > 0)
142 if ((*cmp) (b1, b2, arg) <= 0)
144 tmp = (char *) __mempcpy (tmp, b1, s);
145 b1 += s;
146 --n1;
148 else
150 tmp = (char *) __mempcpy (tmp, b2, s);
151 b2 += s;
152 --n2;
155 break;
158 if (n1 > 0)
159 memcpy (tmp, b1, n1 * s);
160 memcpy (b, p->t, (n - n2) * s);
164 void
165 qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
167 size_t size = n * s;
168 char *tmp = NULL;
169 struct msort_param p;
171 /* For large object sizes use indirect sorting. */
172 if (s > 32)
173 size = 2 * n * sizeof (void *) + s;
175 if (size < 1024)
176 /* The temporary array is small, so put it on the stack. */
177 p.t = __alloca (size);
178 else
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;
185 if (phys_pages == 0)
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. */
198 phys_pages /= 4;
200 pagesize = __sysconf (_SC_PAGESIZE);
203 /* Just a comment here. We cannot compute
204 phys_pages * pagesize
205 and compare the needed amount of memory against this value.
206 The problem is that some systems might have more physical
207 memory then can be represented with a `size_t' value (when
208 measured in bytes. */
210 /* If the memory requirements are too high don't allocate memory. */
211 if (size / pagesize > (size_t) phys_pages)
213 _quicksort (b, n, s, cmp, arg);
214 return;
217 /* It's somewhat large, so malloc it. */
218 int save = errno;
219 tmp = malloc (size);
220 __set_errno (save);
221 if (tmp == NULL)
223 /* Couldn't get space, so use the slower algorithm
224 that doesn't need a temporary array. */
225 _quicksort (b, n, s, cmp, arg);
226 return;
228 p.t = tmp;
231 p.s = s;
232 p.var = 4;
233 p.cmp = cmp;
234 p.arg = arg;
236 if (s > 32)
238 /* Indirect sorting. */
239 char *ip = (char *) b;
240 void **tp = (void **) (p.t + n * sizeof (void *));
241 void **t = tp;
242 void *tmp_storage = (void *) (tp + n);
244 while ((void *) t < tmp_storage)
246 *t++ = ip;
247 ip += s;
249 p.s = sizeof (void *);
250 p.var = 3;
251 msort_with_tmp (&p, p.t + n * sizeof (void *), n);
253 /* tp[0] .. tp[n - 1] is now sorted, copy around entries of
254 the original array. Knuth vol. 3 (2nd ed.) exercise 5.2-10. */
255 char *kp;
256 size_t i;
257 for (i = 0, ip = (char *) b; i < n; i++, ip += s)
258 if ((kp = tp[i]) != ip)
260 size_t j = i;
261 char *jp = ip;
262 memcpy (tmp_storage, ip, s);
266 size_t k = (kp - (char *) b) / s;
267 tp[j] = jp;
268 memcpy (jp, kp, s);
269 j = k;
270 jp = kp;
271 kp = tp[k];
273 while (kp != ip);
275 tp[j] = jp;
276 memcpy (jp, tmp_storage, s);
279 else
281 if ((s & (sizeof (uint32_t) - 1)) == 0
282 && ((char *) b - (char *) 0) % __alignof__ (uint32_t) == 0)
284 if (s == sizeof (uint32_t))
285 p.var = 0;
286 else if (s == sizeof (uint64_t)
287 && ((char *) b - (char *) 0) % __alignof__ (uint64_t) == 0)
288 p.var = 1;
289 else if ((s & (sizeof (unsigned long) - 1)) == 0
290 && ((char *) b - (char *) 0)
291 % __alignof__ (unsigned long) == 0)
292 p.var = 2;
294 msort_with_tmp (&p, b, n);
296 free (tmp);
298 libc_hidden_def (qsort_r)
301 void
302 qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
304 return qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
306 libc_hidden_def (qsort)