Formerly stdlib/stdlib.h.~12~
[kopensolaris-gnu/glibc.git] / stdlib / msort.c
1 /* msort -- an alternative to qsort, with an identical interface.
2    Copyright (C) 1992 Free Software Foundation, Inc.
3    Written by Mike Haertel, September 1988.
4
5 This file is part of the GNU C Library.
6
7 The GNU C Library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Library General Public License as
9 published by the Free Software Foundation; either version 2 of the
10 License, or (at your option) any later version.
11
12 The GNU C Library is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15 Library General Public License for more details.
16
17 You should have received a copy of the GNU Library General Public
18 License along with the GNU C Library; see the file COPYING.LIB.  If
19 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
20 Cambridge, MA 02139, USA.  */
21
22 #include <ansidecl.h>
23 #include <stdlib.h>
24 #include <string.h>
25
26 #define MEMCPY(dst, src, s)                     \
27   ((s) == sizeof (int)                          \
28    ? (*(int *) (dst) = *(int *) (src), (dst))   \
29    : memcpy (dst, src, s))
30
31 static void
32 DEFUN(msort_with_tmp, (b, n, s, cmp, t),
33       PTR b AND size_t n AND size_t s AND __compar_fn_t cmp AND char *t)
34 {
35   char *tmp;
36   char *b1, *b2;
37   size_t n1, n2;
38
39   if (n <= 1)
40     return;
41
42   n1 = n / 2;
43   n2 = n - n1;
44   b1 = b;
45   b2 = (char *) b + (n1 * s);
46
47   msort_with_tmp (b1, n1, s, cmp, t);
48   msort_with_tmp (b2, n2, s, cmp, t);
49
50   tmp = t;
51
52   while (n1 > 0 && n2 > 0)
53     {
54       if ((*cmp) (b1, b2) <= 0)
55         {
56           MEMCPY (tmp, b1, s);
57           b1 += s;
58           --n1;
59         }
60       else
61         {
62           MEMCPY (tmp, b2, s);
63           b2 += s;
64           --n2;
65         }
66       tmp += s;
67     }
68   if (n1 > 0)
69     memcpy (tmp, b1, n1 * s);
70   memcpy (b, t, (n - n2) * s);
71 }
72
73 void
74 DEFUN(qsort, (b, n, s, cmp),
75       PTR b AND size_t n AND size_t s AND __compar_fn_t cmp)
76 {
77   CONST size_t size = n * s;
78
79   if (size < 1024)
80     /* The temporary array is small, so put it on the stack.  */
81     msort_with_tmp (b, n, s, cmp, __alloca (size));
82   else
83     {
84       /* It's somewhat large, so malloc it.  */
85       int save = errno;
86       char *tmp = malloc (size);
87       if (tmp == NULL)
88         {
89           /* Couldn't get space, so use the slower algorithm
90              that doesn't need a temporary array.  */
91           extern void EXFUN(_quicksort, (PTR __base,
92                                          size_t __nmemb, size_t __size,
93                                          __compar_fn_t __compar));
94           _quicksort (b, n, s, cmp);
95         }
96       else
97         {
98           msort_with_tmp (b, n, s, cmp, tmp);
99           free (tmp);
100         }
101       errno = save;
102     }
103 }