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 : 327139 : msort_with_tmp (const struct msort_param *p, void *b, size_t n)
71 : : {
72 : : char *b1, *b2;
73 : : size_t n1, n2;
74 : 327139 : char *tmp = p->t;
75 : 327139 : const size_t s = p->s;
76 : 327139 : GCompareDataFunc cmp = p->cmp;
77 : 327139 : void *arg = p->arg;
78 : :
79 : 327139 : if (n <= 1)
80 : 164341 : return;
81 : :
82 : 162798 : n1 = n / 2;
83 : 162798 : n2 = n - n1;
84 : 162798 : b1 = b;
85 : 162798 : b2 = (char *) b + (n1 * p->s);
86 : :
87 : 162798 : msort_with_tmp (p, b1, n1);
88 : 162798 : msort_with_tmp (p, b2, n2);
89 : :
90 : 162798 : switch (p->var)
91 : : {
92 : 99990 : case 0:
93 : 1304411 : while (n1 > 0 && n2 > 0)
94 : : {
95 : 1204421 : if ((*cmp) (b1, b2, arg) <= 0)
96 : : {
97 : 591476 : *(guint32 *) tmp = *(guint32 *) b1;
98 : 591476 : b1 += sizeof (guint32);
99 : 591476 : --n1;
100 : : }
101 : : else
102 : : {
103 : 612945 : *(guint32 *) tmp = *(guint32 *) b2;
104 : 612945 : b2 += sizeof (guint32);
105 : 612945 : --n2;
106 : : }
107 : 1204421 : tmp += sizeof (guint32);
108 : : }
109 : 99990 : break;
110 : 52512 : case 1:
111 : 659505 : while (n1 > 0 && n2 > 0)
112 : : {
113 : 606993 : if ((*cmp) (b1, b2, arg) <= 0)
114 : : {
115 : 298754 : *(guint64 *) tmp = *(guint64 *) b1;
116 : 298754 : b1 += sizeof (guint64);
117 : 298754 : --n1;
118 : : }
119 : : else
120 : : {
121 : 308239 : *(guint64 *) tmp = *(guint64 *) b2;
122 : 308239 : b2 += sizeof (guint64);
123 : 308239 : --n2;
124 : : }
125 : 606993 : tmp += sizeof (guint64);
126 : : }
127 : 52512 : break;
128 : 99 : case 2:
129 : 455 : while (n1 > 0 && n2 > 0)
130 : : {
131 : 356 : guintptr *tmpl = (guintptr *) tmp;
132 : : guintptr *bl;
133 : :
134 : 356 : tmp += s;
135 : 356 : if ((*cmp) (b1, b2, arg) <= 0)
136 : : {
137 : 0 : bl = (guintptr *) b1;
138 : 0 : b1 += s;
139 : 0 : --n1;
140 : : }
141 : : else
142 : : {
143 : 356 : bl = (guintptr *) b2;
144 : 356 : b2 += s;
145 : 356 : --n2;
146 : : }
147 : 1424 : while (tmpl < (guintptr *) tmp)
148 : 1068 : *tmpl++ = *bl++;
149 : : }
150 : 99 : break;
151 : 9999 : case 3:
152 : 130539 : while (n1 > 0 && n2 > 0)
153 : : {
154 : 120540 : if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
155 : : {
156 : 59217 : *(void **) tmp = *(void **) b1;
157 : 59217 : b1 += sizeof (void *);
158 : 59217 : --n1;
159 : : }
160 : : else
161 : : {
162 : 61323 : *(void **) tmp = *(void **) b2;
163 : 61323 : b2 += sizeof (void *);
164 : 61323 : --n2;
165 : : }
166 : 120540 : tmp += sizeof (void *);
167 : : }
168 : 9999 : break;
169 : 198 : default:
170 : 1286 : while (n1 > 0 && n2 > 0)
171 : : {
172 : 1088 : if ((*cmp) (b1, b2, arg) <= 0)
173 : : {
174 : 550 : memcpy (tmp, b1, s);
175 : 550 : tmp += s;
176 : 550 : b1 += s;
177 : 550 : --n1;
178 : : }
179 : : else
180 : : {
181 : 538 : memcpy (tmp, b2, s);
182 : 538 : tmp += s;
183 : 538 : b2 += s;
184 : 538 : --n2;
185 : : }
186 : : }
187 : 198 : break;
188 : : }
189 : :
190 : 162798 : if (n1 > 0)
191 : 72629 : memcpy (tmp, b1, n1 * s);
192 : 162798 : memcpy (b, p->t, (n - n2) * s);
193 : : }
194 : :
195 : :
196 : : static void
197 : 1543 : msort_r (void *b, size_t n, size_t s, GCompareDataFunc cmp, void *arg)
198 : : {
199 : 1543 : size_t size = n * s;
200 : 1543 : char *tmp = NULL;
201 : : struct msort_param p;
202 : :
203 : : /* For large object sizes use indirect sorting. */
204 : 1543 : if (s > 32)
205 : 1 : size = 2 * n * sizeof (void *) + s;
206 : :
207 : 1543 : if (size < 1024)
208 : : /* The temporary array is small, so put it on the stack. */
209 : 1526 : p.t = g_alloca (size);
210 : : else
211 : : {
212 : : /* It's large, so malloc it. */
213 : 17 : tmp = g_malloc (size);
214 : 17 : p.t = tmp;
215 : : }
216 : :
217 : 1543 : p.s = s;
218 : 1543 : p.var = 4;
219 : 1543 : p.cmp = cmp;
220 : 1543 : p.arg = arg;
221 : :
222 : 1543 : 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 : 9993 : size_t k = (kp - (char *) b) / s;
253 : 9993 : tp[j] = jp;
254 : 9993 : memcpy (jp, kp, s);
255 : 9993 : j = k;
256 : 9993 : jp = kp;
257 : 9993 : kp = tp[k];
258 : : }
259 : 9993 : while (kp != ip);
260 : :
261 : 5 : tp[j] = jp;
262 : 5 : memcpy (jp, tmp_storage, s);
263 : : }
264 : : }
265 : : else
266 : : {
267 : 1542 : if ((s & (sizeof (guint32) - 1)) == 0
268 : 1540 : && (gsize) (guintptr) b % G_ALIGNOF(guint32) == 0)
269 : : {
270 : 1540 : if (s == sizeof (guint32))
271 : 11 : p.var = 0;
272 : 1529 : else if (s == sizeof (guint64)
273 : 1528 : && (gsize) (guintptr) b % G_ALIGNOF(guint64) == 0)
274 : 1528 : p.var = 1;
275 : 1 : else if ((s & (sizeof (void *) - 1)) == 0
276 : 1 : && (gsize) (guintptr) b % G_ALIGNOF(void *) == 0)
277 : 1 : p.var = 2;
278 : : }
279 : 1542 : msort_with_tmp (&p, b, n);
280 : : }
281 : 1543 : g_free (tmp);
282 : 1543 : }
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()`](man:qsort(3)) function, but
293 : : * the comparison routine accepts a user data argument
294 : : * (like [`qsort_r()`](man:qsort_r(3))).
295 : : *
296 : : * Unlike `qsort()`, this is guaranteed to be a stable sort (since GLib 2.32).
297 : : *
298 : : * Deprecated: 2.82: `total_elems` is too small to represent larger arrays; use
299 : : * [func@GLib.sort_array] instead
300 : : */
301 : : void
302 : 1 : g_qsort_with_data (gconstpointer pbase,
303 : : gint total_elems,
304 : : gsize size,
305 : : GCompareDataFunc compare_func,
306 : : gpointer user_data)
307 : : {
308 : 1 : g_sort_array (pbase, total_elems, size, compare_func, user_data);
309 : 1 : }
310 : :
311 : : /**
312 : : * g_sort_array:
313 : : * @array: (not nullable) (array length=n_elements): start of array to sort
314 : : * @n_elements: number of elements in the array
315 : : * @element_size: size of each element
316 : : * @compare_func: (scope call): function to compare elements
317 : : * @user_data: data to pass to @compare_func
318 : : *
319 : : * This is just like the standard C [`qsort()`](man:qsort(3)) function, but
320 : : * the comparison routine accepts a user data argument
321 : : * (like [`qsort_r()`](man:qsort_r(3))).
322 : : *
323 : : * Unlike `qsort()`, this is guaranteed to be a stable sort.
324 : : *
325 : : * Since: 2.82
326 : : */
327 : : void
328 : 1543 : g_sort_array (const void *array,
329 : : size_t n_elements,
330 : : size_t element_size,
331 : : GCompareDataFunc compare_func,
332 : : void *user_data)
333 : : {
334 : 1543 : msort_r ((void *) array, n_elements, element_size, compare_func, user_data);
335 : 1543 : }
|
