]>
Commit | Line | Data |
---|---|---|
7434ccad | 1 | /* An alternative to qsort, with an identical interface. |
7cc27f44 | 2 | This file is part of the GNU C Library. |
688903eb | 3 | Copyright (C) 1992-2018 Free Software Foundation, Inc. |
fa8d436c | 4 | Written by Mike Haertel, September 1988. |
28f540f4 | 5 | |
7cc27f44 | 6 | The GNU C Library is free software; you can redistribute it and/or |
41bdb6e2 AJ |
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. | |
28f540f4 | 10 | |
7cc27f44 UD |
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 | |
41bdb6e2 | 14 | Lesser General Public License for more details. |
28f540f4 | 15 | |
41bdb6e2 | 16 | You should have received a copy of the GNU Lesser General Public |
59ba27a6 PE |
17 | License along with the GNU C Library; if not, see |
18 | <http://www.gnu.org/licenses/>. */ | |
28f540f4 | 19 | |
061d137b | 20 | #include <alloca.h> |
375d9429 | 21 | #include <stdint.h> |
28f540f4 RM |
22 | #include <stdlib.h> |
23 | #include <string.h> | |
8358825c | 24 | #include <unistd.h> |
44c8d1a2 | 25 | #include <memcopy.h> |
60092701 | 26 | #include <errno.h> |
fb88ac72 | 27 | #include <atomic.h> |
28f540f4 | 28 | |
375d9429 UD |
29 | struct msort_param |
30 | { | |
31 | size_t s; | |
32 | size_t var; | |
e458144c UD |
33 | __compar_d_fn_t cmp; |
34 | void *arg; | |
375d9429 UD |
35 | char *t; |
36 | }; | |
37 | static void msort_with_tmp (const struct msort_param *p, void *b, size_t n); | |
b750d5e7 | 38 | |
fa8d436c | 39 | static void |
375d9429 | 40 | msort_with_tmp (const struct msort_param *p, void *b, size_t n) |
b750d5e7 | 41 | { |
fa8d436c | 42 | char *b1, *b2; |
b750d5e7 | 43 | size_t n1, n2; |
b750d5e7 UD |
44 | |
45 | if (n <= 1) | |
fa8d436c | 46 | return; |
b750d5e7 | 47 | |
fa8d436c | 48 | n1 = n / 2; |
b750d5e7 | 49 | n2 = n - n1; |
b750d5e7 | 50 | b1 = b; |
375d9429 | 51 | b2 = (char *) b + (n1 * p->s); |
fa8d436c | 52 | |
375d9429 UD |
53 | msort_with_tmp (p, b1, n1); |
54 | msort_with_tmp (p, b2, n2); | |
fa8d436c | 55 | |
375d9429 UD |
56 | char *tmp = p->t; |
57 | const size_t s = p->s; | |
e458144c UD |
58 | __compar_d_fn_t cmp = p->cmp; |
59 | void *arg = p->arg; | |
375d9429 UD |
60 | switch (p->var) |
61 | { | |
62 | case 0: | |
63 | while (n1 > 0 && n2 > 0) | |
64 | { | |
e458144c | 65 | if ((*cmp) (b1, b2, arg) <= 0) |
375d9429 UD |
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 | { | |
e458144c | 83 | if ((*cmp) (b1, b2, arg) <= 0) |
375d9429 UD |
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; | |
e458144c | 105 | if ((*cmp) (b1, b2, arg) <= 0) |
375d9429 UD |
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 | { | |
e458144c | 124 | if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0) |
375d9429 UD |
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 | { | |
e458144c | 142 | if ((*cmp) (b1, b2, arg) <= 0) |
375d9429 UD |
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 | } | |
fa8d436c | 157 | |
fa8d436c UD |
158 | if (n1 > 0) |
159 | memcpy (tmp, b1, n1 * s); | |
375d9429 | 160 | memcpy (b, p->t, (n - n2) * s); |
28f540f4 RM |
161 | } |
162 | ||
e458144c | 163 | |
28f540f4 | 164 | void |
bef8fd60 | 165 | __qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg) |
28f540f4 | 166 | { |
375d9429 UD |
167 | size_t size = n * s; |
168 | char *tmp = NULL; | |
169 | struct msort_param p; | |
28f540f4 | 170 | |
375d9429 UD |
171 | /* For large object sizes use indirect sorting. */ |
172 | if (s > 32) | |
173 | size = 2 * n * sizeof (void *) + s; | |
284128f6 | 174 | |
375d9429 UD |
175 | if (size < 1024) |
176 | /* The temporary array is small, so put it on the stack. */ | |
177 | p.t = __alloca (size); | |
28f540f4 RM |
178 | else |
179 | { | |
8358825c UD |
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 | ||
fb88ac72 | 185 | if (pagesize == 0) |
28f540f4 | 186 | { |
8358825c UD |
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 | ||
fb88ac72 UD |
200 | /* Make sure phys_pages is written to memory. */ |
201 | atomic_write_barrier (); | |
202 | ||
8358825c | 203 | pagesize = __sysconf (_SC_PAGESIZE); |
28f540f4 | 204 | } |
8358825c UD |
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. */ | |
57b36a0a | 214 | if (size / pagesize > (size_t) phys_pages) |
28f540f4 | 215 | { |
e458144c | 216 | _quicksort (b, n, s, cmp, arg); |
375d9429 UD |
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. */ | |
e458144c | 228 | _quicksort (b, n, s, cmp, arg); |
375d9429 UD |
229 | return; |
230 | } | |
231 | p.t = tmp; | |
232 | } | |
233 | ||
234 | p.s = s; | |
375d9429 | 235 | p.var = 4; |
e458144c UD |
236 | p.cmp = cmp; |
237 | p.arg = arg; | |
375d9429 UD |
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; | |
e458144c | 279 | memcpy (jp, tmp_storage, s); |
375d9429 UD |
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; | |
28f540f4 | 296 | } |
375d9429 | 297 | msort_with_tmp (&p, b, n); |
28f540f4 | 298 | } |
375d9429 | 299 | free (tmp); |
28f540f4 | 300 | } |
bef8fd60 JM |
301 | libc_hidden_def (__qsort_r) |
302 | weak_alias (__qsort_r, qsort_r) | |
e458144c UD |
303 | |
304 | ||
305 | void | |
306 | qsort (void *b, size_t n, size_t s, __compar_fn_t cmp) | |
307 | { | |
bef8fd60 | 308 | return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL); |
e458144c | 309 | } |
284128f6 | 310 | libc_hidden_def (qsort) |