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 |
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, b: b1, n: n1); |
86 | msort_with_tmp (p, b: b2, n: 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 (dest: tmp, src: b1, n: s); |
173 | tmp += s; |
174 | b1 += s; |
175 | --n1; |
176 | } |
177 | else |
178 | { |
179 | memcpy (dest: tmp, src: b2, n: s); |
180 | tmp += s; |
181 | b2 += s; |
182 | --n2; |
183 | } |
184 | } |
185 | break; |
186 | } |
187 | |
188 | if (n1 > 0) |
189 | memcpy (dest: tmp, src: b1, n: n1 * s); |
190 | memcpy (dest: b, src: p->t, n: (n - n2) * s); |
191 | } |
192 | |
193 | |
194 | static void |
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 (n_bytes: 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, b: 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 (dest: tmp_storage, src: ip, n: s); |
247 | |
248 | do |
249 | { |
250 | size_t k = (kp - (char *) b) / s; |
251 | tp[j] = jp; |
252 | memcpy (dest: jp, src: kp, n: s); |
253 | j = k; |
254 | jp = kp; |
255 | kp = tp[k]; |
256 | } |
257 | while (kp != ip); |
258 | |
259 | tp[j] = jp; |
260 | memcpy (dest: jp, src: tmp_storage, n: 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: &p, b, n); |
279 | } |
280 | g_free (mem: 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 |
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 (b: (gpointer)pbase, n: total_elems, s: size, cmp: compare_func, arg: user_data); |
304 | } |
305 | |