Update.
[glibc.git] / stdlib / msort.c
blob1c36a4cb9ca9979cd67a889674c08a25c45a2c08
1 /* An alternative to qsort, with an identical interface.
2 This file is part of the GNU C Library.
3 Copyright (C) 1992, 1995, 1996, 1997 Free Software Foundation, Inc.
4 Written by Mike Haertel, September 1988.
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Library General Public License as
8 published by the Free Software Foundation; either version 2 of the
9 License, or (at your option) any later version.
11 The GNU C 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 Library General Public License for more details.
16 You should have received a copy of the GNU Library General Public
17 License along with the GNU C Library; see the file COPYING.LIB. If not,
18 write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
21 #include <stdlib.h>
22 #include <string.h>
23 #include <memcopy.h>
24 #include <errno.h>
26 static void msort_with_tmp __P ((void *b, size_t n, size_t s,
27 __compar_fn_t cmp, char *t));
29 static void
30 msort_with_tmp (b, n, s, cmp, t)
31 void *b;
32 size_t n;
33 size_t s;
34 __compar_fn_t cmp;
35 char *t;
37 char *tmp;
38 char *b1, *b2;
39 size_t n1, n2;
41 if (n <= 1)
42 return;
44 n1 = n / 2;
45 n2 = n - n1;
46 b1 = b;
47 b2 = (char *) b + (n1 * s);
49 msort_with_tmp (b1, n1, s, cmp, t);
50 msort_with_tmp (b2, n2, s, cmp, t);
52 tmp = t;
54 if (s == OPSIZ && (b1 - (char *) 0) % OPSIZ == 0)
55 /* We are operating on aligned words. Use direct word stores. */
56 while (n1 > 0 && n2 > 0)
58 if ((*cmp) (b1, b2) <= 0)
60 --n1;
61 *((op_t *) tmp)++ = *((op_t *) b1)++;
63 else
65 --n2;
66 *((op_t *) tmp)++ = *((op_t *) b2)++;
69 else
70 while (n1 > 0 && n2 > 0)
72 if ((*cmp) (b1, b2) <= 0)
74 tmp = (char *) __mempcpy (tmp, b1, s);
75 b1 += s;
76 --n1;
78 else
80 tmp = (char *) __mempcpy (tmp, b2, s);
81 b2 += s;
82 --n2;
85 if (n1 > 0)
86 memcpy (tmp, b1, n1 * s);
87 memcpy (b, t, (n - n2) * s);
90 void
91 qsort (b, n, s, cmp)
92 void *b;
93 size_t n;
94 size_t s;
95 __compar_fn_t cmp;
97 const size_t size = n * s;
99 if (size < 1024)
100 /* The temporary array is small, so put it on the stack. */
101 msort_with_tmp (b, n, s, cmp, __alloca (size));
102 else
104 /* It's somewhat large, so malloc it. */
105 int save = errno;
106 char *tmp = malloc (size);
107 if (tmp == NULL)
109 /* Couldn't get space, so use the slower algorithm
110 that doesn't need a temporary array. */
111 extern void _quicksort __P ((void *const __base,
112 size_t __nmemb, size_t __size,
113 __compar_fn_t __compar));
114 _quicksort (b, n, s, cmp);
116 else
118 msort_with_tmp (b, n, s, cmp, tmp);
119 free (tmp);
121 __set_errno (save);