Branch data Line data Source code
1 : : /* GLIB - Library of useful routines for C programming
2 : : * Copyright (C) 1991, 1992, 1996, 1997,1999,2004 Free Software Foundation, Inc.
3 : : * Copyright (C) 2000 Eazel, Inc.
4 : : * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
5 : : *
6 : : * SPDX-License-Identifier: LGPL-2.1-or-later
7 : : *
8 : : * This library is free software; you can redistribute it and/or
9 : : * modify it under the terms of the GNU Lesser General Public
10 : : * License as published by the Free Software Foundation; either
11 : : * version 2.1 of the License, or (at your option) any later version.
12 : : *
13 : : * This library is distributed in the hope that it will be useful,
14 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 : : * Lesser General Public License for more details.
17 : : *
18 : : * You should have received a copy of the GNU Lesser General Public
19 : : * License along with this library; if not, see <http://www.gnu.org/licenses/>.
20 : : */
21 : :
22 : : #include "config.h"
23 : :
24 : : #include <limits.h>
25 : : #include <stdlib.h>
26 : : #include <string.h>
27 : : #include "galloca.h"
28 : : #include "gmem.h"
29 : :
30 : : #include "gqsort.h"
31 : :
32 : : #include "gtestutils.h"
33 : :
34 : : /* This file was originally from stdlib/msort.c in gnu libc, just changed
35 : : to build inside glib and to not fall back to an unstable quicksort
36 : : for large arrays. */
37 : :
38 : : /* An alternative to qsort, with an identical interface.
39 : : This file is part of the GNU C Library.
40 : : Copyright (C) 1992,95-97,99,2000,01,02,04,07 Free Software Foundation, Inc.
41 : : Written by Mike Haertel, September 1988.
42 : :
43 : : The GNU C Library is free software; you can redistribute it and/or
44 : : modify it under the terms of the GNU Lesser General Public
45 : : License as published by the Free Software Foundation; either
46 : : version 2.1 of the License, or (at your option) any later version.
47 : :
48 : : The GNU C Library is distributed in the hope that it will be useful,
49 : : but WITHOUT ANY WARRANTY; without even the implied warranty of
50 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
51 : : Lesser General Public License for more details.
52 : :
53 : : You should have received a copy of the GNU Lesser General Public
54 : : License along with the GNU C Library; if not, see
55 : : <http://www.gnu.org/licenses/>. */
56 : :
57 : :
58 : : struct msort_param
59 : : {
60 : : size_t s;
61 : : size_t var;
62 : : GCompareDataFunc cmp;
63 : : void *arg;
64 : : char *t;
65 : : };
66 : :
67 : : static void msort_with_tmp (const struct msort_param *p, void *b, size_t n);
68 : :
69 : : static void
70 : 306383 : msort_with_tmp (const struct msort_param *p, void *b, size_t n)
71 : : {
72 : : char *b1, *b2;
73 : : size_t n1, n2;
74 : 306383 : char *tmp = p->t;
75 : 306383 : const size_t s = p->s;
76 : 306383 : GCompareDataFunc cmp = p->cmp;
77 : 306383 : void *arg = p->arg;
78 : :
79 [ + + ]: 306383 : if (n <= 1)
80 : 153940 : return;
81 : :
82 : 152443 : n1 = n / 2;
83 : 152443 : n2 = n - n1;
84 : 152443 : b1 = b;
85 : 152443 : b2 = (char *) b + (n1 * p->s);
86 : :
87 : 152443 : msort_with_tmp (p, b1, n1);
88 : 152443 : msort_with_tmp (p, b2, n2);
89 : :
90 [ + + - + : 152443 : switch (p->var)
+ ]
91 : : {
92 : 89991 : case 0:
93 [ + + + + ]: 1173897 : while (n1 > 0 && n2 > 0)
94 : : {
95 [ + + ]: 1083906 : if ((*cmp) (b1, b2, arg) <= 0)
96 : : {
97 : 532273 : *(guint32 *) tmp = *(guint32 *) b1;
98 : 532273 : b1 += sizeof (guint32);
99 : 532273 : --n1;
100 : : }
101 : : else
102 : : {
103 : 551633 : *(guint32 *) tmp = *(guint32 *) b2;
104 : 551633 : b2 += sizeof (guint32);
105 : 551633 : --n2;
106 : : }
107 : 1083906 : tmp += sizeof (guint32);
108 : : }
109 : 89991 : break;
110 : 52255 : case 1:
111 [ + + + + ]: 658814 : while (n1 > 0 && n2 > 0)
112 : : {
113 [ + + ]: 606559 : if ((*cmp) (b1, b2, arg) <= 0)
114 : : {
115 : 298645 : *(guint64 *) tmp = *(guint64 *) b1;
116 : 298645 : b1 += sizeof (guint64);
117 : 298645 : --n1;
118 : : }
119 : : else
120 : : {
121 : 307914 : *(guint64 *) tmp = *(guint64 *) b2;
122 : 307914 : b2 += sizeof (guint64);
123 : 307914 : --n2;
124 : : }
125 : 606559 : tmp += sizeof (guint64);
126 : : }
127 : 52255 : break;
128 : 0 : case 2:
129 [ # # # # ]: 0 : while (n1 > 0 && n2 > 0)
130 : : {
131 : 0 : guintptr *tmpl = (guintptr *) tmp;
132 : : guintptr *bl;
133 : :
134 : 0 : tmp += s;
135 [ # # ]: 0 : if ((*cmp) (b1, b2, arg) <= 0)
136 : : {
137 : 0 : bl = (guintptr *) b1;
138 : 0 : b1 += s;
139 : 0 : --n1;
140 : : }
141 : : else
142 : : {
143 : 0 : bl = (guintptr *) b2;
144 : 0 : b2 += s;
145 : 0 : --n2;
146 : : }
147 [ # # ]: 0 : while (tmpl < (guintptr *) tmp)
148 : 0 : *tmpl++ = *bl++;
149 : : }
150 : 0 : break;
151 : 9999 : case 3:
152 [ + + + + ]: 130456 : while (n1 > 0 && n2 > 0)
153 : : {
154 [ + + ]: 120457 : if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
155 : : {
156 : 59107 : *(void **) tmp = *(void **) b1;
157 : 59107 : b1 += sizeof (void *);
158 : 59107 : --n1;
159 : : }
160 : : else
161 : : {
162 : 61350 : *(void **) tmp = *(void **) b2;
163 : 61350 : b2 += sizeof (void *);
164 : 61350 : --n2;
165 : : }
166 : 120457 : tmp += sizeof (void *);
167 : : }
168 : 9999 : break;
169 : 198 : default:
170 [ + + + + ]: 1289 : while (n1 > 0 && n2 > 0)
171 : : {
172 [ + + ]: 1091 : if ((*cmp) (b1, b2, arg) <= 0)
173 : : {
174 : 547 : memcpy (tmp, b1, s);
175 : 547 : tmp += s;
176 : 547 : b1 += s;
177 : 547 : --n1;
178 : : }
179 : : else
180 : : {
181 : 544 : memcpy (tmp, b2, s);
182 : 544 : tmp += s;
183 : 544 : b2 += s;
184 : 544 : --n2;
185 : : }
186 : : }
187 : 198 : break;
188 : : }
189 : :
190 [ + + ]: 152443 : if (n1 > 0)
191 : 67908 : memcpy (tmp, b1, n1 * s);
192 : 152443 : memcpy (b, p->t, (n - n2) * s);
193 : : }
194 : :
195 : :
196 : : static void
197 : 1497 : msort_r (void *b, size_t n, size_t s, GCompareDataFunc cmp, void *arg)
198 : : {
199 : 1497 : size_t size = n * s;
200 : 1497 : char *tmp = NULL;
201 : : struct msort_param p;
202 : :
203 : : /* For large object sizes use indirect sorting. */
204 [ + + ]: 1497 : if (s > 32)
205 : 1 : size = 2 * n * sizeof (void *) + s;
206 : :
207 [ + + ]: 1497 : if (size < 1024)
208 : : /* The temporary array is small, so put it on the stack. */
209 : 1482 : p.t = g_alloca (size);
210 : : else
211 : : {
212 : : /* It's large, so malloc it. */
213 : 15 : tmp = g_malloc (size);
214 : 15 : p.t = tmp;
215 : : }
216 : :
217 : 1497 : p.s = s;
218 : 1497 : p.var = 4;
219 : 1497 : p.cmp = cmp;
220 : 1497 : p.arg = arg;
221 : :
222 [ + + ]: 1497 : if (s > 32)
223 : : {
224 : : /* Indirect sorting. */
225 : 1 : char *ip = (char *) b;
226 : 1 : void **tp = (void **) (p.t + n * sizeof (void *));
227 : 1 : void **t = tp;
228 : 1 : void *tmp_storage = (void *) (tp + n);
229 : : char *kp;
230 : : size_t i;
231 : :
232 [ + + ]: 10001 : while ((void *) t < tmp_storage)
233 : : {
234 : 10000 : *t++ = ip;
235 : 10000 : ip += s;
236 : : }
237 : 1 : p.s = sizeof (void *);
238 : 1 : p.var = 3;
239 : 1 : msort_with_tmp (&p, p.t + n * sizeof (void *), n);
240 : :
241 : : /* tp[0] .. tp[n - 1] is now sorted, copy around entries of
242 : : the original array. Knuth vol. 3 (2nd ed.) exercise 5.2-10. */
243 [ + + ]: 10001 : for (i = 0, ip = (char *) b; i < n; i++, ip += s)
244 [ + + ]: 10000 : if ((kp = tp[i]) != ip)
245 : : {
246 : 5 : size_t j = i;
247 : 5 : char *jp = ip;
248 : 5 : memcpy (tmp_storage, ip, s);
249 : :
250 : : do
251 : : {
252 : 9995 : size_t k = (kp - (char *) b) / s;
253 : 9995 : tp[j] = jp;
254 : 9995 : memcpy (jp, kp, s);
255 : 9995 : j = k;
256 : 9995 : jp = kp;
257 : 9995 : kp = tp[k];
258 : : }
259 [ + + ]: 9995 : while (kp != ip);
260 : :
261 : 5 : tp[j] = jp;
262 : 5 : memcpy (jp, tmp_storage, s);
263 : : }
264 : : }
265 : : else
266 : : {
267 [ + + ]: 1496 : if ((s & (sizeof (guint32) - 1)) == 0
268 [ + - ]: 1494 : && (gsize) (guintptr) b % G_ALIGNOF(guint32) == 0)
269 : : {
270 [ + + ]: 1494 : if (s == sizeof (guint32))
271 : 10 : p.var = 0;
272 [ + - ]: 1484 : else if (s == sizeof (guint64)
273 [ + - ]: 1484 : && (gsize) (guintptr) b % G_ALIGNOF(guint64) == 0)
274 : 1484 : p.var = 1;
275 [ # # ]: 0 : else if ((s & (sizeof (void *) - 1)) == 0
276 [ # # ]: 0 : && (gsize) (guintptr) b % G_ALIGNOF(void *) == 0)
277 : 0 : p.var = 2;
278 : : }
279 : 1496 : msort_with_tmp (&p, b, n);
280 : : }
281 : 1497 : g_free (tmp);
282 : 1497 : }
283 : :
284 : : /**
285 : : * g_qsort_with_data:
286 : : * @pbase: (not nullable): start of array to sort
287 : : * @total_elems: elements in the array
288 : : * @size: size of each element
289 : : * @compare_func: (scope call): function to compare elements
290 : : * @user_data: data to pass to @compare_func
291 : : *
292 : : * This is just like the standard C qsort() function, but
293 : : * the comparison routine accepts a user data argument.
294 : : *
295 : : * This is guaranteed to be a stable sort since version 2.32.
296 : : */
297 : : void
298 : 1497 : g_qsort_with_data (gconstpointer pbase,
299 : : gint total_elems,
300 : : gsize size,
301 : : GCompareDataFunc compare_func,
302 : : gpointer user_data)
303 : : {
304 : 1497 : msort_r ((gpointer)pbase, total_elems, size, compare_func, user_data);
305 : 1497 : }
|
