Update.
[glibc.git] / stdlib / msort.c
blobd174edd3b7f7e04c498e96eee485069bfbefa790
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 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)
94 /* The temporary array is small, so put it on the stack. */
95 msort_with_tmp (b, n, s, cmp, __alloca (size));
96 else
98 /* We should avoid allocating too much memory since this might
99 have to be backed up by swap space. */
100 static long int phys_pages;
101 static int pagesize;
103 if (phys_pages == 0)
105 phys_pages = __sysconf (_SC_PHYS_PAGES);
107 if (phys_pages == -1)
108 /* Error while determining the memory size. So let's
109 assume there is enough memory. Otherwise the
110 implementer should provide a complete implementation of
111 the `sysconf' function. */
112 phys_pages = (long int) (~0ul >> 1);
114 /* The following determines that we will never use more than
115 a quarter of the physical memory. */
116 phys_pages /= 4;
118 pagesize = __sysconf (_SC_PAGESIZE);
121 /* Just a comment here. We cannot compute
122 phys_pages * pagesize
123 and compare the needed amount of memory against this value.
124 The problem is that some systems might have more physical
125 memory then can be represented with a `size_t' value (when
126 measured in bytes. */
128 /* If the memory requirements are too high don't allocate memory. */
129 if (size / pagesize > phys_pages)
130 _quicksort (b, n, s, cmp);
131 else
133 /* It's somewhat large, so malloc it. */
134 int save = errno;
135 char *tmp = malloc (size);
136 if (tmp == NULL)
138 /* Couldn't get space, so use the slower algorithm
139 that doesn't need a temporary array. */
140 __set_errno (save);
141 _quicksort (b, n, s, cmp);
143 else
145 __set_errno (save);
146 msort_with_tmp (b, n, s, cmp, tmp);
147 free (tmp);