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
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 of the License, or (at your option) any later version.
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.
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the
18 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 * Boston, MA 02111-1307, USA.
32 #include "gtestutils.h"
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
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.
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.
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.
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/>. */
67 static void msort_with_tmp (const struct msort_param
*p
, void *b
, size_t n
);
70 msort_with_tmp (const struct msort_param
*p
, void *b
, size_t n
)
75 const size_t s
= p
->s
;
76 GCompareDataFunc cmp
= p
->cmp
;
85 b2
= (char *) b
+ (n1
* p
->s
);
87 msort_with_tmp (p
, b1
, n1
);
88 msort_with_tmp (p
, b2
, n2
);
93 while (n1
> 0 && n2
> 0)
95 if ((*cmp
) (b1
, b2
, arg
) <= 0)
97 *(guint32
*) tmp
= *(guint32
*) b1
;
98 b1
+= sizeof (guint32
);
103 *(guint32
*) tmp
= *(guint32
*) b2
;
104 b2
+= sizeof (guint32
);
107 tmp
+= sizeof (guint32
);
111 while (n1
> 0 && n2
> 0)
113 if ((*cmp
) (b1
, b2
, arg
) <= 0)
115 *(guint64
*) tmp
= *(guint64
*) b1
;
116 b1
+= sizeof (guint64
);
121 *(guint64
*) tmp
= *(guint64
*) b2
;
122 b2
+= sizeof (guint64
);
125 tmp
+= sizeof (guint64
);
129 while (n1
> 0 && n2
> 0)
131 unsigned long *tmpl
= (unsigned long *) tmp
;
135 if ((*cmp
) (b1
, b2
, arg
) <= 0)
137 bl
= (unsigned long *) b1
;
143 bl
= (unsigned long *) b2
;
147 while (tmpl
< (unsigned long *) tmp
)
152 while (n1
> 0 && n2
> 0)
154 if ((*cmp
) (*(const void **) b1
, *(const void **) b2
, arg
) <= 0)
156 *(void **) tmp
= *(void **) b1
;
157 b1
+= sizeof (void *);
162 *(void **) tmp
= *(void **) b2
;
163 b2
+= sizeof (void *);
166 tmp
+= sizeof (void *);
170 while (n1
> 0 && n2
> 0)
172 if ((*cmp
) (b1
, b2
, arg
) <= 0)
191 memcpy (tmp
, b1
, n1
* s
);
192 memcpy (b
, p
->t
, (n
- n2
) * s
);
197 msort_r (void *b
, size_t n
, size_t s
, GCompareDataFunc cmp
, void *arg
)
201 struct msort_param p
;
203 /* For large object sizes use indirect sorting. */
205 size
= 2 * n
* sizeof (void *) + s
;
208 /* The temporary array is small, so put it on the stack. */
209 p
.t
= g_alloca (size
);
212 /* It's large, so malloc it. */
213 tmp
= g_malloc (size
);
224 /* Indirect sorting. */
225 char *ip
= (char *) b
;
226 void **tp
= (void **) (p
.t
+ n
* sizeof (void *));
228 void *tmp_storage
= (void *) (tp
+ n
);
232 while ((void *) t
< tmp_storage
)
237 p
.s
= sizeof (void *);
239 msort_with_tmp (&p
, p
.t
+ n
* sizeof (void *), n
);
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
)
248 memcpy (tmp_storage
, ip
, s
);
252 size_t k
= (kp
- (char *) b
) / s
;
262 memcpy (jp
, tmp_storage
, s
);
267 if ((s
& (sizeof (guint32
) - 1)) == 0
268 && ((char *) b
- (char *) 0) % ALIGNOF_GUINT32
== 0)
270 if (s
== sizeof (guint32
))
272 else if (s
== sizeof (guint64
)
273 && ((char *) b
- (char *) 0) % ALIGNOF_GUINT64
== 0)
275 else if ((s
& (sizeof (unsigned long) - 1)) == 0
276 && ((char *) b
- (char *) 0)
277 % ALIGNOF_UNSIGNED_LONG
== 0)
280 msort_with_tmp (&p
, b
, n
);
287 * @pbase: start of array to sort
288 * @total_elems: elements in the array
289 * @size: size of each element
290 * @compare_func: function to compare elements
291 * @user_data: data to pass to @compare_func
293 * This is just like the standard C qsort() function, but
294 * the comparison routine accepts a user data argument.
296 * This is guaranteed to be a stable sort since version 2.32.
299 g_qsort_with_data (gconstpointer pbase
,
302 GCompareDataFunc compare_func
,
305 msort_r ((gpointer
)pbase
, total_elems
, size
, compare_func
, user_data
);