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 : 651258 : msort_with_tmp (const struct msort_param *p, void *b, size_t n)
71 : : {
72 : : char *b1, *b2;
73 : : size_t n1, n2;
74 : 651258 : char *tmp = p->t;
75 : 651258 : const size_t s = p->s;
76 : 651258 : GCompareDataFunc cmp = p->cmp;
77 : 651258 : void *arg = p->arg;
78 : :
79 : 651258 : if (n <= 1)
80 : 326789 : return;
81 : :
82 : 324469 : n1 = n / 2;
83 : 324469 : n2 = n - n1;
84 : 324469 : b1 = b;
85 : 324469 : b2 = (char *) b + (n1 * p->s);
86 : :
87 : 324469 : msort_with_tmp (p, b1, n1);
88 : 324469 : msort_with_tmp (p, b2, n2);
89 : :
90 : 324469 : switch (p->var)
91 : : {
92 : 99990 : case 0:
93 : 2609307 : while (n1 > 0 && n2 > 0)
94 : : {
95 : 2409327 : if ((*cmp) (b1, b2, arg) <= 0)
96 : : {
97 : 1183010 : *(guint32 *) tmp = *(guint32 *) b1;
98 : 1183010 : b1 += sizeof (guint32);
99 : 1183010 : --n1;
100 : 591258 : }
101 : : else
102 : : {
103 : 1226317 : *(guint32 *) tmp = *(guint32 *) b2;
104 : 1226317 : b2 += sizeof (guint32);
105 : 1226317 : --n2;
106 : : }
107 : 2409327 : tmp += sizeof (guint32);
108 : : }
109 : 199980 : break;
110 : 52819 : case 1:
111 : 1314879 : while (n1 > 0 && n2 > 0)
112 : : {
113 : 1210982 : if ((*cmp) (b1, b2, arg) <= 0)
114 : : {
115 : 597001 : *(guint64 *) tmp = *(guint64 *) b1;
116 : 597001 : b1 += sizeof (guint64);
117 : 597001 : --n1;
118 : 297339 : }
119 : : else
120 : : {
121 : 613981 : *(guint64 *) tmp = *(guint64 *) b2;
122 : 613981 : b2 += sizeof (guint64);
123 : 613981 : --n2;
124 : : }
125 : 1210982 : tmp += sizeof (guint64);
126 : : }
127 : 103897 : break;
128 : 99 : case 2:
129 : 910 : while (n1 > 0 && n2 > 0)
130 : : {
131 : 712 : guintptr *tmpl = (guintptr *) tmp;
132 : : guintptr *bl;
133 : :
134 : 712 : tmp += s;
135 : 712 : if ((*cmp) (b1, b2, arg) <= 0)
136 : : {
137 : 0 : bl = (guintptr *) b1;
138 : 0 : b1 += s;
139 : 0 : --n1;
140 : 0 : }
141 : : else
142 : : {
143 : 712 : bl = (guintptr *) b2;
144 : 712 : b2 += s;
145 : 712 : --n2;
146 : : }
147 : 2848 : while (tmpl < (guintptr *) tmp)
148 : 2136 : *tmpl++ = *bl++;
149 : : }
150 : 198 : break;
151 : 9999 : case 3:
152 : 260799 : while (n1 > 0 && n2 > 0)
153 : : {
154 : 240801 : if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
155 : : {
156 : 118137 : *(void **) tmp = *(void **) b1;
157 : 118137 : b1 += sizeof (void *);
158 : 118137 : --n1;
159 : 59025 : }
160 : : else
161 : : {
162 : 122664 : *(void **) tmp = *(void **) b2;
163 : 122664 : b2 += sizeof (void *);
164 : 122664 : --n2;
165 : : }
166 : 240801 : tmp += sizeof (void *);
167 : : }
168 : 19998 : break;
169 : 198 : default:
170 : 2565 : while (n1 > 0 && n2 > 0)
171 : : {
172 : 2169 : if ((*cmp) (b1, b2, arg) <= 0)
173 : : {
174 : 1079 : memcpy (tmp, b1, s);
175 : 1079 : tmp += s;
176 : 1079 : b1 += s;
177 : 1079 : --n1;
178 : 547 : }
179 : : else
180 : : {
181 : 1090 : memcpy (tmp, b2, s);
182 : 1090 : tmp += s;
183 : 1090 : b2 += s;
184 : 1090 : --n2;
185 : : }
186 : : }
187 : 396 : break;
188 : : }
189 : :
190 : 324469 : if (n1 > 0)
191 : 144709 : memcpy (tmp, b1, n1 * s);
192 : 324469 : memcpy (b, p->t, (n - n2) * s);
193 : 323317 : }
194 : :
195 : :
196 : : static void
197 : 2320 : msort_r (void *b, size_t n, size_t s, GCompareDataFunc cmp, void *arg)
198 : : {
199 : 2320 : size_t size = n * s;
200 : 2320 : char *tmp = NULL;
201 : : struct msort_param p;
202 : :
203 : : /* For large object sizes use indirect sorting. */
204 : 2320 : if (s > 32)
205 : 2 : size = 2 * n * sizeof (void *) + s;
206 : :
207 : 2320 : if (size < 1024)
208 : : /* The temporary array is small, so put it on the stack. */
209 : 2286 : p.t = g_alloca (size);
210 : : else
211 : : {
212 : : /* It's large, so malloc it. */
213 : 34 : tmp = g_malloc (size);
214 : 34 : p.t = tmp;
215 : : }
216 : :
217 : 2320 : p.s = s;
218 : 2320 : p.var = 4;
219 : 2320 : p.cmp = cmp;
220 : 2320 : p.arg = arg;
221 : :
222 : 2320 : if (s > 32)
223 : : {
224 : : /* Indirect sorting. */
225 : 2 : char *ip = (char *) b;
226 : 2 : void **tp = (void **) (p.t + n * sizeof (void *));
227 : 2 : void **t = tp;
228 : 2 : void *tmp_storage = (void *) (tp + n);
229 : : char *kp;
230 : : size_t i;
231 : :
232 : 20002 : while ((void *) t < tmp_storage)
233 : : {
234 : 20000 : *t++ = ip;
235 : 20000 : ip += s;
236 : : }
237 : 2 : p.s = sizeof (void *);
238 : 2 : p.var = 3;
239 : 2 : 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 : 20002 : for (i = 0, ip = (char *) b; i < n; i++, ip += s)
244 : 20007 : if ((kp = tp[i]) != ip)
245 : : {
246 : 18 : size_t j = i;
247 : 18 : char *jp = ip;
248 : 18 : memcpy (tmp_storage, ip, s);
249 : :
250 : 7 : do
251 : : {
252 : 19980 : size_t k = (kp - (char *) b) / s;
253 : 19980 : tp[j] = jp;
254 : 19980 : memcpy (jp, kp, s);
255 : 19980 : j = k;
256 : 19980 : jp = kp;
257 : 19980 : kp = tp[k];
258 : 9993 : }
259 : 19980 : while (kp != ip);
260 : :
261 : 18 : tp[j] = jp;
262 : 18 : memcpy (jp, tmp_storage, s);
263 : 7 : }
264 : 1 : }
265 : : else
266 : : {
267 : 2318 : if ((s & (sizeof (guint32) - 1)) == 0
268 : 2316 : && (gsize) (guintptr) b % G_ALIGNOF(guint32) == 0)
269 : : {
270 : 2314 : if (s == sizeof (guint32))
271 : 22 : p.var = 0;
272 : 2292 : else if (s == sizeof (guint64)
273 : 2291 : && (gsize) (guintptr) b % G_ALIGNOF(guint64) == 0)
274 : 2290 : p.var = 1;
275 : 2 : else if ((s & (sizeof (void *) - 1)) == 0
276 : 2 : && (gsize) (guintptr) b % G_ALIGNOF(void *) == 0)
277 : 2 : p.var = 2;
278 : 586 : }
279 : 2318 : msort_with_tmp (&p, b, n);
280 : : }
281 : 2320 : g_free (tmp);
282 : 2320 : }
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 : 2 : g_qsort_with_data (gconstpointer pbase,
303 : : gint total_elems,
304 : : gsize size,
305 : : GCompareDataFunc compare_func,
306 : : gpointer user_data)
307 : : {
308 : 2 : g_sort_array (pbase, total_elems, size, compare_func, user_data);
309 : 2 : }
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 : : * An example of sorting an array of strings (a strv):
326 : : * ```
327 : : * static int
328 : : * strcmp_data (const void *a,
329 : : * const void *b,
330 : : * void *user_data)
331 : : * {
332 : : * return strcmp (*((const char * const *) a), *((const char * const *) b));
333 : : * }
334 : : *
335 : : * char **my_strv = …;
336 : : * size_t my_strv_length = g_strv_length (my_strv);
337 : : * g_sort_array (my_strv, (my_strv_length, sizeof (*my_strv), strcmp_data, NULL);
338 : : * ```
339 : : *
340 : : * Since: 2.82
341 : : */
342 : : void
343 : 2320 : g_sort_array (const void *array,
344 : : size_t n_elements,
345 : : size_t element_size,
346 : : GCompareDataFunc compare_func,
347 : : void *user_data)
348 : : {
349 : 2320 : msort_r ((void *) array, n_elements, element_size, compare_func, user_data);
350 : 2320 : }
|
