Include errno.h.
[kopensolaris-gnu/glibc.git] / stdlib / msort.c
1 /* msort -- an alternative to qsort, with an identical interface.
2    Copyright (C) 1992, 1995 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 #include <memcopy.h>
26 #include <errno.h>
27
28 static void
29 DEFUN(msort_with_tmp, (b, n, s, cmp, t),
30       PTR b AND size_t n AND size_t s AND __compar_fn_t cmp AND char *t)
31 {
32   char *tmp;
33   char *b1, *b2;
34   size_t n1, n2;
35
36   if (n <= 1)
37     return;
38
39   n1 = n / 2;
40   n2 = n - n1;
41   b1 = b;
42   b2 = (char *) b + (n1 * s);
43
44   msort_with_tmp (b1, n1, s, cmp, t);
45   msort_with_tmp (b2, n2, s, cmp, t);
46
47   tmp = t;
48
49   if (s == OPSIZ && (b1 - (char *) 0) % OPSIZ == 0)
50     /* We are operating on aligned words.  Use direct word stores.  */
51     while (n1 > 0 && n2 > 0)
52       {
53         if ((*cmp) (b1, b2) <= 0)
54           {
55             --n1;
56             *((op_t *) tmp)++ = *((op_t *) b1)++;
57           }
58         else
59           {
60             --n2;
61             *((op_t *) tmp)++ = *((op_t *) b2)++;
62           }
63       }
64   else
65     while (n1 > 0 && n2 > 0)
66       {
67         if ((*cmp) (b1, b2) <= 0)
68           {
69             memcpy (tmp, b1, s);
70             b1 += s;
71             --n1;
72           }
73         else
74           {
75             memcpy (tmp, b2, s);
76             b2 += s;
77             --n2;
78           }
79         tmp += s;
80       }
81   if (n1 > 0)
82     memcpy (tmp, b1, n1 * s);
83   memcpy (b, t, (n - n2) * s);
84 }
85
86 void
87 DEFUN(qsort, (b, n, s, cmp),
88       PTR b AND size_t n AND size_t s AND __compar_fn_t cmp)
89 {
90   CONST size_t size = n * s;
91
92   if (size < 1024)
93     /* The temporary array is small, so put it on the stack.  */
94     msort_with_tmp (b, n, s, cmp, __alloca (size));
95   else
96     {
97       /* It's somewhat large, so malloc it.  */
98       int save = errno;
99       char *tmp = malloc (size);
100       if (tmp == NULL)
101         {
102           /* Couldn't get space, so use the slower algorithm
103              that doesn't need a temporary array.  */
104           extern void EXFUN(_quicksort, (PTR __base,
105                                          size_t __nmemb, size_t __size,
106                                          __compar_fn_t __compar));
107           _quicksort (b, n, s, cmp);
108         }
109       else
110         {
111           msort_with_tmp (b, n, s, cmp, tmp);
112           free (tmp);
113         }
114       errno = save;
115     }
116 }