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