update from main archive 970214
[kopensolaris-gnu/glibc.git] / stdlib / msort.c
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.
5
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.
10
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.
15
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.  */
20
21 #include <stdlib.h>
22 #include <string.h>
23 #include <memcopy.h>
24 #include <errno.h>
25
26 static void msort_with_tmp __P ((void *b, size_t n, size_t s,
27                                  __compar_fn_t cmp, char *t));
28
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;
36 {
37   char *tmp;
38   char *b1, *b2;
39   size_t n1, n2;
40
41   if (n <= 1)
42     return;
43
44   n1 = n / 2;
45   n2 = n - n1;
46   b1 = b;
47   b2 = (char *) b + (n1 * s);
48
49   msort_with_tmp (b1, n1, s, cmp, t);
50   msort_with_tmp (b2, n2, s, cmp, t);
51
52   tmp = t;
53
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)
57       {
58         if ((*cmp) (b1, b2) <= 0)
59           {
60             --n1;
61             *((op_t *) tmp)++ = *((op_t *) b1)++;
62           }
63         else
64           {
65             --n2;
66             *((op_t *) tmp)++ = *((op_t *) b2)++;
67           }
68       }
69   else
70     while (n1 > 0 && n2 > 0)
71       {
72         if ((*cmp) (b1, b2) <= 0)
73           {
74             memcpy (tmp, b1, s);
75             b1 += s;
76             --n1;
77           }
78         else
79           {
80             memcpy (tmp, b2, s);
81             b2 += s;
82             --n2;
83           }
84         tmp += s;
85       }
86   if (n1 > 0)
87     memcpy (tmp, b1, n1 * s);
88   memcpy (b, t, (n - n2) * s);
89 }
90
91 void
92 qsort (b, n, s, cmp)
93      void *b;
94      size_t n;
95      size_t s;
96      __compar_fn_t cmp;
97 {
98   const size_t size = n * s;
99
100   if (size < 1024)
101     /* The temporary array is small, so put it on the stack.  */
102     msort_with_tmp (b, n, s, cmp, __alloca (size));
103   else
104     {
105       /* It's somewhat large, so malloc it.  */
106       int save = errno;
107       char *tmp = malloc (size);
108       if (tmp == NULL)
109         {
110           /* Couldn't get space, so use the slower algorithm
111              that doesn't need a temporary array.  */
112           extern void _quicksort __P ((void *const __base,
113                                        size_t __nmemb, size_t __size,
114                                        __compar_fn_t __compar));
115           _quicksort (b, n, s, cmp);
116         }
117       else
118         {
119           msort_with_tmp (b, n, s, cmp, tmp);
120           free (tmp);
121         }
122       __set_errno (save);
123     }
124 }