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 msort_with_tmp (const struct msort_param *p, void *b, size_t n)
71 {
72 char *b1, *b2;
73 size_t n1, n2;
74 char *tmp = p->t;
75 const size_t s = p->s;
76 GCompareDataFunc cmp = p->cmp;
77 void *arg = p->arg;
78
79 if (n <= 1)
80 return;
81
82 n1 = n / 2;
83 n2 = n - n1;
84 b1 = b;
85 b2 = (char *) b + (n1 * p->s);
86
87 msort_with_tmp (p, b1, n1);
88 msort_with_tmp (p, b2, n2);
89
90 switch (p->var)
91 {
92 case 0:
93 while (n1 > 0 && n2 > 0)
94 {
95 if ((*cmp) (b1, b2, arg) <= 0)
96 {
97 *(guint32 *) tmp = *(guint32 *) b1;
98 b1 += sizeof (guint32);
99 --n1;
100 }
101 else
102 {
103 *(guint32 *) tmp = *(guint32 *) b2;
104 b2 += sizeof (guint32);
105 --n2;
106 }
107 tmp += sizeof (guint32);
108 }
109 break;
110 case 1:
111 while (n1 > 0 && n2 > 0)
112 {
113 if ((*cmp) (b1, b2, arg) <= 0)
114 {
115 *(guint64 *) tmp = *(guint64 *) b1;
116 b1 += sizeof (guint64);
117 --n1;
118 }
119 else
120 {
121 *(guint64 *) tmp = *(guint64 *) b2;
122 b2 += sizeof (guint64);
123 --n2;
124 }
125 tmp += sizeof (guint64);
126 }
127 break;
128 case 2:
129 while (n1 > 0 && n2 > 0)
130 {
131 guintptr *tmpl = (guintptr *) tmp;
132 guintptr *bl;
133
134 tmp += s;
135 if ((*cmp) (b1, b2, arg) <= 0)
136 {
137 bl = (guintptr *) b1;
138 b1 += s;
139 --n1;
140 }
141 else
142 {
143 bl = (guintptr *) b2;
144 b2 += s;
145 --n2;
146 }
147 while (tmpl < (guintptr *) tmp)
148 *tmpl++ = *bl++;
149 }
150 break;
151 case 3:
152 while (n1 > 0 && n2 > 0)
153 {
154 if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
155 {
156 *(void **) tmp = *(void **) b1;
157 b1 += sizeof (void *);
158 --n1;
159 }
160 else
161 {
162 *(void **) tmp = *(void **) b2;
163 b2 += sizeof (void *);
164 --n2;
165 }
166 tmp += sizeof (void *);
167 }
168 break;
169 default:
170 while (n1 > 0 && n2 > 0)
171 {
172 if ((*cmp) (b1, b2, arg) <= 0)
173 {
174 memcpy (tmp, b1, s);
175 tmp += s;
176 b1 += s;
177 --n1;
178 }
179 else
180 {
181 memcpy (tmp, b2, s);
182 tmp += s;
183 b2 += s;
184 --n2;
185 }
186 }
187 break;
188 }
189
190 if (n1 > 0)
191 memcpy (tmp, b1, n1 * s);
192 memcpy (b, p->t, (n - n2) * s);
193 }
194
195
196 static void
197 msort_r (void *b, size_t n, size_t s, GCompareDataFunc cmp, void *arg)
198 {
199 size_t size = n * s;
200 char *tmp = NULL;
201 struct msort_param p;
202
203 /* For large object sizes use indirect sorting. */
204 if (s > 32)
205 size = 2 * n * sizeof (void *) + s;
206
207 if (size < 1024)
208 /* The temporary array is small, so put it on the stack. */
209 p.t = g_alloca (size);
210 else
211 {
212 /* It's large, so malloc it. */
213 tmp = g_malloc (size);
214 p.t = tmp;
215 }
216
217 p.s = s;
218 p.var = 4;
219 p.cmp = cmp;
220 p.arg = arg;
221
222 if (s > 32)
223 {
224 /* Indirect sorting. */
225 char *ip = (char *) b;
226 void **tp = (void **) (p.t + n * sizeof (void *));
227 void **t = tp;
228 void *tmp_storage = (void *) (tp + n);
229 char *kp;
230 size_t i;
231
232 while ((void *) t < tmp_storage)
233 {
234 *t++ = ip;
235 ip += s;
236 }
237 p.s = sizeof (void *);
238 p.var = 3;
239 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 for (i = 0, ip = (char *) b; i < n; i++, ip += s)
244 if ((kp = tp[i]) != ip)
245 {
246 size_t j = i;
247 char *jp = ip;
248 memcpy (tmp_storage, ip, s);
249
250 do
251 {
252 size_t k = (kp - (char *) b) / s;
253 tp[j] = jp;
254 memcpy (jp, kp, s);
255 j = k;
256 jp = kp;
257 kp = tp[k];
258 }
259 while (kp != ip);
260
261 tp[j] = jp;
262 memcpy (jp, tmp_storage, s);
263 }
264 }
265 else
266 {
267 if ((s & (sizeof (guint32) - 1)) == 0
268 && (gsize) (guintptr) b % G_ALIGNOF(guint32) == 0)
269 {
270 if (s == sizeof (guint32))
271 p.var = 0;
272 else if (s == sizeof (guint64)
273 && (gsize) (guintptr) b % G_ALIGNOF(guint64) == 0)
274 p.var = 1;
275 else if ((s & (sizeof (void *) - 1)) == 0
276 && (gsize) (guintptr) b % G_ALIGNOF(void *) == 0)
277 p.var = 2;
278 }
279 msort_with_tmp (&p, b, n);
280 }
281 g_free (tmp);
282 }
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 g_qsort_with_data (gconstpointer pbase,
299 gint total_elems,
300 gsize size,
301 GCompareDataFunc compare_func,
302 gpointer user_data)
303 {
304 msort_r ((gpointer)pbase, total_elems, size, compare_func, user_data);
305 }