Use test-skeleton.c.
[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,95-97,99,2000,01,02 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 Lesser General Public
8    License as published by the Free Software Foundation; either
9    version 2.1 of the 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    Lesser General Public License for more details.
15
16    You should have received a copy of the GNU Lesser General Public
17    License along with the GNU C Library; if not, write to the Free
18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19    02111-1307 USA.  */
20
21 #include <alloca.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <unistd.h>
25 #include <memcopy.h>
26 #include <errno.h>
27
28 static void msort_with_tmp (void *b, size_t n, size_t s,
29                             __compar_fn_t cmp, char *t);
30
31 static void
32 msort_with_tmp (void *b, size_t n, size_t s, __compar_fn_t cmp,
33                 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   if (s == OPSIZ && (b1 - (char *) 0) % OPSIZ == 0)
53     /* We are operating on aligned words.  Use direct word stores.  */
54     while (n1 > 0 && n2 > 0)
55       {
56         if ((*cmp) (b1, b2) <= 0)
57           {
58             --n1;
59             *((op_t *) tmp)++ = *((op_t *) b1)++;
60           }
61         else
62           {
63             --n2;
64             *((op_t *) tmp)++ = *((op_t *) b2)++;
65           }
66       }
67   else
68     while (n1 > 0 && n2 > 0)
69       {
70         if ((*cmp) (b1, b2) <= 0)
71           {
72             tmp = (char *) __mempcpy (tmp, b1, s);
73             b1 += s;
74             --n1;
75           }
76         else
77           {
78             tmp = (char *) __mempcpy (tmp, b2, s);
79             b2 += s;
80             --n2;
81           }
82       }
83   if (n1 > 0)
84     memcpy (tmp, b1, n1 * s);
85   memcpy (b, t, (n - n2) * s);
86 }
87
88 void
89 qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
90 {
91   const size_t size = n * s;
92
93   if (size < 1024)
94     {
95       void *buf = __alloca (size);
96
97       /* The temporary array is small, so put it on the stack.  */
98       msort_with_tmp (b, n, s, cmp, buf);
99     }
100   else
101     {
102       /* We should avoid allocating too much memory since this might
103          have to be backed up by swap space.  */
104       static long int phys_pages;
105       static int pagesize;
106
107       if (phys_pages == 0)
108         {
109           phys_pages = __sysconf (_SC_PHYS_PAGES);
110
111           if (phys_pages == -1)
112             /* Error while determining the memory size.  So let's
113                assume there is enough memory.  Otherwise the
114                implementer should provide a complete implementation of
115                the `sysconf' function.  */
116             phys_pages = (long int) (~0ul >> 1);
117
118           /* The following determines that we will never use more than
119              a quarter of the physical memory.  */
120           phys_pages /= 4;
121
122           pagesize = __sysconf (_SC_PAGESIZE);
123         }
124
125       /* Just a comment here.  We cannot compute
126            phys_pages * pagesize
127            and compare the needed amount of memory against this value.
128            The problem is that some systems might have more physical
129            memory then can be represented with a `size_t' value (when
130            measured in bytes.  */
131
132       /* If the memory requirements are too high don't allocate memory.  */
133       if (size / pagesize > (size_t) phys_pages)
134         _quicksort (b, n, s, cmp);
135       else
136         {
137           /* It's somewhat large, so malloc it.  */
138           int save = errno;
139           char *tmp = malloc (size);
140           if (tmp == NULL)
141             {
142               /* Couldn't get space, so use the slower algorithm
143                  that doesn't need a temporary array.  */
144               __set_errno (save);
145               _quicksort (b, n, s, cmp);
146             }
147           else
148             {
149               __set_errno (save);
150               msort_with_tmp (b, n, s, cmp, tmp);
151               free (tmp);
152             }
153         }
154     }
155 }
156 libc_hidden_def (qsort)