Update.
[glibc.git] / stdlib / msort.c
blob7d5409b30f6932a8071fa367779a960f590122dc
1 /* An alternative to qsort, with an identical interface.
2 This file is part of the GNU C Library.
3 Copyright (C) 1992, 1995-1997, 1999, 2000, 2001 Free Software Foundation, Inc.
4 Written by Mike Haertel, September 1988.
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.
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.
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. */
21 #include <alloca.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <unistd.h>
25 #include <memcopy.h>
26 #include <errno.h>
28 static void msort_with_tmp (void *b, size_t n, size_t s,
29 __compar_fn_t cmp, char *t);
31 static void
32 msort_with_tmp (void *b, size_t n, size_t s, __compar_fn_t cmp,
33 char *t)
35 char *tmp;
36 char *b1, *b2;
37 size_t n1, n2;
39 if (n <= 1)
40 return;
42 n1 = n / 2;
43 n2 = n - n1;
44 b1 = b;
45 b2 = (char *) b + (n1 * s);
47 msort_with_tmp (b1, n1, s, cmp, t);
48 msort_with_tmp (b2, n2, s, cmp, t);
50 tmp = t;
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)
56 if ((*cmp) (b1, b2) <= 0)
58 --n1;
59 *((op_t *) tmp)++ = *((op_t *) b1)++;
61 else
63 --n2;
64 *((op_t *) tmp)++ = *((op_t *) b2)++;
67 else
68 while (n1 > 0 && n2 > 0)
70 if ((*cmp) (b1, b2) <= 0)
72 tmp = (char *) __mempcpy (tmp, b1, s);
73 b1 += s;
74 --n1;
76 else
78 tmp = (char *) __mempcpy (tmp, b2, s);
79 b2 += s;
80 --n2;
83 if (n1 > 0)
84 memcpy (tmp, b1, n1 * s);
85 memcpy (b, t, (n - n2) * s);
88 void
89 qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
91 const size_t size = n * s;
93 if (size < 1024)
95 void *buf = __alloca (size);
97 /* The temporary array is small, so put it on the stack. */
98 msort_with_tmp (b, n, s, cmp, buf);
100 else
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;
107 if (phys_pages == 0)
109 phys_pages = __sysconf (_SC_PHYS_PAGES);
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);
118 /* The following determines that we will never use more than
119 a quarter of the physical memory. */
120 phys_pages /= 4;
122 pagesize = __sysconf (_SC_PAGESIZE);
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. */
132 /* If the memory requirements are too high don't allocate memory. */
133 if (size / pagesize > phys_pages)
134 _quicksort (b, n, s, cmp);
135 else
137 /* It's somewhat large, so malloc it. */
138 int save = errno;
139 char *tmp = malloc (size);
140 if (tmp == NULL)
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);
147 else
149 __set_errno (save);
150 msort_with_tmp (b, n, s, cmp, tmp);
151 free (tmp);