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